aoc::year2024

Module day17

Source
Expand description

§Chronospatial Computer

Part one implements the computer specification then runs the provided program. The b and c registers are assumed to be always zero in the provided input. The computer uses a resumable run method that returns Some(out) to indicate output and None to indicate program end. This is the same flexible approach used by the 2019 Intcode computer.

For part two, reverse engineering the assembly shows that it implements the following algorithm:

    while a != 0 {
        b = // Some hash based on value of a
        out b
        a >>= 3
    }

This means that the final value of a must be zero. Starting with this knowledge we work backwards digit by digit. The right shift wipes out the lowest 3 bits of a so there could be 8 possible previous values. We check each possible value recursively, exploring only those that result in the correct program digit.

For each new item we check each of the 8 possible combinations against the next digit in reverse, and so on until we have all possible valid starting values of a.

Although it may seem that checking could grow exponentially to 8¹⁶ potential values, in practice filtering by correct digit keeps the total less than 50.

Structs§

Functions§