PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This problem had the lowest number of successful submissions ever for a challenge problem, which I found quite surprising. I did not mean for the problem to be so difficult.
The author’s solution works as follows:
The main solver function takes 2 parameters. The first parameter is the number of moves to look ahead, and the second parameter is a value that will change how the heuristic is calculated. From any state, consider all possible sequences of moves of length equal to the “look ahead” parameter. Rank these sequences based on the change in score, the heuristic, and whether any balls fell into holes. Execute the first move of the best sequence (or if there’s a tie, choose randomly).
The heuristic is calculated as follows:
If there are no inverter balls left, add m for every remaining positive ball, and subtract m for every negative ball, where m is a parameter that varies from run to run. Otherwise, add m for every remaining positive ball and negative ball. Then, subtract cieling((remaining balls)/holes).
Since the algorithm may not always yield a solution, it is executed repeatedly with different parameters and random number seeds until a solution is found.
A better solution is to use a Beam Search. See ACRush’s winning solution for an implementation.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Will be updated soon.