Comment by dxbydt | Hacker News Reader

Comment by dxbydt | Hacker News Reader

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 instead focus on dubious speed metrics (dubious in the sense these metrics change with the chip/cache/RAM/compiler/lang/coding-style & aren't that relevant anyways, compared to the underlying problem)

Lemme rephrase this rather interesting problem: There are 2055 startups, 2006 bigcorps & 2017 zombies. If the startup gets bought out by the bigcorp, the bigcorp has wasted its well earned money and soon becomes a zombie. If the zombie folks instead join hands with the startup, they suddenly make pots of money & the startup become a bigcorp. Finally, if the bigcorp uses its cash prudently and buys the zombie, it starts innovating & becomes a startup.

So the claim is that if you let this economy play out in all its glory, there will be 1.448 billion buyouts. To arrive at this giant figure of 1,448,575,636 takes anywhere between 335 seconds for the C++ hacker to 7000 seconds for the JS guys.

Now give it your best shot!

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.

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

Your code contains a bug in the function getForestKey. See gist.

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

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)

Reply on news.ycombinator.com