Posted in:

In yesterday’s Advent of Code post, I talked about “YAGNI” – you aren’t gonna need it. Well, for today’s solution, we did need to borrow some code from day 12. We were simulating a computer with the same instruction set, except for there was one new instruction – toggle.

Since we had a discriminated union defined for all possible instructions, in theory we should just have needed to add a new entry to it, and written the code to process the instruction.

However, it was more complicated than that. My day 12 solution assumed the program was immutable – but now it could change. And the toggle command can result in some impossible to implement instructions.

One benefit of using discriminated unions in F# is that you can “make illegal states impossible to represent”. But that meant my Instruction type was now too restrictive – I needed to be able to store invalid versions of some commands.

So my domain model now looks like this:

type Source= Constant of int | Register of string 

type Instruction = Copy of Source*Source | Inc of Source | Dec of Source | Jnz of Source*Source | Toggle of Source

And after introducing a helper function called read, here’s the new implementations of the original functions. As you can see, copy, inc and dec now need to ignore invalid forms of the instruction:

let read (state:Map<string,int>) = function | Constant n -> n | Register r -> state.[r]

let copy source dest (state:Map<string,int>) =
    match dest with 
    | Register register -> state.Add(register, read state source)
    | _ -> state

let inc arg (state:Map<string,int>) =
    match arg with 
    | Register register -> state.Add(register, state.[register] + 1)
    | _ -> state

let dec arg (state:Map<string,int>) =
    match arg with
    | Register register -> state.Add(register, state.[register] - 1)
    | _ -> state

let jnz source offset (state:Map<string,int>) =
    if read state source = 0 then 1 else read state offset

But what about the toggle instruction? This needs to update the program itself. Now I allowed myself to cheat a little here, and mutated the program array, rather than returning a new program, which would have been the correct functional approach. So the toggle function ends up modifying the program, and returns the same register state, and instructing us to move to the next command (offset of 1):

let toggle state source (prog:_[]) index =
    let offset = index + (read state source)
    if offset >= 0 && offset < prog.Length then
        let toggled = match prog.[offset] with
                        | Copy (source, register) -> Jnz (source, register) 
                        | Inc register -> Dec register 
                        | Dec register -> Inc register
                        | Jnz (source,off) -> Copy (source, off)
                        | Toggle source -> Inc source
        prog.[offset] <- toggled
    state,1

And what happens to our apply function from day 12? Well now it needs to take the program array in so that toggle can modify it, but otherwise it is pretty similar:

let apply (st:Map<string,int>) (prog:_[]) index = 
    match prog.[index] with
    | Copy (source, register) -> copy source register st, 1
    | Inc register -> inc register st, 1
    | Dec register -> dec register st, 1
    | Jnz (source,offset) -> st, jnz source offset st
    | Toggle source -> toggle st source prog index

The good news is that almost all the rest of the code was similar. The solve function remains the same, recursively working through each instruction. The input parsing just needed to cope with the new tgl command. And the start state had 7 in the “a” register.

let rec solve (prog:Instruction[]) (state:Map<string,int>) index =
    if index >= prog.Length then
        state
    else
        let newState,next = apply state prog index 
        solve prog newState (index+next)

let (|Source|_|) str = match System.Int32.TryParse str with true, value -> Some (Constant value) | _ -> Some (Register str)

let parseInstruction (inst:string) =
    let parts = inst.Split(' ')
    match parts with 
    | [| "cpy"; Source src; Source dst |] -> Copy (src,dst)
    | [| "inc"; Source reg |] -> Inc reg
    | [| "dec"; Source reg |] -> Dec reg
    | [| "jnz"; Source src; Source offset |] -> Jnz (src, offset) 
    | [| "tgl"; Source src |] -> Toggle src
    | _ -> failwith ("can't parse " + inst)

let program = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") |> Array.map parseInstruction

let startState = Map.empty.Add("a",7).Add("b",0).Add("c",0).Add("d",0)

let endState = solve program  startState 0
printfn "part a: %d" endState.["a"]

It took a few seconds to run, but got me my answer to the first part of the puzzle.

Part 2 in theory was easy. Just change the start state so we have 12 in register a and wait for the answer. But there was a huge hint in the puzzle description. We might be waiting a long time, and sure enough leaving the code running for 30 minutes did not yield an answer.

Could the program be optimised? Well, I did two things to find out. First of all, I made a version of my program that printed out what it was doing. This made it pretty obvious that there were some loops going on. Here’s a small section of the output:

[4] copying Register "b" to Register "c"
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[5] incrementing Register "a"
[6] decrementing Register "c"
[7] jnz Register "c" Constant -2
[8] decrementing Register "d"
[9] jnz Register "d" Constant -5
[4] copying Register "b" to Register "c"

We can see that there are some loops going on there. Looking again at my puzzle input I noticed that this pattern appeared in a few places:

inc a
dec c
jnz c -2

We’d keep incrementing register a until we’d decremented register c to 0. So essentially this was implementing a += c. But there was more. In two places, this three instruction pattern became a five instruction pattern:

inc a
dec c
jnz c -2
dec d
jnz d -5

Now we’re repeating the a += c operation d times. So this essentially is the same as implementing a += (c * d). So could I strip this code out and replace it with a multiply command? Not so fast – the extensive use of offsets, and the presence of the toggle command meant I didn’t want to mess with the contents of the instruction array.  But from examining the output of my part a solution I could tell that the only toggles that affected this 5 instruction pattern were toggling inc to dec. The jnz commands remained intact.

So I decided to do a very quick experiment. What happens if I put something very hacky into the apply function? When I hit either of these 5 instruction patterns, just increment a by the product of c and d. I use abs because whether we’re incrementing or decrementing d or c, we must be heading towards 0 or we’d have an infinite loop. So here’s the experimental hack version of apply (my loops appeared at indexes 5 and 21, and once we’ve processed them we move on 5 commands):

let apply (st:Map<string,int>) (prog:_[]) index = 
    if index = 5 || index = 21 then // multiplication loops
        st.Add("a",st.["a"] + (abs st.["c"]) * (abs st.["d"])), 5
    else
        match prog.[index] with
        | Copy (source, register) -> copy source register st, 1
        | Inc register -> inc register st, 1
        | Dec register -> dec register st, 1
        | Jnz (source,offset) -> st, jnz source offset st
        | Toggle source -> toggle st source prog index

This produced the correct answer for part a and in a fraction of the time. I then tried it on part b, but got the wrong answer. What had I done wrong?

Well, the perils of mutable code had come to bite me. Now that my solver function can mutate the program array, it’s not the same after solving part a of the problem. Had I kept it all immutable, it would have worked first time. The quick fix was to take a copy of the program array before running it through the solver:

let endState = solve (program |> Array.copy) startState 0
printfn "part a: %d" endState.["a"]

let endStateB = solve (program |> Array.copy) (startState.Add("a",12)) 0
printfn "part b: %d" endStateB.["a"]

This worked, and solved the problem in blazing fast time.

But just like yesterday, we have a solution that only works for our specific input. This one could at least be improved to be more general purpose. I could update the apply function to recognize the five instruction pattern and turn it into a multiply instruction. And if I were refactoring this code (for which there is sadly no time), I’d also return a new program from toggling, rather than mutating the existing one.

But once again, this puzzle is a great lesson in how paying attention to the shape of your input data can allow you to optimize your algorithm for your specific needs. My solution is up on GitHub if you want to see the full code.