12 March 2017

AOC 2016 - Day 2 Afterthoughts

AOC 2016 - Day 2 Afterthoughts

After I first finished coding the Advent of Code Day 2 challenge and then again after I wrote the corresponding blog entry, I felt dissatisfied with my solution.

The reasons for this are numerous:

  1. The keypad was never formally modeled as a type.
  2. The move function basically encoded the constraints of the keypad, with rather brittle assumptions about what that keypad looks like.
  3. The move function operated on strings, as opposed to a more 'proper' data type.

For a toy problem such as the AOC challenge, the poor choice I made there is barely acceptable. However, in the 'real world', this type of decision can mean the difference between gibberish and maintainable code.

Let's take this problem one step further. If you look closely, you will see that the keypad is really just a specialized version of a general 2-dimensional (2D) board.

How Can A 2D Board Be Represented As A Functional Data Structure?

In general, 2D boards are often represented as some form of graph. We have some choices when it comes to representing a 2D board in F#. We are aided by the fact that, for the AOC problem, we don't 'need' to (though we may want to) change this data structure once it is created. This means that even if we use an inherently mutable data structure like an array, our logic can be written so that we do not to 'lose' immutability in this scenario.

If you were implementing an actual game where the state of the board changes (e.g. the locations of the players, threats, obstacles, etc.), your decision would require different analysis.

Here are some data structures we can use to represent a 2D board in F#:

  • Adjacency matrix
  • Edge list
  • Adjacency list
  • Inductive graphs

Adjacency matrix

References: Wikipedia, NIST, Khan Academy

Per Wikipedia, an adjacency matrix is "a square matrix used to represent a finite graph".

F# comes with a convenient data structure called Array2D that we can use for this purpose. You can also represent a fixed-width 2D array as a 1D array/list/seq using row- or column-major order to store the information.

In general, adjacency matrices have the following characteristics:

  • Space:
    • \mathcal{O}(V^2) space usage, where V is the number of vertices.
  • Speed:
    • \mathcal{O}(1) constant time operations to:
      • Check if an edge exists.
      • Add an edge.
      • Remove an edge.
    • \mathcal{O}(n) time operations to:
      • Get all the edges for a given vertex.

Edge List

References: Khan Academy

An edge list is a way to represent a graph by simply keeping an exhaustive list of all the edges. For undirected graphs, a 2-tuple is sufficient. For directed graphs, a 3-tuple (or more) may be required to hold additional information about the edge.

Though these data structures are quite simple, they work very well for smaller graphs and are easy to reason about. You can also optimize these structures (to a certain degree) by creatively reducing the number of edges that need to be tracked.

In general, edge lists have the following characteristics:

  • Space:
    • \mathcal{O}(E) space usage, where E is the number of edges.
  • Speed:
    • \mathcal{O}(n) time operations to:
      • Get all the edges for a given vertex (if using a list to store the edge list).
    • \mathcal{O}(1) constant time operations to:
      • Get all the edges for a given vertex (if using a hash-based structure to store the edge list).
    • \mathcal{O}(d) speed to check if a particular edge exists, where d is the degree of the vertex in question.

Adjacency List

References: Wikipedia, Open Data Structures, NIST, Khan Academy

Per Wikipedia, an adjacency list is "a collection of unordered lists used to represent a finite graph". It is a combination of an adjacency matrix and an edge list.

In F#, an adjacency list can use a number of data structures, including list, map, dict, etc. Hash-based structures (such as dict) should provide good performance due to faster access to the mapping from vertex to edges.

In general, adjacency lists have the following characteristics:

  • Space:
    • 2|E| space usage for an undirected graph, where E is the number of edges.
    • |E| space usage for a directed graph, where E is the number of edges.
  • Speed:
    • \mathcal{O}(d) time operations to:
      • Check if a particular edge exists, where d is the degree of the vertex in question.
    • \mathcal{O}(1) constant time operations to:
      • Get all the edges for a given vertex.

Inductive Graph

References: Inductive Graphs and Functional Graph Algorithms, Martin Erwig's Functional Graph Library, Hekate - Graphs for F#, Wikipedia

Per Martin Erwig's paper, there is a gap in how graph structures are represented and manipulated in functional languages, especially when it comes to performance as compared to imperative implementations (I completely, 100% agree). His paper lays out a strategy for creating a graph as an inductively defined data type. Inductive data types are algebraic data types or sum types (i.e. F# discriminated unions) which can also be recursive (e.g. the classic functional representation of a tree or list structure that is based on discriminated unions).

I actually found this paper when I was looking for information on how to represent graphs in functional languages. I strongly recommend that anyone who is interested in such data structures should read the original paper.

Erwig's goal was to create a fully functional data structure whose performance is as close to imperative data structures (e.g. adjacency lists) as possible. Erwig performed some analysis based on his recommended implementation of inductive graphs using binary search trees, and I'll provide those characteristics here:

  • Speed:
    • \mathcal{O}(n \log n) time operations to:
      • Insert new vertices into the graph
    • \mathcal{O}(n^2 \log n) or \mathcal{O}(n \log^2 n) time operations to:
      • Delete vertices from the graph

So, What Comes Next?

Returning to our problem, we see that we have a number of implementation choices. Naively, we have up to 9 vertices and 36 edges in this example (Day 2, Part 1) or 13 vertices and 52 edges (Day 2, Part 2). This means that even a poorly selected data structure will most likely have minimum impact on the run speed.

When I first started the exercise of blogging about my AOC solutions, I had no intention of rewriting solutions. However, I did start this as a personal learning exercise, so I feel that this is a good use of my time (and will allow me to play with data structures and libraries that I've never used in F#).

I am currently going through the exercise of re-writing an implementation for Day 2 using the 4 choices presented above. My goal is to finish and write about those implementations before writing about the solution for AOC Day 3.

See you next time!

10 March 2017

AOC 2016 - Day 2

AOC 2016 - Day 2

tl;dr Code for Day 2, Parts 1 and 2 can be found on GitHub.

Background

On Day 1, you located the Easter Bunny headquarters. On Day 2, you have entered the building, but need to use the bathroom. You have to break the code on the door lock to enter the bathroom.

Problem - Part 1

The problem for Day 2 is in a similar vein to the Day 1 problem. Your instructions are that you are using a 3x3 numeric grid, similar to the one below, and you have to decipher a set of instructions where you move up, down, left, and right on the keypad to arrive at each digit of the code.

1 2 3
4 5 6
7 8 9

And here are some sample instructions for a 4-digit keypad code.

ULL
RRDDD
LURDL
UUUUD

For Part 1, each digit of the code is calculated by starting at 5 and following the instructions.

If you hit an edge and the next instruction would take you past the edge, you do not move.

Solution - Part 1

Similar to last time, I started by defining a simple type to hold my instructions and a corresponding function to transform text instructions to that new type.

(* The Directions that you can move (no diagonals allowed) *)
type Direction = | L | R | D | U

(* Converts a string to a Direction *)
let toDirection = function
  | "L" -> L
  | "R" -> R
  | "D" -> D
  | "U" -> U
  | _ -> failwith "toDirection"

I defined a function to move one step at a time. The function is a simple exhaustive match for all possible inputs.

I am certain now that I could have written a set of functions to calculate the next position based on the current position and an instruction. That would have gained me some brevity, but this worked just as well.

let move curBtn input =
  match input with
  | L ->
    match curBtn with
    | '1' | '2' -> '1'
    | '3' -> '2'
    | '4' | '5' -> '4'
    | '6' -> '5'
    | '7' | '8' -> '7'
    | '9' -> '8'
    | _ -> failwith "move.L"
  | R ->
    match curBtn with
    | '1' -> '2'
    | '2' | '3' -> '3'
    | '4' -> '5'
    | '5' | '6' -> '6'
    | '7' -> '8'
    | '8' | '9' -> '9'
    | _ -> failwith "move.R"
  | D ->
    match curBtn with
    | '1' -> '4'
    | '2' -> '5'
    | '3' -> '6'
    | '4' | '7' -> '7'
    | '5' | '8' -> '8'
    | '6' | '9' -> '9'
    | _ -> failwith "move.D"
  | U ->
    match curBtn with
    | '1' | '4' -> '1'
    | '2' | '5' -> '2'
    | '3' | '6' -> '3'
    | '7' -> '4'
    | '8' -> '5'
    | '9' -> '6'
    | _ -> failwith "move.U"

As you can see from the function above, hitting an edge keeps you in your current position.

The moveAll function takes a list of instructions (i.e. to calculate one digit of the final code) and just performs a Seq.fold to move according to the list. Finally, the last function I wrote, getCode, ran moveAll for each digit and concatenated the result using another Seq.fold.

The one thing I did do (because I thought that the Part 2 problem might need it) was to add an additional input parameter to moveAll and getCode which represented the starting position. For getCode, it represented the starting position for the first digit's instructions. For moveAll, it represented the starting point for that particular digit's instructions. For Part 1, this input was always 5 for both functions. It turned out later that that was a good idea :).

Referring back to my previous blog post, I had mentioned at the end that I really should have picked up file parsing. However, this did not happen for the Day 2 problem. In fact, the input was so long that I had to setup a StringWriter and use fprintf to write each successive set of instructions into it. Just craziness - I really should have learned my lesson earlier.

If you run the Day 1 code, you will get 97289, which is the correct answer for Day 2, Part 1.

Problem - Part 2

Part 2 added two major twists to the problem.

  1. The keypad layout changed.
  2. To calculate the next digit, you now had to start from the result of the previous calculation. The calculation of the first digit still started at 5 (which is no longer in the center, as shown below).
    1
  2 3 4
5 6 7 8 9
  A B C
    D

Solution - Part 2

To solve this problem, I created two new functions - move2 and getCode2.

I did not have to rewrite moveAll. Instead, I made the move function for moveAll a parameter, allowing me to pass in either move or move2 depending on the problem I was solving.

move2 essentially became a larger version of move. I won't post the whole thing here (please see GitHub for the full function), but here's just one branch of the match.

let move2 curBtn input =
  match input with
  | L ->
    match curBtn with
    | '1' -> '1'
    | '2' | '3' -> '2'
    | '4' -> '3'
    | '5' | '6' -> '5'
    | '7' -> '6'
    | '8' -> '7'
    | '9' -> '8'
    | 'A' | 'B' -> 'A'
    | 'C' -> 'B'
    | 'D' -> 'D'
    | _ -> failwith "move2.L"
  | R -> ...

The change to getCode2 was much simpler - I just had to ensure that I used the previous result to initiate the calculation of the next digit. I chose to continue with a fold, but added some more data by keeping track of the result in the accumulator.

(*
  Makes it so that the last character of the previous digit is used as the first character of the new digit.  The first digit gets a start value of '5'
*)
let getCode2 instr func stBtn =
  Regex.Matches (instr, @"[ULRD]+")
  |> Seq.cast
  |> Seq.map (fun (x : System.Text.RegularExpressions.Match) -> x.Value)
  |> Seq.fold
    (fun (ans, st) nxtInstr ->
      let nxtChar = moveAll func st nxtInstr in
      (ans + nxtChar.ToString(), nxtChar)
    )
    ("", stBtn)

If you run the code for Day 2, Part 2, you will get 9A7DC as the answer, which is correct.

Interesting Footnote About getCode2

I found out after I finished coding that I got the same result for Part 2 whether I used getCode or getCode2. These functions fundamentally differ in the starting position that they provide to moveAll. So, there was no way I could have known this beforehand. But, this is just an interesting tidbit that, given the 'right' input, even two disparate functions can result in the same answer.

Lessons Learned

From Day 2, I started recognizing a few small patterns about the Advent of Code problems.

  1. The inputs don't change between the two problems within a single day.
  2. As much as possible, parametrize your functions.
  3. Don't over-engineer the solution, especially for Part 1, because you may need to make changes after the fact to re-use the code for Part 2.
  4. Start writing tests. move and move2 were perfect candidates for unit testing.
    • When writing tests, ensure that the examples that AoC provides are encoded as unit tests of your solution. If the solution gives the correct answer for those examples, it will most likely work for the main problem.

See you next time!