5 ms·

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?i

by dxbydt 12y ago

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 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.

xxs 12y ago
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)...
Strilanc 12y ago
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/magicForest.js http://www.unisoftwareplus.com/download/blog/2014-06/magicFo...

by dxbydt 12y ago

xxs 12y ago

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)...

Strilanc 12y ago

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/magicForest.js http://www.unisoftwareplus.com/download/blog/2014-06/magicFo...