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)
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
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)
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