Advent of Code 2024 - Day 11

Learning Questions & Discussions Coding Challenges
,
21

Seriously short of time to do this today, so I used Memoize rather than roll my own memoization implementation, if I get a chance I’ll re-write using a hand rolled cache.

Still happy with the solution and run-time though.

Solution for 2024 day 11
part_one: 193607 in 12.01ms
part_two: 229557103025807 in 252.98ms

Name               ips        average  deviation         median         99th %
part_two        7.63 K      131.09 μs    ±50.31%      123.25 μs      226.81 μs
part_one        7.53 K      132.72 μs    ±54.50%      124.13 μs      231.54 μs

Comparison: 
part_two        7.63 K
part_one        7.53 K - 1.01x slower +1.64 μs

defmodule Aoc2024.Solutions.Y24.Day11 do
  require Integer
  alias AoC.Input

  use Memoize

  def parse(input, _part) do
    Input.read!(input)
    |> String.trim()
    |> String.split(" ", trim: true)
    |> Enum.map(&String.to_integer/1)
  end

  def part_one(problem) do
    Enum.reduce(problem, 0, fn stone, acc ->
      acc + apply_rules(stone, 0, 25)
    end)
  end

  def part_two(problem) do
    Enum.reduce(problem, 0, fn stone, acc ->
      acc + apply_rules(stone, 0, 75)
    end)
  end

  defmemo apply_rules(stone, count, target) do
    if count == target do
      1
    else
      target_stones = rule(stone)

      case target_stones do
        [_first, _second] ->
          Enum.reduce(target_stones, 0, fn stone, acc ->
            acc + apply_rules(stone, count + 1, target)
          end)

        stone ->
          apply_rules(stone, count + 1, target)
      end
    end
  end

  defmemo rule(stone) do
    if stone == 0 do
      1
    else
      stone_string = Integer.to_string(stone)
      digits = String.length(Integer.to_string(stone))

      case Integer.is_even(digits) do
        true ->
          String.split_at(stone_string, div(digits, 2))
          {left, right} = String.split_at(stone_string, div(digits, 2))

          [
            String.to_integer(left),
            String.to_integer(right)
          ]

        _ ->
          stone * 2024
      end
    end
  end

  defmemo split_into_chunks(options) do
    workers = :erlang.system_info(:schedulers_online)
    options_count = Enum.count(options)
    options_per_chunk = :erlang.ceil(options_count / workers)

    Enum.chunk_every(options, options_per_chunk)
  end
end
1 Like
22

Updated version using my own ETS cache, much quicker which is interesting . . .

Solution for 2024 day 11
part_one: **193607** in **3.71ms**
part_two: **229557103025807** in **59.43ms**


defmodule Aoc2024.Solutions.Y24.Day11 do
  require Integer
  alias AoC.Input

  def parse(input, _part) do
    Input.read!(input)
    |> String.trim()
    |> String.split(" ", trim: true)
    |> Enum.map(&String.to_integer/1)
  end

  def part_one(problem) do
    :ets.new(:apply_rules_cache, [:named_table, :public, :set, :protected])

    result =
      Enum.reduce(problem, 0, fn stone, acc ->
        acc + apply_rules(stone, 0, 25)
      end)

    :ets.delete(:apply_rules_cache)
    result
  end

  def part_two(problem) do
    :ets.new(:apply_rules_cache, [:named_table, :public, :set, :protected])

    result =
      Enum.reduce(problem, 0, fn stone, acc ->
        acc + apply_rules(stone, 0, 75)
      end)

    :ets.delete(:apply_rules_cache)
    result
  end

  def apply_rules(stone, count, target) do
    case :ets.lookup(:apply_rules_cache, {stone, count, target}) do
      [{_, result}] ->
        result

      [] ->
        result =
          if count == target do
            1
          else
            target_stones = rule(stone)

            case target_stones do
              [_first, _second] ->
                Enum.reduce(target_stones, 0, fn stone, acc ->
                  acc + apply_rules(stone, count + 1, target)
                end)

              stone ->
                apply_rules(stone, count + 1, target)
            end
          end

        :ets.insert(:apply_rules_cache, {{stone, count, target}, result})
        result
    end
  end

  def rule(stone) do
    if stone == 0 do
      1
    else
      stone_length = Integer.digits(stone)
      num_digits = length(stone_length)
      # stone_string = Integer.to_string(stone)
      # digits = byte_size(stone_string)

      case Integer.is_even(num_digits) do
        true ->
          stone_string = Integer.to_string(stone)
          mid = div(num_digits, 2)
          <<left::binary-size(mid), right::binary>> = stone_string
          [String.to_integer(left), String.to_integer(right)]

        _ ->
          stone * 2024
      end
    end
  end
end
23

My part 2 is really slow, but I did get it down from “it’ll never finish” to “bearable”. Definitely going to take a closer look at some of the better solutions in this thread.

24

You don’t need memoization or a cache.

2 Likes
25

I took the naive solution bait for part 1:

#!/usr/bin/env elixir

defmodule Day11.Part1 do
  @blinks 25

  defp parse(str) do
    stones =
      str
      |> String.split([" ", "\n"], trim: true)
      |> Enum.map(&String.to_integer/1)

    stones
  end

  defp blunk(0), do: [1]

  defp blunk(stone) do
    digits =
      stone
      |> Integer.digits()

    size =
      digits
      |> Enum.count()

    half = div(size, 2)
    if rem(size, 2) == 0 do
        left = digits |> Enum.slice(0..(half - 1)) |> Integer.undigits()
        right = digits |> Enum.slice(half..-1//1) |> Integer.undigits()
        [left, right]
    else
        [stone * 2024]
    end
  end

  defp blink(stones) do
    {stones,
     stones
     |> Enum.flat_map(&blunk/1)}
  end

  def solve() do
    File.read!("11/input.txt")
    |> parse()
    |> Stream.unfold(&blink/1)
    |> Stream.drop(@blinks)
    |> Enum.take(1)
    |> List.first()
    |> Enum.count()
    |> IO.puts()
  end
end

Day11.Part1.solve()

Spent the rest of the day figuring out how to memoize this thing for part 2 after realizing the tree approach was a thing. After many attempts of getting that wrong, I landed on the following:

#!/usr/bin/env elixir

defmodule Day11.Part2 do
  @blinks 75

  defp parse(str) do
    stones =
      str
      |> String.split([" ", "\n"], trim: true)
      |> Enum.map(&String.to_integer/1)

    stones
  end

  defp digit_count(n) when n < 10, do: 1
  defp digit_count(n), do: 1 + digit_count(div(n, 10))

  def split(n, half) do
    left = div(n, 10 ** half)
    right = rem(n, 10 ** half)
    [left , right]
  end

  defp blink(0), do: 1

  defp blink(stone) do
    size = digit_count(stone)

    half = div(size, 2)

    if rem(size, 2) == 0 do
        split(stone, half)
    else
        stone * 2024
    end
  end

  def blink_count(_stone, 0, _index, seen), do: {1, seen}

  def blink_count(stone, times, index, seen) when is_number(stone) do
    case seen[{stone, index}] do
      nil ->
        case blink(stone) do
          [left, right] ->
            {left_count, updated_seen} = blink_count(left, times - 1, index + 1, seen)
            {right_count, doubly_updated_seen} = blink_count(right, times - 1, index + 1, updated_seen)
            {left_count + right_count, doubly_updated_seen}

          m ->
            blink_count(m, times - 1, index + 1, seen)
        end
        |> (fn {c, final_seen} -> {c, final_seen |> Map.put({stone, index}, c)} end).()
      m ->
        {m, seen}
    end
  end

  def blink_count(stones, times) when is_list(stones) do
    stones
    |> Enum.reduce(
      {0, %{}},
      fn stone, {count, seen} ->
        {blink_count, seen} = blink_count(stone, times, 0, seen)
        {count + blink_count, seen}
      end
    )
    |> elem(0)
  end

  def solve() do
    File.read!("11/input.txt")
    |> parse()
    |> blink_count(@blinks)
    |> IO.puts()
  end
end

Day11.Part2.solve()
26

My initial attempt using lists failed to execute part2 as expected. Had to come here for some inspiration. Switching to a map of counts did the trick nicely.

defmodule Aoc2024.Day11 do
  @moduledoc false

  def part1(file) do
    get_input(file)
    |> Enum.frequencies()
    |> flutter(25)
    |> Map.values()
    |> Enum.sum()
  end

  def part2(file) do
    get_input(file)
    |> Enum.frequencies()
    |> flutter(75)
    |> Map.values()
    |> Enum.sum()
  end

  defp get_input(file) do
    File.read!(file)
    |> String.trim()
    |> String.split(" ", trim: true)
    |> Enum.map(&String.to_integer/1)
  end

  defp flutter(stones, 0), do: stones

  defp flutter(stones, count) do
    flutter(blink(stones), count - 1)
  end

  defp blink(stones) do
    stones
    |> Map.to_list()
    |> Enum.filter(fn {_, count} -> count > 0 end)
    |> Enum.reduce(stones, fn {stone, count}, acc ->
      removed = Map.update!(acc, stone, &(&1 - count))

      Enum.reduce(change(stone), removed, fn new, map ->
        Map.update(map, new, count, &(&1 + count))
      end)
    end)
  end

  defp change(0), do: [1]

  defp change(stone) do
    if Integer.mod(l = String.length(s = Integer.to_string(stone)), 2) == 0 do
      mid = Integer.floor_div(l, 2)
      [String.to_integer(String.slice(s, 0, mid)), String.to_integer(String.slice(s, mid, l))]
    else
      [stone * 2024]
    end
  end
end
27

Yeah I originally had this as well, but the overhead of keeping it and managing other state around made it much less performant than… simply not saving it. *shrug

1 Like
28

Fairly straightforward once i realised a cache allowed my naive solution to work for part 2.

1 Like
29

Hindsight is 20x20 :slight_smile:

Now I’ve seen all the “Just keep track of the qty of stones” posts, there is obviously another way. I do like that about AOC, the learning afterwards, hopefully retaining some of the tricks for next year,

1 Like
30

Nice, my attempt with lists failed miserably. I always go with handling lists instead of stopping and thinking about the solution in terms of maps. Lesson learned (hopefully). :bug:

31

I don’t think so. It looks like a diversion for humans to me. This requires us to extract the parameters/notions that are truly essential.

32

I would be interested to see your implementation of Performance.memoize()?

Do you need to do anything to avoid problems when running say unit tests across many days/years of problems? Say in my case whenever I run mix test, it actually runs all the tests for all the tests I’ve been playing. I’m wondering how you partition your cache?

33

My previous was meant to be a reply to antoine-duchenet

I’m obviously an idiot, I have clicked reply on his post twice and it doesn’t seem to cause a reply to his actual post, nor can I figure out how to delete this second comment??

34

I’m using ETS to memoize.

first I create a named ETS table

:ets.new(:my_table, [:named_table])

then the memoize function

def memoize(key, fun) do
  case :ets.lookup(@table, key) do
    [{^key, val}] -> val
    [] -> fun.() |> tap(&:ets.insert(@table, {key, &1}))
  end
end

which I use like this:

def count_stones(stone, n) do
  memoize({stone, n}, fn ->
    case blink(stone) do
      [s1, s2] -> count_stones(s1, n - 1) + count_stones(s2, n - 1)
      stone -> count_stones(stone, n - 1)
    end
  end)
end
1 Like
35

I would be interested to see your implementation of Performance.memoize()?

Here it is :

defmodule Performance do
  def memoize(key, f) do
    with nil <- Process.get(key), do: tap(f.(), &Process.put(key, &1))
  end
end

I’m only using this implementation for AoC exercises, I don’t use it in production. It uses the process dictionary, which will have flaws if you need to share this cache between multiple BEAM processes.

You can still wrap it in a agent or use ETS if you need concurrency, but I never needed concurrency to solve AoC challenges (IMHO, if you do, it probably means that you missed something more elaborate than raw concurrency :smiley_cat: ).

Please note that this is a lazy solution, I could use a Map instead but this gives me a quick and dirty way to add a “global” (to the process) state that I can read and write anywhere !

36

I hate dynamic programming problems. Didn’t do anything interesting here. ETS for the memoization.

defmodule Day11 do
  require Integer

  @test "125 17"

  @real File.read!(__DIR__ <> "/input.txt") |> String.trim()

  @run1 25
  @run2 75

  defp rules(0), do: 1

  defp rules(n) do
    x = :math.log10(n) |> floor()

    if Integer.is_odd(x) do
      divisor = Integer.pow(10, div(x + 1, 2))
      [div(n, divisor), Integer.mod(n, divisor)]
    else
      n * 2024
    end
  end

  def run(mode) do
    data = mode |> input() |> parse()
    :ets.new(:memo, [:named_table, :set, :public])

    part_1(data) |> IO.inspect(label: :part_1)
    part_2(data) |> IO.inspect(label: :part_2)

    :ets.delete(:memo)
  end

  defp input(:test), do: @test
  defp input(:real), do: @real
  defp input(_), do: raise("Please use :test or :real as modes to run.")

  defp parse(input) do
    input
    |> String.split(" ", trim: true)
    |> Enum.map(&String.to_integer/1)
  end

  defp part_1(stones) do
    count_stones(stones, @run1)
  end

  defp part_2(stones) do
    count_stones(stones, @run2)
  end

  defp count_stones(stones, runs) when is_list(stones) do
    stones
    |> Enum.reduce(0, fn stone, acc -> count_stones(stone, runs) + acc end)
  end

  defp count_stones(stone, runs) do
    case :ets.lookup(:memo, {stone, runs}) do
      [] ->
        apply_rules(stone, runs) |> tap(fn res -> :ets.insert(:memo, {{stone, runs}, res}) end)

      [{_, res}] ->
        res
    end
  end

  defp apply_rules(stones, 0) when is_list(stones), do: length(stones)
  defp apply_rules(_, 0), do: 1

  defp apply_rules(stones, runs) when is_list(stones) do
    stones
    |> Enum.reduce(0, fn stone, acc -> acc + count_stones(stone, runs - 1) end)
  end

  defp apply_rules(stone, runs) do
    count_stones(rules(stone), runs - 1)
  end
end

Day11.run(:real)

@antoine-duchenet re: not needing concurrency, it’s probably true, but I did test with splitting the stones into chunks to create worker pools in parallel and got 50-60% improvement in performance by :timer.tc excluding the time for input parsing and starting the ETS cache. So, not necessary but can still be useful.

For grins I also tested whether it made a difference what type of table ETS used (set, ordered set, or bag) and it did not seem to make a difference for my implementation. Ordered set may have trended a few percent slower but meaningfully so.