199 lines
6.2 KiB
Plaintext
199 lines
6.2 KiB
Plaintext
[1]Advent of Code
|
||
|
||
• [2][About]
|
||
• [3][Events]
|
||
• [4][Shop]
|
||
• [5][Settings]
|
||
• [6][Log Out]
|
||
|
||
br0xen [7](AoC++) 36*
|
||
|
||
$year=[8]2023;
|
||
|
||
• [9][Calendar]
|
||
• [10][AoC++]
|
||
• [11][Sponsors]
|
||
• [12][Leaderboard]
|
||
• [13][Stats]
|
||
|
||
Our [14]sponsors help make Advent of Code possible:
|
||
[15]McGraw Hill - Transforming education, one line of code at a time.
|
||
|
||
--- Day 11: Cosmic Expansion ---
|
||
|
||
You continue following signs for "Hot Springs" and eventually come across
|
||
an [16]observatory. The Elf within turns out to be a researcher studying
|
||
cosmic expansion using the giant telescope here.
|
||
|
||
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.
|
||
|
||
Maybe you can help him with the analysis to speed things up?
|
||
|
||
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:
|
||
|
||
...#......
|
||
.......#..
|
||
#.........
|
||
..........
|
||
......#...
|
||
.#........
|
||
.........#
|
||
..........
|
||
.......#..
|
||
#...#.....
|
||
|
||
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.
|
||
|
||
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.
|
||
|
||
In the above example, three columns and two rows contain no galaxies:
|
||
|
||
v v v
|
||
...#......
|
||
.......#..
|
||
#.........
|
||
>..........<
|
||
......#...
|
||
.#........
|
||
.........#
|
||
>..........<
|
||
.......#..
|
||
#...#.....
|
||
^ ^ ^
|
||
|
||
These rows and columns need to be twice as big; the result of cosmic
|
||
expansion therefore looks like this:
|
||
|
||
....#........
|
||
.........#...
|
||
#............
|
||
.............
|
||
.............
|
||
........#....
|
||
.#...........
|
||
............#
|
||
.............
|
||
.............
|
||
.........#...
|
||
#....#.......
|
||
|
||
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:
|
||
|
||
....1........
|
||
.........2...
|
||
3............
|
||
.............
|
||
.............
|
||
........4....
|
||
.5...........
|
||
............6
|
||
.............
|
||
.............
|
||
.........7...
|
||
8....9.......
|
||
|
||
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.)
|
||
|
||
For example, here is one of the shortest paths between galaxies 5 and 9:
|
||
|
||
....1........
|
||
.........2...
|
||
3............
|
||
.............
|
||
.............
|
||
........4....
|
||
.5...........
|
||
.##.........6
|
||
..##.........
|
||
...##........
|
||
....##...7...
|
||
8....9.......
|
||
|
||
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:
|
||
|
||
• Between galaxy 1 and galaxy 7: 15
|
||
• Between galaxy 3 and galaxy 6: 17
|
||
• Between galaxy 8 and galaxy 9: 5
|
||
|
||
In this example, after expanding the universe, the sum of the shortest
|
||
path between all 36 pairs of galaxies is 374.
|
||
|
||
Expand the universe, then find the length of the shortest path between
|
||
every pair of galaxies. What is the sum of these lengths?
|
||
|
||
Your puzzle answer was 9957702.
|
||
|
||
--- Part Two ---
|
||
|
||
The galaxies are much older (and thus much farther apart) than the
|
||
researcher initially estimated.
|
||
|
||
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.
|
||
|
||
(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.)
|
||
|
||
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?
|
||
|
||
Your puzzle answer was 512240933238.
|
||
|
||
Both parts of this puzzle are complete! They provide two gold stars: **
|
||
|
||
At this point, you should [17]return to your Advent calendar and try
|
||
another puzzle.
|
||
|
||
If you still want to see it, you can [18]get your puzzle input.
|
||
|
||
You can also [Shareon [19]Twitter [20]Mastodon] this puzzle.
|
||
|
||
References
|
||
|
||
Visible links
|
||
1. https://adventofcode.com/
|
||
2. https://adventofcode.com/2023/about
|
||
3. https://adventofcode.com/2023/events
|
||
4. https://teespring.com/stores/advent-of-code
|
||
5. https://adventofcode.com/2023/settings
|
||
6. https://adventofcode.com/2023/auth/logout
|
||
7. Advent of Code Supporter
|
||
https://adventofcode.com/2023/support
|
||
8. https://adventofcode.com/2023
|
||
9. https://adventofcode.com/2023
|
||
10. https://adventofcode.com/2023/support
|
||
11. https://adventofcode.com/2023/sponsors
|
||
12. https://adventofcode.com/2023/leaderboard
|
||
13. https://adventofcode.com/2023/stats
|
||
14. https://adventofcode.com/2023/sponsors
|
||
15. https://mheducation.com/
|
||
16. https://en.wikipedia.org/wiki/Observatory
|
||
17. https://adventofcode.com/2023
|
||
18. https://adventofcode.com/2023/day/11/input
|
||
19. https://twitter.com/intent/tweet?text=I%27ve+completed+%22Cosmic+Expansion%22+%2D+Day+11+%2D+Advent+of+Code+2023&url=https%3A%2F%2Fadventofcode%2Ecom%2F2023%2Fday%2F11&related=ericwastl&hashtags=AdventOfCode
|
||
20. javascript:void(0);
|