Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 10
Useful Links
Concepts and Packages Demonstrated
ClassMatplotliblist comprehensionIntrospectionzip
Page Navigation
Problem Intro
Not too bad, this one. But it still took me a couple of hours. I think my brain wasn’t working properly this morning.
We’re told we have a We have a CRT CPU that processes instructions. It has a single register, x. There is only one instruction that modifies x, called addx. The other instruction, noop, does nothing.
The input is our instructions, and it looks something like this:
addx 15
addx -11
addx 6
addx -3
addx 5
addx -1
addx -8
addx 13
addx 4
noop
addx -1
Instructions start on a given clock cycle, aka tick. The addx instruction requires 2 ticks; noop takes only 1. We’re also told that signal strength is given by the product of the current cycle, and the current value in register x.
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?
Here’s my strategy:
- Create a
CrtComputerclass that takes instructions as a parameter.- Track the current instruction in an instruction pointer.
- Track which instruction was last started, by storing it to a
self._doingproperty.- This property contains both the instruction itself (command and value), and the number of cycles required to complete it.
- We will decrement this cycles required count with each tick.
- When the value reaches 0, we can complete the task the instruction was meant to do.
- Externalise a tick method. This:
- Increments the cycle.
- If an instruction is ready to complete, it executes the completion by retrieving the instruction from
self._doing. It then starts the next instructions.
- Provide a method to calculate and return the signal strength at any time.
- Externalise a property to inform the caller when the program is finished.
- From the calling application, tick the computer for as long as the program hasn’t completed.
- With each tick, check if we’re on one of our required cycles. If so, retrieve the signal strength and store it.
- Finally, add up our signal strengths.
The code looks like this:
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
class CrtComputer():
""" Performs instructions. Add instructions take 2 ticks. Noop takes 1 tick. """
def __init__(self, instructions: list[str]) -> None:
self._x = 1 # represents middle of horizontal sprite position
self._instructions = self._convert_to_instructions(instructions)
self._ip = 0 # instruction pointer
self.cycle = 0
self._doing = [] # [[instruction], duration]
self.running_program = True # Set to false when instructions are complete
@property
def x(self):
return self._x
@property
def signal_strength(self) -> int:
return self.cycle * self.x
def _convert_to_instructions(self, data: list[str]):
""" Create a list of instructions in [[instr, val],[],...] format. """
instructions = []
for line in data:
line_words = line.split()
instr = line_words[0]
val = None
if len(line_words) > 1:
val = int(line_words[1])
instructions.append((instr, val))
return instructions
def tick(self):
""" Perform one CPU cycle """
# print(self)
if len(self._doing) > 0: # we're processing an instruction
self._doing[1] -= 1
if self._doing[1] == 0:
# Complete the running instruction
instruction = self._doing[0]
self.__getattribute__(f"_op_{instruction[0]}")(instruction)
# print(f"Completed instruction: {instruction}")
self._start_next_instruction() # and start the next one
else: # our first instruction
self._start_next_instruction()
self.cycle += 1
def _start_next_instruction(self):
""" Takes an instruction, and calls the appropriate implementation method. """
instruction = self._instructions[self._ip]
# print(f"Starting instruction: {instruction}")
if instruction[0] == "addx":
self._doing = [instruction, 2]
elif instruction[0] == "noop":
self._doing = [instruction, 1]
self._ip += 1 # increment the instruction pointer
if self._ip == len(self._instructions): # we've finished
self.running_program = False
def _op_addx(self, instruction: tuple):
""" Takes 2 cycles. Adds val to register x """
self._x += instruction[-1]
def _op_noop(self, _: tuple):
""" Takes 1 cycle. Does nothing. Instruction parameter will be empty. """
def __repr__(self):
return f"{self.__class__.__name__}(Cycle={self.cycle};x={self._x},pixel={self._display_posn})"
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
# Part 1
interesting_cycles = [20, 60, 100, 140, 180, 220]
signal_strength_sum = 0
crt_computer = CrtComputer(data)
while crt_computer.running_program:
crt_computer.tick()
if crt_computer.cycle in interesting_cycles:
signal_strength_sum += crt_computer.signal_strength
print(signal_strength_sum)
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
Part 2
We’re told that we have a 40x6 display. With each tick, the current pixel is incremented by 1. The movement is across, then down… Like a typewriter.
We’re told that the x register stores the middle x (row) position of a sprite, which is itself three pixels wide. We’re told that if the current display pixel coincides with any of the three horizontal pixels that make up the sprite, then this pixel is lit. Else, the pixel is dark.
Render the image given by your program. What eight capital letters appear on your CRT?
This bit was quite fun!
I add some class attributes as constants that represent the display, and a lit pixel:
DISPLAY_WIDTH = 40
DISPLAY_HEIGHT = 6
LIT = "#"
Then I initialise some additional attributes in our __init__() method:
self._display_posn = [0,0]
self._display = [[" " for _ in range(CrtComputer.DISPLAY_WIDTH)]
for _ in range(CrtComputer.DISPLAY_HEIGHT)]
I.e. we set the initial pixel position to 0,0. And we use a multi-sequence list comprehension to create a list of lists that represent the display. I.e.
- A list containing 6 rows.
- Each row is a list of 40 single character strings.
- I’ve set all the characters to space, to represent an “empty” display.
Now I create a method to render the display to the console:
def render_display(self):
return "\n".join("".join(row) for row in self._display)
Again, this is just about of string joining and list comprehension, to render a single multiline string.
Now, a method that updates the display:
def _update_display(self):
# Current horizontal pixel position being drawn
x_posn = self._display_posn[0]
# Check if horizontal position is *within* to current sprite position
# The sprite is 3 pixels wide, and the x register gives us the middle position
if x_posn in range(self.x-1, self.x+2):
self._display[self._display_posn[1]][x_posn] = CrtComputer.LIT
# display position moves across the row, then down,
# one pixel at a time with each tick
if x_posn < CrtComputer.DISPLAY_WIDTH-1:
self._display_posn[0] += 1
else:
self._display_posn[0] = 0
self._display_posn[1] += 1
This code is well documented. This is the code that checks if our current pixel is aligned with the current sprite position (given by register x), and if so, sets the current pixel to be lit.
We need to call self._update_display() with each tick. So we add this to our tick() method, just before increasing the cycle count:
self._update_display()
All done!!
Results
The final code looks like this:
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
class CrtComputer():
""" Performs instructions. Add instructions take 2 ticks. Noop takes 1 tick. """
DISPLAY_WIDTH = 40
DISPLAY_HEIGHT = 6
LIT = "#"
def __init__(self, instructions: list[str]) -> None:
self._x = 1 # represents middle of horizontal sprite position
self._instructions = self._convert_to_instructions(instructions)
self._ip = 0 # instruction pointer
self.cycle = 0
self._doing = [] # [[instruction], duration]
self.running_program = True # Set to false when instructions are complete
self._display_posn = [0,0]
self._display = [[" " for _ in range(CrtComputer.DISPLAY_WIDTH)]
for _ in range(CrtComputer.DISPLAY_HEIGHT)]
@property
def x(self):
return self._x
@property
def signal_strength(self) -> int:
return self.cycle * self.x
def _convert_to_instructions(self, data: list[str]):
""" Create a list of instructions in [[instr, val],[],...] format. """
instructions = []
for line in data:
line_words = line.split()
instr = line_words[0]
val = None
if len(line_words) > 1:
val = int(line_words[1])
instructions.append((instr, val))
return instructions
def tick(self):
""" Perform one CPU cycle """
# print(self)
if len(self._doing) > 0: # we're processing an instruction
self._doing[1] -= 1
if self._doing[1] == 0:
# Complete the running instruction
instruction = self._doing[0]
self.__getattribute__(f"_op_{instruction[0]}")(instruction)
# print(f"Completed instruction: {instruction}")
self._start_next_instruction() # and start the next one
else: # our first instruction
self._start_next_instruction()
self._update_display()
self.cycle += 1
def _update_display(self):
# Current horizontal pixel position being drawn
x_posn = self._display_posn[0]
# Check if horizontal position is *within* to current sprite position
# The sprite is 3 pixels wide, and the x register gives us the middle position
if x_posn in range(self.x-1, self.x+2):
self._display[self._display_posn[1]][x_posn] = CrtComputer.LIT
# display position moves across the row, then down,
# one pixel at a time with each tick
if x_posn < CrtComputer.DISPLAY_WIDTH-1:
self._display_posn[0] += 1
else:
self._display_posn[0] = 0
self._display_posn[1] += 1
def _start_next_instruction(self):
""" Takes an instruction, and calls the appropriate implementation method. """
instruction = self._instructions[self._ip]
# print(f"Starting instruction: {instruction}")
if instruction[0] == "addx":
self._doing = [instruction, 2]
elif instruction[0] == "noop":
self._doing = [instruction, 1]
self._ip += 1 # increment the instruction pointer
if self._ip == len(self._instructions): # we've finished
self.running_program = False
def _op_addx(self, instruction: tuple):
""" Takes 2 cycles. Adds val to register x """
self._x += instruction[-1]
def _op_noop(self, _: tuple):
""" Takes 1 cycle. Does nothing. Instruction parameter will be empty. """
def __repr__(self):
return f"{self.__class__.__name__}(Cycle={self.cycle};x={self._x},pixel={self._display_posn})"
def render_display(self):
return "\n".join("".join(row) for row in self._display)
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
# Part 1
interesting_cycles = [20, 60, 100, 140, 180, 220]
signal_strength_sum = 0
crt_computer = CrtComputer(data)
while crt_computer.running_program:
crt_computer.tick()
if crt_computer.cycle in interesting_cycles:
signal_strength_sum += crt_computer.signal_strength
print(f"Part 1: {signal_strength_sum}")
print(f"Part 2:\n{crt_computer.render_display()}")
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
And the output looks like this:
Part 1: 12840
Part 2:
#### # # ## #### ### ## #### ####
# # # # # # # # # #
# ## # ### ### # ### #
# # # # # # # # # #
# # # # # # # # # # # #
#### # # ## # ### ## # ####
Execution time: 0.0010 seconds
That’s pretty quick!
Visualisation
The characters are not very readable! Let’s use Matplotlib to render some pretty output:
All we need to do is add this to our class:
def render_as_plt(self):
""" Render the display as a scatter plot """
all_points = [(x,y) for x in range(CrtComputer.DISPLAY_WIDTH)
for y in range(CrtComputer.DISPLAY_HEIGHT)
if self._display[y][x] == CrtComputer.LIT]
x_vals, y_vals = zip(*all_points)
axes = plt.gca()
axes.set_aspect('equal')
plt.axis("off") # hide the border around the plot axes
axes.set_xlim(min(x_vals)-1, max(x_vals)+1)
axes.set_ylim(min(y_vals)-1, max(y_vals)+1)
axes.invert_yaxis()
axes.scatter(x_vals, y_vals, marker="o", s=50)
plt.show()
Again, it uses some multi-sequence list comprehension to obtain all the points in the display, as (x,y) coordinates. Then we use zip(*all_points) to transpose our list of [x,y] to become a list of x values and a list of y values. This is explained here. Then we’re ready to plot!
The output looks like this:
