Advent of Code Day 25

So we came to the end of the Advent of Code puzzles, and I was hoping that it would be a quick one for Christmas Day, but sadly it did not prove the case.

The problem built on the assembly language of day 23, so much of the code could be reused, but there was a new instruction “output” that emitted a signal, and the hard-coded loop optimisation I created for day 23 needed to be re-created for today’s input. So the code as I had it clearly was not in the best state to be reused.

A bigger issue was the challenge itself. We had to find the lowest starting value for the “a” register that caused the program to output a sequence 0,1,0,1 infinitely. This obviously raised some performance issues – how many values of “a” will we need to test and how long will it take to test each one? How will we know if the program is going to emit 0,1,0,1 infinitely?

So my first inclination was to try to manually decompile the program into C#. Commands like inc, dec, cpy obviously were easy to turn into assignment statements, but the jnz commands were harder to get my head around. They turned into if or break statements if we jumped forwards, and while loops to let us jump backwards.

The idea was that by decompiling into a language I am more familiar with, I would understand what the program did and what input would be required to generate the desired output sequence. However, at some point in the decompilation process I realised I’d made a mistake, so I abandoned the approach. Later however, I discovered that some people on the reddit group had indeed successfully decompiled their program, and it’s worth looking at their solutions.

So I fell back to testing every possible value of ‘a’. I decided that if I got a sequence of length 20, that would probably be good enough.

I started by making the refactoring I should have done on day 23, and included the program, the instruction index and now the list of values emitted by the output command in the state object along with just the registers. This gives us a more functional solution instead of mutating the program with the toggle command.

type State = { Registers:Map<string,int>; Program:Instruction[]; Index:int; Output:int list}

Now to be honest I still didn’t implement all the refactoring this problem deserved. When I found a solution, I just used failwith to break out and relied on the fact that my console output would contain the last value of register ‘a’ that I’d tried. So my ugly implementation of the new out instruction looks like this:

let out source state =
    let emit = (read state.Registers source)
    let expect = match state.Output with
                    | [] -> 0
                    | head::tail -> if head = 0 then 1 else 0
    let next = if emit=expect then state.Index + 1 else 1001
    if List.length state.Output = 20 then
        printfn "SUCCESS"
        failwith "get out of here" 
    else                
        { state with Output = emit :: state.Output; Index = next }

The apply function’s signature becomes simpler as a result of our State type. It just takes the input state and returns the output state. And it includes a hard-coded optimization of a multiplication loop just like we had on day 23.

let apply (st:State) : State = 
    if st.Index = 3 then // multiplication loops
        { st with 
            Registers= (st.Registers.Add("d",st.Registers.["d"] + (abs st.Registers.["c"]) * (abs st.Registers.["b"]))); 
            Index = st.Index + 5 }
    else
        match st.Program.[st.Index] with
        | Copy (source, register) -> { st with Registers = copy source register st.Registers; Index =st.Index + 1 } 
        | Inc register -> { st with Registers = inc register st.Registers; Index = st.Index + 1 }
        | Dec register -> { st with Registers = dec register st.Registers; Index = st.Index + 1 }
        | Jnz (source,offset) -> { st with Index = st.Index + jnz source offset st.Registers }
        | Toggle source -> failwith "not supported" // toggle st state.Registers prog index
        | Out source -> out source st

Now we could just try to solve with an incrementing start value for register a:

for a in [0..10000] do
    printfn "Trying %d" a
    let x = solve { Registers = startState.Add("a",a); Program=program; Index = 0; Output = [] } 
    printfn "Fail"

This got me my answer pretty quickly, and with hindsight I wish I’d started with this approach rather than going for decompilation. I did at least get my two stars for day 25 before the end of the day.

But the code I ended up with to solve day 25 is a horrible mess. It needs a real clean-up that I don’t have time for. So I’m hoping I won’t end up needing to reuse this code for Advent of Code 2017! This is a good example of the “technical debt” problem I created a Pluralsight course about. We have code that does actually work, but is in a far from ideal state. Should we spend time refactoring it and improving its design? If we don’t then next time we need to work on the code we will find ourselves struggling and going much slower. But if we do, we’ve potentially wasted our time if that code turns out not to need any future modifications. It takes good judgment to know when you need to keep refactoring, and when its OK to just lay your code to one side and move onto the next task.