Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

Two-Factor Authentication Display

Advent of Code 2016 - Day 8

Day 8: Two-Factor Authentication

Useful Links

‹›

Concepts and Packages Demonstrated

NumPyRegular ExpressionsList Comprehension

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:

  1. rect AxB: Turns on all pixels in a rectangle of A width and B height, starting from the top-left corner (0,0).
  2. rotate row y=A by B: Shifts all pixels in row A to the right by B pixels. Pixels that move off the right edge reappear on the left.
  3. rotate column x=A by B: Shifts all pixels in column A down by B pixels. 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:

  1. Initialize the grid: Create a 50x6 numpy array filled with zeros (representing off pixels).
  2. Process instructions: Iterate through each instruction, parsing it with regular expressions and applying the corresponding numpy operations.
  3. Count lit pixels: After all instructions are processed, sum all the elements in the numpy array 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:

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

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

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)

Display Animation

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.

‹›