aoc2021_day14.livemd

AoC Day 14 - Extended Polymerization

Section

Mix.install([:kino])

input = Kino.Input.textarea("Please input data:")

[polymer | instructions] =
  input
  |> Kino.Input.read()
  |> String.split(["\n\n", "\n"], trim: true)

polymer = String.to_charlist(polymer)

instructions =
  Enum.map(instructions, &String.split(&1, " -> "))
  |> Map.new(fn [a, b] -> {String.to_charlist(a), String.to_charlist(b)} end)

Part 1

defmodule Polymerization.Naive do
  defp merge([[a, b, c] | t], []), do: merge(t, [[a, b, c]])

  defp merge([[c, d, e] | t], [[a, b, c] | rest]) do
    merge(t, [[c, d, e] | [[a, b] | rest]])
  end

  defp merge([], acc), do: Enum.reverse(acc)

  defp next(polymer, instructions) do
    chunks =
      polymer
      |> Enum.chunk_every(2, 1, :discard)

    Enum.map(chunks, fn [s, e] = chunk ->
      middle = instructions[chunk]
      [s, middle, e]
    end)
    |> merge([])
    |> List.flatten()
  end

  def build(polymer, instructions, steps) do
    Enum.reduce(1..steps, polymer, fn _step, polymer ->
      next(polymer, instructions)
    end)
  end
end

freqs =
  Polymerization.Naive.build(polymer, instructions, 10)
  |> Enum.frequencies()

{{_, min}, {_, max}} = Enum.min_max_by(freqs, fn {_k, v} -> v end)
max - min

Part 2

defmodule Polymerization.Fast do
  defp next(chunks, instructions) do
    Enum.reduce(chunks, %{}, fn
      {[i1, i2] = pair, count}, acc ->
        case instructions do
          %{^pair => [char_code]} ->
            acc
            |> Map.update([i1, char_code], count, &(&1 + count))
            |> Map.update([char_code, i2], count, &(&1 + count))

          %{} ->
            Map.put(acc, pair, count)
        end
    end)
  end

  def build(polymer, instructions, steps) do
    # here we track the elements
    chunks =
      polymer
      |> Enum.chunk_every(2, 1, [0])
      |> Enum.frequencies()

    Enum.reduce(1..steps, chunks, fn _step, acc ->
      # in every step we apply all instructions
      next(acc, instructions)
    end)
  end
end

{{_, min}, {_, max}} =
  Polymerization.Fast.build(polymer, instructions, 40)
  |> Enum.group_by(&hd(elem(&1, 0)), &elem(&1, 1))
  |> Enum.min_max_by(fn {_, cnt} -> Enum.sum(cnt) end)

Enum.sum(max) - Enum.sum(min)

Part 2 - first try with extra count map

When doing this exercise for the first time, I did not realize that we can count the elements by grouping by the first character in a pair.

Therefore I counted the inserted elements instead.

defmodule Polymerization.Fast2 do
  defp update_chain(chunks, start_chunks, pair = [a, b], v) do
    count = Map.get(start_chunks, pair)

    chunks
    |> Map.update(pair, 0, &(&1 - count))
    |> Map.filter(fn {_k, v} -> v > 0 end)
    |> Map.update(
      [a, v],
      count,
      &(&1 + count)
    )
    |> Map.update(
      [v, b],
      count,
      &(&1 + count)
    )
  end

  defp next({chunks, countmap}, instructions) do
    # we pass a separate copy of the chunks
    # as "inserted elements are not considered to be part of
    #     a pair until the next step"
    {_, chunks, countmap} =
      Enum.reduce(instructions, {chunks, chunks, countmap}, fn
        {pair, [char_code]}, {start_chunks, end_chunks, countmap} = acc ->
          if cnt = start_chunks[pair] do
            {
              start_chunks,
              update_chain(end_chunks, start_chunks, pair, char_code),
              Map.update(countmap, char_code, 1, &(&1 + cnt))
            }
          else
            # no pair, no do
            acc
          end
      end)

    {chunks, countmap}
  end

  def build(polymer, instructions, steps) do
    # here we count the occurrences of the elements
    countmap = Enum.frequencies(polymer)

    # here we track the elements
    chunks =
      polymer
      |> Enum.chunk_every(2, 1, :discard)
      |> Enum.frequencies()

    Enum.reduce(1..steps, {chunks, countmap}, fn _step, acc ->
      # in every step we apply all instructions
      next(acc, instructions)
    end)
  end
end

{acc, countmap} = Polymerization.Fast2.build(polymer, instructions, 40)

{{_, min}, {_, max}} = Enum.min_max_by(countmap, fn {_k, v} -> v end)
max - min