Mercurial > repos > other > adventofcode2023
annotate day9.txt @ 39:0e17e4bd97a9 default tip
Rewrite as four-dimensional route finding
The grid isn't just a 2D grid. The constraints make it 4D:
* X
* Y
* Last direction
* Number of steps in that direction
By tracking all four dimensions, we can find the shortest route
for _all_ combinations of the constraint. Previously, we were dropping
routes that were currently longer but ended up shorter because
they could take subsequent steps that other routes couldn't.
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Sun, 22 Sep 2024 11:30:53 +0100 |
parents | 1e16a25a9553 |
children |
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. |