AOC 2016 - Day 7

Problem statement on the 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 EBHQ's 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 figured out how to communicate with Santa through the Easter Bunnies' jamming technology.

On Day 7, we will figure out which of the EBHQ's computers use encryption on the network.

Problem - Part 1

For Part 1, we need to find the IP addresses (aka computers) that support the TLS (transport-layer snooping) protocol.

We determine this by parsing the IP address and checking for certain patterns.

Solution - Part 1

When I read the problem description, Day 7 sounded very similar, at least in form, to the Day 4 problem.

The problem has multiple parts:

Extract supernet and hypernet sequences from an IP address.
Check for an ABBA pattern.
Check an entire IP address.
Connect the pieces.

Extract supernet and hypernet sequences from an IP address

The first part of the problem is understanding the format of the IP address. IP addresses are strings of characters alternating between being outside and inside square brackets. Here are some examples of IP addresses:

abba[mnop]qrst
abcd[bddb]xyyx[bddb]xyyx
ioxxoj[asdfgh]zxcvbn

This solution, just like the Day 4 solution, stretched and expanded my regular expression skills. I would like to thank Will Boyd for the Regex Storm Regex Tester. This site made it much faster and easier to quickly test a regular expression (and its expected results) against a corpus of test data.

After a number of attempts, I ended up with two sets of regular expressions.

For supernet strings (whose proper name I did not know until Part 2), I used the following strategy:

Remove all text between square brackets [].
Break the resulting compound string into a list of strings.

  let outerStrings =
  Regex.Replace (str, @"\[\w+\]", " ")
  |> fun s -> s.Split ([|' '|])

For hypernet strings, I used the following strategy:

Extract all text that is between square brackets [].
Remove the brackets.

  let hypernetStrings =
  Regex.Matches (str, @"\[\w+\]")
  |> Seq.cast
  |> Seq.map (fun (m:Match) -> Regex.Match(m.Value, @"\w+"))
  |> Seq.cast<Match>
  |> Seq.map (fun x -> x.Value)

Check for an ABBA pattern

An ABBA (Autonomous Bridge Bypass Annotation) pattern is a palindrome of exactly 4 characters within a string of length 4 or more.

let isABBA (str:string) =
str
|> Seq.windowed 4
|> Seq.exists (fun s -> s.[0] = s.[3] && s.[1] = s.[2] && s.[0] <> s.[1])

Check an entire IP address

For Part 1, we have two primary requirements.

The supernet sequences must contain at least one ABBA.
The hypernet sequences must not contain any ABBAs.

The check for this is a one-liner.

  (Seq.exists isABBA outerStrings) && (Seq.exists isABBA hypernetStrings |> not)

Connect the pieces

The final function that puts it all together is responsible for the following.

Read the list of IP addresses.
Find the addresses that support TLS.

let day7part1 filename =
File.ReadAllLines filename
|> Seq.filter supportsTLS
|> Seq.length

When you run this function, you get 105, which is the correct number of IP addresses that support TLS.

Problem - Part 2

In Part 2, we have to determine which IP addresses support the SSL (super-secret listening) protocol.

The problem for Part 2 keeps the concept of supernet and hypernet sequences, but it changes the checks we need to perform on them. Instead of checking for ABBAs, we have to now check for ABAs and their dependent BABs.

Solution - Part 2

Part 2 introduces two new types of patterns in IP addresses:

ABA
- Area-Broadcast Accessor
- Follows the pattern of 'First char', 'Second char', 'First char'
- E.g. aba, xyx, pup
BAB
- Byte Allocation Block
- Contains the same characters as an ABA, but is reversed positions.
- E.g. bab, yxy, upu

The requirements are as follows.

There must be at least one ABA in the supernet sequences.
There must be at least one BAB in the hypernet sequences.

My strategy for the Part 2 solution has slightly different steps.

Extract supernet and hypernet sequences from an IP address.
Check if a supernet sequence has at least one ABA.
Check if a hypernet sequence has at least one BAB.
Check a single IP address.
Connect the pieces.

Extract supernet and hypernet sequences from an IP address

Extracting the supernet and hypernet sequences from an IP address follows exactly the same logic as the Part 1 problem. I extracted this code into two new functions and refactored the Part 1 code to use these new functions.

/// Extract supernet sequences from an IP address.
let supernetSeq ip =
Regex.Replace (ip, @"\[\w+\]", " ")
|> fun s -> s.Split ([|' '|])

/// Extract hypernet sequences from an IP address.
let hypernetSeq ip =
Regex.Matches (ip, @"\[\w+\]")
|> Seq.cast<Match>
|> Seq.map (fun m -> Regex.Match(m.Value, @"\w+"))
|> Seq.cast<Match>
|> Seq.map (fun x -> x.Value)

Check if a supernet sequence has at least one ABA

The function hasABA takes a string of any length and tries to find at least one 3-character substring which matches the ABA pattern, which is:

The first and third character must be the same.
The first and second character must be different.

let hasABA (str:string) =
str
|> Seq.windowed 3
|> Seq.exists (fun x -> x.[0] = x.[2] && x.[0] <> x.[1])

Check if a hypernet sequence has at least one BAB

To check if a hypernet sequence contains a BAB, I decided to use the Set collection. My overall strategy is as follows.

Get all ABAs from the supernet sequences.
Flip the ABAs (i.e. turn them into BABs).
Get all the BABs from the hypernet sequences.
Check if the Sets intersect.

First (and third), here is the code to get ABAs (or BABs) from IP addresses.

let getABAs (str:string) =
str
|> Seq.windowed 3
|> Seq.map (System.String)
|> Seq.filter hasABA

Second, here is the code to flip an ABA.

let flipABA (str:string) = sprintf "%c%c%c" str.[1] str.[0] str.[1]

Finally, I connected these pieces in the hasBAB function.

let hasBAB abas hnStr =
let babs =
  hnStr
  |> getABAs
  |> Set.ofSeq
abas
|> Set.ofSeq
|> Set.map flipABA
|> Set.intersect babs
|> (Set.isEmpty >> not)

Check a single IP address

The function supportsSSL is responsible for ensuring that the supernet sequences contains at least one ABA and that the hypernet sequences contain at least one BAB.

let supportsSSL line =
let abas =
  supernetSeq line
  |> Seq.collect getABAs
(supernetSeq line |> Seq.exists hasABA)
&& (hypernetSeq line |> Seq.exists (hasBAB abas))

Connect the pieces

The last function, day7part2, is responsible for linking the input file to supportsSSL and for calculating the final answer (i.e. the number of IP addresses that support SSL).

let day7part2 filename =
File.ReadAllLines filename
|> Seq.filter supportsSSL
|> Seq.length

Lessons learned

Thanks to Day 7 being a relatively simple problem, my goal here was to expand my knowledge of testing.

"If at first you don't succeed, try, try again." I once again worked on making Expecto and FsCheck work together.
- As with Day 6, I did not end up using FsCheck - however, this was mainly because I could not get a good generator written for IP addresses.
- In the end, I used the provided tests to ensure that my code is working correctly.
- Since the time that I finished Day 7, I actually rewrote the solution to Day 2 using a variety of graph data structures (and corresponding algorithms) and used FsCheck extensively there and with the updated MD5 testing I did. I feel a little more comfortable with FsCheck now, though I am still not completely clear on how to generate restricted data (e.g. positive ints) other than through rather rudimentary methods.

My goal with Day 8 (and beyond) is to start using new platforms (specifically, Fable, Elmish, Suave, etc.). I'm extremely excited to be doing this.

See you next time!