Link to Advent of Code day 9

I liked this day. It was simple, since the solution was given with the rules. But it made me learn a new thing: how to find the next number of a sequence, which is cool !

Part 1

Rules

So we need to calculate the next number of a sequence.

I had no idea how to do this but luckily, the description of today give us a method:

For a line of digits, we need to get the differences between each number.

For example, 1 3 6 10 15 21 would give 2 3 4 5 6.

We then calculate the differences from this new list, until we have a list of only zeroes: 2 3 4 5 6 -> 1 1 1 1 1 1 1 1 -> 0 0 0

In this case, we ends with 4 lists: 1 3 6 10 15 21 2 3 4 5 6 1 1 1 1 0 0 0

We then have to compute the next number for each line. To find a value, we needs to sum the value to it's left, and the right most value of the previous line.

For example here, we would do the following: Line 3, A is gonna be the sum of 0 (right most value from line 4) and 1 (the value to it's left), which gives us 1

1 1 3 6 10 15 21 C
2 2 3 4 5 6 B
3 1 1 1 1 A
4 0 0 0

1 1 3 6 10 15 21 C
2 2 3 4 5 6 B
3 1 1 1 1 1
4 0 0 0

B is the sum of 6 (left value) and 1 (the right most value we just computed), givin us 7:

1 1 3 6 10 15 21 C
2 2 3 4 5 6 7
3 1 1 1 1 1
4 0 0 0

We can then find the value of C by summing 21 and 7, for a final result of 28.

For a given list of sequences, we need to sum up the next number for each line.

For example with

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

The next numbers are 18, 28 and 68, for a sum of 114

Code

Let's start by parsing the input, which is very straightforward today:

def get_sequences(input_file: str) -> list[list[int]]:
    sequences = []
    with open(input_file) as f:
        for line in f.readlines():
            sequences.append([int(n) for n in line.split()])
    return sequences

We then wants a function to expand a list of numbers, until we reach a sequence containing only zeroes is reached.

To do this, we just need to iter on a list pair by pair, push their differences into a new list, start again with this new list until the end condition is reached:

def get_sequence_differences_list(sequence: list[int]) -> list[list[int]]:
    """Generates a list of difference sequences from an input sequence
        until a sequence of all zeros is reached.

    Example:
        >>> get_sequence_differences_list([1, 3, 6, 10, 15, 21])
        [[1, 3, 6, 10, 15, 21], [2, 3, 4, 5, 6], [1, 1, 1, 1], [0, 0, 0]]
    """
    sequences = [sequence]
    current_sequence = sequence

    while not all(n == 0 for n in current_sequence):
        current_sequence = [y - x for (x, y) in pairwise(current_sequence)]
        sequences.append(current_sequence)
    return sequences


def pairwise(iterable):
    """s -> (s0,s1), (s1,s2), (s2, s3), ..."""
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

The pairwise function is provided by itertools list of recipes.

Then, getting the last digit for this sequence consists of iterating on the expanded sequence in reverse, using indexing to get the previous and left numbers, and append their sum to the current sequence:

def get_last_sequence_number(sequence: list[int]) -> int:
    sequences = get_sequence_differences_list(sequence)

    # Find next number from last to first
    for idx in reversed(range(0, len(sequences) - 1)):
        left_nbr = sequences[idx][-1]
        prev_nbr = sequences[idx + 1][-1]
        sequences[idx].append(left_nbr + prev_nbr)

    return sequences[0][-1]

We then just have to apply this function to each sequence, and sum it's return to solve part 1:

def part_one(input_file: str) -> int:
    sequences = get_sequences(input_file)
    return sum(map(get_last_sequence_number, sequences))

Part 2

Rules

The twist of this part is that we have to extrapolate backward: instead of taking the rightmost previous number and the left number, before inserting it to the right, we do the opposite: we should instead fill in new first values for each previous sequence, with the leftmost numbers.

This means that with

10  13  16  21  30  45
   3   3   5   9  15
     0   2   4   6
       2   2   2
         0   0

We will instead have this result:

5  10  13  16  21  30  45
  5   3   3   5   9  15
   -2   0   2   4   6
      2   2   2   2
        0   0   0

Code

With the previous implementation, we just have to change the code from get_last_sequence_number to update the indexing so we take the first instead of the last element to retrieve the numbers, and that we need to insert at the beginning of the list:

def get_first_sequence_number(sequence: list[int]) -> int:
    sequences = get_sequence_differences_list(sequence)

    for idx in reversed(range(0, len(sequences) - 1)):
        # We index by 0 instead of -1
        right_nbr = sequences[idx][0]
        prev_nbr = sequences[idx + 1][0]
        # And be careful to insert the difference at the beginning of the list
        sequences[idx].insert(0, right_nbr - prev_nbr)

    return sequences[0][0]

Then, as for part 1, solving part 2 just consists of getting the sum each sequence:

def part_two(input_file: str):
    sequences = get_sequences(input_file)
    return sum(map(get_first_sequence_number, sequences))

That's it for today !

---

The full code is available here