Advent of Code

Day 22 is a story about negociating banana prices with a bunch of monkeys. The setup is fairly convoluted, which made the main difficulty of the day reading comprehension. Otherwise it was very easy compared to yesterday.

Part 1 - a pseudorandom generator

Part 1 is very straightforward – once you remove all the monkey stuff. We start with a list of initial numbers. Each number starts a pseudorandom sequence that evolves according to a set of rules. We need to compute which numbers we get after applying those rules 2000 times. The rules are as follow:

This is where I made my first mistake, which was that I initially misread the instructions and thought that at each step we had to XOR with \(x\), not with \(x_{step}\). But I eventually realized my mistake.

The input file is just the list of initial number, so no fancy parsing necessary:

def parse_input() -> list[int]:
    with open("day22", 'r') as fp:
        data = fp.read().strip().split('\n')
    return [int(d) for d in data]

And we can use binary operations to implement all the steps, as all the multipliers and dividers are powers of 2:

M = 2 << 23

def next_number(n: int) -> int: 
    k = ((n << 6)^n)%M 
    k = ((k >> 5)^k)%M
    return ((k << 11)^k)%M

That gives us our part 1 answer, which is the sum of all 2000th number in the sequences:

start = parse_input()
tot = 0
for n in start:
    for _ in range(2000):
        n = next_number(last_n)
    tot += n
    
print(f"Part 1 answer: {tot}")

Part 2: tracking differences

For the second part, we had a bit of complexity to the setup, but the code is not much more complicated. In banana-buying land, our pseudorandom sequence is used to compute the number of bananas we can buy from our monkey sellers. It works like this: if we take a sequence:

We need to track the last digit of each number (which is a number of bananas), then look at the difference between successive banana numbers:

With a sequence of four successive differences (e.g. -3, +6, -1, -1), we can trigger the banana sale. The idea is that, for each initial number, the sale happens whenever we hit this particular sequence of differences, with the price being the last price in the sequence (e.g. if we used -3, +6, -1, -1, it would trigger the sale for this example sequence with the price at 4). We need to find one sequence of four differences that will maximize the numbers of bananas we get across all sequences.

So now in addition to computing the next number in the sequence, we need to keep track of the last four differences, and of which price we get on each sequence with each possible four-differences. I decided to keep track of that in a dict, using a four integers tuple as the key (the four differences), associated to an int (the price we get). Then, for all sequences, we use the same keys but keep a list of all the prices we get per sequence. So after computing the next number, we need to call this accumulator function:

def accumulate_differences(n: int, 
                           last_n: int, 
                           current_sequence: deque[int], 
                           accumulator: dict[tuple[int, int, int, int], int]):
    diff = n-last_n
    current_sequence.append(diff)
    if len(current_sequence) > 4:
        current_sequence.popleft()
    if len(current_sequence) == 4:
        if tuple(current_sequence) not in accumulator:
            accumulator[tuple(current_sequence)] = n
    return diff

This function gets as input the last digit of the current and previous number in the sequence (n and last_n), the current sequence of four differences (stored in a deque, which is basically a list optimized for appending and popping from both sides), and our dict accumulator. We compute the difference, append it to the current sequence (to the right), pop from the left if we have more than four elements in it, and if we have four differences (which will always be the case after the fourth number in the seqence) we put the tuple/price pair in the accumulator.

Here I initially made stupid mistake number two, as instead of taking the first occurence of the four-differences to get the price, I took the maximum price with that four-differences sequence. That was annoying to fix because I got the correct results on the example input provided, and it only failed on the real data. But after carefully re-re-re-reading the story, I got it.

start = parse_input()
tot = 0
total_accumulator = defaultdict(list)
for n in start:
    accumulator = {}
    current_sequence = deque()
    last_n = n
    for _ in range(2000):
        n = next_number(last_n)
        accumulate_differences(n%10, last_n%10, current_sequence, accumulator)
        last_n = n
    tot += n
    for key, val in accumulator.items():
        total_accumulator[key].append(val)   
print(f"Part 1 answer: {tot}")

With that, total_accumulator will contain for each tuple of possible four-difference sequence that appears, the list of prices that we get in each pseudorandom sequence. We now just need to keep the maximum sum of prices that we can get:

print(f"Part 2 answer: {max(sum(values) for values in total_accumulator.values())}")

And we’re through to the next one. A few days late, but still 100% puzzles solved so far.