AOC 2016 - Day 6

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.
• On Day 3, we helped the EBs' design department by removing invalid triangles from the list.
• On Day 4, we figured out which rooms in the information kiosk are valid.
• On Day 5, we figured out how to get past security doors by calculating the code.

On Day 6, we will figure out how to communicate with Santa through the Easter Bunnies' jamming technology.

Problem - Part 1

For Part 1, we are given a list of garbled versions of a message that we sent to Santa. Per the protocol, we switched to a simple repetition code to get the message through.

Our goal is to figure out the original message.

Solution - Part 1

Compared to the rather more difficult problem on Day 5, the solution to Part 1 is relatively simple.

The problem states that we have to find the most frequent character in each column and, by stringing these characters together, we will derive the original message.

To solve this problem, I performed three explicit steps.

1. Calculate the length of the longest string from the list of garbled messages.
   • I did not want to assume that all strings are the same length.
2. Find the most frequent character for each position from the subset of strings that are long enough for that position.
3. Combine the characters to construct the final answer.

Calculate length of the longest garbled message

To calculate the length of the longest garbled message, I used a simple function to take the list, map each string message to its length, and then get the largest number.

let longestLength list =
list
|> Seq.map (String.length)
|> Seq.max

Find the most frequent character in a given position

To find the most frequent character in a given position, I performed the following steps.

1. Filter the list of strings and only retain those strings that are long enough to have a character in the desired position.
2. Count the number of occurrences of each character.
3. Sort the list so that the character with the highest number of occurrences is at the head of the list.
4. Return the character.

let mostFreqentCharAt pos list =
list
|> Seq.filter (fun line -> String.length line >= (pos + 1))
|> Seq.map (Seq.item pos)
|> Seq.countBy id
|> Seq.sortByDescending snd
|> Seq.head
|> fst

Collect the most frequent characters in each position

The final collection function is responsible for the following steps.

1. Read the garbled messages from a file.
2. Find the most frequent character in each position, based on the length of the longest message.
3. Concatenate the MFCs to get the original message.

let day6part1 filename =
let lines = File.ReadAllLines filename
seq {
  for i = 0 to (longestLength lines - 1) do
    yield (mostFreqentCharAt i lines |> string)
}
|> Seq.reduce (+)

If you run the above function, you will get tsreykjj, which is the correct answer.

Problem - Part 2

The problem statement for Part 2 only makes a slight change to the problem in Part 1. Instead of the most frequent character, we had agreed to use a modified repetition code when communicating with Santa and actually want the least frequent character in each position.

Unfortunately, I chose not to make the "frequency" function a parameter to the day6part1 function in the original implementation. Because of this, I had two options:

1. Go back and make the frequency function a parameter so that I can re-use the function.
2. Implement another version of the function using the new leastFreqentCharAt function.

I chose to go with option 2 for expediency sake. This is because I was experimenting with two other things for the Day 6 project.

1. Using a F# project and .fs files instead of .fsx files
2. Using the Expecto testing framework

Solution - Part 2

For the Part 2 solution, I kept the function that finds the longest string in the list of garbled messages. I had to reimplement two functions.

1. A function to find the least frequent character in a given position.
2. The collection function to derive the original message.

Find the least frequent character in a given position

This function is very similar to Part 1's implementation, except that my sort now puts items in ascending instead of descending order.

let leastFreqentCharAt pos list =
list
|> Seq.filter (fun line -> String.length line >= (pos + 1))
|> Seq.map (Seq.item pos)
|> Seq.countBy id
|> Seq.sortBy snd
|> Seq.head
|> fst

The F# library functions for collections truly make it easy to perform the types of transformations requested in this problem.

Collect the least-frequent characters in each position

This collection function is identical in all ways to the Part 1 solution except for the frequency function that it uses.

let day6part2 filename =
let lines = File.ReadAllLines filename
seq {
  for i = 0 to (longestLength lines - 1) do
    yield (leastFreqentCharAt i lines |> string)
}
|> Seq.reduce (+)

When you run this function, you get hnfbujie which is, in fact, the correct answer.

Considerations for Day 6

When it came to the Day 6 problem, I wanted to try some new things to continue the learning process with F#. To that end, I incorporated two new pieces into my solution.

1. Writing the code in .fs files as part of a "proper" project that compiles to an executable.
2. Writing tests using the Expecto testing library.

Using a F# project template

For the most part, using a F# project template and .fs files was seamless. I was already familiar with Paket from previous projects, so the only difference was that I had to invoke my build script when I wanted to test my code.

However, I ran into an extremely frustrating bug that almost caused me to give up on Ionide. For whatever reason, Ionide is unable to understand references to DLLs in FsProj files and, thus, is unable to provide any Intellisense support for downloaded NuGet packages. This problem was so frustrating that I actually downloaded, installed, and used Visual Studio 2017 Community Edition to finish off the Day 6 implementation (which is why the indentation scheme in the source files is different for Day 6 compared to all previous solutions).

Based on some searching and reading, I am not the only person having this problem (1, 2, 3, etc.). I can only hope that the authors are able to resolve the issue soon. Until this problem is fixed, I have stopped using F# projects and .fs files and have gone back to using F# scripts (.fsx files).

Using a testing framework

For Day 6, I did quite a bit of research to find a testing framework that I would be able to use with my solution. I specifically did this with the Day 6 problem because the solutions were relatively simple compared to previous Days.

Here is a list of the frameworks that I considered.

1. Expecto
2. Fuchu
3. xUnit.net
4. NUnit
5. FsCheck, without a framework

In the end, I chose to go with Expecto. This was a rather difficult transition for me because I bit off a little more than I could chew - I tried to use both Expecto and FsCheck for the Day 6 problem. In hindsight, this was a terrible idea for my first-time use of Expecto. Long story short, I was unable to get Expecto+FsCheck to work in a reasonable amount of time and settled for implementing the AOC-provided tests in Expecto. My frustration stemmed, in no small part, from a fundamental misunderstanding of FsCheck's purpose and capabilities.

Despite the large amount of frustration I felt while trying to get FsCheck to work, I was able to get basic testing working and even built a simple driver to either run tests (default) or calculate the Part 1 / Part 2 answer.

[<EntryPoint>]
let main argv =
match argv with
| [| first |] when first = "p1" ->
  let ans = Solution.day6part1 @"..\SixMain\SixMain\puzzle_input.txt"
  printfn "Day 6 Part 1: %A" ans
  0
| [| first |] when first = "p2" ->
  let ans = Solution.day6part2 @"..\SixMain\SixMain\puzzle_input.txt"
  printfn "Day 6 Part 2: %A" ans
  0
| _ -> Tests.runTestsInAssembly defaultConfig argv

My actual tests were also simple and encoded only the AOC-provided tests and results. Here is the Part 1 test.

[<Tests>]
let testsPart1 =
testList "part1"
  [ testCase "easter" <| fun _ ->
      let answer = "easter"
      let funcAns = Solution.day6part1 @"..\SixMain\SixMain\test_input1.txt"
      Expect.isTrue (answer = funcAns) @"test input answer should be 'easter'" ]

And here is the Part 2 test.

[<Tests>]
let testsPart2 =
testList "part2"
  [ testCase "advent" <| fun _ ->
      let answer = "advent"
      let funcAns = Solution.day6part2 @"..\SixMain\SixMain\test_input1.txt"
      Expect.isTrue (answer = funcAns) @"test input answer should be 'advent'" ]

Lessons learned

While not strictly F#-related, I learned a few lessons from this exercise.

1. When incorporating new frameworks, take it one step at a time. It's better to integrate one framework and become comfortable with it before trying to add the next one.
   • Trying to do Expecto+FsCheck while being unfamiliar with both frameworks (and, in FsCheck's case, being unfamiliar with its purpose and limitations) was simply an exercise in frustration.
2. When dealing with tooling issues, ask for help early and often.
   • When I first encountered the Intellisense issues in Ionide, I thought I had done something wrong (esp. since all GitHub issues I found at first were closed).
   • However, it turns out that people are still experiencing these issues.

See you next time!