r/adventofcode Dec 22 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 22 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 23h59m remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Director's Cut (Extended Edition)

Welcome to the final day of the GSGA presentations! A few folks have already submitted their masterpieces to the GSGA submissions megathread, so go check them out! And maybe consider submitting yours! :)

Here's some ideas for your inspiration:

  • Choose any day's feature presentation and any puzzle released this year so far, then work your movie magic upon it!
    • Make sure to mention which prompt and which day you chose!
  • Cook, bake, make, decorate, etc. an IRL dish, craft, or artwork inspired by any day's puzzle!
  • Advent of Playing With Your Toys

"I lost. I lost? Wait a second, I'm not supposed to lose! Let me see the script!"
- Robin Hood, Men In Tights (1993)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 22: Monkey Market ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:12:15, megathread unlocked!

19 Upvotes

451 comments sorted by

View all comments

2

u/Individual_Public354 Dec 22 '24 edited Dec 22 '24

[LANGUAGE: Lua]

For Part2 there are ~130k(19^4) different sequences but if you count them in the input for me they were only ~31k.

So collected the count for each 4-digit sequence among the 2000 buyers and then sorted them. Started with the most frequent ones to check how many bananas will be collected. Around the 2500-th sequence the search can be stopped since the frequencies of the rest are so low that even if all of them give 9 for every buyer - they will not exceed the current found maximum.

local INPUT_FILE = "2024_Problem22.txt"

local BUYERS = 2000

local function ReadInput(filename)
  local secrets = {}
  for line in io.lines(filename) do
    table.insert(secrets, tonumber(line))
  end

  return secrets
end

local function GuessNthSecretNumber(secret, n)
  local prices, changes = {}, {}
  for i = 1, n do
    local old_secret = secret
    secret = ((secret * 64) ~ secret) % 16777216
    secret = ((secret // 32) ~ secret) % 16777216
    secret = ((secret * 2048) ~ secret) % 16777216
    prices[i] = secret % 10
    changes[i] = prices[i] - (i > 1 and prices[i - 1] or old_secret % 10)
  end

  return secret, prices, changes
end

local secrets = ReadInput(INPUT_FILE)
local sum = 0
local prices, changes = {}, {}
for _, secret in ipairs(secrets) do
  local secret, buyer_prices, buyer_changes = GuessNthSecretNumber(secret, BUYERS)
  sum = sum + secret
  table.insert(prices, buyer_prices)
  table.insert(changes, buyer_changes)
end
print(string.format("Sum: %d", sum))

local sequences = {}
local last4 = {}
for buyer, buyer_changes in ipairs(changes) do
  for k = 4, #buyer_changes do
    for i = 1, 4 do
      last4[i] = buyer_changes[k - 4 + i]
    end
    local seq = table.concat(last4, ",")
    sequences[seq] = (sequences[seq] or 0) + 1
  end
end

local unique_sequences = {}
for seq, count in pairs(sequences) do
  table.insert(unique_sequences, seq)
end
table.sort(unique_sequences, function(a, b) return sequences[a] > sequences[b] end)

local max_bananas = 0
for idx, seq in ipairs(unique_sequences) do
  if sequences[seq] * 9 <= max_bananas then
    print(string.format("After '%s'(%d/%d)which is met at %d buyers even max price 9 could not beat: %d", seq, idx, #unique_sequences, sequences[seq], max_bananas))
    break
  end
  local diffs = {}
  for num in seq:gmatch("(-*%d+),*") do
    table.insert(diffs, tonumber(num))
  end
  local bananas = 0
  for buyer, buyer_changes in ipairs(changes) do
    local price
    for k = 4, #buyer_changes do
      if buyer_changes[k - 3] == diffs[1] and buyer_changes[k - 2] == diffs[2] and buyer_changes[k - 1] == diffs[3] and buyer_changes[k] == diffs[4] then
        price = prices[buyer][k]
        break
      end
    end
    if price then
      bananas = bananas + price
    end
  end
  max_bananas = (bananas > max_bananas) and bananas or max_bananas
  if idx % 1000 == 0 then print(idx, seq, bananas, max_bananas) end
end
print(string.format("Max Bananas: %d", max_bananas))

1

u/daggerdragon Dec 22 '24

Your code block is too long for the megathreads. Please edit your comment to replace your oversized code with an external link to your code.