AOC 2016 - Day 3

Problem statement on Advent of Code website.

Code for this post can be found on GitHub.

Background

• On Day 1, we located Easter Bunny headquarters.
• On Day 2, we broke the code to use the bathroom in Easter Bunny HQ.

Problem - Part 1

On Day 3, we are walking through a design department and see a list values specifying various triangles. Our job is to be a good citizen and help the design department by identifying the triangles which are "possible".

Solution - Part 1

The algorithm which determines whether a triangle is "possible" is stated as follows:

In a valid triangle, the sum of any two sides must be larger than the remaining side.

I rephrased this for myself as follows:

In a valid triangle, the sum of the two smaller sides must be larger than the largest side.

The steps of the solution are as follows:

1. Parse each line of the input file into 3 integers
   • This is the first problem where I broke down and finally learned how to parse an input file.
   • The problem input was 1,902 lines.
   • I did not want to copy those lines into my source file.
2. Filter the list of triangles by removing those which are not possible.
3. Calculate the length of the list.

Some choices I made up-front:

• Based on experience with the previous two problems, I assumed that some part of the problem would change.
• My guess was that it would either be the input or the way we determine valid triangles.
• Thus, I parameterized the triangle algorithm.
• I thought that if the input changes (specifically, the input file), I would go back and parameterize that as well.

Save the input

For Step 1, I started by creating an input file.

Validate a triangle

I wrote a small function to determine whether a triangle is valid or not.

let possibleTriangle ptr =
ptr
|> Seq.sort
|> fun x -> (Seq.item 0 x) + (Seq.item 1 x) > (Seq.item 2 x)

Parse and filter the list of triangles

The largest part of the solution was to write a function to:

1. Read the file
2. Parse the values
3. Filter the list to remove invalid triangles

let possibleTrianglesCount triangleEvaluator =
File.ReadLines @"./puzzle_input"
|> Seq.map
  ((fun line -> Regex.Matches (line, @"[0-9]+"))
  >> Seq.cast
  >> Seq.map
    (fun (x : System.Text.RegularExpressions.Match) -> x.Value |> int)
  )
|> Seq.filter triangleEvaluator

I like the fact that the 3 steps needed to perform this part of the job are so obviously mapped to the source code:

1. Read the file ==> File.ReadLines
2. Parse the file and turn the values into ints ==> Seq.map
3. Filter the list ==> Seq.filter

Get the count of valid triangles

The last step was to connect possibleTriangle to possibleTrianglesCount.

let day3part1 =
possibleTrianglesCount possibleTriangle
|> Seq.length

I deliberately kept the summarization step separate from the filtering action on the off-chance that the problem for Part 2 would ask me to do something different with the list of valid triangles (oh, how wrong I was!).

This function, when executed on the input, gives a value of 982, which is the correct answer.

Problem - Part 2

Part 2 threw in a twist that I did not expect. It changed the way that the program has to interpret the input file:

• Even though the input file is organized in 3 columns of numbers, values in each row are unrelated to each other
• Instead, the data must be read in column-order.

For example, if this is the input file with just 9 numbers:

101 301 501
102 302 502
103 303 503

Then the three triangles are:

• 101, 102, 103
• 301, 302, 303
• 501, 502, 503

Solution - Part 2

My goal for the solution to Part 2 was to try and re-use as much code as possible. The first, obvious candidate for re-use was the possibleTriangle function. Unfortunately, I could not re-use the parsing code, since that code was embedded in the possibleTrianglesCount function.

Parse and filter the list of triangles

To parse and filter the list of triangles, I chose the following steps:

1. Parse file into ints
2. Transform input from 3 columns of ints into 1 longer column
3. Group values into seqs of 3
4. Filter the list

let possibleVerticalTrianglesCount triangleEvaluator =
(* Turn 3 columns of ints into 1 column *)
let colOfInts ints =
  ints
  |> Seq.map (Seq.item 0)
  |> Seq.append (ints |> Seq.map (Seq.item 1))
  |> Seq.append (ints |> Seq.map (Seq.item 2))
(* Read the data, serialize it, re-group it, then filter using evaluation function *)
File.ReadLines @"./puzzle_input"
|> Seq.map
  ((fun line -> Regex.Matches (line, @"[0-9]+"))
  >> Seq.cast
  >> Seq.map
    (fun (x : System.Text.RegularExpressions.Match) -> x.Value |> int)
  )
|> colOfInts
|> Seq.chunkBySize 3
|> Seq.filter triangleEvaluator

Thanks to F#'s OOTB functions in the Seq module, the only real change compared to the previous function was adding the part to change columns of 3 integers into a single column of integers.

Get the count of valid triangles

The last step was to invoke the new function.

let day3part2 =
possibleVerticalTrianglesCount possibleTriangle
|> Seq.length

This function produces a value of 1826, which is the correct answer.

Lessons Learned

From Day 3, I picked up a few more lessons learned.

1. Parameterize everything, since there is almost no other way to really have re-use in these problems.
2. Write more tests!!!
   1. Writing the code to turn a list of 3 columns into 1 took quite a bit of trial and error in F# interactive, and having automated tests, either with or without intermediate outputs, would have sped up the process greatly.
   2. This is something I noted before, on the Day 2 blog post.
   3. Obviously, I didn't learn my lesson while solving the Day 3 problem.

See you next time!