Eating Lions, Wolves, and Goats Faster(strilanc.com)
strilanc.com
Eating Lions, Wolves, and Goats Faster
http://strilanc.com/algorithm/2014/06/07/Eating-Lions-Wolves-and-Goats-Faster.html
5 comments
I believe finding the single optimal solution wasn't the point - as others have pointed out ( for a very good solution, see: https://news.ycombinator.com/item?id=7856275 ), one can find that by hand - you don't need to write any code for that.
The OP tried to exhaustively enumerate all possible unique forests (he considered a forest unique if the (lion,wolf,goat) triple was unique ). That obviously means some data structure has to track all these unique forests - store them, ensure uniqueness etc. Usually this is some implementation of a set. In Scala for example, a HashSet[(Int,Int,Int)] would be the obvious choice. Unfortunately, finding all these forests & adding them to the set to ensure uniqueness will also ensure your code buckles down to its knees. That's why with a triple of (2055,2006,2017), you get 1,448,575,636 unique triples - finding 1.4 billion unique triples will surely slow you down.
Even if that's the problem they intended to solve, they're using an inefficient solution. (Could you point to where they say they intend to count the unique reachable forests? Their javascript code [1] does enumerate stable forests.)
If you want to enumerate stable forests, you only need to know the largest pure lion/goat/wolf forests. You get all the other stables one by repeatedly subtracting 2 from those. Takes linear time to yield everything, and constant space.
If you want to enumerate all reachable forests, stable or not, you just do a triple loop over how many times to apply each operation and yield the results. The results you get won't overlap because the operations are linearly independent. Takes cubic time to yield everything, but only constant space.
1: http://www.unisoftwareplus.com/download/blog/2014-06/magicFo...
If you want to enumerate stable forests, you only need to know the largest pure lion/goat/wolf forests. You get all the other stables one by repeatedly subtracting 2 from those. Takes linear time to yield everything, and constant space.
If you want to enumerate all reachable forests, stable or not, you just do a triple loop over how many times to apply each operation and yield the results. The results you get won't overlap because the operations are linearly independent. Takes cubic time to yield everything, but only constant space.
1: http://www.unisoftwareplus.com/download/blog/2014-06/magicFo...
If you do that your best bet is using a simple long[] (or a direct LongBuffer) and each forest is represent by just a long. Not a stock HashSet(...). Even then the simplest optimization is not adding when the total forest population is inferior to the current best solution.
Rewriting the solution to use a single long smashes the C++ too but yet again, it feels horrid when the real solution is O(1)...
Rewriting the solution to use a single long smashes the C++ too but yet again, it feels horrid when the real solution is O(1)...
Or you could do it even faster by solving it directly. First note that all the parities change together, so pick the two smallest groups with the same parity, say wolves and goats. These will be the species to try to eliminate.
Then have all the wolves eat goats until only one of the species is left, say 2k wolves. Then do k iterations of lion eat wolf and wolf eat goat.
Then have all the wolves eat goats until only one of the species is left, say 2k wolves. Then do k iterations of lion eat wolf and wolf eat goat.
This reminds me of those counting problems in college. First you get an answer by trying examples, writing programs, OEIS, etc. and then you come up with an almost trivial counting proof completely unrelated to how the problem was actually solved.
This was surprising to see here. unRisk is a hugely technical company, doing quant finance with Mathematica. Not the type of thing you normally find here.
As to the problem, the second I started reading I knew it would be an operations research problem. Though, to be honest I thought there would be a closed form solution
As to the problem, the second I started reading I knew it would be an operations research problem. Though, to be honest I thought there would be a closed form solution
This article is not the blog post you described, but someone else's blog providing the closed solution.
Nice! I managed to get a javascript solution down to 0.388s (https://gist.github.com/curveship/f1f7155ef5243af18bc2), but this is considerably faster.