AOC 2016 - Day 1, Part 1

Disclaimer

I want to start this post by saying that when I first started with Advent of Code, I had no idea that each day's problem is divided into two parts. Thus, the code will often look awkward and weird. If I were to re-code the solution, knowing what I know now, I would definitely make some changes.

Please note that I have NOT gone back and "fixed up" the code. This is the actual code I wrote to successfully solve each challenge. Are there things I would change - Yes. However, I am much more interested in finding solutions for new problems than I am in fixing this code, especially since no one else is relying on it.

I have tried to learn from my mistakes, as will hopefully be obvious from code written for future challenges.

The setup

The following theme is used, at least as far as I know, to tie all 25 days worth of AOC problems together.

Santa's sleigh uses a very high-precision clock to guide its movements, and the clock's oscillator is regulated by stars. Unfortunately, the stars have been stolen... by the Easter Bunny. To save Christmas, Santa needs you to retrieve all fifty stars by December 25th.

The second paragraph actually tells you that there are 2 problems each day. Obviously, I was not paying attention to detail like I should have (emphasis is mine).

Collect stars by solving puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

The reason I mention this is that the code may look awkward for certain solutions when I am trying to re-use code from that day's first part.

The problem

Rather than copy-paste lots of text, I will briefly describe the problem. Please go to the AOC website to see the original information.

The first problem is a relatively simple example of writing an algorithm to move in a grid-like pattern with no diagonal movements (since you can only turn left and right by 90°) - this is also known as Taxicab geometry.

The solution

Types

Sidenote: Although I am solving all these problems in F#, what really got me back into programming (and loving it again!) is the language Elm. If you don't know what Elm is, I highly recommend taking a look. It is a beginner-friendly functional language designed to write safe web applications (it is compiled into Javascript). One of the tips to solve problems in Elm (or pretty much any language for that matter), is to start by defining your types. That is what I did here.

After a few false starts, here is how I chose to define the types. Initially, I did not have the Point type but this was added later on to facilitate work on Day 1, Part 2.

type Direction =
  | North
  | South
  | East
  | West

type TurnTo =
  | R
  | L

type Point = {
  x : int
  y : int
}

type Location = {
  dir : Direction
  pt : Point
}

In order to make life easier, I have a few base values for my complex types.

let startPt = {
  x = 0
  y = 0
}

let startLoc = {
  dir = North
  pt = startPt
}

Reading the instructions

Now that I have defined my types, I can start diving into the logic. The first task I need to solve is to convert instructions (which was not as easy as I thought - more on that further down in the post) into my nice types. I built a small helper function to translate a character representing the direction (L and R) into a TurnTo value.

let toTurn = function
  | 'R' -> R
  | 'L' -> L
  | _ -> failwith "Unknown turn type"

Individual moves

For each individual instruction in the list, I need to do 2 things:

  1. turn in the appropriate direction
  2. move forward the specified number of blocks.

In the spirit of writing small, digestible functions and stringing them together, I broke this logic into two steps. First, since my current location includes my cardinal direction, I wrote a small function to implement the turn. The signature of this function is TurnTo -> Location -> Location. It takes a Direction to turn in and the current Location (which includes my current Direction), and returns a new Location record where I am pointing in the updated direction based on the instruction.

let turn way loc =
  match way with
  | L ->
    match loc.dir with
    | North -> { loc with dir = West }
    | West -> { loc with dir = South }
    | South -> { loc with dir = East }
    | East -> { loc with dir = North }
  | R ->
    match loc.dir with
    | North -> { loc with dir = East }
    | East -> { loc with dir = South }
    | South -> { loc with dir = West }
    | West -> { loc with dir = North }

The second function I wrote advances me in the given direction. This function's signature is int -> Location -> Location. Similar to turn, this function takes the number of blocks to move and current Location, and returns a new, post-move Location.

let advance dist loc =
  match loc.dir with
  | North ->
    let npt = { x = loc.pt.x; y = loc.pt.y + dist }
    { loc with pt = npt }
  | South ->
    let npt = { x = loc.pt.x; y = loc.pt.y - dist }
    { loc with pt = npt }
  | West ->
    let npt = { x = loc.pt.x - dist; y = loc.pt.y }
    { loc with pt = npt }
  | East ->
    let npt = { x = loc.pt.x + dist; y = loc.pt.y }
    { loc with pt = npt }

And now we just need to tie them together to move. Move is quite simple - it's purpose is to put together a turn and an advancement into a single action. Its signature is TurnTo -> int -> (Location -> Location). What this means is that it takes a TurnTo and an int, then returns a function. When a Location is passed to this new function, the character will perform a single move. Here, I am using the F# function composition operator.  You can find a good writeup on it here.

let move way dist = (turn way) >> (advance dist)

Stringing moves together

Most of the guts of this algorithm are now coded, but we are still missing 2 main pieces:

  1. the connection from a list of instructions to actual movements, and
  2. calculating the distance from the start point (assumed to be (0,0) facing North) to the final Location.

This duty falls to the moveAll function. This function takes a string and returns a Location. It parses the list of instructions and then progressively folds the intermediate results into a final Location.

let moveAll strList =
  Regex.Matches (strList, @"[LR]\d+")
  |> Seq.cast
  |> Seq.fold
    (fun oldloc (instr : System.Text.RegularExpressions.Match) ->
      move
        (instr.Value.[0] |> toTurn)
        (instr.Value.Substring 1 |> int)
        oldloc
    )
    startLoc

Now we come to the end and put a bow on the solution. The distance function just calculates the distance between the initial and final points using Taxicab geometry and partOne : strList:string -> int ties moveAll to distance.

let distance stloc endloc = (abs (stloc.x - endloc.x)) + (abs (stloc.y - endloc.y))

let partOne strList =
  strList |> moveAll |> fun x -> distance startPt x.pt

Getting the answer, and a note about parsing and file manipulation

I mentioned earlier that I would speak more about parsing. Well, the smart thing to do with a problem like this is to take the input from the AOC website, put it into a file, and then parse it in the code. However, when I started on AOC, I did not know how to perform file manipulation with F# (and apparently didn't want to learn for the first few days of problems). Thus, you will see odd things like this block of code in my solutions for the first few days. At some point, I realized that copy/pasting large blocks of text into an F# script file is not a smart idea and learned how to manipulate files (which turns out to be quite easy in .NET).

Putting all this together and seeing it run (at last!) was a great feeling. The answer you get if you run my code is 239, which is, in fact, the correct answer.

I am intending to put all my code into GitHub sometime in the near future. Until then, all my code for the first solution is actually on this page (and in my gists) except for one import of System.Text.RegularExpressions.

See you next time!