Mercurial > repos > other > adventofcode2023

annotate day9.txt @ 38:8e92cb172e6b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Output final distance Also minor code cleanup
author IBBoard <dev@ibboard.co.uk>
date Fri, 20 Sep 2024 20:30:11 +0100
parents 1e16a25a9553
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
12
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 --- Day 9: Mirage Maintenance ---
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
3 You have 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:
12
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 0 3 6 9 12 15
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 1 3 6 10 15 21
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 10 13 16 21 30 45
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
9 You need to report 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.
12
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 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:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 0 3 6 9 12 15
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 3 3 3 3 3
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 0 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 To 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:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 0 3 6 9 12 15 B
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 3 3 3 3 3 A
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 0 0 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 You 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:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 0 3 6 9 12 15 B
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 3 3 3 3 3 3
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 0 0 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 Finally, 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:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 0 3 6 9 12 15 18
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 3 3 3 3 3 3
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 0 0 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 So, the next value of the first history is 18.
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 Finding all-zero differences for the second history requires an additional sequence:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 1 3 6 10 15 21
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 2 3 4 5 6
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 1 1 1 1
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 Then, following the same process as before, work out the next value in each sequence from the bottom up:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 1 3 6 10 15 21 28
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 2 3 4 5 6 7
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 1 1 1 1 1
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 0 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 So, the next value of the second history is 28.
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 The third history requires even more sequences, but its next value can be found the same way:
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 10 13 16 21 30 45 68
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 3 3 5 9 15 23
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 0 2 4 6 8
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 2 2 2 2
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 0 0 0
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 So, the next value of the third history is 68.
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 If you find the next value for each history in this example and add them together, you get 114.
891878e52a31 Implement Day 9 - diffing and predicting
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
65 What is the sum of these extrapolated values?
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
66
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
67 --- Part 2 ---
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
68
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 12
diff changeset
69 Now extrapolate backwards in the same manner and sum _those_ values.