Overall Editorial by TheEpicCowOfLife
36th place solutionThe sortedBubble() routine
There is a very well performing greedy solution, that caused a 50-way tie an hour into the contest
Go through the balls in order from smallest to highest. For each ball, keep swapping it with the larger parent until the ball is larger than both parents, “bubbling” it up to the top of the heap. This is guaranteed to produce a pyramid that globally satisfies the heap condition.
It is quite difficult to improve this routine, many ideas/changes that introduce randomness do not yield any results.
Initial random moves.
The first solution I found that improved the sortedBubble() routine, was making a few random moves at the start (I tried 1-20), then running it. Then you can use the whole 2 seconds to try a couple thousand initial random moves.
Trying to specify what kinds of random moves did not yield much better results
Beam search
Rather than relying on completely random initial moves before running sortedBubble(), one can run beam search on the prefix of moves with the cost to optimise being the total number of moves to sort the pyramid after running the sortedBubble.
After some experimentation, a beam width of 5, number of adjacent states generated = 50, it could run about 50 iterations. I did not have time to optimise the implementation, and this was my best scoring submission.
posted:
last update: