Fox was 1 of 3 to get the best score in part 1.

Or in slow motion:

I’m sure this program was generated, it has 367 lines. It has a lot of lines like this:

S_AB B*****B*** S_ABBB _PP_**____ RUDLUDLUDR

2 heads begin at the ends and work their way in. The states keep track of what was just seen and what is here now. Also there are 10 heads in all, so there’s a lot of places to write the P’s. In the example above, there’s actually some backtracking. In the final step, 1 P is deleted. Let me just find which rules were actually used in this example (I added a little formatting):

START    A*****C*** S_AC     P*****P*** RUDLLLLUDR
S_AC     B*****A*** S_ACBA   _PP_**____ RUDLUDLUDR
S_ACBA   B*****B*** S_ACBABB _PP***_*** RUDLRRLUDR
S_ACBABB _*****_*** STOP     ****_***** RUDLSSLUDR

For the 2 reading heads, ABBAC is seen as AC-BA-BB. (ABCDE would be seen as AE-BD-CC.) The 1st rule writes 2 P’s — that’s all it can do, as the heads haven’t spread out yet. So remember, we need to write 1 more P at some point. The 2nd rule writes 2 P’s, and we’re square. The 3rd rule writes 2 P’s, because it’s seeing 2 B’s. But then the final rule sees, that it was only 1 B seen by 2 heads and deletes a P. And done!

Let’s look at case 2.

And the corresponding program.

START        C*****C*** S_CC         P*****P*** RUDLLLLUDR
S_CC         A*****A*** REMAIN_1_ODD _PPP**_P__ RUDLUDLUDR
REMAIN_1_ODD B*****B*** STOP         _P****_*** RUDLSSLUDR

I’m actually not quite sure how this program detects, that BB is 1 B seen by 2 heads and therefore a stopping condition… Or how it detects, that there’s only 1 character left? Maybe this whole program is very specifically tailored to the input and knows, that CC-AA means, there’s only 1 character left? With larger strings, we run into stuff like:

REMAIN_2_EVEN A*****A*** REMAIN_1_EVEN _*****_*** RUDLSSLUDR

Keeping track of how many steps are left. Wow.

Code .