ZNProjects

Software is beautiful again!

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  | Westtype TurnTo =  | R  | Ltype 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}``

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 `advance`s 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. |> 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``

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`.