Posted in:

Today’s Advent of Code challenge involved finding a path through a maze. I knew this would require some kind of variation on the A* algorithm, but it’s not one I’d implemented before so I had to invent my own (probably inefficient) version from scratch.

The first part of the problem was simply calculating where the walls were. This was done using a simple calculation which involved counting how many bits were set in the binary representation of a number. Although a Stack Overflow search reveals that there are some clever hacks to do this, I implemented a recursive bit counter using the F# bitwise operators &&& and >>>

let countBits number = 
    let rec countBits' count number =
        if number = 0 then count
        else
            let set = number &&& 0x1 = 1 
            countBits' (count + if set then 1 else 0)  (number >>> 1)
    countBits' 0 number

let isWall favourite (x,y) =
    if x < 0 || y < 0 then true
    else
        let n = x*x + 3*x + 2*x*y + y + y*y
        (countBits (n + favourite)) % 2 = 1

I did know that the path-finding algorithm would be breadth-first, which gave me a head-start since I’d learned how to do that in day 11’s challenge. I decided to use a Dictionary keyed on position to distance from start to represent the map, and a regular queue of the neighbouring positions we need to calculate. Obviously this means I am using mutable state, but after being burned on day 11 I was happy to gamble that it might be needed today for performance reasons as well.

For part a of the problem, we were just measuring the distance to a specific target, so the search function returned an int, but for part b I wanted it to be more generic, returning the full state of the map as well as taking a function to decide if we’ve reached our target.

I mark walls with Int32.MaxValue simply to prevent us keeping having to run the isWall function repeatedly. The breadth-first search works similarly to day 11 – for each point on the queue, if we’ve found the solution, return, and if not, calculate the child positions (up down left right) and if they’ve not already been visited and aren’t walls, add them to the state with the new distance, and queue them up to be processed.

open System.Collections.Generic
let search (start:int*int) isTarget (isWall:int*int->bool) =
    let points = new Queue<int*int>()
    let distances = new Dictionary<int*int,int>()
    let rec search'() =
        if points.Count = 0 then
            -1, distances
        else
            let (x,y) = points.Dequeue()
            let steps = distances.[(x,y)]
            if isTarget (x,y) steps then
                steps, distances
            else
                let newPoints = [(x+1,y);(x-1,y);(x,y+1);(x,y-1)]
                for newPoint in newPoints do
                    if not (distances.ContainsKey(newPoint)) then
                        if isWall newPoint then 
                            distances.[newPoint] <- System.Int32.MaxValue
                        else
                            distances.[newPoint] <- steps + 1
                            points.Enqueue(newPoint)
                search'()
    distances.[start] <- 0
    points.Enqueue(start)
    search'()

With these in place, I was able to solve parts a and b, by passing in different terminating conditions, and for part b, counting all places in the map whose  distance was less than or equal to 50.

search (1,1) (fun a b -> a = (31,39)) (isWall 1350) |> fst

search (1,1) (fun a b -> b = 51) (isWall 1350) 
    |> snd 
    |> (fun a -> a.Values)
    |> Seq.filter (fun a -> a <= 50) 
    |> Seq.length

All in all, I surprised myself at how quickly I solved this one. It just goes to show that the little bit of knowledge I learned from day 11 meant I immediately knew how the structure I wanted for today’s solution.

The other thing that has really surprised me is that I’ve made it to day 13 without yet having submitted an incorrect value. I guess it is some sort of confirmation of the claim that with functional code, if it compiles, that probably means it works. Although I came very close to messing up as I initially misread part b as asking for the number of locations that were exactly 50 away. It was only because my answer came out as 1 that caused me to double-check everything. So I suspect this record won’t last too much longer!

As usual, code up on GitHub.