3 ms·

It is rather sad that none of the 49 comments (at this time of posting) have made a mention of the underlying math problem, which is super interesting, and inst

• HardyLeung 12y ago
  This is indeed an interesting problem. I don't know what the runtime breakdown is, most likely in the sorting routine, but if that's the case the problem can be solved much faster but not resorting to generic stable_sort(). I summarize the author's algorithm as follows: take an array of R^3 vectors, and for each element in the vector, perform the [+,-,-], [-,+,-], and [-,-,+] transform. So N numbers become 3N numbers, which is followed by a duplicate removal process faciliated by the sorting. The improvement is that the duplicate removal can be accomplished without sorting. Let's say you have an array of R^3 already sorted. Then say you create 3 arrays each of which is created by "shifting" the array in each of the 3 directions. Call the original A, and the derived B0, B1, B2. Note that B0, B1, and B2 are each sorted since element within each array is adjusted in the same direction. Then all you need to do is to do a 3-way merge, which takes linear time. I bet by doing this, the runtime could be significantly reduced. My guess is that it runs in the range of 10-30 seconds (instead of 335 seconds).
• aromogato 12y ago
  It is a really cool math problem, and we should be using math to solve it! This problem took me 30 minutes to solve without programming and so I'm only a few minutes off Fortran. (I scale well too since I can now do it in constant time - fine log time if we count reading the input.) A minor nit to pick: the 1,448,575,636 number is not the number of buyouts. (It looks like the number of nodes in the evaluation graph.) Spoiler: the answer is 111110110111_2. (edit: had the wrong answer)
• curveship 12y ago
  Let s = startups, b = bigcorps, z = zombies 1) In any of the transformations [(-,-,+),(-,+,-),(+,-,-)], the delta b/w numbers (s-b, s-z, b-z) changes by 0 or 2. What this tells us is that if the delta is odd to start, it will always be odd, if even always even. 2) Since the final state will involve only one type left standing (or else the stronger could eat the weaker), we know that the final counts will be two at 0, one at something >0. Since our losers end with an even delta (0), they must always have had an even delta. In the scenario you proposed, that's s and z (2055 - 2017 = 38). So b, bigcorps, is going to be our winner. 3) Now that we know who will win, we need to find the maximum possible number of bs remaining. Since each move reduces the total population by one, the maximum bs will be produced by the shortest sequence of moves that gets rid of all zs and ss. 4) As long as z>0 and s>0, our best move is to have z eat s, as it drops the population of z and s by 2. So our first sequence is to have all zs eat ss, leaving us with s = 38, b = 4023, z = 0. 5) When z = 0, our only possible move is b eats s, creating a z, which can then be eaten by an s to produce a b, thereby restoring b to its original count and lowering s by 2. After repeating this sequence 19 times to get rid of the 38 ss, we'll have s = 0, b = 4023, z = 0. Ergo, maximal final state is 4023 bigcorps.
• chapel 12y ago
  The code is very inefficient to say the least. I made some modifications (diverging further from the "functional" nature, if you could call it that) and as you can see it is much faster[0]. Output: $ node new-magicForest.js 2017 2055 2006 total forests: 6128 { goats: 0, wolves: 0, lions: 4023 } total time: 20ms [0] https://gist.github.com/chapel/1c038b2bf64b3037aaea https://gist.github.com/chapel/1c038b2bf64b3037aaea
  • skratky 12y ago
    Your code contains a bug in the function getForestKey. See gist.