-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathyear2023_day11_puzzle.html
205 lines (142 loc) · 8.68 KB
/
year2023_day11_puzzle.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
<!DOCTYPE html>
<html lang="en-us">
<head>
<meta charset="utf-8"/>
<title>Day 11 - Advent of Code 2023</title>
<link rel="stylesheet" type="text/css" href="/static/style.css?31"/>
<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?1" title="High Contrast"/>
<link rel="shortcut icon" href="/favicon.png"/>
<script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
</head><!--
Oh, hello! Funny seeing you here.
I appreciate your enthusiasm, but you aren't going to find much down here.
There certainly aren't clues to any of the puzzles. The best surprises don't
even appear in the source until you unlock them for real.
Please be careful with automated requests; I'm not a massive company, and I can
only take so much traffic. Please be considerate so that everyone gets to play.
If you're curious about how Advent of Code works, it's running on some custom
Perl code. Other than a few integrations (auth, analytics, social media), I
built the whole thing myself, including the design, animations, prose, and all
of the puzzles.
The puzzles are most of the work; preparing a new calendar and a new set of
puzzles each year takes all of my free time for 4-5 months. A lot of effort
went into building this thing - I hope you're enjoying playing it as much as I
enjoyed making it for you!
If you'd like to hang out, I'm @was.tl on Bluesky, @[email protected] on
Mastodon, and @ericwastl on Twitter.
- Eric Wastl
-->
<body>
<div id="sidebar">
</div><!--/sidebar-->
<main>
<article class="day-desc"><h2>--- Day 11: Cosmic Expansion ---</h2><p>You continue following signs for "Hot Springs" and eventually come across an <a href="https://en.wikipedia.org/wiki/Observatory" target="_blank">observatory</a>. The Elf within turns out to be a researcher studying cosmic expansion using the giant telescope here.</p>
<p>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.</p>
<p>Maybe you can help him with the analysis to speed things up?</p>
<p>The researcher has collected a bunch of data and compiled the data into a single giant <em>image</em> (your puzzle input). The image includes <em>empty space</em> (<code>.</code>) and <em>galaxies</em> (<code>#</code>). For example:</p>
<pre><code>...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
</code></pre>
<p>The researcher is trying to figure out the sum of the lengths of the <em>shortest path between every pair of galaxies</em>. However, there's a catch: the universe expanded in the time it took the light from those galaxies to reach the observatory.</p>
<p>Due to something involving gravitational effects, <em>only some space expands</em>. In fact, the result is that <em>any rows or columns that contain no galaxies</em> should all actually be twice as big.</p>
<p>In the above example, three columns and two rows contain no galaxies:</p>
<pre><code> v v v
...#......
.......#..
#.........
>..........<
......#...
.#........
.........#
>..........<
.......#..
#...#.....
^ ^ ^
</code></pre>
<p>These rows and columns need to be <em>twice as big</em>; the result of cosmic expansion therefore looks like this:</p>
<pre><code>....#........
.........#...
#............
.............
.............
........#....
.#...........
............#
.............
.............
.........#...
#....#.......
</code></pre>
<p>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:</p>
<pre><code>....1........
.........2...
3............
.............
.............
........4....
.5...........
............6
.............
.............
.........7...
8....9.......
</code></pre>
<p>In these 9 galaxies, there are <em>36 pairs</em>. 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 <code>.</code> or <code>#</code> at a time. (The shortest path between two galaxies is allowed to pass through another galaxy.)</p>
<p>For example, here is one of the shortest paths between galaxies <code>5</code> and <code>9</code>:</p>
<pre><code>....1........
.........2...
3............
.............
.............
........4....
.5...........
.##.........6
..##.........
...##........
....##...7...
8....9.......
</code></pre>
<p>This path has length <code><em>9</em></code> because it takes a minimum of <em>nine steps</em> to get from galaxy <code>5</code> to galaxy <code>9</code> (the eight locations marked <code>#</code> plus the step onto galaxy <code>9</code> itself). Here are some other example shortest path lengths:</p>
<ul>
<li>Between galaxy <code>1</code> and galaxy <code>7</code>: 15</li>
<li>Between galaxy <code>3</code> and galaxy <code>6</code>: 17</li>
<li>Between galaxy <code>8</code> and galaxy <code>9</code>: 5</li>
</ul>
<p>In this example, after expanding the universe, the sum of the shortest path between all 36 pairs of galaxies is <code><em>374</em></code>.</p>
<p>Expand the universe, then find the length of the shortest path between every pair of galaxies. <em>What is the sum of these lengths?</em></p>
</article>
<p>Your puzzle answer was <code>9799681</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>The galaxies are much <em>older</em> (and thus much <em>farther apart</em>) than the researcher initially estimated.</p>
<p>Now, instead of the expansion you did before, make each empty row or column <em><span title="And you have to have your pinky near your mouth when you do it.">one million</span> times</em> larger. That is, each empty row should be replaced with <code>1000000</code> empty rows, and each empty column should be replaced with <code>1000000</code> empty columns.</p>
<p>(In the example above, if each empty row or column were merely <code>10</code> times larger, the sum of the shortest paths between every pair of galaxies would be <code><em>1030</em></code>. If each empty row or column were merely <code>100</code> times larger, the sum of the shortest paths between every pair of galaxies would be <code><em>8410</em></code>. However, your universe will need to expand far beyond these values.)</p>
<p>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. <em>What is the sum of these lengths?</em></p>
</article>
<p>Your puzzle answer was <code>513171773355</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
<p>At this point, you should <a href="/2023">return to your Advent calendar</a> and try another puzzle.</p>
<p>If you still want to see it, you can <a href="11/input" target="_blank">get your puzzle input</a>.</p>
<p>You can also <span class="share">[Share<span class="share-content">on
<a href="https://bsky.app/intent/compose?text=I%27ve+completed+%22Cosmic+Expansion%22+%2D+Day+11+%2D+Advent+of+Code+2023+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2023%2Fday%2F11" target="_blank">Bluesky</a>
<a href="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" target="_blank">Twitter</a>
<a href="javascript:void(0);" onclick="var ms; try{ms=localStorage.getItem('mastodon.server')}finally{} if(typeof ms!=='string')ms=''; ms=prompt('Mastodon Server?',ms); if(typeof ms==='string' && ms.length){this.href='https://'+ms+'/share?text=I%27ve+completed+%22Cosmic+Expansion%22+%2D+Day+11+%2D+Advent+of+Code+2023+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2023%2Fday%2F11';try{localStorage.setItem('mastodon.server',ms);}finally{}}else{return false;}" target="_blank">Mastodon</a
></span>]</span> this puzzle.</p>
</main>
<!-- ga -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-69522494-1', 'auto');
ga('set', 'anonymizeIp', true);
ga('send', 'pageview');
</script>
<!-- /ga -->
</body>
</html>