There was a 24 hours competition this weekend on codingame.com. The problem was simple: Bilbo is in a forest in Middle-Earth, and needs to spell out a sequence of words. He did this using the rune stones found in the forest. They required Bilbo to walk over them and change the letters on them to the desired one, then activate them in order to register the letter.
You could give orders to Bilbo using dedicated characters (<>+-.[]). The goal was to minimize the output produced by the program. Whoever gets the less characters in the end, wins.
I’ve started out with a simple solution, looking only for the most efficient move for each letter, considering moving the nearest rune having the letter currently active, moving to the nearest rune which can be swapped to the desired letter, and checking/changing the rune Bilbo is currently standing on. I was able to get down to 6003 instructions using this approach, which provided a good position when I first submitted my code.
I haven’t allocated a lot of time to this contest over the weekend, because I thought it would also be a 3-4 hours one. I have only returned on Sunday morning for a couple of hours to improve my solution. I’ve introduced a basic recursion to my code, enabling Bilbo to look a bit forward and examine the possibilities to the next few letters as well. This way he was able to consider if it is a good idea to change the rune he was about to change, or to leave it for the next letters. I didn’t go very deep, only checking the next 5 letters, and comparing the 5 best solutions for each. After a bit of experimentation it turned out, that Bilbo would produce the best results when only examines 3 possible moves, and looks only 1 letter further. Expanding the search space produced less effective outcomes.
The [] chars were used to create simple loops inside the instructions we give to Bilbo, but I didn’t look at how to use them this time.
The overall outcome was as expected. I usually try to be in the first 1/3 of all participants. This time I made it into the best 25% with a position of 523/2618 with 5922 instructions.