Advent of Code 2024 - Day 22

Yep. I did part 1 just to prove to myself that part 2 was going to be “and now a bazillion secrets??”, but was pleasantly surprised.

My part 2 takes ~7 seconds on a Core i5.
For each secret, I built a map of changes to bananas, using Map.put_new/3 to make sure I didn’t count a repeated sequence. Then I merged all the maps together, and took the maximum.

input
|> Enum.map(fn secret ->
  1..2000
  |> Enum.map_reduce(secret, fn _, secret -> {rem(secret, 10), next(secret)} end)
  |> elem(0)
  |> Enum.chunk_every(5, 1, :discard)
  |> Enum.reduce(%{}, fn [a, b, c, d, bananas], changes ->
    Map.put_new(changes, {b - a, c - b, d - c, bananas - d}, bananas)
  end)
end)
|> Enum.reduce(&Map.merge(&1, &2, fn _k, v1, v2 -> v1 + v2 end))
|> Enum.max_by(fn {_sequence, bananas} -> bananas end)
|> elem(1)

https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2024/day22.exs

Brute force going for 3.2 seconds on part 2:

defmodule AdventOfCode.Solutions.Y24.Day22 do
  alias AoC.Input

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

  def part_one(problem) do
    problem
    |> Enum.map(&next_number(&1, 2000))
    |> Enum.sum()
  end

  defp next_number(n, i) when i > 0 do
    next_number(next_number(n), i - 1)
  end

  defp next_number(n, 0) do
    n
  end

  defp next_number(num) do
    num = prune(mix(num, num * 64))
    num = prune(mix(num, Integer.floor_div(num, 32)))
    num = prune(mix(num, num * 2048))
    num
  end

  defp mix(a, b), do: Bitwise.bxor(a, b)
  defp prune(n), do: Integer.mod(n, 16_777_216)

  def part_two(problem) do
    all_sequences = Enum.map(problem, fn monkey_seed -> monkey_seed |> compute_future() |> compute_sequences() end)
    merged = Enum.reduce(all_sequences, fn seqs1, seq2 -> Map.merge(seqs1, seq2, fn _, v1, v2 -> v1 + v2 end) end)
    Enum.reduce(merged, 0, fn {_, v}, best -> max(best, v) end)
  end

  defp compute_future(monkey_seed) do
    Enum.scan(1..2000, {monkey_seed, unit_part(monkey_seed), nil}, fn _, {prev_secret, prev_unit, _} ->
      next_secret = next_number(prev_secret)
      unit = unit_part(next_secret)
      {next_secret, unit, unit - prev_unit}
    end)
  end

  defp compute_sequences(monkey_future, prev \\ [], acc \\ %{})

  defp compute_sequences([h | monkey_future], [c, b, a | prev], acc) do
    {_secret, price, d} = h
    seq = {a, b, c, d}
    acc = Map.put_new(acc, seq, price)
    compute_sequences(monkey_future, [d, c, b, a | prev], acc)
  end

  defp compute_sequences([], _prev, acc) do
    acc
  end

  # prefill the previous
  defp compute_sequences([{_, _, seqn} | monkey_future], prev, acc) do
    compute_sequences(monkey_future, [seqn | prev], acc)
  end

  # returns the rightmost digit of number
  defp unit_part(number) do
    rem(number, 10)
  end
end

I wonder what optimizations could be made other than memoizing.

@adamu I can see we had the same approach. When I saw I could just merge the sequences I was happy haha.

Alright, you made me crack out the M4. 2.67 seconds. Now we’re even

I also realised I used Enum.sum_by/2, which was just added in Elixir 1.18

I can’t believe I didn’t do that and serialized to string instead. Fixing that gets it down to 7.5s on the i5.

Anyone care to help me out on part 2? I took a straight forward brute force approach and my answer is off by 50? The code works on the small example. I’ve been going over it carefully for an hour now, and I can’t find the bug.

I copied in @igorb 's code, because he was first here, and his works (of course). We both come up with the same best sequence, but his total bananas on my input data is is 1831 while mine is 1881.

Sequence: 1831 [0, -1, 0, 1]
igorbs solve of part 2: 1831


Sequence: 1881 {0, -1, 0, 1}
Best sequence: {{0, -1, 0, 1}, 1881}

https://github.com/rvnash/aoc2024/blob/main/lib/d22.ex

Thanks if you take a look.

This was a nice break after the last two days.

The combined runtime for both parts is 2.4 seconds.

https://github.com/bjorng/advent-of-code/blob/main/2024/day22/lib/day22.ex

Maybe this ?

            if price > Map.get(sequences, sequence, 0) do
              {sequence, Map.put(sequences, sequence, price)}
            else
              {sequence, sequences}
            end

If I read correctly you are not yet finding the best price, so you should not keep the best price here. The puzzle says that you need to keep the first price for each different sequence.

Also instead of:

        {d0, diffs} = List.pop_at(diffs, 0)
        {d1, diffs} = List.pop_at(diffs, 0)
        {d2, diffs} = List.pop_at(diffs, 0)
        {d3, diffs} = List.pop_at(diffs, 0)

You can write:

[d0,d1,d2,d3|diffs] = diffs

(lud beat me to it while typing)

It says that the bid is placed as soon as the sequence occurs. So even if there’s a better price for a later secret (same seed, later iteration) with the same sequence, that’s too late and shouldn’t be used.

That was it. Thanks so much! I didn’t fully get the instructions. Now I can go on with my day.

I found a first optimization on reddit.

Instead of doing:

seq = {a,b,c,d} # last 4 price changes
Map.put(sequences, seq, price)

It is possible to do:

<<seq::integer-20>> = <<a::5, b::5, c::5, d::5>>
Map.put_new(sequences, seq, price)

That’s not a game changer but it definitely improve times.