Mercurial > repos > other > adventofcode2023
annotate day11.txt @ 27:6b58ddfaed38
Add Day 18 part 1 solution using line crossing
author | IBBoard <dev@ibboard.co.uk> |
---|---|
date | Tue, 02 Jan 2024 16:04:33 +0000 |
parents | 1e16a25a9553 |
children |
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? |