Dazbo's Advent of Code solutions, written in Python

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 | 1 3 6 10 15 21
2 | 2 5 9 14 20
3 | 4 8 13 19
4 | 7 12 18
5 | 11 17
6 | 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
---+---------+---------+---------+---------+---------+---------+
1 | 20151125 18749137 17289845 30943339 10071777 33511524
2 | 31916031 21629792 16929656 7726640 15514188 4041754
3 | 16080970 8057251 1601130 7981243 11661866 16474243
4 | 24592653 32451966 21345942 9380097 10600672 31527494
5 | 77061 17552253 28094349 6899651 9250759 31663883
6 | 33071741 6796745 25397450 24659492 1534922 27995004
```

**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.

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

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!