Part 1 looks very similar to the basic version. 2 heads is converted into 1 head + 1 state.

The same goes for part 2.

Part 3 is a little more tricky, and I didn’t optimize my solution. My 1 head looks at all 3 characters (this one, the one below it, and the one to the right of it). Vertical pair, write @ above. Horizontal pair, replace this character. Move on. There’s a little extra work, if the position above isn’t empty. Also I write a character at the beginning of the line, so that I can find it again easily later.

Moving up until I find an empty spot:

All my code .