Mercurial > repos > other > adventofcode2023

annotate day11.txt @ 35:ca54f9702892

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Day 24 part 2 instructions and partial solution
author IBBoard <dev@ibboard.co.uk>
date Thu, 18 Apr 2024 19:54:59 +0100
parents 1e16a25a9553
children
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
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 18
diff changeset
3 There is a map (your puzzle input). The image includes empty space (.) and galaxies (#). For example:
18
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 ...#......
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 #.........
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 ......#...
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
19
1e16a25a9553 Strip down the text to just the puzzle, not the fluff
IBBoard <dev@ibboard.co.uk>
parents: 18
diff changeset
16 We need to calculate the distance between each galaxy. But the space between them is non-linear. Any rows or columns that contain no galaxies should all actually be twice as big.
18
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 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
19
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 v v v
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 .......#..
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 >..........<
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 .#........
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 >..........<
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 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
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 .#...........
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 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
49
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 ....1........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 .........2...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 3............
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 ........4....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 .5...........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
57 ............6
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
58 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
59 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
60 .........7...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
61 8....9.......
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 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
64
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
65 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
66
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
67 ....1........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
68 .........2...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
69 3............
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 .............
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
72 ........4....
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
73 .5...........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
74 .##.........6
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
75 ..##.........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
76 ...##........
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
77 ....##...7...
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
78 8....9.......
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 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
81
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
82 Between galaxy 1 and galaxy 7: 15
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
83 Between galaxy 3 and galaxy 6: 17
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
84 Between galaxy 8 and galaxy 9: 5
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
85
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
86 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
87
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
88 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
89
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
90 --- Part Two ---
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
91
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
92 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
93
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
94 (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
95
ddb69833346c Implement day 11 distance finding in space
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
96 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?