problems/day18.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 18 - Advent of Code 2019</title>
   6 <!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
   7 <link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'>
   8 <link rel="stylesheet" type="text/css" href="/static/style.css?24"/>
   9 <link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
  10 <link rel="shortcut icon" href="/favicon.png"/>
  11 </head><!--
  12
  13
  14
  15
  16 Oh, hello!  Funny seeing you here.
  17
  18 I appreciate your enthusiasm, but you aren't going to find much down here.
  19 There certainly aren't clues to any of the puzzles.  The best surprises don't
  20 even appear in the source until you unlock them for real.
  21
  22 Please be careful with automated requests; I'm not a massive company, and I can
  23 only take so much traffic.  Please be considerate so that everyone gets to play.
  24
  25 If you're curious about how Advent of Code works, it's running on some custom
  26 Perl code. Other than a few integrations (auth, analytics, ads, social media),
  27 I built the whole thing myself, including the design, animations, prose, and
  28 all of the puzzles.
  29
  30 The puzzles are most of the work; preparing a new calendar and a new set of
  31 puzzles each year takes all of my free time for 4-5 months. A lot of effort
  32 went into building this thing - I hope you're enjoying playing it as much as I
  33 enjoyed making it for you!
  34
  35 If you'd like to hang out, I'm @ericwastl on Twitter.
  36
  37 - Eric Wastl
  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 <body>
  90 <header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2019/about">[About]</a></li><li><a href="/2019/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode-2019" target="_blank">[Shop]</a></li><li><a href="/2019/settings">[Settings]</a></li><li><a href="/2019/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2019/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">36*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">int y=</span><a href="/2019">2019</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2019">[Calendar]</a></li><li><a href="/2019/support">[AoC++]</a></li><li><a href="/2019/sponsors">[Sponsors]</a></li><li><a href="/2019/leaderboard">[Leaderboard]</a></li><li><a href="/2019/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2019/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://about.sourcegraph.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Sourcegraph</a> - Build the new standard developer platform on a globally-distributed remote-first team. We value ownership, autonomy, communication, and transparency.</div></div>
  94 </div><!--/sidebar-->
  95
  96 <main>
  97 <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>
  98 <article class="day-desc"><h2>--- Day 18: Many-Worlds Interpretation ---</h2><p>As you approach Neptune, a planetary security system detects you and activates a giant <a href="https://en.wikipedia.org/wiki/Tractor_beam">tractor beam</a> on <a href="https://en.wikipedia.org/wiki/Triton_(moon)">Triton</a>!  You have no choice but to land.</p>
  99 <p>A scan of the local area reveals only one interesting feature: a massive underground vault.  You generate a map of the tunnels (your puzzle input).  The tunnels are too narrow to move diagonally.</p>
 100 <p>Only one <em>entrance</em> (marked <code>@</code>) is present among the <em>open passages</em> (marked <code>.</code>) and <em>stone walls</em> (<code>#</code>), but you also detect an assortment of <em>keys</em> (shown as lowercase letters) and <em>doors</em> (shown as uppercase letters). Keys of a given letter open the door of the same letter: <code>a</code> opens <code>A</code>, <code>b</code> opens <code>B</code>, and so on.  You aren't sure which key you need to disable the tractor beam, so you'll need to <em>collect all of them</em>.</p>
 101 <p>For example, suppose you have the following map:</p>
 102 <pre><code>#########
 103 #b.A.@.a#
 104 #########
 105 </code></pre>
 106 <p>Starting from the entrance (<code>@</code>), you can only access a large door (<code>A</code>) and a key (<code>a</code>). Moving toward the door doesn't help you, but you can move <code>2</code> steps to collect the key, unlocking <code>A</code> in the process:</p>
 107 <pre><code>#########
 108 #b.....@#
 109 #########
 110 </code></pre>
 111 <p>Then, you can move <code>6</code> steps to collect the only other key, <code>b</code>:</p>
 112 <pre><code>#########
 113 #@......#
 114 #########
 115 </code></pre>
 116 <p>So, collecting every key took a total of <code><em>8</em></code> steps.</p>
 117 <p>Here is a larger example:</p>
 118 <pre><code>########################
 119 #f.D.E.e.C.b.A.@.a.B.c.#
 120 ######################.#
 121 #d.....................#
 122 ########################
 123 </code></pre>
 124 <p>The only reasonable move is to take key <code>a</code> and unlock door <code>A</code>:</p>
 125 <pre><code>########################
 126 #f.D.E.e.C.b.....@.B.c.#
 127 ######################.#
 128 #d.....................#
 129 ########################
 130 </code></pre>
 131 <p>Then, do the same with key <code>b</code>:</p>
 132 <pre><code>########################
 133 #f.D.E.e.C.@.........c.#
 134 ######################.#
 135 #d.....................#
 136 ########################
 137 </code></pre>
 138 <p>...and the same with key <code>c</code>:</p>
 139 <pre><code>########################
 140 #f.D.E.e.............@.#
 141 ######################.#
 142 #d.....................#
 143 ########################
 144 </code></pre>
 145 <p>Now, you have a choice between keys <code>d</code> and <code>e</code>.  While key <code>e</code> is closer, collecting it now would be slower in the long run than collecting key <code>d</code> first, so that's the best choice:</p>
 146 <pre><code>########################
 147 #f...E.e...............#
 148 ######################.#
 149 #@.....................#
 150 ########################
 151 </code></pre>
 152 <p>Finally, collect key <code>e</code> to unlock door <code>E</code>, then collect key <code>f</code>, taking a grand total of <code><em>86</em></code> steps.</p>
 153 <p>Here are a few more examples:</p>
 154 <ul>
 155 <li><pre><code>########################
 156 #...............b.C.D.f#
 157 #.######################
 158 #.....@.a.B.c.d.A.e.F.g#
 159 ########################
 160 </code></pre>
 161 <p>Shortest path is <code>132</code> steps: <code>b</code>, <code>a</code>, <code>c</code>, <code>d</code>, <code>f</code>, <code>e</code>, <code>g</code></p></li>
 162 <li><pre><code>#################
 163 #i.G..c...e..H.p#
 164 ########.########
 165 #j.A..b...f..D.o#
 166 ########@########
 167 #k.E..a...g..B.n#
 168 ########.########
 169 #l.F..d...h..C.m#
 170 #################
 171 </code></pre>
 172 <p>Shortest paths are <code>136</code> steps;<br/>one is: <code>a</code>, <code>f</code>, <code>b</code>, <code>j</code>, <code>g</code>, <code>n</code>, <code>h</code>, <code>d</code>, <code>l</code>, <code>o</code>, <code>e</code>, <code>p</code>, <code>c</code>, <code>i</code>, <code>k</code>, <code>m</code></p></li>
 173 <li><pre><code>########################
 174 #@..............ac.GI.b#
 175 ###d#e#f################
 176 ###A#B#C################
 177 ###g#h#i################
 178 ########################
 179 </code></pre>
 180 <p>Shortest paths are <code>81</code> steps; one is: <code>a</code>, <code>c</code>, <code>f</code>, <code>i</code>, <code>d</code>, <code>g</code>, <code>b</code>, <code>e</code>, <code>h</code></p></li>
 181 </ul>
 182 <p><em>How many steps is the shortest path that collects all of the keys?</em></p>
 183 </article>
 184 <p>Your puzzle answer was <code>6286</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>You arrive at the vault only to <span title="To see the inspiration for this puzzle, look up 'Link to the Past Randomizer Multiworld'.">discover</span> that there is not one vault, but <em>four</em> - each with its own entrance.</p>
 185 <p>On your map, find the area in the middle that looks like this:</p>
 186 <pre><code>...
 187 .@.
 188 ...
 189 </code></pre>
 190 <p>Update your map to instead use the correct data:</p>
 191 <pre><code>@#@
 192 ###
 193 @#@
 194 </code></pre>
 195 <p>This change will split your map into four separate sections, each with its own entrance:</p>
 196 <pre><code>#######       #######
 197 #a.#Cd#       #a.#Cd#
 198 ##...##       ##<em>@#@</em>##
 199 ##.@.##  --&gt;  ##<em>###</em>##
 200 ##...##       ##<em>@#@</em>##
 201 #cB#Ab#       #cB#Ab#
 202 #######       #######
 203 </code></pre>
 204 <p>Because some of the keys are for doors in other vaults, it would take much too long to collect all of the keys by yourself.  Instead, you deploy four remote-controlled robots. Each starts at one of the entrances (<code>@</code>).</p>
 205 <p>Your goal is still to <em>collect all of the keys in the fewest steps</em>, but now, each robot has its own position and can move independently.  You can only remotely control a single robot at a time. Collecting a key instantly unlocks any corresponding doors, regardless of the vault in which the key or door is found.</p>
 206 <p>For example, in the map above, the top-left robot first collects key <code>a</code>, unlocking door <code>A</code> in the bottom-right vault:</p>
 207 <pre><code>#######
 208 #@.#Cd#
 209 ##.#@##
 210 #######
 211 ##@#@##
 212 #cB#.b#
 213 #######
 214 </code></pre>
 215 <p>Then, the bottom-right robot collects key <code>b</code>, unlocking door <code>B</code> in the bottom-left vault:</p>
 216 <pre><code>#######
 217 #@.#Cd#
 218 ##.#@##
 219 #######
 220 ##@#.##
 221 #c.#.@#
 222 #######
 223 </code></pre>
 224 <p>Then, the bottom-left robot collects key <code>c</code>:</p>
 225 <pre><code>#######
 226 #@.#.d#
 227 ##.#@##
 228 #######
 229 ##.#.##
 230 #@.#.@#
 231 #######
 232 </code></pre>
 233 <p>Finally, the top-right robot collects key <code>d</code>:</p>
 234 <pre><code>#######
 235 #@.#.@#
 236 ##.#.##
 237 #######
 238 ##.#.##
 239 #@.#.@#
 240 #######
 241 </code></pre>
 242 <p>In this example, it only took <code><em>8</em></code> steps to collect all of the keys.</p>
 243 <p>Sometimes, multiple robots might have keys available, or a robot might have to wait for multiple keys to be collected:</p>
 244 <pre><code>###############
 245 #d.ABC.#.....a#
 246 ######@#@######
 247 ###############
 248 ######@#@######
 249 #b.....#.....c#
 250 ###############
 251 </code></pre>
 252 <p>First, the top-right, bottom-left, and bottom-right robots take turns collecting keys <code>a</code>, <code>b</code>, and <code>c</code>, a total of <code>6 + 6 + 6 = 18</code> steps. Then, the top-left robot can access key <code>d</code>, spending another <code>6</code> steps; collecting all of the keys here takes a minimum of <code><em>24</em></code> steps.</p>
 253 <p>Here's a more complex example:</p>
 254 <pre><code>#############
 255 #DcBa.#.GhKl#
 256 #.###@#@#I###
 257 #e#d#####j#k#
 258 ###C#@#@###J#
 259 #fEbA.#.FgHi#
 260 #############
 261 </code></pre>
 262 <ul>
 263 <li>Top-left robot collects key <code>a</code>.</li>
 264 <li>Bottom-left robot collects key <code>b</code>.</li>
 265 <li>Top-left robot collects key <code>c</code>.</li>
 266 <li>Bottom-left robot collects key <code>d</code>.</li>
 267 <li>Top-left robot collects key <code>e</code>.</li>
 268 <li>Bottom-left robot collects key <code>f</code>.</li>
 269 <li>Bottom-right robot collects key <code>g</code>.</li>
 270 <li>Top-right robot collects key <code>h</code>.</li>
 271 <li>Bottom-right robot collects key <code>i</code>.</li>
 272 <li>Top-right robot collects key <code>j</code>.</li>
 273 <li>Bottom-right robot collects key <code>k</code>.</li>
 274 <li>Top-right robot collects key <code>l</code>.</li>
 275 </ul>
 276 <p>In the above example, the fewest steps to collect all of the keys is <code><em>32</em></code>.</p>
 277 <p>Here's an example with more choices:</p>
 278 <pre><code>#############
 279 #g#f.D#..h#l#
 280 #F###e#E###.#
 281 #dCba@#@BcIJ#
 282 #############
 283 #nK.L@#@G...#
 284 #M###N#H###.#
 285 #o#m..#i#jk.#
 286 #############
 287 </code></pre>
 288 <p>One solution with the fewest steps is:</p>
 289 <ul>
 290 <li>Top-left robot collects key <code>e</code>.</li>
 291 <li>Top-right robot collects key <code>h</code>.</li>
 292 <li>Bottom-right robot collects key <code>i</code>.</li>
 293 <li>Top-left robot collects key <code>a</code>.</li>
 294 <li>Top-left robot collects key <code>b</code>.</li>
 295 <li>Top-right robot collects key <code>c</code>.</li>
 296 <li>Top-left robot collects key <code>d</code>.</li>
 297 <li>Top-left robot collects key <code>f</code>.</li>
 298 <li>Top-left robot collects key <code>g</code>.</li>
 299 <li>Bottom-right robot collects key <code>k</code>.</li>
 300 <li>Bottom-right robot collects key <code>j</code>.</li>
 301 <li>Top-right robot collects key <code>l</code>.</li>
 302 <li>Bottom-left robot collects key <code>n</code>.</li>
 303 <li>Bottom-left robot collects key <code>m</code>.</li>
 304 <li>Bottom-left robot collects key <code>o</code>.</li>
 305 </ul>
 306 <p>This example requires at least <code><em>72</em></code> steps to collect all keys.</p>
 307 <p>After updating your map and using the remote-controlled robots, <em>what is the fewest steps necessary to collect all of the keys?</em></p>
 308 </article>
 309 <p>Your puzzle answer was <code>2140</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 310 <p>At this point, you should <a href="/2019">return to your Advent calendar</a> and try another puzzle.</p>
 311 <p>If you still want to see it, you can <a href="18/input" target="_blank">get your puzzle input</a>.</p>
 312 <p>You can also <span class="share">[Share<span class="share-content">on
 313   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Many%2DWorlds+Interpretation%22+%2D+Day+18+%2D+Advent+of+Code+2019&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F18&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 314   <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Many%2DWorlds+Interpretation%22+%2D+Day+18+%2D+Advent+of+Code+2019+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F18'}else{return false;}" target="_blank">Mastodon</a
 315 ></span>]</span> this puzzle.</p>
 316 </main>
 317
 318 <!-- ga -->
 319 <script>
 320 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 321 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 322 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 323 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 324 ga('create', 'UA-69522494-1', 'auto');
 325 ga('set', 'anonymizeIp', true);
 326 ga('send', 'pageview');
 327 </script>
 328 <!-- /ga -->
 329 </body>
 330 </html>