I'm a big fan of Advent of Code. This yearly programming challenge gives me achance to see how my problem solving skills have developed over the last year, and provides an opportunity to get my hands dirty with some lesser-used F# functions.
Day 6: Guard Gallivant
In this blog post, I want to have a look at day 6 of Advent of Code 2024, the puzzle tracking the whereabouts of a guard navigating a lab. The puzzle input is something like this:
........#..
.#.....#...
#....#.....
..#...#....
#....^....#
.#...#.....The guard is indicated by the ^, while the # are obstructions. The guard initially starts moving north, and will rotate 90 degrees clockwise every time he encounters an obstacle.
The initial problem is: how many squares will the guard cover before leaving the grid?
Building the basis
Since we love domain modelling, let's establish our domain; the map is a bool array array, where true indicates an obstacle:
type Direction =
| North
| East
| South
| West
type GuardState =
{ Position: int * int
Direction: Direction }
type Map = bool array arrayThen the boring bit, parsing our data into our domain:
let parse (data: string array): (Map * GuardState)=
let map =
data
|> Array.map (
Seq.map (function
| '#' -> true
| _ -> false)
>> Array.ofSeq
)
let guardState =
let position =
let row = data |> Array.findIndex (Seq.contains '^')
let col = data[row] |> Seq.findIndex ((=) '^')
row, col
{ Position = position
Direction = North }
(map, guardState)
We are ready to start solving!
Moving Around
In order to answer the question of how many squares the guard touches before he leaves the grid, let's model how the guard moves around.
Let's add a function move, that returns a new Guard in the new position:
let move map guard =
let newPos =
let x, y = guard.Position
match guard.Direction with
| North -> (x - 1), y
| East -> x, (y + 1)
| South -> (x + 1), y
| West -> x, (y - 1)
{ guard with Position = newPos }
Very naive! What if we hit an obstacle? Or leave the grid!? Let's add a function that checks for both of these cases. if the location is out of bounds, we return None. Otherwise we return whether the position is blocked:
module Map =
let tryIsBlocked (map: bool array array) (x, y) =
if x >= 0 && x < map.Length && y >= 0 && y < map[0].Length then
Some(map[x][y])
else
NoneWe add this check to our move function, which now becomes tryMove; if we leave the map we return None.
let tryMove map guard =
let newPos =
let x, y = guard.Position
match guard.Direction with
| North -> (x - 1), y
| East -> x, (y + 1)
| South -> (x + 1), y
| West -> x, (y - 1)
Map.tryIsBlocked map newPos
|> Option.map(
failWith "implement how we move based on the state of position we are facing"
)The next part is easy; if position we are facing is blocked, rotate. Otherwise, move into that square.
module Direction =
let rotate =
function
| North -> East
| East -> South
| South -> West
| West -> North
module Guard =
let tryMove map guard =
...
Map.tryIsBlocked map newPos
|> Option.map (fun nextPosIsBlocked ->
if nextPosIsBlocked then
{ guard with
Direction = Direction.rotate guard.Direction }
else
{ guard with Position = newPos })Tying it all together
That's all good, but how do we figure out how many positions we covered based on this?
We have:
- A map we can navigate
- A starting position
- A function that can tell us where we go, based on a position
We want:
- The number of squares we touched. It's probably easiest to create a list of positions, and then count those
How do we use that function to convert the state into a list? Presenting List.unfold!
Intermission: List.(un)fold
His sister List.fold is slightly better known; she transforms a collection into an aggregate given a starting state:
(folder: 'State -> 'T -> 'State) -> (initialState: 'State) -> (list: 'T list) -> 'State Unfold does the exact opposite: Given a known state and a generator, it can produce a list.
The generator takes a state, and returns a list item, as well as a new state, so the generator can be called on that again. It returns an option, so we can return None to indicate we can not generate more values.
(generator: 'State -> ('T * 'State) option) -> (state: 'State) -> `T listBack to that pesky guard
So how do we apply List.unfold to our problem? We actually got really close to writing a generator already! Our Guard.tryMove has the following signature:
(map: bool array array) -> (guard: Guard) -> Guard optionWe can partially apply map, because it will not change. We are left with a function of Guard -> Guard option. The generator should not just return the new state, but also something to add to the list. Let's map the result of our tryMove function to do that:
Guard.tryMove map >> Option.map(fun s -> (s.Position, s))We can now pass our complete generator into List.unfold to get a list of all positions we visited:
let solve map guardState =
let (positions: (int*int list)) =
List.unfold (Guard.tryMove map >> Option.map(fun s -> (s.Position, s))) guardStateWe're almost there! We might have visited a position twice, so let's filter those out before writing our solution to the console:
let solve map guardState =
let (positions: (int*int list)) =
List.unfold (Guard.tryMove map >> Option.map(fun s -> (s.Position, s))) guardState
printfn $"The guard visited {positions |> List.distinct |> List.length} locations"And there you have it!
I had a lot of fun solving this puzzle; it's a very clear problem, but figuring out how to solve it was definitely a bit tricky. Before I started solving this solution, I did not know about List.unfold, but once I wrote the function to model the movement, a quick look at the F# List module handed me exactly what I needed to tie it all together!
Check out my full solution to this and other Advent of Code problems on GitHub.
