Advent of Code 2015 - Day 25

Useful Links

Concepts and Packages Demonstrated

Problem Intro
Part 1
Part 2
Alternative Solution

Problem Intro

We need to turn on Santa’s weather machine. But to turn it on, we need to supply a code from the manual. Unfortunately, we don’t have the manual! We phone tech support, and an engineer tells us:

The codes are printed on an infinite sheet of paper, starting in the top-left corner.
The codes are filled in by diagonals: starting with the first row with an empty first box, the codes are filled in diagonally up and to the right.
This process repeats until the infinite paper is covered.

So, the first few codes are filled in in this order:

   |  1   2   3   4   5   6  
---+---+---+---+---+---+---+
|  1   3   6  10  15  21
|  2   5   9  14  20
|  4   8  13  19
|  7  12  18
| 11  17
| 16

The table above shows the sequence of the codes, not their values. The actual values are determined as follows:

The first code is 20151125.
The nth code is given by the remainder of ([n-1]*252533)//33554393

We’re given the first few numbers, to help us validate our algorithm:

   |    1         2         3         4         5         6
---+---------+---------+---------+---------+---------+---------+
| 20151125  18749137  17289845  30943339  10071777  33511524
| 31916031  21629792  16929656   7726640  15514188   4041754
| 16080970   8057251   1601130   7981243  11661866  16474243
| 24592653  32451966  21345942   9380097  10600672  31527494
|    77061  17552253  28094349   6899651   9250759  31663883
| 33071741   6796745  25397450  24659492   1534922  27995004

Part 1

What code do you give the machine?

The input file specifies the code we require, in the form of a row,column pair.

The key realisation here is that the numbers are filled diagonally from bottom left to top right. So if we’re asked to find the number at row 4, column 3, then we need to know the value at row 5, column 2, and the value at row 6, column 1.

But similarly, if we need to calculate the value at row 6, column 1, then we’ll need to determine the preceding value, which is at row 1, column 5.

We can summarise by saying that to find a code at row y, column x, we need to need to calculate the value at row y+x-1, column 1, and work diagonally up and right from there. So this sets the upper bound for the number of rows we need to populate. And if we want that entire diagonal, then we also need to go out as far as column y+x-1. (Technically, we don’t need that entire diagonal, but if we decide to stop at the exact cell we need, then we need to introduce an extra check. And if we introduce that check, it costs about the same amount of time as it takes to finish the entire diagonal.)

So here’s my solution…

First, let’s create a generator function, which always yields the next available code:

def get_next_code():
    current_code = 20151125
    yield current_code
    
    multiplier = 252533
    dividend = 33554393
    
    while True:
        current_code = (current_code * multiplier) % dividend
        yield current_code

Recall that a generator works a lot like an iterator, and it returns the next successive value with each call. It evaluates the next value at the time it is called, rather than in advance. For obvious reasons, you need to do this when you’re working with a potentially infinite sequence. The generator function persists state between calls.

Whenever you’re asked to continually provide the next value in some sort of infinite sequence, you should be thinking to yourself: maybe I’ll use a generator.

And my main() function looks like this:

def main():
    code_generator = get_next_code()
        
    coord_max = TARGET_ROW + TARGET_COL - 1 
    rows = []
    
    # initialise the 2D array.  Fill it with zeroes.
    for row in range(coord_max):
        column = []
        for col in range(coord_max):
            column.append(0)
        
        rows.append(column)
    
    # now use the generator to fill the values.
    for row in range(coord_max):
        # the sequence of locations is... 0,0 | 1,0 0,1 | 2,0 1,1 0,2 | 3,0 2,1 1,2 0,3...
        for col in range(row+1):
            rows[row-col][col] = next(code_generator)
        
    logger.info(f"Value at row {TARGET_ROW}, col {TARGET_COL} is: {rows[TARGET_ROW-1][TARGET_COL-1]}")

We create a 2D array using a list of lists, and initialise each cell value to 0. Then, we use our generator to populate cell values, according to the diagonal pattern that we need to follow.

And that’s it! Pretty simple. It takes about 2 seconds on my machine, with the specified code location.

Part 2

Hurrah! There is no Part 2. We’re done with 2015!!

Alternative Solution - Using NumPy

I decided to try using NumPy. The code changes required were trivial:

def main():
    code_generator = get_next_code()
    coord_max = TARGET_ROW + TARGET_COL - 1
    
    # initialise the 2D array.  Fill it with zeroes.
    my_array = np.zeros((coord_max, coord_max), dtype=np.int32)
    
    # now use the generator to fill the values.
    for row in range(coord_max):
        # the sequence is... 0,0 | 1,0 0,1 | 2,0 1,1 0,2 | 3,0 2,1 1,2 0,3...
        for col in range(row+1):
            my_array[row-col][col] = next(code_generator)
        
    logger.info(f"Value at row {TARGET_ROW}, col {TARGET_COL} is: {my_array[TARGET_ROW-1][TARGET_COL-1]}")

You’ll see the code is a bit shorter, because I can just use NumPy to initialise my 2D array, rather than using a list of lists. But other than that, the code is basically identical.

I was surprised to find the NumPy solution was about one second slower. Well, it was fun to try!

‹

Learning Python with Advent of Code Walkthroughs