### AOC 2016 - Day 3

# Table of Contents

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

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

- Filter the list of triangles by removing those which are not possible.
- 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:

- Read the file
- Parse the values
- 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:

- Read the file ==>
`File.ReadLines`

- Parse the file and turn the values into
`int`

s ==>`Seq.map`

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

- Parse file into
`int`

s - Transform input from 3 columns of
`int`

s into 1 longer column - Group values into
`seq`

s of 3 - 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.

- Parameterize everything, since there is almost no other way to really have re-use in these problems.
- Write more tests!!!
- 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.
- This is something I noted before, on the Day 2 blog post.
- Obviously, I didn't learn my lesson while solving the Day 3 problem.

See you next time!

## Comments

## Post a Comment