Today was a nice break from Day 21. Part 2 is just brute-force, with a bit of optimization tracking what sequences return how many bananas per number: advent-of-code-2024/lib/advent_of_code2024/day22.ex at main · ibarakaiev/advent-of-code-2024 · GitHub
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)
1 Like
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.
1 Like
@adamu I can see we had the same approach. When I saw I could just merge the sequences I was happy haha.
1 Like
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.
1 Like
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}
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.
2 Likes
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
1 Like
(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.
2 Likes
That was it. Thanks so much! I didn’t fully get the instructions. Now I can go on with my day.
1 Like
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.
3 Likes
@bjorng did something similar.
2 Likes
Didn’t work out too slow. Part 2 took about 20s on my laptop.
Whatever works as long as you get the answer 
Today was easy:
defmodule Buyer do
def hash(number, rounds \\ 2000) do
Enum.map_reduce(1..rounds//1, number, fn _, acc ->
r = do_round(acc)
{rem(r, 10), r}
end)
end
defp do_round(num) do
num = subround(num, num * 64)
num = subround(num, div(num, 32))
subround(num, num * 2048)
end
defp subround(a, b), do: rem(Bitwise.bxor(a, b), 16777216)
def sequences(prices) do
prices
|> Enum.chunk_every(5, 1, :discard)
|> Enum.reduce(%{}, fn seq, map ->
Map.put_new(map, diffs(seq), List.last(seq))
end)
end
def diffs(vals), do: vals |> Enum.chunk_every(2, 1, :discard) |> Enum.map(fn [a, b] -> b - a end)
end
# P1
inits
|> Enum.map(&elem(Buyer.hash(&1), 1))
|> Enum.sum()
# P2
seqs =
inits
|> Task.async_stream(
fn init ->
{prices, _} = Buyer.hash(init)
Buyer.sequences(prices)
end,
ordered: false
)
|> Enum.reduce(%{}, fn {:ok, a}, b -> Map.merge(a, b, fn _k, v, k -> v + k end) end)
Enum.max_by(seqs, &elem(&1, 1))
Any idea what’s the fastest value type as a key in a map? Atom maybe?
I would expect atoms and small integers (fitting in 60 bits) to be fast when used as map keys.
Just FYI. I tried for keys that maps sequences to bananas, unique Integers, Atoms, Tuples, and Strings as keys. Here are the times for the final bunch of merges that produce the answer.
# Integer 747ms
# Atom 670ms
# Tuple 1024ms
# String 2371ms
I wonder what optimizations could be made other than memoizing.
I ran brute force to get the solution, then optimized that. If you know when to stop adding bananas for a specific pricing sequence, you can skip a lot of computation.
Compute the min and max unit price for the pricing sequence; the most bananas you can get is max unit price * monkeys with that pricing sequence. You can track the maximum while computing a banana run to short circuit early.
Then if you order the pricings based on their expected average price, you can start short circuiting earlier using the more likely “best banana” price sequence results.
UPDATE: optimized even further - I no longer needed this strategy. Instead, I just loop through each pricing on each monkey, check to make sure it’s the first pricing seen, and add it to the total bananas in a pricing hash table of total bananas. Max on that table is the result.
Running now in about 400ms.
–
I just compute the total bananas and keep track of a pricing
In my code, it cut the number of pricing sequences additions I had to compute from brute force ~4.5M to ~118K.
For price sequence D1 - D4, the magic calculations were these:
int MinimumUnitPrice =>
Max(0, Max(0, Max(0, Max(0, 0 - D1) - D2) - D3) - D4)
+ D4 + D3 + D2 + D1;
int MaximumUnitPrice =>
Min(9, Min(9, Min(9, Min(9, 9 - D1) - D2) - D3) - D4)
+ D4 + D3 + D2 + D1;
1 Like
In C#? This is the Elixir forum so sharing the Elixir running time would also be helpful. Elixir being immutable can be quite inefficient when doing things that involve many updates to data structures.
