Advent of Code - 2023
This is a solution to Day 9 of Advent of Code 2023.
Day 9: Mirage Maintenance
You ride the camel through the sandstorm and stop where the ghost's maps told you to stop. The sandstorm subsequently subsides, somehow seeing you standing at an oasis!
The camel goes to get some water and you stretch your neck. As you look up, you discover what must be yet another giant floating island, this one made of metal! That must be where the parts to fix the sand machines come from.
There's even a hang glider partially buried in the sand here; once the sun rises and heats up the sand, you might be able to use the glider and the hot air to get all the way up to the metal island!
While you wait for the sun to rise, you admire the oasis hidden here in the middle of Desert Island. It must have a delicate ecosystem; you might as well take some ecological readings while you wait. Maybe you can report any environmental instabilities you find to someone so the oasis can be around for the next sandstorm-worn traveler.
You pull out your handy Oasis And Sand Instability Sensor and analyze your surroundings. The OASIS produces a report of many values and how they are changing over time (your puzzle input). Each line in the report contains the history of a single value. For example:
0 3 6 9 12 15 1 3 6 10 15 21 10 13 16 21 30 45To best protect the oasis, your environmental report should include a prediction of the next value in each history. To do this, start by making a new sequence from the difference at each step of your history. If that sequence is not all zeroes, repeat this process, using the sequence you just generated as the input sequence. Once all of the values in your latest sequence are zeroes, you can extrapolate what the next value of the original history should be.
In the above dataset, the first history is 0 3 6 9 12 15. Because the values increase by 3 each step, the first sequence of differences that you generate will be 3 3 3 3 3. Note that this sequence has one fewer value than the input sequence because at each step it considers two numbers from the input. Since these values aren't all zero, repeat the process: the values differ by 0 at each step, so the next sequence is 0 0 0 0. This means you have enough information to extrapolate the history! Visually, these sequences can be arranged like this:
0 3 6 9 12 15 3 3 3 3 3 0 0 0 0To extrapolate, start by adding a new zero to the end of your list of zeroes; because the zeroes represent differences between the two values above them, this also means there is now a placeholder in every sequence above it:
0 3 6 9 12 15 B 3 3 3 3 3 A 0 0 0 0 0You can then start filling in placeholders from the bottom up. A needs to be the result of increasing 3 (the value to its left) by 0 (the value below it); this means A must be 3:
0 3 6 9 12 15 B 3 3 3 3 3 3 0 0 0 0 0Finally, you can fill in B, which needs to be the result of increasing 15 (the value to its left) by 3 (the value below it), or 18:
0 3 6 9 12 15 18 3 3 3 3 3 3 0 0 0 0 0So, the next value of the first history is 18.
Finding all-zero differences for the second history requires an additional sequence:
1 3 6 10 15 21 2 3 4 5 6 1 1 1 1 0 0 0Then, following the same process as before, work out the next value in each sequence from the bottom up:
1 3 6 10 15 21 28 2 3 4 5 6 7 1 1 1 1 1 0 0 0 0So, the next value of the second history is 28.
The third history requires even more sequences, but its next value can be found the same way:
10 13 16 21 30 45 68 3 3 5 9 15 23 0 2 4 6 8 2 2 2 2 0 0 0So, the next value of the third history is 68.
If you find the next value for each history in this example and add them together, you get 114.
Analyze your OASIS report and extrapolate the next value for each history. What is the sum of these extrapolated values?
Read input
These kind of days I appreciate a simple input. Each line has space separated numbers and nothing else. No need for regular expressions or other more complex solutions. Split by. that space and convert everything to integer.
from utils import read_input
def transformer(line):
return [int(value) for value in line.split(' ')]
sequences = read_input(9, transformer)
To calculate the sequences of previous sequence's differences, I start with the current sequence and loop, calculating a new sequence until the new one is all zeroes.
Few day ago I mentioned how zip is handy when combining two lists. It's also very handy for combining a list with itself. Here I use it to compare two consecutive values in pairs throughout the entire list by zipping sequence (all numbers) with sequence[1:] (all but first value).
To check if a sequence is all zeroes, I use all to check that each difference equal 0.
This function also relies on the fact that the puzzle input is one where the differences eventually converge to all zeroes. For an arbitrary input, it will loop forever. Because it's used for this specific puzzle, I'm willing to make this trade-off.
def create_diff_sequences(sequence):
full_sequence = [sequence[:]]
while True:
current_differences = [
current - previous
for previous, current
in zip(sequence, sequence[1:])
]
full_sequence.append(current_differences)
sequence = current_differences
if all(difference == 0 for difference in current_differences):
break
return full_sequence
To calculate the next number in the original sequence, we first create all difference sequences. We then go through all of them in reverse order pairwise like in the previous function but this time we use itertools.pairwise. They both do the same thing - the reason I'm using different ones here is to show what zip can do and that pairwise exists.
We calculate the new value by summing the final numbers in each sequence and add it to the end of the list. Finally, we return the last added value.
Final score is the sum of all the new values.
from itertools import pairwise
def calculate_next_number(sequence):
differences = create_diff_sequences(sequence)
differences = differences[::-1]
for current, previous in pairwise(differences):
previous.append(current[-1] + previous[-1])
return differences[-1][-1]
part_1 = 0
for seq in sequences:
part_1 += calculate_next_number(seq)
print(f'Solution: {part_1}')
assert part_1 == 1806615041
Solution: 1806615041
Part 2
Of course, it would be nice to have even more history included in your report. Surely it's safe to just extrapolate backwards as well, right?
For each history, repeat the process of finding differences until the sequence of differences is entirely zero. Then, rather than adding a zero to the end and filling in the next values of each previous sequence, you should instead add a zero to the beginning of your sequence of zeroes, then fill in new first values for each previous sequence.
In particular, here is what the third example history looks like when extrapolating back in time:
5 10 13 16 21 30 45 5 3 3 5 9 15 -2 0 2 4 6 2 2 2 2 0 0 0Adding the new values on the left side of each sequence from bottom to top eventually reveals the new left-most history value: 5.
Doing this for the remaining example data above results in previous values of -3 for the first history and 0 for the second history. Adding all three new values together produces 2.
Analyze your OASIS report again, this time extrapolating the previous value for each history. What is the sum of these extrapolated values?
Second part is not that much different from the first. I didn't check if there are any major performance issues if one tries to insert to the beginning of the list but that was my guess would be the issue.
So instead, I used collections.deque which is a data structure that has efficient way to add numbers to the beginning of the iterable without having to shift all the values around like you'd have to with list. Otherwise, the solution is nearly identical to the first: instead of adding the sum of last values to the end, we add the subtraction of first items to the beginning.
from collections import deque
def calculate_prev_number(sequence):
# In a real world situation, I'd just create
# them as deques to begin with but this is
# good enough for the puzzle
differences = [
deque(seq)
for seq
in create_diff_sequences(sequence)[::-1]
]
for current, previous in pairwise(differences):
previous.appendleft(previous[0] - current[0])
return differences[-1][0]
part_2 = 0
for seq in sequences:
prev = calculate_prev_number(seq)
part_2 += prev
print(f'Solution: {part_2}')
assert part_2 == 1211
Solution: 1211
Two stars!
18 is a beautiful number.