Posted in:

Thankfully, after yesterday’s failure, today’s Advent of Code challenge was much more straightforward. We have a series of instructions that need to be parsed, and then applied in order, with the caveat that some of the instructions are “jump” instructions which means we may jump backwards or forwards as we go.

I used the F# type system to represent the possible instruction types:

type Source= Constant of int | Register of string 
type Instruction = Copy of Source*string | Inc of string | Dec of string | Jnz of Source*int

And created an apply function that calculated the result of each instruction, returning a tuple of a new state (state is the registers expressed as a map of register name to value) and the offset to the next command that should be implemented:

let copy source register (state:Map<string,int>) =
    match source with
    | Constant n -> state.Add(register, n)
    | Register r -> state.Add(register, state.[r])

let inc register (state:Map<string,int>) =
    state.Add(register, state.[register] + 1)

let dec register (state:Map<string,int>) =
    state.Add(register, state.[register] - 1)

let jnz source offset (state:Map<string,int>) =
    let test = match source with
                | Register register -> state.[register]
                | Constant constant -> constant 
    if test = 0 then 1 else offset

let apply st = function 
    | 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

With the apply function in place, we recursively solve given a starting state and an array of instructions until the index of the next instruction goes beyond the end of the program.

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

There was of course a parsing part to this problem, and I used an active pattern to simplify matching:

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; dst |] -> Copy (src,dst)
    | [| "inc"; reg |] -> Inc reg
    | [| "dec"; reg |] -> Dec reg
    | [| "jnz"; Source src; offset |] -> Jnz (src, int offset) 
    | _ -> failwith ("can't parse " + inst)

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

With that in place, I could construct the initial start state, and solve parts a and be quite easily:

let startState = Map.empty.Add("a",0).Add("b",0).Add("c",0).Add("d",0)
let endState = solve instructions startState 0
printfn "part a: %d" endState.["a"]
let endStateB = solve instructions (startState.Add("c",1)) 0
printfn "part b: %d" endStateB.["a"]

It was nice to get back on track, and at least I’ve maintained my track record of not submitting an incorrect answer to any puzzle yet. The code (available on GitHub) could do with with some cleanup, but my next priority is to revisit day 11 and see if I can finally crack it (have done part a, but still need more optimisation for part b).