Advent of Code Day 12–Machine Code
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
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).