Page Navigation
Problem Intro
This puzzle presents us with a damaged two-factor authentication display, a 50x6 pixel screen that starts completely off. We need to process a series of instructions to manipulate the pixels on this screen. The instructions come in three forms:
rect AxB: Turns on all pixels in a rectangle ofAwidth andBheight, starting from the top-left corner (0,0).rotate row y=A by B: Shifts all pixels in rowAto the right byBpixels. Pixels that move off the right edge reappear on the left.rotate column x=A by B: Shifts all pixels in columnAdown byBpixels. Pixels that move off the bottom edge reappear at the top.
The input data consists of a list of these instructions, for example:
rect 3x2
rotate column x=1 by 1
rotate row y=0 by 4
rotate column x=1 by 1
Part 1
How many pixels are lit after all instructions are executed?
The core of this problem is simulating the pixel grid and applying the operations. Given the grid-like nature of the problem and the need for efficient manipulation of rows and columns, numpy arrays are an excellent choice.
My strategy for Part 1 is as follows:
- Initialize the grid: Create a 50x6
numpyarray filled with zeros (representing off pixels). - Process instructions: Iterate through each instruction, parsing it with regular expressions and applying the corresponding
numpyoperations. - Count lit pixels: After all instructions are processed, sum all the elements in the
numpyarray to get the total number of lit pixels.
Why NumPy?
For a problem that involves a grid of numbers and requires operations on rows and columns, numpy is the ideal tool. Here’s why:
- Performance:
numpyarrays are implemented in C and are much faster for numerical operations than standard Python lists. - Convenience:
numpyprovides a rich set of functions for array manipulation. Slicing, which we use extensively here, is incredibly powerful and concise. - Broadcasting: Although not used heavily in this specific solution,
numpy’s broadcasting capabilities allow for efficient operations between arrays of different shapes and sizes.
Solution Code - Part 1
import logging
import os
import re
import numpy as np
SCRIPT_DIR = os.path.dirname(__file__)
INPUT_FILE = "input/input.txt"
rect_pattern = re.compile(r"rect (\d+)x(\d+)")
shift_pattern = re.compile(r"rotate [a-z]* (.)=(\d+) by (\d+)")
def main():
logging.basicConfig(level=logging.DEBUG, format="%(asctime)s:%(levelname)s:\t%(message)s")
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
data = f.read().splitlines()
np.set_printoptions(linewidth=150) # For better printing of the numpy array
cols = 50
rows = 6
# Part 1
grid = np.zeros((rows, cols), dtype=np.int8)
process_instructions(data, grid)
print("Part 1")
print("------")
print(f"Pixels lit: {grid.sum()}")
def process_instructions(data, grid):
for line in data:
if "rect" in line:
x_size, y_size = rect_pattern.search(line).groups()
x_size, y_size = map(int, [x_size, y_size])
# Set all the pixels in this rect to 1
grid[0:y_size, 0:x_size] = 1
else:
axis, val, shift = shift_pattern.search(line).groups()
val, shift = map(int, [val, shift])
if axis == 'x': # Rotate column
# np.roll is a more direct way to do this
grid[:, val] = np.roll(grid[:, val], shift)
else: # Rotate row
grid[val, :] = np.roll(grid[val, :], shift)
if __name__ == "__main__":
main()
Explanation
numpy.zeros((rows, cols), dtype=np.int8): This creates our 6x50 pixel grid, initialized with all0s.np.int8is used to save memory as pixels are either 0 or 1.- Regular Expressions (
re):rect_pattern = re.compile(r"rect (\d+)x(\d+)"): This regex captures the width and height forrectinstructions.\d+matches one or more digits.shift_pattern = re.compile(r"rotate [a-z]* (.)=(\d+) by (\d+)"): This more complex regex captures the axis (xory), the index (val), and the amount ofshiftforrotateinstructions.
- Applying
rectinstructions:grid[0:y_size, 0:x_size] = 1directly sets the slice of thenumpyarray corresponding to the rectangle to1. This is a very efficientnumpyoperation. - Applying
rotateinstructions: Instead of converting to a list and back, we can use thenumpy.roll()function. This function shifts the elements of an array along a given axis. This is a more direct and “NumPy-onic” way to perform the rotation. grid.sum(): After all operations, thisnumpymethod quickly sums all1s in the array, giving us the count of lit pixels.
Part 2
You notice the screen is still on; in fact, it’s showing a message. What message is being displayed?
For Part 2, we need to visually interpret the final state of the grid. The solution code already has the logic to print the grid.
Solution Code - Part 2
# Part 2
print("\nPart 2")
print("------")
grid_list = grid.tolist()
rendered = "\n".join(["".join(["*" if char == 1 else " " for char in line])
for line in grid_list])
print(rendered)
Explanation
grid.tolist(): Converts thenumpyarray back into a standard Python list of lists.- List Comprehension for Rendering:
["*" if char == 1 else " " for char in line]: This inner list comprehension iterates through eachchar(pixel value) in aline(row) of the grid. If the pixel is1(on), it’s replaced with an asterisk*; otherwise, it’s a space ` `"".join(...): Joins these characters to form a string representing a single row."\n".join(...): Joins all the row strings with newline characters to create the final multi-line string representation of the display.
This approach effectively renders the pixel grid, allowing us to read the hidden message.
Results
Part 1
------
Pixels lit: 121
Part 2
------
*** * * *** * * ** **** ** **** *** *
* * * * * * * * * * * * * * * *
* * * * * * * * * *** * * *** * *
*** * * *** * * * * * * * * *
* * * * * * * * * * * * * * * *
* * ** * * ** ** **** ** **** *** ****
Visualisation
An animation is a great way to see how the display changes over time. We can use matplotlib and imageio to create a GIF of the process.
I’ll need to modify the process_instructions function to yield the grid state after each instruction. Then, I can use a separate script to generate the animation.
Note: The animation code is not included in the main solution but is provided here as an example of how to create a visualisation.
# animation.py
import imageio
import matplotlib.pyplot as plt
import numpy as np
from display_pixels import process_instructions, rect_pattern, shift_pattern
def generate_animation(data):
cols = 50
rows = 6
grid = np.zeros((rows, cols), dtype=np.int8)
frames = []
for line in data:
process_instructions([line], grid)
fig, ax = plt.subplots(figsize=(10, 2))
ax.imshow(grid, cmap='gray_r', interpolation='nearest')
ax.axis('off')
fig.canvas.draw()
image = np.frombuffer(fig.canvas.tostring_rgb(), dtype='uint8')
image = image.reshape(fig.canvas.get_width_height()[::-1] + (3,))
frames.append(image)
plt.close(fig)
imageio.mimsave('docs/assets/images/2016-08-animation.gif', frames, fps=10)
if __name__ == "__main__":
with open("src/AoC_2016/d8_display_numpy/input/input.txt", mode="rt") as f:
data = f.read().splitlines()
generate_animation(data)

Conclusion
This puzzle was a great exercise in grid manipulation and string parsing. The use of numpy significantly simplified the grid operations, especially for the rect and rotate commands, making the solution concise and efficient. Regular expressions proved invaluable for robustly parsing the varied instruction formats.