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!