AoC 2020 D15: Rambunctious Recitation

| Problem statement | Source code | Tags: Brute forceData structures

← Previous Back to AoC Index Next →

This is literally just simulating the game rules, no questions asked. While 30,000,000 turns is a lot, if we have an $\mathcal{O}(n)$ algorithm, it's still feasible. The only bottleneck is finding the last occurrence of a number. Instead of storing all numbers physically in an array, notice that previous occurrences of the same number are irrelevant, so we should instead maintain a dictionary that maps each number to its last occurrence index.

most_recent_turn = {x: i + 1 for i, x in enumerate(nums)}
last_num = nums[-1]
for i in range(len(nums) + 1, round + 1):
    num = i - 1 - most_recent_turn.get(last_num, i - 1)
    most_recent_turn[last_num] = i - 1
    last_num = num
print(last_num)

← Previous Back to AoC Index Next →