Day 14

Setup

sample = """
NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C
"""

input = """
HBHVVNPCNFPSVKBPPCBH

HV -> B
KS -> F
NH -> P
OP -> K
OV -> C
HN -> O
FF -> K
CP -> O
NV -> F
VB -> C
KC -> F
CS -> H
VC -> F
HF -> V
NK -> H
CF -> O
HH -> P
FP -> O
OH -> K
NN -> C
VK -> V
FB -> F
VP -> N
FC -> P
SV -> F
NO -> C
VN -> S
CH -> N
FN -> N
FV -> P
CN -> H
PS -> S
VF -> K
BN -> S
FK -> C
BB -> H
VO -> P
KN -> N
ON -> C
BO -> S
VS -> O
PK -> C
SK -> P
KF -> K
CK -> O
PB -> H
PF -> O
KB -> V
CC -> K
OK -> B
CV -> P
PO -> O
SH -> O
NP -> F
CO -> F
SS -> P
FO -> K
NS -> O
PN -> H
PV -> V
KP -> C
BK -> B
BP -> F
NB -> C
OF -> O
OC -> O
HO -> C
SC -> K
HC -> C
HS -> B
KH -> N
FS -> N
PH -> O
PC -> V
BS -> O
KO -> F
SP -> K
OB -> O
SF -> K
KV -> F
NC -> B
SO -> C
CB -> S
VH -> V
FH -> F
SN -> V
SB -> P
PP -> B
BF -> K
HB -> O
OO -> V
HP -> H
KK -> O
BV -> K
BH -> B
HK -> H
BC -> C
VV -> S
OS -> F
NF -> B
"""

Part A

defmodule Day14 do
  def polymerize_n_times(sequence, instructions, n) do
    polymerize_n_times(sequence, instructions, n, Time.utc_now())
  end

  def polymerize_n_times(sequence, _instructions, 0, _timer), do: sequence

  def polymerize_n_times(sequence, instructions, n, timer) do
    IO.puts(
      "#{n} passes remaining. Last pass took #{Time.diff(Time.utc_now(), timer, :microsecond)} ms."
    )

    polymerize_n_times(
      polymerize_v2(sequence, instructions),
      instructions,
      n - 1,
      Time.utc_now()
    )
  end

  # Hopefully smarter implementation that keeps the stack only as big as the string itself
  def polymerize_v2(sequence, instructions) do
    polimerize_single_pair(sequence, instructions, "")
  end

  def polimerize_single_pair(
        <>,
        _instructions,
        processed_sequence
      ) do
    processed_sequence <> <>
  end

  def polimerize_single_pair(
        <>,
        instructions,
        processed_sequence
      ) do
    insertion = Map.get(instructions, pair, "")
    <> = pair

    polimerize_single_pair(
      right <> rest,
      instructions,
      processed_sequence <> <> <> insertion
    )
  end

  # Naive implementation that requires a huge stack
  def polymerize_v1(sequence, instructions) do
    sequence
    |> String.graphemes()
    |> Enum.chunk_every(2, 1)
    |> Enum.map(&amp;Enum.join/1)
    |> Enum.map(fn
      <<a>> ->
        <<a>> <> <<a>>

      <> = pair ->
        if Map.has_key?(instructions, pair) do
          <<a>> <> Map.fetch!(instructions, pair) <> rest
        else
          pair
        end
    end)
    |> Enum.map(fn string -> String.slice(string, 0..-2) end)
    |> Enum.join()
  end
end

[start | instructions] =
  sample
  |> String.split("\n\n", trim: true)

instructions =
  instructions
  |> Enum.at(0)
  |> String.split(["\n", " -> "], trim: true)
  |> Enum.chunk_every(2)
  |> Enum.reduce(%{}, fn [pair | insertion], acc -> Map.put(acc, pair, Enum.at(insertion, 0)) end)

start
|> Day14.polymerize_n_times(instructions, 18)
|> String.graphemes()
|> Enum.frequencies()
|> Map.values()
|> then(fn freqs -> Enum.max(freqs) - Enum.min(freqs) end)