Advent of Code - 2022
This is a solution to Day 10 of Advent of Code 2022.
Day 10 - Cathode-Ray Tube
You avoid the ropes, plunge into the river, and swim to shore.
The Elves yell something about meeting back up with them upriver, but the river is too loud to tell exactly what they're saying. They finish crossing the bridge and disappear from view.
Situations like this must be why the Elves prioritized getting the communication system on your handheld device working. You pull it out of your pack, but the amount of water slowly draining from a big crack in its screen tells you it probably won't be of much immediate use.
Unless, that is, you can design a replacement for the device's video system! It seems to be some kind of cathode-ray tube screen and simple CPU that are both driven by a precise clock circuit. The clock circuit ticks at a constant rate; each tick is called a cycle.
Start by figuring out the signal being sent by the CPU. The CPU has a single register, X, which starts with the value 1. It supports only two instructions:
addx Vtakes two cycles to complete. After two cycles, the X register is increased by the value V. (V can be negative.)nooptakes one cycle to complete. It has no other effect.The CPU uses these instructions in a program (your puzzle input) to, somehow, tell the screen what to draw.
Consider the following small program:
noop addx 3 addx -5Execution of this program proceeds as follows:
- At the start of the first cycle, the noop instruction begins execution. During the first cycle, X is 1. After the first cycle, the noop instruction finishes execution, doing nothing.
- At the start of the second cycle, the addx 3 instruction begins execution. During the second cycle, X is still 1.
- During the third cycle, X is still 1. After the third cycle, the addx 3 instruction finishes execution, setting X to 4.
- At the start of the fourth cycle, the addx -5 instruction begins execution. During the fourth cycle, X is still 4.
- During the fifth cycle, X is still 4. After the fifth cycle, the addx -5 instruction finishes execution, setting X to -1.
Maybe you can learn something by looking at the value of the X register throughout execution. For now, consider the signal strength (the cycle number multiplied by the value of the X register) during the 20th cycle and every 40 cycles after that (that is, during the 20th, 60th, 100th, 140th, 180th, and 220th cycles).
For example, consider this larger program:
addx 15 addx -11 addx 6 addx -3 addx 5 addx -1 addx -8 addx 13 addx 4 noop addx -1 addx 5 addx -1 addx 5 addx -1 addx 5 addx -1 addx 5 addx -1 addx -35 addx 1 addx 24 addx -19 addx 1 addx 16 addx -11 noop noop addx 21 addx -15 noop noop addx -3 addx 9 addx 1 addx -3 addx 8 addx 1 addx 5 noop noop noop noop noop addx -36 noop addx 1 addx 7 noop noop noop addx 2 addx 6 noop noop noop noop noop addx 1 noop noop addx 7 addx 1 noop addx -13 addx 13 addx 7 noop addx 1 addx -33 noop noop noop addx 2 noop noop noop addx 8 noop addx -1 addx 2 addx 1 noop addx 17 addx -9 addx 1 addx 1 addx -3 addx 11 noop noop addx 1 noop addx 1 noop noop addx -13 addx -19 addx 1 addx 3 addx 26 addx -30 addx 12 addx -1 addx 3 addx 1 noop noop noop addx -9 addx 18 addx 1 addx 2 noop noop addx 9 noop noop noop addx -1 addx 2 addx -37 addx 1 addx 3 noop addx 15 addx -21 addx 22 addx -6 addx 1 noop addx 2 addx 1 noop addx -10 noop noop addx 20 addx 1 addx 2 addx 2 addx -6 addx -11 noop noop noopThe interesting signal strengths can be determined as follows:
- During the 20th cycle, register X has the value 21, so the signal strength is 20 * 21 = 420. (The 20th cycle occurs in the middle of the second addx -1, so the value of register X is the starting value, 1, plus all of the other addx values up to that point: 1 + 15 - 11 + 6 - 3 + 5 - 1 - 8 + 13 + 4 = 21.)
- During the 60th cycle, register X has the value 19, so the signal strength is 60 * 19 = 1140.
- During the 100th cycle, register X has the value 18, so the signal strength is 100 * 18 = 1800.
- During the 140th cycle, register X has the value 21, so the signal strength is 140 * 21 = 2940.
- During the 180th cycle, register X has the value 16, so the signal strength is 180 * 16 = 2880.
- During the 220th cycle, register X has the value 18, so the signal strength is 220 * 18 = 3960.
The sum of these signal strengths is 13140.
Today's puzzle is super fun! I really like these "build a simple computer" type of exercises.
Read input
I read all the lines and based on the input, create either a 'noop' or 'add' instruction.
from utils import read_input
from collections import namedtuple
Instruction = namedtuple('Instruction', ['command', 'value'])
def transformer(line):
parts = line.split(' ')
if len(parts) == 1:
return Instruction(parts[0], None)
else:
return Instruction(parts[0], int(parts[1]))
program = read_input(10, transformer)Part 1
Find the signal strength during the 20th, 60th, 100th, 140th, 180th, and 220th cycles. What is the sum of these six signal strengths?
To start, we need to build our CPU. I'm calling it an interpreter since that is what our program execution is: we go line by line and execute what we see.
First, we have the state of our interpreter: it knows the value in the register (this is the register X in the description), it has a clock cycle, it has an index for which instruction we are currently executing (this is due to some instructions taking multiple cycles) and a helper execute_add flag to keep track of which cycle inside the addx instruction we are in.
I built this interpreter as a generator so we can inspect it at each clock cycle and then build all the functionality we want, separate from the execution itself.
Let's talk about Python generators
Previously we've used generator expressions (for example, sum(1 for _ in booleans)) where we generate a value on each iteration but we don't create a new list in memory. We're doing similar here but instead, we have a function that we write and instead of returning a value and stopping the execution of the function, we yield a value and continue the execution.
Let's start with a simpler example:
def generator(start=0):
number = start
while True:
yield number
number += 1We have a generator that gets a number as a parameter and then runs a never-ending loop. On each loop iteration, it yields (returns) a number and increases it on one.
The way we'd then use this generator is that we first initialize it:
numbers = generator(0)and we can then call next function with this generator to get its next value:
print(next(numbers)) # Prints 0
print(next(numbers)) # Prints 1
print(next(numbers)) # Prints 2or we can iterate over it for example in a for loop:
for num in numbers:
print(num)
if num > 10:
breakBecause our generator is infinite, we need to figure out the break point ourself.
It's important to note that if we'd run all of the above three blocks in a row, the for loop would start with the value 3 because we've already run the generator a few rounds.
Back to our interpreter
We run the while loop for as long as there are program instructions.
Each cycle, we start by returning the current cycle and register values. Then we take the command and update the internal state based on the instruction.
For a noop, we just increment cycle and index. For addx instruction, if we're on the second cycle, we add the value to register, increment cycle and index and mark execute_add to False so the next addx instruction won't immediately trigger.
If we're on the first cycle of addx, we increment cycle and set the flag for execute_add. We don't increment index here because we want to stay on the same instruction.
def interpreter(program):
register = 1
cycle = 1
index = 0
execute_add = False
while index < len(program):
yield cycle, register
command = program[index]
match command:
case Instruction('noop', None):
cycle += 1
index += 1
case Instruction('addx', value):
if execute_add:
register += value
cycle += 1
index += 1
execute_add = False
else:
execute_add = True
cycle += 1Now that we have our program, we can build "apps" for it. Our first piece of software is a signal strength calculator. It keeps running the program and on each cycle, it checks if we've reached a checkpoint that the problem description gave us and if yes, calculate the strength as the product of cycle and register and add it to our total.
def signal_strength_calculator(program):
checkpoints = [20, 60, 100, 140, 180, 220]
signal_strength = 0
for cycle, register in interpreter(program):
if cycle in checkpoints:
signal_strength += cycle * register
return signal_strength
signal_strength = signal_strength_calculator(program)
print(f'Part 1: {signal_strength}')
assert signal_strength == 14760Part 2
It seems like the X register controls the horizontal position of a sprite. Specifically, the sprite is 3 pixels wide, and the X register sets the horizontal position of the middle of that sprite. (In this system, there is no such thing as "vertical position": if the sprite's horizontal position puts its pixels where the CRT is currently drawing, then those pixels will be drawn.)
You count the pixels on the CRT: 40 wide and 6 high. This CRT screen draws the top row of pixels left-to-right, then the row below that, and so on. The left-most pixel in each row is in position 0, and the right-most pixel in each row is in position 39.
Like the CPU, the CRT is tied closely to the clock circuit: the CRT draws a single pixel during each cycle. Representing each pixel of the screen as a #, here are the cycles during which the first and last pixel in each row are drawn:
Cycle 1 -> ######################################## <- Cycle 40 Cycle 41 -> ######################################## <- Cycle 80 Cycle 81 -> ######################################## <- Cycle 120 Cycle 121 -> ######################################## <- Cycle 160 Cycle 161 -> ######################################## <- Cycle 200 Cycle 201 -> ######################################## <- Cycle 240So, by carefully timing the CPU instructions and the CRT drawing operations, you should be able to determine whether the sprite is visible the instant each pixel is drawn. If the sprite is positioned such that one of its three pixels is the pixel currently being drawn, the screen produces a lit pixel (#); otherwise, the screen leaves the pixel dark (.).
The first few pixels from the larger example above are drawn as follows:
Sprite position: ###..................................... Start cycle 1: begin executing addx 15 During cycle 1: CRT draws pixel in position 0 Current CRT row: # During cycle 2: CRT draws pixel in position 1 Current CRT row: ## End of cycle 2: finish executing addx 15 (Register X is now 16) Sprite position: ...............###...................... Start cycle 3: begin executing addx -11 During cycle 3: CRT draws pixel in position 2 Current CRT row: ##. During cycle 4: CRT draws pixel in position 3 Current CRT row: ##.. End of cycle 4: finish executing addx -11 (Register X is now 5) Sprite position: ....###................................. Start cycle 5: begin executing addx 6 During cycle 5: CRT draws pixel in position 4 Current CRT row: ##..# During cycle 6: CRT draws pixel in position 5 Current CRT row: ##..## End of cycle 6: finish executing addx 6 (Register X is now 11) Sprite position: ..........###........................... Start cycle 7: begin executing addx -3 During cycle 7: CRT draws pixel in position 6 Current CRT row: ##..##. During cycle 8: CRT draws pixel in position 7 Current CRT row: ##..##.. End of cycle 8: finish executing addx -3 (Register X is now 8) Sprite position: .......###.............................. Start cycle 9: begin executing addx 5 During cycle 9: CRT draws pixel in position 8 Current CRT row: ##..##..# During cycle 10: CRT draws pixel in position 9 Current CRT row: ##..##..## End of cycle 10: finish executing addx 5 (Register X is now 13) Sprite position: ............###......................... Start cycle 11: begin executing addx -1 During cycle 11: CRT draws pixel in position 10 Current CRT row: ##..##..##. During cycle 12: CRT draws pixel in position 11 Current CRT row: ##..##..##.. End of cycle 12: finish executing addx -1 (Register X is now 12) Sprite position: ...........###.......................... Start cycle 13: begin executing addx -8 During cycle 13: CRT draws pixel in position 12 Current CRT row: ##..##..##..# During cycle 14: CRT draws pixel in position 13 Current CRT row: ##..##..##..## End of cycle 14: finish executing addx -8 (Register X is now 4) Sprite position: ...###.................................. Start cycle 15: begin executing addx 13 During cycle 15: CRT draws pixel in position 14 Current CRT row: ##..##..##..##. During cycle 16: CRT draws pixel in position 15 Current CRT row: ##..##..##..##.. End of cycle 16: finish executing addx 13 (Register X is now 17) Sprite position: ................###..................... Start cycle 17: begin executing addx 4 During cycle 17: CRT draws pixel in position 16 Current CRT row: ##..##..##..##..# During cycle 18: CRT draws pixel in position 17 Current CRT row: ##..##..##..##..## End of cycle 18: finish executing addx 4 (Register X is now 21) Sprite position: ....................###................. Start cycle 19: begin executing noop During cycle 19: CRT draws pixel in position 18 Current CRT row: ##..##..##..##..##. End of cycle 19: finish executing noop Start cycle 20: begin executing addx -1 During cycle 20: CRT draws pixel in position 19 Current CRT row: ##..##..##..##..##.. During cycle 21: CRT draws pixel in position 20 Current CRT row: ##..##..##..##..##..# End of cycle 21: finish executing addx -1 (Register X is now 20) Sprite position: ...................###..................Allowing the program to run to completion causes the CRT to produce the following image:
##..##..##..##..##..##..##..##..##..##.. ###...###...###...###...###...###...###. ####....####....####....####....####.... #####.....#####.....#####.....#####..... ######......######......######......#### #######.......#######.......#######.....Render the image given by your program. What eight capital letters appear on your CRT?
Our second software we can run on our CPU is a graphics program.
For each cycle, we check if the register is +/- of the index (since cycles start on 1 but index on 0, we need to subtract 1). Since each line is 40 pixels, we need to take the modulo (%) to map our index (0-239) into the correct position in the line (0-39).
If the register value matches, we print # and if not, we print ..
At the end of each line, we print a line break.
def display(program):
line_length = 40
for cycle, register in interpreter(program):
if register-1 <= (cycle-1) % line_length <= register+1:
print('#', end="")
else:
print('.', end="")
if cycle % line_length == 0:
print()display(program)
##Should print EFGERURE