0 Comments

In day 23 of the Advent of Code challenge, we were given a program in machine code for an imaginary computer, and asked to execute it. My great achievement was due to being woken up very early by my wife, I actually made it onto the leaderboard for the first time ever. In this video, I show the C# solution that got me there, as well as two approaches in F#.

For C#, my approach was very straightforward. Parse the instructions to arrays of strings, use a dictionary to store register states, and a switch statement to implement the instruction types. Today was a rarity in that I didn’t make any silly mistakes or misread the instructions. The one thing that I should have done that I didn’t was used unsigned integers as the problem text stated, but it turned out not to matter for my program. Here’s the code:

var registers = new Dictionary<string,int>() { ["a"] = 0, ["b"] = 0 };
var instructions = File.ReadAllLines("day23.txt")
                    .Select(i => i.Split(' ').Select(s => s.Trim(',')).ToArray())
                    .ToArray();
int index = 0;
while (index < instructions.Length)
{
    var ins = instructions[index];
    switch (ins[0])
    {
        case "inc":
            registers[ins[1]]++;
            index++;
            break;
        case "tpl":
            registers[ins[1]] *= 3;
            index++;
            break;
        case "hlf":
            registers[ins[1]] /= 2;
            index++;
            break;
        case "jio":
            index += registers[ins[1]] == 1 ? int.Parse(ins[2]) : 1;
            break;
        case "jie":
            index += registers[ins[1]] % 2 == 0 ? int.Parse(ins[2]) : 1;
            break;
        case "jmp":
            index += int.Parse(ins[1]);
            break;
        default:
            throw new NotImplementedException(ins[0]);
    }
}
registers.Dump();

In F#, discriminated unions are an obvious way to represent the various instructions, and using pattern matching to execute them. I went for a fully immutable solution, making use of the F# Map type, which is an immutable dictionary. A recursive function executes each instruction, calculating the new index and state of the registers.

type Instruction = | Increment of string
                   | Triple of string
                   | Half of string
                   | Jump of int
                   | JumpIfEven of string * int
                   | JumpIfOne of string * int
let instructions = "day23.txt"
                   |> File.ReadAllLines
                   |> Seq.map (fun i -> i.Split(' ') 
                                        |>Array.map (fun p->p.Trim(',')))
                   |> Seq.map (function
                        | [|"inc";r|] -> Increment r
                        | [|"tpl";r|] -> Triple r
                        | [|"hlf";r|] -> Half r
                        | [|"jio";r;n|] -> JumpIfOne (r, int n)
                        | [|"jie";r;n|] -> JumpIfEven (r, int n)
                        | [|"jmp";n|] -> Jump (int n)
                        | x -> failwith "invalid instruction")
                    |> Seq.toArray

let rec run index state = 
    if index >= instructions.Length then state,index else
    let a,b = 
        match instructions.[index] with
        | Increment r -> state |> Map.add r (state.[r] + 1), 1
        | Half r -> state |> Map.add r (state.[r] / 2), 1
        | Triple r -> state |> Map.add r (state.[r] * 3), 1
        | JumpIfOne (r,n) -> state, if state.[r] = 1 then n else 1
        | JumpIfEven (r,n) -> state, if state.[r] % 2 = 0 then n else 1
        | Jump n -> state, n
    run (index+b) a 

run 0 ([("a",0);("b",0)] |> Map) |> (fun (s,n) -> s.["b"]) |> printfn "a: %d" 
run 0 ([("a",1);("b",0)] |> Map) |> (fun (s,n) -> s.["b"]) |> printfn "b: %d"

I also made a slightly more compact F# solution, ditching the discriminated union, as the run function is still quite readable without it.

let instructions = "day23.txt"
                   |> File.ReadAllLines
                   |> Array.map (fun i -> i.Split(' ') 
                                        |>Array.map (fun p->p.Trim(',')))
                    
let rec run state index = 
    if index >= instructions.Length then state, index else
    let a,b =
        match instructions.[index] with
        | [|"inc";r|] -> state |> Map.add r (state.[r] + 1), 1
        | [|"tpl";r|] -> state |> Map.add r (state.[r] * 3), 1
        | [|"hlf";r|] -> state |> Map.add r (state.[r] / 2), 1
        | [|"jio";r;n|] -> state, if state.[r] = 1 then (int n) else 1
        | [|"jie";r;n|] -> state, if state.[r] % 2 = 0 then (int n) else 1
        | [|"jmp";n|] -> state, (int n)
        | x -> failwith "invalid instruction"
    run a (b+index)

run ([("a",0);("b",0)] |> Map) 0 |> (fun (s,n) -> s.["b"]) |> printfn "a: %d" // 184
run ([("a",1);("b",0)] |> Map) 0 |> (fun (s,n) -> s.["b"]) |> printfn "b: %d" // 231
Vote on HN
comments powered by Disqus