Already a lot of people have worked on improving their score for this game. I wanted to either beat the best known score (132 commands) or prove it to be minimal by trying every possible solution for every level and seeing if it completes the level.
To cut a long story short, the solver managed to beat the best known solution for level 8, reducing it from 10 commands to 9 commands. The solution is complex and I find it difficult to imagine how a human could discover this solution without assistance from a computer.
Here are the solutions that the brute forcer found.
In particular the crazy solution to level 8 starts here.
The rest of the post describes how I approached the problem and optimized the solver so that it could run fast enough to solve the harder levels at the end of the game.
I named the commands by single character abbreviations: F, R, L, J, X, 1, 2, in the same order that the icons appear in the game. To prove that the length 17 solutions to the hardest levels are optimal I will need to check all possibilities up to length 16 and show that they do not work. A quick calculation shows that there are 33,232,930,569,601 different unique 16 letter string containing only these 7 characters. This is further complicated because they can be put into the three functions in many different ways, for example 5 symbols in main, 7 in F1 and and the remaining 4 in F2. For any given 16 character string there are 71 ways to separate the parts into the three functions. This gives a total of 2,359,538,070,441,671 possible programs to test. This is far more than can reasonably be brute forced. So what can we do?
An important observation is that if a sequence is a valid solution, then by removing all occurrences of the 'light' command (which I call X) I get a shorter sequence that doesn't light any lights, but still must walk onto them. I can therefore first test all solutions without any X commands to see whether or not all lights are reached. If I find a program that walks onto all the lights, I can then retest it by adding the Xs in all the possible positions. The effect of this is that now there are only 6 possible commands in the majority of the sequences I test instead of 7. I can also search to one search depth fewer, because if I find a solution of length 15 without any Xs, then this will grow to at least 16 when I start adding Xs.
6 ** 15 multiplied by the 74 different ways of splitting each is sequence into three functions is now "only" 34,793,688,858,624. A factor 100 improvement! But it's still not enough...
At this point I decided I will consider programs containing a loop, and programs not containing a loop separately. It seems that in most cases a solution containing a loop will be the best solution to a level. For looping solutions there are a few more tricks I can use.
A looping solution contains a function which calls itself. I can define that this function will be F1. I then know that the last command in main, and the last command in F1 will both be '1' and 1 cannot occur anywhere else in the program. This reduces the search depth by a further two levels, and removes one more command from the list of possible commands.
5 ** 13 * 74 = 451,660,156,250.
OK, so if we forget non-looping solutions for the moment, and consider only looping it's almost managable now... but it's still about a factor 100 more than I'd like. What more can we do?
I noticed that any functions containing the sequences LR or RL are obviously not optimal, because these two commands together result in no effect. So these possibilities can be discarded. Similarly, there is no point checking both LL and RR, since they do the same thing - so I discard all potential solutions containing LL. RRR is identical to L, so sequences containing RRR are also discarded.
This is the code that generates the functions:
def functions(prefix, n, choice):
if n == 0:
yield prefix
else:
last = prefix and prefix[-1]
for c in choice:
if c == 'L' and (last == 'L' or last == 'R'): continue
elif c == 'R' and (last == 'L' or prefix[-2:] == 'RR'): continue
for p in functions(prefix + c, n - 1, choice):
yield p
For example, this call generates the 18980 possible functions of length 8 containing the commands 'FLRJ'.
functions('', 8, 'FLRJ')
This is a lot less than the naïve 4**8 = 65536 possibilities. Similarly, the main function and function 1 provide similar savings, giving another order of magnitude optimization.
Several other smaller optimizations are possible.
For example, if there is a solution where F2 contains zero commands, there is also another solution where F2 contains 1 command and F1 contains one fewer command, so we don't need to check both these possibilities.
Another example is that the first command in main will only be called once, so if it has no effect then it might as well not be there. On any map, only one of the commands F or J can have an effect, never both, so for example we can always immediately discard any solutions where main starts with J if the ground in front of the starting position is flat. This gives 20% fewer solutions to check. Not much, but it's simple to implement and will save a few hours computation, so I'll take it.
The end result of all this is that I can check all looping solutions with up to 16 commands in just a couple days on a single computer. And the levels with a solution length of 10 or less take just a few seconds to brute force.
The search is much slower for the non-looping solutions because there are fewer constraints on the positions of the commands. Because of this, for the later levels I have only been able to check the solutions containing loops, and have not tested the non-looping solutions. It could be that there is an even shorter solution for level 10, 11 or 12 with a non-looping program (although I doubt it for level 11). To find such a solution or prove that one does not exist is left as an exercise for the reader as now my holiday has come to an end.
*Update: Before I wrote that there was no looping solution of length 16 for level 12, but I just ran the program again to double-check that and it turns out that there are in fact many such solutions, for example "Main = FJ1, f1 = X2XR22R1, f2= JXJXJ".
