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

• 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:

2. Parse the values
3. Filter the list to remove invalid triangles
``````let possibleTrianglesCount triangleEvaluator =
|> 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 `int`s ==> `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

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 `int`s
2. Transform input from 3 columns of `int`s into 1 longer column
3. Group values into `seq`s 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 *)
|> 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!