Day 8: Two-Factor Authentication

author: Harshvardhan Pandit

license: MIT

link to problem statement

You come across a door implementing what you can only assume is an implementation of two-factor authentication after a long game of requirements telephone.

To get past the door, you first swipe a keycard (no problem; there was one on a nearby desk). Then, it displays a code on a little screen, and you type that code on a keypad. Then, presumably, the door unlocks.

Unfortunately, the screen has been smashed. After a few minutes, you've taken everything apart and figured out how it works. Now you just have to work out what the screen would have displayed.

The magnetic strip on the card you swiped encodes a series of instructions for the screen; these instructions are your puzzle input. The screen is 50 pixels wide and 6 pixels tall, all of which start off, and is capable of three somewhat peculiar operations:

  • rect AxB turns on all of the pixels in a rectangle at the top-left of the screen which is A wide and B tall.
  • rotate row y=A by B shifts all of the pixels in row A (0 is the top row) right by B pixels. Pixels that would fall off the right end appear at the left end of the row.
  • rotate column x=A by B shifts all of the pixels in column A (0 is the left column) down by B pixels. Pixels that would fall off the bottom appear at the top of the column.

For example, here is a simple sequence on a smaller screen:

rect 3x2 creates a small rectangle in the top-left corner:

###....
###....
.......

rotate column x=1 by 1 rotates the second column down by one pixel:

#.#....
###....
.#.....

rotate row y=0 by 4 rotates the top row right by four pixels:

....#.#
###....
.#.....

rotate row x=1 by 1 again rotates the second column down by one pixel, causing the bottom pixel to wrap back to the top:

.#..#.#
#.#....
.#.....

As you can see, this display technology is extremely powerful, and will soon dominate the tiny-code-displaying-screen market. That's what the advertisement on the back of the display tries to convince you, anyway.

There seems to be an intermediate check of the voltage used by the display: after you swipe your card, if the screen did work, how many pixels should be lit?

Solution logic

Since solving the problem depends on keeping track of the pixels on screen, we need to store the display and track the pixels. An easy way to do this is to create a tuple for the display holding the pixels as a set of boolean values. True if the pixel is ON, and False otherwise. We store the height of the display in two variables, DISPLAY_ROWS and DISPLAY_COLS.

display = [[False for i in range(0, DISPLAY_COLS)] for i in range(0, DISPLAY_ROWS)]

The rect function turns on all the pixels in the given area denoted by A and B, starting form the top left corner of the display. So the function starts at row 0, col 0 and turns on all pixels until row A, col B.

The rotate functions shift the pixels by the given offset. In case of rows, it shifts right, and in case of columns, it shifts left. Additionally, the display is rotating, as in the pixels that go out at the end are added back in towards the beginning.

rotate row is fairly trivial to write since we are storing the display row-wise. We only need to cut (the technical term is splice) the row at the specified offset and put it back together with the order reversed.

rotate row A by B positions
    row A = row[-B:] + row[:-B]

The negative offset in python trims the list from the other end, so it gets the last B values with row[-B:] and everything except the last B values with row[:-B] and then adds them together.

rotate col requires the same operations, but by moving through columns, which means some fixed index in every row.

rotate col A by B positions
    col A = row[A] for all rows
    treat col as row, and rotate row by B positions
    copy col back to display


Parsing the input - since the input is a fixed format line where we need to extract the values, we can use regex to match and extract the values. There is an instructions dictionary with patterns that have associated handlers to perform the correct operations.

instructions:
    rect (\d+)x(\d+)'): rect - turn on pixels
    rotate row y=(\d+) by (\d+): rotate_row - shift row
    rotate column x=(\d+) by (\d+): rotate_col - shift col

Calculating lit pixels is simply counting the number of True values in the display lists. Instead of using a for loop to iterate over it, we use the much handy sum function that counts all truthy values.

Creating the display matrix (or list of lists)


In [1]:
DISPLAY_ROWS = 6   # screen is  6 pixels tall
DISPLAY_COLS = 50  # screen is 50 pixels wide 
display = [  # set display pixels to False
    [False for i in range(0, DISPLAY_COLS)]
    for i in range(0, DISPLAY_ROWS)]

Instructions patterns and handlers


In [2]:
def rect(display, a, b):
    '''rect AxB turns on all of the pixels in a rectangle at the top-left of the screen which is A wide and B tall'''
    # a: col b: row
    for i in range(0, b):
        for j in range(0, a):
            display[i][j] = True

            
def rotate_row(display, a, b):
    '''rotate row y=A by B shifts all of the pixels in row A (0 is the top row) right by B pixels'''
    display[a] = display[a][-b:] + display[a][:-b]

    
def rotate_col(display, a, b):
    '''rotate column x=A by B shifts all of the pixels in column A (0 is the left column) down by B pixels'''
    new_col_a = [display[i][a] for i in range(DISPLAY_ROWS - b, DISPLAY_ROWS)]
    new_col_b = [display[i][a] for i in range(0, DISPLAY_ROWS - b)]
    new_col = new_col_a + new_col_b
    for i in range(0, DISPLAY_ROWS):
        display[i][a] = new_col[i]

import re
instructions = {
    re.compile(r'rect (\d+)x(\d+)'): rect,
    re.compile(r'rotate row y=(\d+) by (\d+)'): rotate_row,
    re.compile(r'rotate column x=(\d+) by (\d+)'): rotate_col,
}

Retrieving the input


In [3]:
with open('../inputs/day08.txt', 'r') as f:
    data = [line.strip() for line in f.readlines()]
#     TEST DATA from problem description
#     data = [
#         'rect 3x2',
#         'rotate column x=1 by 1',
#         'rotate row y=0 by 4',
#         'rotate column x=1 by 1'
#     ]

In [4]:
for line in data:
    for pattern, handler in instructions.items():
        match = pattern.match(line)
        if match:
            inputs = [int(i) for i in match.groups()]
            handler(display, *inputs)
            break
    else:
        print('ERROR', line)

Counting number of pixels that are ON


In [5]:
def display_pixels_lit(display):
    '''return number of pixels that are ON'''
    return sum(sum(row) for row in display)

display_pixels_lit(display)


Out[5]:
116

Part Two

You notice that the screen is only capable of displaying capital letters; in the font it uses, each letter is 5 pixels wide and 6 tall.

After you swipe your card, what code is the screen trying to display?

Solution logic

To get the letters without any fuss, we simply print out the display on screen and then identify what letters are present and type them out. No fancy letter shapes stored in data structures matched at runtime.


In [6]:
def print_display(display):
    for row in display:
        print(''.join(['#' if i else '.' for i in row]))
        
print_display(display)


#..#.###...##....##.####.#....###...##..####.####.
#..#.#..#.#..#....#.#....#....#..#.#..#.#.......#.
#..#.#..#.#..#....#.###..#....###..#....###....#..
#..#.###..#..#....#.#....#....#..#.#....#.....#...
#..#.#....#..#.#..#.#....#....#..#.#..#.#....#....
.##..#.....##...##..#....####.###...##..####.####.

== END ==