Day 11: Plutonian Pebbles

Mix.install([
  {:kino, "~> 0.14.0"}
])

Reading

• There are a number of stones in a straight line
• They all simulate the follwing rules left to right (when blinking):
  • if stone has number 0, it changes to 1
  • if stone has even number of digits it splits into two stones
    • the left half of the digits go onto the new left stone
    • the right half of the digits go onto the new right stone
    • leading zeros are simply dropped (can use integers)
  • if no other rule applies, multiply the stones number by 2024
• The order is always preserved
• Input the numbers on the initial stones

> The text says the stones change “simultaniously” but then all examples evaluate the rules left-to-right. I’m not sure if this is an oversight on their/my part of if its just a poorly chosen word.

Input

initial_stones =
  Kino.FS.file_path("day11_input.bin")
  |> File.read!()
  |> String.split()
  |> Enum.map(&String.to_integer/1)

Implementation

defmodule WeirdStones do
  require Integer

  defp count_digits(nr), do: nr |> to_string() |> String.length()
  
  def simulate(stones) when is_list(stones) do
    Enum.flat_map(stones, fn stone ->
      digits = count_digits(stone)
      
      cond do
        stone == 0 ->
          [1]

        Integer.is_even(digits) ->
          {l, r} = stone |> to_string() |> String.split_at(div(digits, 2))
          [String.to_integer(l), String.to_integer(r)]

        true ->
          [stone * 2024]
      end
    end)
  end
end

Enum.reduce(1..25, initial_stones, fn _i, stones ->
  WeirdStones.simulate(stones)
end)
|> then(fn stones -> length(stones) end)

Part 2

This is the exact same thing, just with more simulation steps now.

The problem is that this works until about iteration 40 where a single simulation/1 step takes multiple seconds, increasing in exponential fassion.

We need to further optimize this. I did small things like replacing String.length/1 with byte_size/1 (since we know its only numbers, no need to handle UTF-8 stuff) and replacing Enum.flat_map with Enum.reduce with list prepending. None of this really made a large difference though.

Thorugh measuring with :timer.tc/3, I can tell that the single step/1 invocation stays fast (even with larger numbers) but the operation on the whole array seems to slow everything down.

defmodule FastWeirdStones do
  require Integer
  
  def simulate(stones) when is_map(stones) do
    Enum.reduce(stones, %{}, fn {stone, count}, acc ->
      case step(stone) do
        result when is_number(result) ->
          Map.update(acc, result, count, fn current -> current + count end)

        {left, right} ->
          acc
          |> Map.update(left, count, fn current -> current + count end)
          |> Map.update(right, count, fn current -> current + count end)
      end
    end)
  end

  defp step(stone) do
    as_string = to_string(stone)
    digits = byte_size(as_string)
    
    cond do
      stone == 0 ->
        1

      Integer.is_even(digits) ->
        {l, r} = String.split_at(as_string, div(digits, 2))
        {String.to_integer(l), String.to_integer(r)}

      true ->
        stone * 2024
    end
  end
end

Enum.reduce(initial_stones, %{}, fn stone, map ->
  Map.update(map, stone, 1, fn count -> count + 1 end)
end)
|> then(&Enum.reduce(1..75, &1, fn _i, stone_map ->
  FastWeirdStones.simulate(stone_map)
end))
|> Enum.reduce(0, fn {_stone, count}, acc -> acc + count end)

I think this line in the problem description is a red herring:

> No matter how the stones change, their order is preserved, and they stay on their perfectly straight line.

• The order of the stones is actually irrelevant for the final result, we just need the count.
• The number of rocks will only ever increase
• Each operation only looks at the single number in isolation, no sourroundings are important

The idea came mainly because of the rule for 0, an operation that we could perform “in bulk” by simply taking all zeros. Since we don’t need the final assortment of stones but just the count, the idea was to simply store each unique number once and the count of how often they currently exist. With this, we can then run all operations “in bulk” for a given number.

Mesaurements

• Initial from part 1 (MacBook Pro M2): 48 seconds for iteration 30 alone
• Optimized with Map: 0.2ms for 175 iterations