Mercurial > repos > other > adventofcode2023

annotate day5.txt @ 39:0e17e4bd97a9 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 --- Day 5: If You Give A Seed A Fertilizer ---
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 The almanac (your puzzle input) lists all of the seeds that need to be planted. It also lists what type of soil to use with each kind of seed, what type of fertilizer to use with each kind of soil, what type of water to use with each kind of fertilizer, and so on. Every type of seed, soil, fertilizer and so on is identified with a number, but numbers are reused by each category - that is, soil 123 and fertilizer 123 aren't necessarily related to each other.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 For example:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 seeds: 79 14 55 13
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 seed-to-soil map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10 50 98 2
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 52 50 48
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 soil-to-fertilizer map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 0 15 37
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 37 52 2
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 39 0 15
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 fertilizer-to-water map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 49 53 8
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 0 11 42
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 42 0 7
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 57 7 4
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 water-to-light map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 88 18 7
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 18 25 70
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 light-to-temperature map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 45 77 23
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 81 45 19
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 68 64 13
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 temperature-to-humidity map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 0 69 1
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 1 0 69
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 humidity-to-location map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 60 56 37
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 56 93 4
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 The almanac starts by listing which seeds need to be planted: seeds 79, 14, 55, and 13.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 The rest of the almanac contains a list of maps which describe how to convert numbers from a source category into numbers in a destination category. That is, the section that starts with seed-to-soil map: describes how to convert a seed number (the source) to a soil number (the destination). This lets the gardener and his team know which soil to use with which seeds, which water to use with which fertilizer, and so on.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 Rather than list every source number and its corresponding destination number one by one, the maps describe entire ranges of numbers that can be converted. Each line within a map contains three numbers: the destination range start, the source range start, and the range length.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 Consider again the example seed-to-soil map:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 50 98 2
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 52 50 48
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 The first line has a destination range start of 50, a source range start of 98, and a range length of 2. This line means that the source range starts at 98 and contains two values: 98 and 99. The destination range is the same length, but it starts at 50, so its two values are 50 and 51. With this information, you know that seed number 98 corresponds to soil number 50 and that seed number 99 corresponds to soil number 51.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 The second line means that the source range starts at 50 and contains 48 values: 50, 51, ..., 96, 97. This corresponds to a destination range starting at 52 and also containing 48 values: 52, 53, ..., 98, 99. So, seed number 53 corresponds to soil number 55.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 Any source numbers that aren't mapped correspond to the same destination number. So, seed number 10 corresponds to soil number 10.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 So, the entire list of seed numbers and their corresponding soil numbers looks like this:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 seed soil
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 0 0
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 1 1
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 ... ...
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 48 48
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 49 49
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 50 52
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 51 53
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 ... ...
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 96 98
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70 97 99
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 98 50
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 99 51
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 With this map, you can look up the soil number required for each initial seed number:
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 Seed number 79 corresponds to soil number 81.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 Seed number 14 corresponds to soil number 14.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 Seed number 55 corresponds to soil number 57.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
79 Seed number 13 corresponds to soil number 13.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
80
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 5
diff changeset
81 We need to know the closest location that needs a seed. Using these maps, find the lowest location number that corresponds to any of the initial seeds. To do this, you'll need to convert each seed number through other categories until you can find its corresponding location number. In this example, the corresponding types are:
4
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
83 Seed 79, soil 81, fertilizer 81, water 81, light 74, temperature 78, humidity 78, location 82.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
84 Seed 14, soil 14, fertilizer 53, water 49, light 42, temperature 42, humidity 43, location 43.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
85 Seed 55, soil 57, fertilizer 57, water 53, light 46, temperature 82, humidity 82, location 86.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
86 Seed 13, soil 13, fertilizer 52, water 41, light 34, temperature 34, humidity 35, location 35.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
87
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
88 So, the lowest location number in this example is 35.
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
89
cd5a8f086973 Implement part 1 plant mapping and lookup
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
90 What is the lowest location number that corresponds to any of the initial seed numbers?
5
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
91
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
92
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
93 --- Part Two ---
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
94
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 5
diff changeset
95 Actually, the values on the initial seeds: line come in pairs. Within each pair, the first value is the start of the range and the second value is the length of the range. So, in the first line of the example above:
5
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
96
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
97 seeds: 79 14 55 13
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
98
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
99 This line describes two ranges of seed numbers to be planted in the garden. The first range starts with seed number 79 and contains 14 values: 79, 80, ..., 91, 92. The second range starts with seed number 55 and contains 13 values: 55, 56, ..., 66, 67.
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
100
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
101 Now, rather than considering four seed numbers, you need to consider a total of 27 seed numbers.
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
102
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
103 In the above example, the lowest location number can be obtained from seed number 82, which corresponds to soil 84, fertilizer 84, water 84, light 77, temperature 45, humidity 46, and location 46. So, the lowest location number is 46.
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
104
a14f6eca67db Record day5 part 2 instructions
IBBoard <dev@ibboard.co.uk>
parents: 4
diff changeset
105 Consider all of the initial seed numbers listed in the ranges on the first line of the almanac. What is the lowest location number that corresponds to any of the initial seed numbers?