Day 2: Bathroom Security

author: Harshvardhan Pandit

license: MIT

link to problem statement

You arrive at Easter Bunny Headquarters under cover of darkness. However, you left in such a rush that you forgot to use the bathroom! Fancy office buildings like this one usually have keypad locks on their bathrooms, so you search the front desk for the code.

"In order to improve security," the document you find says, "bathroom codes will no longer be written down. Instead, please memorize and follow the procedure below to access the bathrooms."

The document goes on to explain that each button to be pressed can be found by starting on the previous button and moving to adjacent buttons on the keypad: U moves up, D moves down, L moves left, and R moves right. Each line of instructions corresponds to one button, starting at the previous button (or, for the first line, the "5" button); press whatever button you're on at the end of each line. If a move doesn't lead to a button, ignore it.

You can't hold it much longer, so you decide to figure out the code as you walk to the bathroom. You picture a keypad like this:

1 2 3
4 5 6
7 8 9

Suppose your instructions are:

ULL
RRDDD
LURDL
UUUUD

You start at "5" and move up (to "2"), left (to "1"), and left (you can't, and stay on "1"), so the first button is 1.

Starting from the previous button ("1"), you move right twice (to "3") and then down three times (stopping at "9" after two moves and ignoring the third), ending up with 9.

Continuing from "9", you move left, up, right, down, and left, ending with 8. Finally, you move up four times (stopping at "2"), then down once, ending with 5. So, in this example, the bathroom code is 1985.

Your puzzle input is the instructions from the document you found at the front desk. What is the bathroom code?

Solution logic

This is quite similar to the previous problem. We have a grid that we traverse. In this case, it is a fixed grid, with only 9 points. For simplicity, we can select 7 as the origin so that all points lie in the first quadrant (all values are positive). Every movement (left, right, up, down) can be mapped into a movement along the axis.

Alternatively, we can start at 1 (0,0) as this allows some simple math to get the position of the number using mod and division. To get the number from the position, we do (y * 3 + x + 1).

Which gives us:

NUMBER    9-origin    1-origin    (y * 3)  (x + 1)  (y * 3 + x + 1)
  1         (0,2)       (0,0)       0        1        1
  2         (1,2)       (1,0)       0        2        2
  3         (2,2)       (2,0)       0        3        3
  4         (0,1)       (0,1)       3        1        4
  5         (1,1)       (1,1)       3        2        5
  6         (2,1)       (2,1)       3        3        6
  7         (0,0)       (0,2)       3        1        7
  8         (1,0)       (1,2)       3        2        8
  9         (2,0)       (2,2)       3        3        9

SYMBOL    DIRECTION    X-AXIS    Y-AXIS
L         LEFT         -1        0
R         RIGHT        +1        0
U         UP           0         -1
D         DOWN         0         +1

To prevent the values from going out of bounds, we take the mod of each operation with an upper bound for each direction. To put it simply - we cap the values of each direction.

DIRECTION     CAPPED VALUE                   FUNCTION
UP            3 (max value is 2)             x % 3
DOWN          0 (max value is 0, min is 2)   x < 0 ? 0 : x
LEFT          0 (max value is 0, min is 2)   x < 0 ? 0 : x
RIGHT         3 (max value is 2)             x % 3

Algorithm:

- Set starting position to number 5 (1,1)
- For each line of input, do the following (handle as a different number)
- Tokenise each character, and identify the direction
- Apply the direction mask to the position and apply the capping function
- At the end of input, add the number of code (as a string, just append it)

Get number from co-ordinate

Apply the function to get the number


In [1]:
def numpad_number_from_point(point):
    return str(point.y * 3 + point.x + 1)

Point

Since each movement is along some direction, we go about this in a very pretentious and academic way. By declaring classes and objects and functions for everything. The end logic is a clean layout of the solution.

The Point class has attributes x and y. We use setter and getter to set the caps on these values.


In [2]:
class Point:
    def __init__(self, x=0, y=0):
        self._x, self._y = x, y
    
    @property
    def x(self):
        return self._x
    
    @property
    def y(self):
        return self._y
    
    @x.setter
    def x(self, value):
        if 0 <= value <= 2:
            self._x = value
    
    @y.setter
    def y(self, value):
        if 0 <= value <= 2:
            self._y = value  
    
    def __str__(self):
        return '(%s, %s)' % (self._x, self._y)

Directions

We use a dictionary to store the directions and the masks they represent. Each mask is a namedtuple having attributes x and y.


In [3]:
from collections import namedtuple
Mask = namedtuple('Mask', ('x', 'y'))
directions = {
    'U': Mask(0, -1),
    'D': Mask(0, 1),
    'L': Mask(-1, 0),
    'R': Mask(1, 0),
}

Solve

code holds the input code, and is a string.


In [4]:
code = ''

point is the point we are moving on the graph


In [5]:
point = Point(1, 1)

Reading in the input from file


In [6]:
with open('../inputs/day02.txt', 'r') as f:
    data = f.readlines()

Define a function that will parse the number from each line of input. We supply it the line.


In [7]:
def calculate_number(line):
    for char in line:
        mask = directions[char]
        point.x += mask.x
        point.y += mask.y
    return numpad_number_from_point(point)

In [8]:
for line in data:
    code += calculate_number(line.strip())

Answer lies in the variable code

Part Two

You finally arrive at the bathroom (it's a several minute walk from the lobby so visitors can behold the many fancy conference rooms and water coolers on this floor) and go to punch in the code. Much to your bladder's dismay, the keypad is not at all like you imagined it. Instead, you are confronted with the result of hundreds of man-hours of bathroom-keypad-design meetings:

    1
  2 3 4
5 6 7 8 9
  A B C
    D

You still start at "5" and stop when you're at an edge, but given the same instructions as above, the outcome is very different:

You start at "5" and don't move at all (up and left are both edges), ending at 5.

Continuing from "5", you move right twice and down three times (through "6", "7", "B", "D", "D"), ending at D.

Then, from "D", you move five more times (through "D", "B", "C", "C", "B"), ending at B.

Finally, after five more moves, you end at 3.

So, given the actual keypad layout, the code would be 5DB3.

Using the same instructions in your puzzle input, what is the correct bathroom code?

Solution logic

Since the keypad design has changed, we need to change our approach as well. In the new keypad, the grid is no longer symmetrical, so we cannot apply the mod logic to this keypad. The simplest approach would be to define each point in a dictionary with their co-ordinates, starting with 7 as the origin. This would allow the points to span in all four quadrants. Then we need to change the setters to accomodate the new co-ordinates, and finally, the numpad function to get the correct number using the dictionary.

Numbers

The numbers dictionary holds the co-ordinates for each key on the numpad. At the end, we can simply lookup the co-ordinate points and get the corresponding number. The number_keys allows the easier declaration of syntax, which is then inverted using the numbers_values dictionary.


In [9]:
numbers_keys = {
    '1': Mask(0, 2),
    '2': Mask(-1, 1),
    '3': Mask(0, 1),
    '4': Mask(1, 1),
    '5': Mask(-2, 0),
    '6': Mask(-1, 0),
    '7': Mask(0, 0),
    '8': Mask(1, 0),
    '9': Mask(2, 0),
    'A': Mask(-1, -1),
    'B': Mask(0, -1),
    'C': Mask(1, -1),
    'D': Mask(0, -2)
}
numbers_values = {v:k for k,v in numbers_keys.items()}

Point

We redefine the point class with updated setters for x and y. The new setters do nothing, and the actual update is done through the xy method, which takes in the two values. This checks whether the given values are in the correct range.


In [10]:
class Point:
    def __init__(self, x=0, y=0):
        self._x, self._y = x, y
    
    @property
    def x(self):
        return self._x
    
    @property
    def y(self):
        return self._y
    
    @x.setter
    def x(self, value):
        pass
    
    @y.setter
    def y(self, value):
        pass
    
    def xy(self, x, y):
        if (
            (-2 <= x <= 2 and y == 0) or
            (-1 <= x <= 1 and -1 <= y <= 1) or
            (x == 0 and -2 <= y <= 2)):
                
            self._x, self._y = x, y            
    
    def __str__(self):
        return '(%s, %s)' % (self._x, self._y)
    
    def __repr__(self):
        return '(%s, %s)' % (self._x, self._y)

Calculate Number

The updated method uses the new xy method to assign the values. Since we assume point to be global (in this scope), we directly use it.


In [11]:
def calculate_number(line):
    for char in line:
        mask = directions[char]
        point.xy(point.x + mask.x, point.y + mask.y)

keys holds the characters of the keypad code


In [12]:
keys = []

Directions

We must also update the directions, as we have changed the order of the numbers on the keypad. This involves reversing the sign of the UP and DOWN directions.


In [13]:
directions = {
    'U': Mask(0, 1),
    'D': Mask(0, -1),
    'L': Mask(-1, 0),
    'R': Mask(1, 0),
}

Point

The starting point for this problem is 5, which we retrieve using the dictionary.


In [14]:
point = Point(*numbers_keys['5'])

Keypad code

We run the keypad code over each line and store the result in keys.


In [15]:
for line in data:
    calculate_number(line.strip())
    keys.append(numbers_values[Mask(point.x, point.y)])

In [16]:
answer = ''.join(keys)

== END ==