Advent of Code 2016 - Day 8

Day 8: Two-Factor Authentication

Useful Links

‹

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

NumPyRegular ExpressionsList Comprehension

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.

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
                seq_data = list(grid[:, val])
                shifted = seq_data[-shift:] + seq_data[:-shift]
                grid[:, val] = shifted
            else: # Rotate row
                seq_data = list(grid[val, :])
                shifted = seq_data[-shift:] + seq_data[:-shift]
                grid[val, :] = shifted

if __name__ == "__main__":
    main()

Explanation

• numpy.zeros((rows, cols), dtype=np.int8): This creates our 6x50 pixel grid, initialized with all 0s. np.int8 is 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 for rect instructions. \d+ matches one or more digits.
  • shift_pattern = re.compile(r"rotate [a-z]* (.)=(\d+) by (\d+)"): This more complex regex captures the axis (x or y), the index (val), and the amount of shift for rotate instructions.
• Applying rect instructions: grid[0:y_size, 0:x_size] = 1 directly sets the slice of the numpy array corresponding to the rectangle to 1. This is a very efficient numpy operation.
• Applying rotate instructions:
  • grid[:, val] selects an entire column, and grid[val, :] selects an entire row.
  • The slicing seq_data[-shift:] + seq_data[:-shift] performs the rotation. For example, [1, 2, 3, 4] shifted by 1 becomes [4] + [1, 2, 3] = [4, 1, 2, 3]. This is a common Python idiom for list rotation.
  • The shifted list is then assigned back to the numpy array slice, updating the grid.
• grid.sum(): After all operations, this numpy method quickly sums all 1s 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 the numpy array 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 each char (pixel value) in a line (row) of the grid. If the pixel is 1 (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.

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.

‹