Advent of Code Day 7–Supernet Sequences
Today’s Advent of Code challenge was particularly well suited to regular expressions (and reminiscent of last year’s naughty and nice strings problem). We have a list of “ip addresses” and need to test them according to some rules.
The first task was to split them out into “supernet” and “hypernet” sequences, so the string
“abc[def]ghi” has two “supernet” sequences of
ghi and one hypernet sequence of
I did manage to come up with a regular expression that can find strings enclosed in square brackets, and by doing that I was able to use
Regex.Split to get them into an alternating sequence of supernet, hypernet, supernet etc. So I then needed to split out every odd and even into separate sequences. I think I made a bit heavy weather of this, so do let me know if there’s a more elegant way. But here’s what I came up with:
let filterByIndex predicate sequence = sequence |> Seq.indexed |> Seq.filter (fst >> predicate) |> Seq.map snd let parseIpAddress ipAddress = let parts = Regex.Split(ipAddress,@"\[(.*?)\]") let supernetSequences = parts |> filterByIndex (fun n -> n % 2= 0) |> Seq.toArray let hypernetSequences = parts |> filterByIndex (fun n -> n % 2= 1) |> Seq.toArray supernetSequences, hypernetSequences
Now we needed to test each ip address. Part of this was looking for an “abba” string – two letters next to each other, with two different letters on either side. I attempted to solve this with regular expressions.
“(\w)(\w)\2\1” is close but doesn’t stipulate that the inner characters are different to the outer ones. In the end I realised that it would make more sense to use
Seq.windowed, which turns a sequence like “abcdef” into “abc”, “bcd”, “def” and use a pattern matching function to test for an “abba”:
let containsAbba s = s |> Seq.windowed 4 |> Seq.exists (function | [|a;b;c;d|] -> a=d&&b=c&&a<>b | _ -> false)
Now we can solve the first part of the problem by checking if there is a supernet containing an “abba” but no hypernets do:
let supportsTls ipAddress = let super,hyper = parseIpAddress ipAddress let containsAbba s = s |> Seq.windowed 4 |> Seq.exists (function | [|a;b;c;d|] -> a=d&&b=c&&a<>b | _ -> false) (super |> Array.exists containsAbba) && not (hyper |> Array.exists containsAbba) input |> Seq.filter supportsTls |> Seq.length |> printfn "Part a: %d"
Part b had a similar problem, we looked for instances of “aba” (same character repeated separated by a different character) inside of the supernets which we again could use
Seq.windowed for. And then each “aba” gets turned into a “bab” by switching the inner and outer characters. Then we just need to find if the corresponding “bab” for one of the “aba”s can be found in the hypernets.
So my code for part b ended up like this:
let supportsSsl ipAddress = let super,hyper = parseIpAddress ipAddress let findAbas s = s |> Seq.windowed 3 |> Seq.filter (function | [|a;b;c|] -> a=c&&a<>b | _ -> false) |> Seq.map System.String let abas = super |> Seq.collect findAbas let makeBab (aba:string) = sprintf "%c%c%c" aba. aba. aba. let babExists bab = hyper |> Seq.exists (fun s -> s.Contains(bab)) super |> Seq.collect findAbas |> Seq.exists (makeBab >> babExists) input |> Seq.filter supportsSsl |> Seq.length |> printfn "Part b: %d"
Overall I feel that my solution for today could certainly be cleaned up a bit, but it does at least work, and I’m particularly proud that so far this year, I’ve entered the correct answer for each puzzle first time. I suspect its a combination of reading the question more carefully, using the example test cases, and using a functional programming language. I’ve still got nowhere near the leaderboard, but I can at least hide behind the excuse that the problems go live at 5am here, so the leaderboard is already full by the time I start the problems.