Day 7 - Advent of Code 2016

Mix.install([:kino, :benchee])

:ok

Links

• Advent of Code (AoC)
• AoC Puzzle Input
• tylerj GitHub - Livebook

Prompt

— Day 7: Internet Protocol Version 7 —

While snooping around the local network of EBHQ, you compile a list of IP addresses (they’re IPv7, of course; IPv6 is much too limited). You’d like to figure out which IPs support TLS (transport-layer snooping).

An IP supports TLS if it has an Autonomous Bridge Bypass Annotation, or ABBA. An ABBA is any four-character sequence which consists of a pair of two different characters followed by the reverse of that pair, such as xyyx or abba. However, the IP also must not have an ABBA within any hypernet sequences, which are contained by square brackets.

For example:

• abba[mnop]qrst supports TLS (abba outside square brackets).
• abcd[bddb]xyyx does not support TLS (bddb is within square brackets, even though xyyx is outside square brackets).
• aaaa[qwer]tyui does not support TLS (aaaa is invalid; the interior characters must be different).
• ioxxoj[asdfgh]zxcvbn supports TLS (oxxo is outside square brackets, even though it’s within a larger string).

How many IPs in your puzzle input support TLS?

To begin, get your puzzle input.

— Part Two —

You would also like to know which IPs support SSL (super-secret listening).

An IP supports SSL if it has an Area-Broadcast Accessor, or ABA, anywhere in the supernet sequences (outside any square bracketed sections), and a corresponding Byte Allocation Block, or BAB, anywhere in the hypernet sequences. An ABA is any three-character sequence which consists of the same character twice with a different character between them, such as xyx or aba. A corresponding BAB is the same characters but in reversed positions: yxy and bab, respectively.

For example:

• aba[bab]xyz supports SSL (aba outside square brackets with corresponding bab within square brackets).
• xyx[xyx]xyx does not support SSL (xyx, but no corresponding yxy).
• aaa[kek]eke supports SSL (eke in supernet with corresponding kek in hypernet; the aaa sequence is not related, because the interior character must be different).
• zazbz[bzb]cdb supports SSL (zaz has no corresponding aza, but zbz has a corresponding bzb, even though zaz and zbz overlap).

How many IPs in your puzzle input support SSL?

Although it hasn’t changed, you can still get your puzzle input.

Input

input = Kino.Input.textarea("Please paste your input file:")

input = input |> Kino.Input.read()

"rhamaeovmbheijj[hkwbkqzlcscwjkyjulk]ajsxfuemamuqcjccbc\ngdlrknrmexvaypu[crqappbbcaplkkzb]vhvkjyadjsryysvj[nbvypeadikilcwg]jwxlimrgakadpxu[dgoanojvdvwfabtt]yqsalmulblolkgsheo\ndqpthtgufgzjojuvzvm[eejdhpcqyiydwod]iingwezvcbtowwzc[uzlxaqenhgsebqskn]wcucfmnlarrvdceuxqc[dkwcsxeitcobaylhbvc]klxammurpqgmpsxsr\ngmmfbtpprishiujnpdi[wedykxqyntvrkfdzom]uidgvubnregvorgnhm\ntxxplravpgztjqcw[txgmmtlhmqpmmwp]bmhfgpmafxqwtrpr[inntmjmgqothdzfqgxq]cvtwvembpvdmcvk\ngkxjhpayoyrrpcr[mwyoahlkqyhtznyzrm]mvmurvsrgjunjjepn[mkoumuohilpcfgbmsmh]hpwggyvjkusjxcyojyr[wqxyuzbewpjzlyqmkhw]nniczueulxtdsmkniex\nvuzyoofrvaanszwndyt[mzcbhmabgnetrpje]tqnygwhmwrbyosbke[gehqzyhlnyufknqmueo]ngendggbjcvazwol\nvdnploylmxnipfudw[pbkxlaozhqhlbzz]kpxnzwjhybgcenyw[fpukiqrjraomftt]rosyxtsdltbsmhykxu[wrucjfwuyypmiic]ydnbgvicfnmwzuatudd\nlknaffpzamlkufgt[uvdgeatxkofgoyoi]ajtqcsfdarjrddrzo[bxrcozuxifgevmog]rlyfschtnrklzufjzm\nkajqeqlafxtmzirn[mkftybdukmghmyoclxd]plvjnikiozkikifpodt[cmufoktkndkhaeqbztz]drjixnnsdxqnrmn[cmzsnhlirtskunngcee]upgxlcjhmoethppx\njoibiixuzgtkjquor[xmnqotlqrhpvlglwaxe]kjmfrpihitjydwda\nkouyuiijgsmpzynmt[xvwuujrfkqjmtqdh]ukjscwcnwktrfvrmvew[quzbelbcfxknvqc]drtrmvnabjkslahadad\nhhlcltfpiwfjhguif[rpasuqltkbudhwjeew]mkcmvbxqukjczex\nxxqceycviwyzqxekn[tiidftrsnlgpesxlf]obtbqfgogpwkoqow[dabhpdntfvbhgtmupy]hbvtghnycgyywavqbtg\nzlqdqmuxebccmndzbl[ykefimjzdqdmfvlflj]ptlphteflzxmolkof\nbabzuaikmedruqsuuv[emlhynmvfhsigdryo]iyblsqlpplrlahtwr\nbyddropvzudnjciymyh[jcebyxyvikkshpn]ggmrxgkzsrfkfkzo\nektijwczwnlancuqfv[luqhtfgwmlilhwnk]gxgivxlnerdhbhetfz[bzczfdorrsptzikjmct]mfrsvxgxijtusmvjd[sbpnwycbrykuhsinudc]bmpikuskzlxcoidp\nigefoemugshofmibco[uhahihzaglmzdpzjvfp]tfbuuhoughgismec[inbtuzxnxekfkulodyk]fxykxfkfnjvswwc\nonmmhtsykubbpdiqvjm[kbfbiyjyuzmemaomkwa]prqwqocsihfnslooel[hysggeprqecalydywlk]taghiwhgnujsduhnffu[ibpvowghgttfsvt]wcajwcxhcriflxi\nevvhkvndeoxrrftqmih[ckxjgqvpdxjvmbwsor]odolgenlgaxujvqg[qyrnnrjgxskuxycoip]jvtjgwaaywdphxpy\nfffaewoawlzsmnqo[ubnpbqpxgenzjiytml]ztberlzwpzdvofcwo\nvhrwunprhbpclog[vqtnbjndcwpuyen]vzuudswovzmjviee\nyfeztpcfgazkijht[xqcjocbnjmvvrzg]maisokokpukpstgpj\nneudpatmnjayamydbrd[heckokdparzefxm]qulfvfivofznkyvkwq[owjrktbaejpffqef]oserqezusmubsertq\nykgyzyqlodjvgqzmzy[ewsxadkknhduejft]yysinlpnxpaqdai[hqagzwigkpvzsje]auibbpljfmkoxaskuh\nkntmgvoypnpibjtp[ispxkdofjsdufpivwrj]ndecwlfcbjtrnrzw\npvjsstffnygbjafe[ztrjbalsthujslnitl]xjsoqghvrjncejwww[khwjgywxyglvhgz]kaxctpvhleqfmlm\novbgzhzmenxocuvdhwk[mzfbtwpwnttyeykuwzo]qrmyqzvxetjbrhossb[tjvdprzdgjgdvjygpnp]bgkkrcsrmfrsrtahxus[owipixzcqisqapz]fsbkjqgxuimcbur\nmbweohfcgybqcqnl[yafsvfrduertfqze]hqaodhzkmhzmlrxuc[bytcgnvzvoovirqwn]njivpwgkkqvgowpenh[erodavzscuubhea]gizvzrqjzhkikhb\nazrzthfimarcdbk[usfjkmhedaqpfnisek]yqowqlqvlranjjvbauq[korlrbzcgrneashdrrq]fjicirnofvlrlnnkeqb[ktlfmzrqxcntvasev]urpuwoiogtcwskygxz\nhtuzgcmjixiaofnm[mbmrnxkedkrjqwff]srvmeadhvwftjmx[vqkaxjmugwdmwcqlg]qxzxczyoqnkcaoqmsd\nqywanrnotepsgufhr[hsmvibiybrxwabambm]tdwinkqnjvirhgx\ncfurhuhjrbxqoefybl[kdcazzlfacaurqguqkz]yufsmycojcxiiomwteo[zcnzchsersrsapze]bhkpjaybdyilwdomfr[ddbxqanevcpjuodnj]ttmxojmazfqzqxlz\nxfpeuaftjtjzzyrlw[vxklxjatlbpevalmb]klpxbsifaszxapsosjq[kjzdnfadnybfnfvm]kodbuiigbiqdbarr[vkgxvvccoyknqcg]yusyefeqfqjkcmnrfd\nwelumvdtzozzqkc[xunvcqdbwitokoerg]euvhbecekwaszsmxu[xrffdzabspotehwg]uqzwhrvygasatdaphac[xexwfcsgfyvciqdu]kioaakhmpgudcsrgnqh\nbvirojodecjwgsfr[xezdftvafflhsabc]dlsuqqzkekwsmgyz\nxxnrooghjqtrtkmhr[xhjrmkybtnsrdkp]krhveuyzhsnfrkxq\nfzgdyuackwckqwg[jcdyvdcmrqxizkqxhke]gkfhkoqwqvkfxgj[wfxghxhkbhxhfnscjy]tdpidwqwryxlubtg[ptldartinsqinuymsc]tglyhrzvexdqkkxrer\nqjmlxlnqzipdflotzl[mwewadvcvkoqjlvlruk]aciqxygnygyordpcvc[sirhqhrjopudmfub]kxexybjqhmqmukxmpug[bbvccqpfdebfmnvald]lgqcpzwrjzlhdcalvxh\ngytjulsxixxkwhtwts[bmwcdokbhvwmzvpths]amvwsotxkvsjszzk[rnbbbelvqlqxdckpgf]mfoelmolxsbibcyss[rhqarjczvrulkfd]smrmbwtejyrtbuxw\nyzlhtplfmpcelnlnfgo[czpwiwgzcuyingho]biwyfjhjxyaougycvdk\nnyqhnhedzzlbyucj[ahtgwmsprvxrhzkb]jutcnlfuavbirrvbe[oybwrlquyqzhlekfj]ngfnydtkqpdyusyk[ojxstfhzjmohguhnq]tupjbscsqbvxtrgah\npktcuxqmiitdhfgja[urxogoqmprdhdod]rynibylhjlnummesvrt\nyetjrczvtanwejhw[fzqzeqjxwqqvpuc]nxjwkjqetsqmfxvjyg[fvyucxjhkszsvzhg]pashbrmyrjwpsii\nwrc" <> ...

Solution

defmodule Day07 do
  defdelegate parse(input), to: __MODULE__.Input

  def part1(input) do
    input
    |> parse()
    |> Enum.reject(fn {_, hypernets} ->
      Enum.any?(hypernets, &abba_match?/1)
    end)
    |> Enum.filter(fn {supernets, _} ->
      Enum.any?(supernets, &abba_match?/1)
    end)
    |> Enum.count()
  end

  def part2(input) do
    input
    |> parse()
    |> Enum.count(fn {supernets, hypernets} ->
      super_abas = get_abas(supernets)
      hyper_abas = get_abas(hypernets)
      Enum.any?(super_abas, fn <> -> <> in hyper_abas end)
    end)
  end

  defp abba_match?(s) do
    Regex.match?(~r/([a-z])(?!\1)([a-z])\2\1/, s)
  end

  def get_abas(list) when is_list(list) do
    Enum.flat_map(list, &amp;get_abas/1) |> Enum.uniq()
  end

  def get_abas(s) when is_binary(s) do
    ~r/(?=(?([a-z])(?!\2)[a-z]\2))/
    |> Regex.scan(s, capture: :all_names)
    |> List.flatten()
  end

  defmodule Input do
    def parse(input) when is_binary(input) do
      input
      |> String.split("\n")
      |> parse()
    end

    def parse(input) when is_list(input) do
      Enum.map(input, &amp;parse_line/1)
    end

    def parse_line(line) do
      line
      |> String.split(["[", "]"])
      |> Enum.with_index()
      |> Enum.split_with(fn {_, i} -> rem(i, 2) == 0 end)
      |> then(fn {a, b} ->
        {Enum.unzip(a) |> elem(0), Enum.unzip(b) |> elem(0)}
      end)
    end
  end
end

{:module, Day07, <<70, 79, 82, 49, 0, 0, 16, ...>>,
 {:module, Day07.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}

How many IPs in your puzzle input support TLS?

Your puzzle answer was 110.

Day07.part1(input)

110

How many IPs in your puzzle input support SSL?

Your puzzle answer was 242.

Day07.part2(input)

242

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, you should return to your Advent calendar and try another puzzle.

If you still want to see it, you can get your puzzle input.

Benchmarking

# https://github.com/bencheeorg/benchee

Benchee.run(%{
  "Part 1" => fn -> Day07.part1(input) end,
  "Part 2" => fn -> Day07.part2(input) end
})

nil

Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 8 GB
Elixir 1.14.2
Erlang 25.1.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s

Benchmarking Part 1 ...
Benchmarking Part 2 ...

Name             ips        average  deviation         median         99th %
Part 1         57.46       17.40 ms     ±1.92%       17.33 ms       18.90 ms
Part 2         29.78       33.58 ms     ±0.84%       33.57 ms       34.79 ms

Comparison: 
Part 1         57.46
Part 2         29.78 - 1.93x slower +16.17 ms

nil