So how is this "challenge" more interesting than thousands of problems on SPOJ, UVA, topcoder or project Euler?
programming challenge
11–20 of 43 posts
Re: programming challenge
#12The solution given is incorrect. It yields 29 white balls, while the following yields 35. 1 jar1:2 2 3 jar2:3 4 5 6 jar1:2 jar2:4 7 8 9 jar2:6 10 11 12 jar1:11 jar2:3 13 14 15
Honestly, I wish I were on the other end of this. I wonder how many solutions I could find test cases to break even assuming I play nice and allow only positive integers?
Yes, I really did imagine all kinds of cases involving zero time and negative time rules (or having zero time to produce anything) and tried to conform them to the spec, but most of them conflict with the output requirements. Not all, though...
Re: programming challenge
#13The solution given is incorrect. It yields 29 white balls, while the following yields 35. 1 jar1:2 2 3 jar2:3 4 5 6 jar1:2 jar2:4 7 8 9 jar2:6 10 11 12 jar1:11 jar2:3 13 14 15
is there a need for jar2:3 at line 12 ?
Doesn't seem like there is. Also, is my count wrong, or does that only produce 31 white balls? It's still more than the 29, though.
Re: programming challenge
#14The section under "Submission Directions" is exactly the same as the directions here: http://www.facebook.com/careers/puzzles.php verbatim even down to the exact version numbers.
Is there some standard testing package that these are both using? Otherwise it seems fishy.
Re: programming challenge
#15This looks like a really cool challenge. Reminds me a bit of the knapsack problem ( http://en.wikipedia.org/wiki/Backpack_problem ) But something tells me the solution is going to be a lot less simple though.
If you treated this as a variant on the backpack problem, you run into trouble as you can't properly memoize or use dynamic programming. You use 'timesteps' as the size of the 'knapsack' since the number of balls is unbounded. At each timestep, you cannot determine the the optimal solution to the subproblem and you'd have to save every possible ball combination. TL;DR - It gets to be a pretty messy/bad backpack and s…
Integer linear programming!
Re: programming challenge
#16Earlier quoted context omitted.
is there a need for jar2:3 at line 12 ?
Doesn't seem like there is. Also, is my count wrong, or does that only produce 31 white balls? It's still more than the 29, though.
We have 5 from the start.
Start producing 4 more (2 jars) at timestep 1.
Start producing 4 more at timestep 6.
Start producing 22 more at timestep 12.
22 + 4 + 4 + 5 = 35
Re: programming challenge
#17The section under "Submission Directions" is exactly the same as the directions here: http://www.facebook.com/careers/puzzles.php verbatim even down to the exact version numbers. Is there some standard testing package that these are both using? Otherwise it seems fishy.
I noticed that too. Googling the text yields quite a few matches; my guess is either they think "Facebook does it, so we should do it like that too", or it's a standard testing package or something.
http://www.google.com/search?q=%22All+submissions+must+execu...
Re: programming challenge
#18This looks like a really cool challenge. Reminds me a bit of the knapsack problem ( http://en.wikipedia.org/wiki/Backpack_problem ) But something tells me the solution is going to be a lot less simple though.
Hm, let's see. 15 moves, an average branching factor of say 5, 5^15 ~ 3E10. Bookkeeping will be a bit of work, so let's give that 1E4 instructions per step gives us 3E14 steps or 1E5 seconds at 3GHz, single-core.
So, brute-forcing this looks doable in a day, probably a lot less, as I took a high estimate for the branching factor. One instruction/cycle probably is on the high side, but that can be compensated for by using multiple cores.
Re: programming challenge
#19The section under "Submission Directions" is exactly the same as the directions here: http://www.facebook.com/careers/puzzles.php verbatim even down to the exact version numbers. Is there some standard testing package that these are both using? Otherwise it seems fishy.
No, Facebook's directions were good so I copied them a bit. I expected people to notice.
Re: programming challenge
#20The solution given is incorrect. It yields 29 white balls, while the following yields 35. 1 jar1:2 2 3 jar2:3 4 5 6 jar1:2 jar2:4 7 8 9 jar2:6 10 11 12 jar1:11 jar2:3 13 14 15
:) you are correct.