Posted in:

Today’s Advent of Code challenge required the ability to MD5 hash a string and return the result as a lower-case string, and to implement a breadth-first search.

Well those are both things we’ve done before this year, so I should have been able to just pull ready-made functions in from previous day’s solutions.

And for the MD5 hasher I already had exactly what I needed:

let md5 = System.Security.Cryptography.MD5.Create()
let hash (s:string) =
    Encoding.Default.GetBytes(s)
    |> md5.ComputeHash
    |> (fun h -> BitConverter.ToString(h).ToLower().Replace("-",""))

But although I’d implemented a breadth first search twice already in this year’s Advent of Code challenge, I hadn’t created a generic implementation. A breadth first search needs three things – a starting state, a function that checks if a given state is a “solution”, and a function that returns the next states from a given state. So I decided to make a generic breadth first search that returns a sequence of solution states. It uses a regular .NET Queue<T> for the states to explore, as that has performed well for me previously.

let bfs (isSolution:'a->bool) (getChildren:'a->seq<'a>) (start:'a) =
    let q = new Queue<'a>()
    q.Enqueue(start)
    let rec search() = seq {
        if q.Count > 0 then
            let s = q.Dequeue()
            if isSolution s then 
                yield s
            else
                for c in getChildren s do
                    q.Enqueue(c)
            yield! search()
    }
    search()

With those generic parts in place, now we need to write the code specific to today’s problem. The state for our problem is the current position and the directions taken to get there. And to check if we’ve solved the problem, we just need to check the current position:

type State = { pos: int*int; path:string}

let isSolution state = state.pos = (3,3)

The function to generate child states is a little more complex, but not really that hard to do. I implemented it as a getValidMoves function that returns a sequence of new states.

let isOpen (c:char) = c >= 'b' && c <= 'f'

let getValidMoves passcode state = seq {
    let (x,y) = state.pos
    let h = hash (passcode + state.path)
    if isOpen h.[0] && y > 0 then
        yield { pos = (x,y-1); path = state.path + "U" }
    if isOpen h.[1] && y < 3 then
        yield { pos = (x,y+1); path = state.path + "D" }
    if isOpen h.[2] && x > 0 then
        yield { pos = (x-1,y); path = state.path + "L" }
    if isOpen h.[3] && x < 3 then
        yield { pos = (x+1,y); path = state.path + "R" }
}

And now to solve part a, we just need to extract the path from the first solution from our searcher. (By the way I finally entered my first wrong answer today. I thought I had to enter the path length rather than the path itself for part a. Very annoying, because my path was correct!)

let startState = { pos=(0,0); path="" }
let solve passcode =
    let s = bfs isSolution (getValidMoves passcode) startState |> Seq.head
    s.path 
solve "pxxbnzuo" |> printfn "Part a: %s"

And then for part b, we need the longest solution where we pick out the longest solution (could equally have just selected the last element in the sequence):

let solveB passcode =
    bfs isSolution (getValidMoves passcode) startState 
        |> Seq.map (fun s -> s.path.Length)
        |> Seq.max 

solveB "pxxbnzuo" |> printfn "Part b: %d"

So today’s solution goes to show how much time can be saved if you have some generic implementations of common algorithms ready and waiting for you to reuse when needed.

As usual, code available on GitHub.