Posted in:

I’ve set up a GitHub repository for my F# solutions to Advent of Code this year, and although this year I suspect I won’t have enough time to blog about every day’s solution, I did attempt the first day’s problem.

As usual, the first part is simply parsing the problem input. For this problem, there was a string of directions like this: “L2, R3” which means turn left, go forward two blocks, turn right, go forward three blocks.

I needed to turn this into a sequence of “instructions”. Initially I used string splitting, and my instruction type encapsulated the change of direction and the number of blocks to move. But as it turned out, part 2 of the problem is more easily solved if there is a separate “turn” instruction, and instead of a “move forward n blocks” command, it should repeat the “move forward 1 block” command n times.

So by using a bit of regular expressions and a Seq.collect to expand the move commands, we can get them into a sequence of Instruction types like this:

open System.Text.RegularExpressions
type Turn = Right | Left
type Instruction = Turn of Turn | Move
let input = System.IO.File.ReadAllText (__SOURCE_DIRECTORY__ + "\\input.txt")
let instructions = Regex.Matches(input, "([LR])|(\\d+)") 
                    |> Seq.cast<Match>
                    |> Seq.map (fun m -> m.Value)
                    |> Seq.collect (function | "L" -> [Turn Left] | "R" -> [Turn Right] | n -> [for _ in 1..int(n) -> Move])

Now the state we need to maintain as we apply these commands is what our current position is, what direction we are facing, and (for part b of the problem), all the places we have visited so far.

This can be done by using a tuple for the current position, a vector indicating the direction we are facing (which eliminates some clumsy match statements from my original solution which created a discriminated union of North | West | South | East), and an immutable set of all locations we have visited so far. Here’s my State type and the starting state:

type State = { pos: int*int; facing: int*int; visited: Set<int*int> }
let startState = { pos = (0,0); facing = (0,-1); visited = Set.empty }

Now we need a move function that takes an instruction and a current state, and applies it, creating a new state. The instructions are either turn, or move one step forwards. So I created a couple of helper functions – one to rotate the direction, and one to add two vectors, and used them to implement the move function:

let rotate (x,y) = function | Right -> (y*(-1),x) | Left -> (y,x*(-1)) 
let move state instruction =
    match instruction with 
    | Turn direction ->
        { state with facing = rotate state.facing direction }
    | Move ->
        let addv (x,y) (i,j) = (x+i,y+j)
        { state with pos = addv state.pos state.facing; visited = Set.add state.pos state.visited  }

Once we can apply one instruction, it is trivial to apply all the instructions with a fold, and get the finishing state from which we only need the current position to solve part a:

let endState = instructions |> Seq.fold move startState
let getDistance (x,y) = abs(x) + abs(y)
printfn "Part a: Distance from home is %d" (getDistance endState.pos)

Part b required us to remember all the places we had been (which is why we maintain the visited set in the state object), and identify the first place we visit twice. We can achieve this by using a scan, which produces a sequence of states as we apply each instruction. That means we can use find to iterate through until we find the first one where the current position is in the list of already visited places.

let visitedTwice = instructions 
                    |> Seq.scan move startState
                    |> Seq.find (fun f -> f.visited.Contains(f.pos))

printfn "Part b: Distance from home is %d" (getDistance visitedTwice.pos)

You can see the full code here, and as always I welcome ideas about how my F# can be improved.

One of the interesting things about solving this challenge in F# was the realisation that I would have been able to solve it much quicker with procedural instead of functional code. I’d simply create a for loop to go through each instruction, mutating a current position and facing direction variable and adding positions to an already visited list.

By contrast, the functional solution was harder to refactor from part a to part b, since the fold function I’d used wasn’t appropriate any more, and I had to significantly change my code to suit it to solving both halves of the problem.

So although I believe a functional paradigm has a lot of benefits over procedural, this challenge highlights that my brain is still wired to think procedurally, and it will be a while yet before I find the functional approach comes more naturally.