Advent of Code 2016 - Day 2

Useful Links

Concepts and Packages Demonstrated

Problem Intro

We need to find the code to a bathroom, and the instructions are a series of moves on a keypad. The input is a list of strings, where each string represents a sequence of moves. ‘U’ is up, ‘D’ is down, ‘L’ is left, and ‘R’ is right.

For example:

ULL
RRDDD
LURDL
UUUUD

We start at ‘5’ on a standard 3x3 keypad. Each line of instructions gives us one digit of the code.

Part 1

What is the bathroom code?

My approach is to represent the keypad as a 2D numpy array. This makes it easy to move around using array indices. I’ll keep track of the current position (row and column) and update it based on the instructions. If a move would take me off the keypad, I’ll ignore it.

Why `numpy`?

For a puzzle like this that involves a grid and movement, numpy is an excellent choice. numpy is a powerful library for numerical computing in Python, and its core data structure, the ndarray (n-dimensional array), is perfect for this kind of problem.

Here’s why numpy is so useful here:

Intuitive Representation: A 2D numpy array is a natural and intuitive way to represent a grid or matrix, like the keypad in this puzzle. It’s a direct translation of the problem’s structure into code.
Efficient Indexing: numpy provides fast and easy indexing to access and manipulate elements in the array. Accessing a specific button on the keypad is as simple as keypad[row, col]. This is much cleaner and more efficient than using nested lists.
Array Properties: numpy arrays have useful properties like .shape, which I use to get the dimensions of the keypad (number of rows and columns). This is helpful for checking if a move would go off the edge of the grid.
Broadcasting and Vectorization: While not used extensively in this particular solution, numpy’s ability to perform operations on entire arrays at once (vectorization) can lead to highly efficient and readable code, especially in more complex grid-based puzzles.
Data Types: numpy arrays can handle a wide variety of data types, including numbers, strings, and mixed types. This is particularly useful in Part 2, where the keypad contains numbers, letters, and spaces.

Here’s the get_combo function that does the heavy lifting:

def get_combo(keypad: np.ndarray, instructions: list, row: int, col: int) -> list:
    """ Process a list of keypad navigation instructions.
    At the end of each line, store the current button position.

    Args:
        keypad (np.ndarray): The 2D array that represents the keypad
        instructions (list): List of navigation instructions, in the format U, D, L, R
        row (int): The starting row.
        col (int): The starting col.

    Returns:
        list: The sequence of keypresses.
    """
    rows, cols = keypad.shape
    logging.debug(f"\n{keypad}")
    logging.debug(f"Starting button: {keypad[row, col]}")
    keypresses = []
    
    for line in instructions:
        for char in line:
            col += NavigationConstants.VECTORS[char][0]
            row += NavigationConstants.VECTORS[char][1]
            
            # if we've gone off the edge, then set the col and row to edge
            if col < 0: 
                col = 0
            if col > cols-1: 
                col = cols-1
            if row < 0: 
                row  = 0
            if row > rows-1: 
                row = rows-1
            
        keypresses.append(str(keypad[row][col]))
        
    return keypresses

I use a dictionary to map the ‘U’, ‘D’, ‘L’, ‘R’ characters to changes in the row and column indices. After each full line of instructions, I append the resulting keypad digit to my list of keypresses.

For Part 1, the keypad is a simple 3x3 grid. I use np.arange(1, 10).reshape(3, 3) to create this keypad.

Let’s break this down:

np.arange(1, 10): This function from the numpy library creates a 1D array (a vector) containing a sequence of numbers. The arguments 1 and 10 specify the start and end of the range. Note that the range is exclusive of the end value, so this creates an array with the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9.
.reshape(3, 3): This is a method of the numpy array object. It reshapes the 1D array into a 2D array (a matrix) with the specified dimensions. In this case, it creates a 3x3 grid.

The resulting keypad array looks like this:

[[1 2 3]
 [4 5 6]
 [7 8 9]]

To access an element in this 2D array, you use the syntax array[row, col]. For example, to get the starting number ‘5’, which is in the second row and second column (remembering that array indices are 0-based), you would use keypad[1, 1].

Part 2

What is the bathroom code using this new keypad?

Part 2 introduces a more complex keypad:

I represent this as a 5x5 numpy array with spaces for the blank areas. This is where using a numpy array really shines. When you create a numpy array from a list of lists containing mixed data types (in this case, strings of numbers, letters, and spaces), numpy is smart enough to determine the most appropriate data type for the array that can accommodate all the elements. In this case, it will create an array of strings.

keypad = np.array([[" ", " ", "1", " ", " "],
                   [" ", "2", "3", "4", " "],
                   ["5", "6", "7", "8", "9"],
                   [" ", "A", "B", "C", " "],
                   [" ", " ", "D", " ", " "]])

The logic for moving around the keypad needs a small addition. If a move lands on a space, the move is invalid and I reverse it. I can check the value of the current position by accessing the array with keypad[row, col].

            # if current array position is ' ', then reverse (ignore) last instruction
            if str(keypad[row][col]) == ' ':
                col -= NavigationConstants.VECTORS[char][0]
                row -= NavigationConstants.VECTORS[char][1]

The rest of the get_combo function remains the same. I just call it with the new keypad and a different starting position.

This numpy-based approach is quite clean and handles both parts of the puzzle with minimal code changes. The use of a 2D array is a natural fit for representing the keypad and makes the movement logic straightforward.

‹›