Posted in:

I’ve been trying to solve the Advent of Code challenges every day in F#, and today’s challenge was one that reminded me of last year’s day 7 challenge. We have a list of instructions we need to apply one by one, but some instructions need to be deferred – we can’t process them yet.

Last year I solved that with a deferAggregate function that let me put instructions I couldn’t process yet at the back of the queue.

This year I wanted to go for a fully immutable solution so the idea was to solve it like this:

Step 1 – parse the input into a list of instructions

Step 2 – create a function that can apply an individual instruction to the current “state”. The state is a Map (which in F# is immutable) showing us which “bots” and “outputs” have which “chips”. The function either returns a new state or indicates it can’t process the instruction yet

Step 3 – create a function that folds a list of instructions and a starting state and returns the end state and a list of instructions that haven’t been applied yet

Step 4 – recursively call that function until there are no instructions left that can’t be applied.

Despite having a clear picture of how I wanted to solve the challenge, I must confess to making heavy weather of implementing it, so I haven’t had time to clean this code up much. But here’s a working solution at least.

In my domain model there are two “targets” – either bots or outputs, and two possible instructions. I abandoned Regex and went for a simpler string splitting approach to parsing the instructions:

type Target = Bot of int | Output of int
type Instruction = StartsWith of int*int | GivesTo of int*Target*Target

let asTarget = function
    | [ "bot"; value ] -> Bot (int value)
    | [ "output"; value ] -> Output (int value)
    | _ -> failwith "invalid target"

let parseInstruction (inst:string) =
    let parts = inst.Split(' ')
    if parts.[0] = "value" then StartsWith(int parts.[1],int parts.[5])
    else GivesTo(int parts.[1], asTarget [parts.[5];parts.[6]], asTarget [parts.[10];parts.[11]])

The state was stored in a Map keyed on Target and containing a list of chip values. I made a simple function to add a new chip to a specific target in the state, returning a new Map

let updateState (state:Map<Target,int list>) target chip =
    if Map.containsKey target state then
        let chips = state.[target]
        state.Add(target, chip::chips)
    else 
        state.Add(target, [chip])

Now we can write the code to apply each instruction. applyInstruction returns either Some state or None if the instruction cannot yet be applied. I factored handing the giving function out into handleGive as it was a little bit cumbersome to write. I’m sure it could be made more succinct with a bit of thought. You’ll see I’m kind of cheating a little as I just print the answer to part a out along the way, rather than returning it as an output to the function. I suspected that part b would need us to complete the full instruction set and it turns out I was right.

let handleGive (st:Map<Target,int list>) bot low high =
    if Map.containsKey (Bot bot) st then
        match st.[Bot bot] with
        | [a;b] -> 
            let lowChip = min a b 
            let highChip = max a b
            if (lowChip = 17 && highChip = 61) then
                printfn "part a: %d" bot
            let st2 = updateState st low lowChip
            Some (updateState st2 high highChip)            
        | _ ->
            None
    else
        None

let applyInstruction (state,leftovers) instruction = 
    let result = match instruction with
                    | StartsWith (chip, bot) -> Some (updateState state (Bot bot) chip) 
                    | GivesTo (bot,low,high) -> handleGive state bot low high
    match result with
        | Some st -> (st,leftovers)
        | None -> (state,instruction::leftovers)

Finally we’re ready to make our recursive function, applyAll, which takes the state and list of instructions. We fold the applyInstruction function across the list and this gives us an ending state and a set of leftover instructions. We can then recursively call ourselves until there are no leftover instructions. (n.b. you can optionally also bomb out if you fail to apply any leftover instructions to avoid getting stuck in an infinite loop)

let rec applyAll state instructions =
    let (newState,leftovers)  = instructions |> List.fold applyInstruction (state, [])
    match leftovers with 
    | [] -> newState 
    | _ -> applyAll newState (leftovers |> List.rev)

Part b is solved by calculating the final state and then multiplying the token values found in outputs 0,1 and 2 together like this:

let instructions = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt") |> Array.map parseInstruction
let finalState = applyAll Map.empty (instructions |> List.ofArray)
[0;1;2] |> List.collect (fun n -> finalState.[Output n]) |> List.reduce (*) |> printfn "part b: %d"

As usual, the full code is on GitHub. Today’s challenge was another reminder that although I am getting better at thinking functionally about solving challenges, I’m still quite slow at writing the code. But that’s the whole point of doing challenges like this, by forcing myself to write functional code, it eventually starts to come more naturally.