Mercurial > repos > other > adventofcode2023

annotate day11.txt @ 18:ddb69833346c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement day 11 distance finding in space "shortest distance" is simplified by it being cardinal directions, so it's the same as taking the right-angle between them. The Part 1 space expansion was quite clean, but the Part 2 approach generalises it to something even nicer.
author IBBoard <dev@ibboard.co.uk>
date Mon, 11 Dec 2023 20:08:47 +0000
parents
children 1e16a25a9553
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
18
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 --- Day 11: Cosmic Expansion ---
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 You continue following signs for "Hot Springs" and eventually come across an observatory. The Elf within turns out to be a researcher studying cosmic expansion using the giant telescope here.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5 He doesn't know anything about the missing machine parts; he's only visiting for this research project. However, he confirms that the hot springs are the next-closest area likely to have people; he'll even take you straight there once he's done with today's observation analysis.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 Maybe you can help him with the analysis to speed things up?
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 The researcher has collected a bunch of data and compiled the data into a single giant image (your puzzle input). The image includes empty space (.) and galaxies (#). For example:
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 ...#......
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12 .......#..
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 #.........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 ..........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 ......#...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 .#........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 .........#
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 ..........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19 .......#..
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 #...#.....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22 The researcher is trying to figure out the sum of the lengths of the shortest path between every pair of galaxies. However, there's a catch: the universe expanded in the time it took the light from those galaxies to reach the observatory.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 Due to something involving gravitational effects, only some space expands. In fact, the result is that any rows or columns that contain no galaxies should all actually be twice as big.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 In the above example, three columns and two rows contain no galaxies:
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28 v v v
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 ...#......
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 .......#..
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31 #.........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 >..........<
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 ......#...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34 .#........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 .........#
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 >..........<
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37 .......#..
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 #...#.....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 ^ ^ ^
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41 These rows and columns need to be twice as big; the result of cosmic expansion therefore looks like this:
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 ....#........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44 .........#...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 #............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 ........#....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 .#...........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 ............#
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 .........#...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54 #....#.......
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 Equipped with this expanded universe, the shortest path between every pair of galaxies can be found. It can help to assign every galaxy a unique number:
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 ....1........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 .........2...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 3............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
62 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
63 ........4....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
64 .5...........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 ............6
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
66 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 .........7...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 8....9.......
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
70
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
71 In these 9 galaxies, there are 36 pairs. Only count each pair once; order within the pair doesn't matter. For each pair, find any shortest path between the two galaxies using only steps that move up, down, left, or right exactly one . or # at a time. (The shortest path between two galaxies is allowed to pass through another galaxy.)
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 For example, here is one of the shortest paths between galaxies 5 and 9:
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 ....1........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 .........2...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 3............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
79 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
80 ........4....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
81 .5...........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82 .##.........6
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
83 ..##.........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
84 ...##........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
85 ....##...7...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
86 8....9.......
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
87
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
88 This path has length 9 because it takes a minimum of nine steps to get from galaxy 5 to galaxy 9 (the eight locations marked # plus the step onto galaxy 9 itself). Here are some other example shortest path lengths:
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
89
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
90 Between galaxy 1 and galaxy 7: 15
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
91 Between galaxy 3 and galaxy 6: 17
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
92 Between galaxy 8 and galaxy 9: 5
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
93
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
94 In this example, after expanding the universe, the sum of the shortest path between all 36 pairs of galaxies is 374.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
95
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
96 Expand the universe, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
97
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
98 --- Part Two ---
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
99
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
100 The galaxies are much older (and thus much farther apart) than the researcher initially estimated.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
101
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
102 Now, instead of the expansion you did before, make each empty row or column one million times larger. That is, each empty row should be replaced with 1000000 empty rows, and each empty column should be replaced with 1000000 empty columns.
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
103
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
104 (In the example above, if each empty row or column were merely 10 times larger, the sum of the shortest paths between every pair of galaxies would be 1030. If each empty row or column were merely 100 times larger, the sum of the shortest paths between every pair of galaxies would be 8410. However, your universe will need to expand far beyond these values.)
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
105
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
106 Starting with the same initial image, expand the universe according to these new rules, then find the length of the shortest path between every pair of galaxies. What is the sum of these lengths?