AOC 2016 - Day 4

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 will figure out which rooms on an encrypted information kiosk are valid and which ones are not.

Problem - Part 1

The kiosk lists one room per line. Each room entry consists of 3 parts.

1. Encrypted name comprised of lowercase letters separated by dashes
   • Always follows by a dash
2. Sector ID
3. Checksum
   • Always in square brackets

For Part 1, we have to determine which entries are real by calculating a checksum based on the encrypted name. The actual answer we have to provide is the sum of the sector IDs for all valid rooms.

Before I dive into the solution, I want to note that this problem has a lot of moving parts and, even though I've already solved it, it took me over half an hour to understand it again. There's just something about it that confuses the heck out of me every time.

Solution - Part 1

I approached the solution from a few different angles before I settled on the following solution.

I started by first trying to understand the overall steps involved in the solution. Then, once I had a basic picture worked out, I focused on creating a data structure that could hold all the data that I needed.

I knew I wanted a single 'flow' to the logic and to do that, I would have to pull together separate pieces of data and then start tying them together. With the right data structure, I could basically thread it through all my functions and tie them together nicely at the end.

My overall solution strategy is as follows.

1. Store each unchanged line of data.
2. Extract the sector ID and checksum.
   • Based on the requested answer, we can assume that all sector IDs are numeric values.
3. Calculate the checksums for each encrypted room name.
4. Finally, filter the list and add up the valid rooms' sector IDs.

The one thing that I noticed above all else is that I had to go out and learn a lot more about regular expressions in general and .NET regular expressions specifically to solve this problem.

Create the data structure

My whole solution hinges on a data structure that can hold all the data I need a series of disparate functions that only come together at the end.

type Line = {
line: string
sectorID: int
calculatedChecksum: string
providedChecksum: string
}

let emptyLine = {
line = ""; sectorID = 0; calculatedChecksum = ""; providedChecksum = "";
decryptedText = ""
}

As you can tell, I chose to go with a record for this solution. emptyLine is simply an empty Line for convenience in various functions.

line

Holds the unaltered line from the input file.

sectorID

The provided sector ID extracted from the raw line.

calculatedChecksum

The calculated checksum based on the encrypted room name.

providedChecksum

The provided checksum extracted from the raw line.

Store each unchanged line of data

I chose to make this its own step because of the lesson I learned from my last solution, where the parsing strategy was different between Parts 1 and 2.

The code to extract each line from the input file is quite simple.

let lines filename =
File.ReadAllLines filename
|> Seq.cast
|> Seq.map (fun x -> {emptyLine with line = string x})

Extract the provided sector ID and checksum

Extracting the sector ID proved to be quite an issue until I read the problem over a few more times. Once I understood that the sector ID is numeric only (since we have to add them up) and the encrypted name (and thus the checksum) is composed of lower-case letters only, the regular expression was relatively simple.

let extractSectorIDs lines =
lines
|> Seq.map
  (fun l ->
  {l with
    sectorID = (Regex.Match (l.line, @"[0-9]+")).Groups.[0].Value |> int})

Extracting the checksum was easier because the problem states that the checksum is enclosed by square brackets [].

let extractProvidedChecksums lines =
lines
|> Seq.map
  (fun l ->
    {l with
      providedChecksum =
      (Regex.Match (l.line, @"\[([a-zA-Z]+)\]")).Groups.[1].Value})

The hardest thing was knowing which Group I wanted from each regular expression. This required a decent amount of trial and error in online .NET regex tools and F# interactive.

Calculate the checksum

I started by:

1. Extracting the encrypted room name from each line
2. Removing the dashes
3. Concatenating all parts of the encrypted name (if more than 1)

let calculateChecksums lines =
lines
|> Seq.map
  (fun l ->
    {l with
      calculatedChecksum =
      (Regex.Matches (l.line, @"([a-zA-Z]+)\-"))
      |> Seq.cast
      |> Seq.map
        (fun (x : System.Text.RegularExpressions.Match) ->
          let substr = x.Value
          substr.Substring(0, String.length substr - 1))
      |> String.concat ""
      |> calculateChecksum
    }
  )

Once the encrypted name was cleaned up and transformed, I passed it over to a separate function to calculate the checksum.

let calculateChecksum (line: string) =
line
|> Seq.countBy id
|> Seq.sortBy fst
|> Seq.sortByDescending snd
|> Seq.truncate 5
|> Seq.fold (fun accum (elt, _) -> accum + elt.ToString()) ""

This function relies heavily on the assertion in the .NET documentation that Seq.sort and its variants are stable sorts.

Tie it all together

The last step is to tie all the steps together by threading a seq<Line> through the logic.

let day4part1 =
lines puzzleInput
|> extractSectorIDs
|> extractProvidedChecksums
|> calculateChecksums
|> Seq.filter (fun x -> x.providedChecksum = x.calculatedChecksum)
|> Seq.fold (fun accum elt -> accum + elt.sectorID) 0

All the heavy lifting has already been done by the time we get to Seq.filter. I chose to go with Seq.fold instead of Seq.reduce because the latter can fail with an ArgumentException when the sequence is empty.

When you run this function on the input file, you get 158835, which is, in fact, the correct answer.

Problem - Part 2

For Part 2, we have to decrypt the encrypted room name using a shift cipher.

The question we have to answer is "what is the sector ID of the room where North Pole objects are stored?"

Solution - Part 2

The changes were minimal for Part 2.

1. Add a field to the Line record to hold the decrypted text.
2. Write a shift cipher.
3. Tie it all together.

Modify the data structure

I added the last field to the record - decryptedText.

type Line = {
line: string
sectorID: int
calculatedChecksum: string
providedChecksum: string
decryptedText: string
}

decryptedText

The decrypted room name. Needed to understand where the North Pole objects are being stored.

Write the shift cipher algorithm

A shift cipher, or Caesar cipher, is a relatively simple substitution cipher. Julius Caesar is widely credited as being its inventor. The key to the Caesar cipher is knowing two things:

1. The space through which we have to shift (e.g. only lowercase letters, upper and lowercase letters, the entire ASCII table, etc.)
2. The number of places to shift within the space.

So, I made some assumptions to guide the development of this algorithm.

1. I restricted the space to lowercase letters only. The single example provided by the problem bears out this assumption.
2. The shift count is the sector ID.
3. The algorithm should not shift dashes, but just convert them directly to spaces.

let shiftCipher (letter: char) shift =
let asciiStart = 97
let numChars = 26
let charToInt x = (int x) - asciiStart
let intToChar x = char (x + asciiStart)
if letter = '-' then ' '
else letter |> charToInt |> (+) shift |> (fun x -> x % numChars) |> intToChar

Tie it all together

The function that tied together the solution for Part 2 went through a few iterations and makes at least one large assumption.

1. The initial part of the algorithm is similar to Part 1, since our starting point is the list of valid rooms.
2. Then, I calculated the decrypted name for each room.
3. Finally, I settled on a big assumption that the room storing the "North Pole objects" would start with the word "north".
   • This assumption turned out to be correct, obviously.
   • I also tried other variations, such as 'north' in the text, 'North' in the text, 'North Pole' in the text, etc.
   • This actually affected my shift cipher algorithm, since capital letters change the shift space.

let day4part2 =
lines puzzleInput
|> extractSectorIDs
|> extractProvidedChecksums
|> calculateChecksums
|> Seq.filter (fun x -> x.calculatedChecksum = x.providedChecksum)
|> Seq.map
  (fun l ->
  {l with
    decryptedText =
    (Regex.Match (l.line, @"([a-zA-Z]+\-)+")).Groups.[0].Value
    |> Seq.map (fun elt -> shiftCipher elt l.sectorID)
    |> System.String.Concat
  })
|> Seq.filter (fun l -> l.decryptedText.StartsWith("north"))

When you calculate day4part2, you get sector ID 993, which is the correct answer.

Testing

This is the first AOC problem where I introduced testing, something that was long overdue. I did not use any framework, but created a separate script file that contained basic unit tests. These tests printed their results to the console and were quite crude (I calculated the results manually and then turned those results into unit tests).

Despite how simple the tests were, they cut down the trial and error time considerably. I especially felt the impact on this problem where I kept hitting roadblocks every step of the way.

Lessons Learned

I learned a few lessons from this exercise.

1. Creating separate functions for different pieces of the solution was a good idea and allowed for a lot of reusability.
   • I will definitely be continuing this trend in the future.
2. The semi-automated testing, as crude as it was, helped immensely.
   • This is even easier for AOC since we have specific examples given with each Part of each problem.
   • I definitely need to put even more effort into testing in the future.

See you next time!