A slow (1 sec) solution before optimization using only a lists of {value, count} for each type of stone.
defmodule AdventOfCode.Solutions.Y24.Day11 do
alias AoC.Input
def parse(input, _part) do
input
|> Input.read!()
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
def part_one(problem) do
solve(problem, 25)
end
def part_two(problem) do
solve(problem, 75)
end
defp solve(problem, cycles) do
stones = Enum.map(problem, &{&1, 1})
stones = merge(stones)
stones =
Enum.reduce(1..cycles, stones, fn _, stones ->
stones
|> blink_all()
|> merge()
end)
Enum.reduce(stones, 0, fn {_, c}, acc -> acc + c end)
end
defp blink_all(stones) do
Enum.flat_map(stones, &blink/1)
end
defp blink({0, count}), do: [{1, count}]
defp blink({figure, count}) do
digits = Integer.digits(figure)
len = length(digits)
if rem(len, 2) == 0 do
{left, right} = Enum.split(digits, div(len, 2))
[{Integer.undigits(left), count}, {Integer.undigits(right), count}]
else
[{figure * 2024, count}]
end
end
defp merge(new_stones) do
merge([], new_stones)
end
defp merge(old_stones, new_stones) do
Enum.reduce(new_stones, old_stones, fn new, olds -> insert(olds, new) end)
end
defp insert([], kv), do: [kv]
defp insert([{k, v1} | rest], {k, v2}), do: [{k, v1 + v2} | rest]
defp insert([{k1, v1} | rest], {k2, v2}) when k1 < k2, do: [{k1, v1} | insert(rest, {k2, v2})]
defp insert([{k1, v1} | rest], {k2, v2}) when k1 > k2, do: [{k2, v2}, {k1, v1} | rest]
end
Edit:
Optimization with memoization and using a map instead of an ordered list (44ms on average)
defmodule AdventOfCode.Solutions.Y24.Day11 do
alias AoC.Input
def parse(input, _part) do
input
|> Input.read!()
|> String.trim()
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
def part_one(problem) do
solve(problem, 25)
end
def part_two(problem) do
solve(problem, 75)
end
defp solve(problem, cycles) do
stones = build_stones(problem)
stones = Enum.reduce(1..cycles, stones, fn _, stones -> blink_all(stones) end)
Enum.reduce(stones, 0, fn {_, c}, acc -> acc + c end)
end
defp build_stones(figures) do
Enum.reduce(figures, %{}, fn k, map -> merge_stone(map, k, 1) end)
end
defp merge_stone(map, k, n) do
Map.update(map, k, n, &(&1 + n))
end
defp blink_all(stones) do
stones
|> Enum.flat_map(&blink/1)
|> Enum.reduce(%{}, fn {k, n}, map -> merge_stone(map, k, n) end)
end
defp blink({0, count}), do: [{1, count}]
defp blink({figure, count}) do
case memoized_blink(figure) do
{left, right} -> [{left, count}, {right, count}]
by_2024 -> [{by_2024, count}]
end
end
defp memoized_blink(figure) do
case Process.get({__MODULE__, figure}, nil) do
nil ->
result = blink_figure(figure)
Process.put({__MODULE__, figure}, result)
result
result ->
result
end
end
defp blink_figure(figure) do
digits = Integer.digits(figure)
len = length(digits)
if rem(len, 2) == 0 do
{left, right} = Enum.split(digits, div(len, 2))
{Integer.undigits(left), Integer.undigits(right)}
else
figure * 2024
end
end
end
).
EDIT: its not increasing linearly, i can say that for sure ⌠O(n^2) maybe ⌠perplexity suggested O(stones * max_value * log(max_value)) ⌠i rewrote it from O(n * m * log(m))
