4 ms·
This looks like a really cool challenge. Reminds me a bit of the knapsack problem (http://en.wikipedia.org/wiki/Backpack_problem http://en.wikipedia.org/wiki/Ba
by Swizec 16y ago
This looks like a really cool challenge. Reminds me a bit of the knapsack problem (http://en.wikipedia.org/wiki/Backpack_problem http://en.wikipedia.org/wiki/Backpack_problem)
But something tells me the solution is going to be a lot less simple though.
- uncompetence 16y agoIf 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
- jules 16y agoInteger linear programming!
- Someone 16y agoHm, 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.
- jaekwon 16y agoThe question is, why on earth would anybody come up with such a confounding puzzle? Jars and balls??