News for hackers. Stuff that matters.
Re:programming challenge by Swizec on Sunday October 17, 2010 @02:47AM (#1799826)
This 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.

Re:programming challenge by uncompetence on Sunday October 17, 2010 @03:49AM (#1799885)
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 should probably be solved another way

Re:programming challenge by jules on Sunday October 17, 2010 @06:32AM (#1800057)
Integer linear programming!
Re:programming challenge by Someone on Sunday October 17, 2010 @07:21AM (#1800112)
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 by jaekwon on Sunday October 17, 2010 @11:57AM (#1800613)
The question is, why on earth would anybody come up with such a confounding puzzle? Jars and balls??