problems/day20.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 20 - 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">40*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">//</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://www.novetta.com/careers/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Novetta</a> - While Santa has elves, we have TS/SCI data scientists rapidly prototyping ML solutions...hot chocolate included. Check us out.</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 20: Donut Maze ---</h2><p>You notice a strange pattern on the surface of Pluto and land nearby to get a closer look. Upon closer inspection, you realize you've come across one of the famous space-warping mazes of the long-lost Pluto civilization!</p>
  99 <p>Because there isn't much space on Pluto, the civilization that used to live here thrived by inventing a method for folding spacetime.  Although the technology is no longer understood, mazes like this one provide a small glimpse into the <span title="So really, this puzzle is more archaeology than math, right?">daily life of an ancient Pluto citizen</span>.</p>
 100 <p>This maze is shaped like a <a href="https://en.wikipedia.org/wiki/Torus">donut</a>. Portals along the inner and outer edge of the donut can instantly teleport you from one side to the other.  For example:</p>
 101 <pre><code>         A
 102          A
 103   #######.#########
 104   #######.........#
 105   #######.#######.#
 106   #######.#######.#
 107   #######.#######.#
 108   #####  B    ###.#
 109 BC...##  C    ###.#
 110   ##.##       ###.#
 111   ##...DE  F  ###.#
 112   #####    G  ###.#
 113   #########.#####.#
 114 DE..#######...###.#
 115   #.#########.###.#
 116 FG..#########.....#
 117   ###########.#####
 118              Z
 119              Z
 120 </code></pre>
 121 <p>This map of the maze shows solid walls (<code>#</code>) and open passages (<code>.</code>). Every maze on Pluto has a start (the open tile next to <code>AA</code>) and an end (the open tile next to <code>ZZ</code>). Mazes on Pluto also have portals; this maze has three pairs of portals: <code>BC</code>, <code>DE</code>, and <code>FG</code>. When on an open tile next to one of these labels, a single step can take you to the other tile with the same label. (You can only walk on <code>.</code> tiles; labels and empty space are not traversable.)</p>
 122 <p>One path through the maze doesn't require any portals.  Starting at <code>AA</code>, you could go down 1, right 8, down 12, left 4, and down 1 to reach <code>ZZ</code>, a total of 26 steps.</p>
 123 <p>However, there is a shorter path:  You could walk from <code>AA</code> to the inner <code>BC</code> portal (4 steps), warp to the outer <code>BC</code> portal (1 step), walk to the inner <code>DE</code> (6 steps), warp to the outer <code>DE</code> (1 step), walk to the outer <code>FG</code> (4 steps), warp to the inner <code>FG</code> (1 step), and finally walk to <code>ZZ</code> (6 steps). In total, this is only <em>23</em> steps.</p>
 124 <p>Here is a larger example:</p>
 125 <pre><code>                   A
 126                    A
 127   #################.#############
 128   #.#...#...................#.#.#
 129   #.#.#.###.###.###.#########.#.#
 130   #.#.#.......#...#.....#.#.#...#
 131   #.#########.###.#####.#.#.###.#
 132   #.............#.#.....#.......#
 133   ###.###########.###.#####.#.#.#
 134   #.....#        A   C    #.#.#.#
 135   #######        S   P    #####.#
 136   #.#...#                 #......VT
 137   #.#.#.#                 #.#####
 138   #...#.#               YN....#.#
 139   #.###.#                 #####.#
 140 DI....#.#                 #.....#
 141   #####.#                 #.###.#
 142 ZZ......#               QG....#..AS
 143   ###.###                 #######
 144 JO..#.#.#                 #.....#
 145   #.#.#.#                 ###.#.#
 146   #...#..DI             BU....#..LF
 147   #####.#                 #.#####
 148 YN......#               VT..#....QG
 149   #.###.#                 #.###.#
 150   #.#...#                 #.....#
 151   ###.###    J L     J    #.#.###
 152   #.....#    O F     P    #.#...#
 153   #.###.#####.#.#####.#####.###.#
 154   #...#.#.#...#.....#.....#.#...#
 155   #.#####.###.###.#.#.#########.#
 156   #...#.#.....#...#.#.#.#.....#.#
 157   #.###.#####.###.###.#.#.#######
 158   #.#.........#...#.............#
 159   #########.###.###.#############
 160            B   J   C
 161            U   P   P
 162 </code></pre>
 163 <p>Here, <code>AA</code> has no direct path to <code>ZZ</code>, but it does connect to <code>AS</code> and <code>CP</code>. By passing through <code>AS</code>, <code>QG</code>, <code>BU</code>, and <code>JO</code>, you can reach <code>ZZ</code> in <em>58</em> steps.</p>
 164 <p>In your maze, <em>how many steps does it take to get from the open tile marked <code>AA</code> to the open tile marked <code>ZZ</code>?</em></p>
 165 </article>
 166 <p>Your puzzle answer was <code>556</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Strangely, the exit isn't open when you reach it.  Then, you remember: the ancient Plutonians were famous for building <em>recursive spaces</em>.</p>
 167 <p>The marked connections in the maze aren't portals: they <em>physically connect</em> to a larger or smaller copy of the maze. Specifically, the labeled tiles around the inside edge actually connect to a smaller copy of the same maze, and the smaller copy's inner labeled tiles connect to yet a <em>smaller</em> copy, and so on.</p>
 168 <p>When you enter the maze, you are at the outermost level; when at the outermost level, only the outer labels <code>AA</code> and <code>ZZ</code> function (as the start and end, respectively); all other outer labeled tiles are effectively walls. At any other level, <code>AA</code> and <code>ZZ</code> count as walls, but the other outer labeled tiles bring you one level outward.</p>
 169 <p>Your goal is to find a path through the maze that brings you back to <code>ZZ</code> at the outermost level of the maze.</p>
 170 <p>In the first example above, the shortest path is now the loop around the right side. If the starting level is <code>0</code>, then taking the previously-shortest path would pass through <code>BC</code> (to level <code>1</code>), <code>DE</code> (to level <code>2</code>), and <code>FG</code> (back to level <code>1</code>). Because this is not the outermost level, <code>ZZ</code> is a wall, and the only option is to go back around to <code>BC</code>, which would only send you even deeper into the recursive maze.</p>
 171 <p>In the second example above, there is no path that brings you to <code>ZZ</code> at the outermost level.</p>
 172 <p>Here is a more interesting example:</p>
 173 <pre><code>             Z L X W       C
 174              Z P Q B       K
 175   ###########.#.#.#.#######.###############
 176   #...#.......#.#.......#.#.......#.#.#...#
 177   ###.#.#.#.#.#.#.#.###.#.#.#######.#.#.###
 178   #.#...#.#.#...#.#.#...#...#...#.#.......#
 179   #.###.#######.###.###.#.###.###.#.#######
 180   #...#.......#.#...#...#.............#...#
 181   #.#########.#######.#.#######.#######.###
 182   #...#.#    F       R I       Z    #.#.#.#
 183   #.###.#    D       E C       H    #.#.#.#
 184   #.#...#                           #...#.#
 185   #.###.#                           #.###.#
 186   #.#....OA                       WB..#.#..ZH
 187   #.###.#                           #.#.#.#
 188 CJ......#                           #.....#
 189   #######                           #######
 190   #.#....CK                         #......IC
 191   #.###.#                           #.###.#
 192   #.....#                           #...#.#
 193   ###.###                           #.#.#.#
 194 XF....#.#                         RF..#.#.#
 195   #####.#                           #######
 196   #......CJ                       NM..#...#
 197   ###.#.#                           #.###.#
 198 RE....#.#                           #......RF
 199   ###.###        X   X       L      #.#.#.#
 200   #.....#        F   Q       P      #.#.#.#
 201   ###.###########.###.#######.#########.###
 202   #.....#...#.....#.......#...#.....#.#...#
 203   #####.#.###.#######.#######.###.###.#.#.#
 204   #.......#.......#.#.#.#.#...#...#...#.#.#
 205   #####.###.#####.#.#.#.#.###.###.#.###.###
 206   #.......#.....#.#...#...............#...#
 207   #############.#.#.###.###################
 208                A O F   N
 209                A A D   M
 210 </code></pre>
 211 <p>One shortest path through the maze is the following:</p>
 212 <ul>
 213 <li>Walk from <code>AA</code> to <code>XF</code> (16 steps)</li>
 214 <li>Recurse into level 1 through <code>XF</code> (1 step)</li>
 215 <li>Walk from <code>XF</code> to <code>CK</code> (10 steps)</li>
 216 <li>Recurse into level 2 through <code>CK</code> (1 step)</li>
 217 <li>Walk from <code>CK</code> to <code>ZH</code> (14 steps)</li>
 218 <li>Recurse into level 3 through <code>ZH</code> (1 step)</li>
 219 <li>Walk from <code>ZH</code> to <code>WB</code> (10 steps)</li>
 220 <li>Recurse into level 4 through <code>WB</code> (1 step)</li>
 221 <li>Walk from <code>WB</code> to <code>IC</code> (10 steps)</li>
 222 <li>Recurse into level 5 through <code>IC</code> (1 step)</li>
 223 <li>Walk from <code>IC</code> to <code>RF</code> (10 steps)</li>
 224 <li>Recurse into level 6 through <code>RF</code> (1 step)</li>
 225 <li>Walk from <code>RF</code> to <code>NM</code> (8 steps)</li>
 226 <li>Recurse into level 7 through <code>NM</code> (1 step)</li>
 227 <li>Walk from <code>NM</code> to <code>LP</code> (12 steps)</li>
 228 <li>Recurse into level 8 through <code>LP</code> (1 step)</li>
 229 <li>Walk from <code>LP</code> to <code>FD</code> (24 steps)</li>
 230 <li>Recurse into level 9 through <code>FD</code> (1 step)</li>
 231 <li>Walk from <code>FD</code> to <code>XQ</code> (8 steps)</li>
 232 <li>Recurse into level 10 through <code>XQ</code> (1 step)</li>
 233 <li>Walk from <code>XQ</code> to <code>WB</code> (4 steps)</li>
 234 <li>Return to level 9 through <code>WB</code> (1 step)</li>
 235 <li>Walk from <code>WB</code> to <code>ZH</code> (10 steps)</li>
 236 <li>Return to level 8 through <code>ZH</code> (1 step)</li>
 237 <li>Walk from <code>ZH</code> to <code>CK</code> (14 steps)</li>
 238 <li>Return to level 7 through <code>CK</code> (1 step)</li>
 239 <li>Walk from <code>CK</code> to <code>XF</code> (10 steps)</li>
 240 <li>Return to level 6 through <code>XF</code> (1 step)</li>
 241 <li>Walk from <code>XF</code> to <code>OA</code> (14 steps)</li>
 242 <li>Return to level 5 through <code>OA</code> (1 step)</li>
 243 <li>Walk from <code>OA</code> to <code>CJ</code> (8 steps)</li>
 244 <li>Return to level 4 through <code>CJ</code> (1 step)</li>
 245 <li>Walk from <code>CJ</code> to <code>RE</code> (8 steps)</li>
 246 <li>Return to level 3 through <code>RE</code> (1 step)</li>
 247 <li>Walk from <code>RE</code> to <code>IC</code> (4 steps)</li>
 248 <li>Recurse into level 4 through <code>IC</code> (1 step)</li>
 249 <li>Walk from <code>IC</code> to <code>RF</code> (10 steps)</li>
 250 <li>Recurse into level 5 through <code>RF</code> (1 step)</li>
 251 <li>Walk from <code>RF</code> to <code>NM</code> (8 steps)</li>
 252 <li>Recurse into level 6 through <code>NM</code> (1 step)</li>
 253 <li>Walk from <code>NM</code> to <code>LP</code> (12 steps)</li>
 254 <li>Recurse into level 7 through <code>LP</code> (1 step)</li>
 255 <li>Walk from <code>LP</code> to <code>FD</code> (24 steps)</li>
 256 <li>Recurse into level 8 through <code>FD</code> (1 step)</li>
 257 <li>Walk from <code>FD</code> to <code>XQ</code> (8 steps)</li>
 258 <li>Recurse into level 9 through <code>XQ</code> (1 step)</li>
 259 <li>Walk from <code>XQ</code> to <code>WB</code> (4 steps)</li>
 260 <li>Return to level 8 through <code>WB</code> (1 step)</li>
 261 <li>Walk from <code>WB</code> to <code>ZH</code> (10 steps)</li>
 262 <li>Return to level 7 through <code>ZH</code> (1 step)</li>
 263 <li>Walk from <code>ZH</code> to <code>CK</code> (14 steps)</li>
 264 <li>Return to level 6 through <code>CK</code> (1 step)</li>
 265 <li>Walk from <code>CK</code> to <code>XF</code> (10 steps)</li>
 266 <li>Return to level 5 through <code>XF</code> (1 step)</li>
 267 <li>Walk from <code>XF</code> to <code>OA</code> (14 steps)</li>
 268 <li>Return to level 4 through <code>OA</code> (1 step)</li>
 269 <li>Walk from <code>OA</code> to <code>CJ</code> (8 steps)</li>
 270 <li>Return to level 3 through <code>CJ</code> (1 step)</li>
 271 <li>Walk from <code>CJ</code> to <code>RE</code> (8 steps)</li>
 272 <li>Return to level 2 through <code>RE</code> (1 step)</li>
 273 <li>Walk from <code>RE</code> to <code>XQ</code> (14 steps)</li>
 274 <li>Return to level 1 through <code>XQ</code> (1 step)</li>
 275 <li>Walk from <code>XQ</code> to <code>FD</code> (8 steps)</li>
 276 <li>Return to level 0 through <code>FD</code> (1 step)</li>
 277 <li>Walk from <code>FD</code> to <code>ZZ</code> (18 steps)</li>
 278 </ul>
 279 <p>This path takes a total of <em>396</em> steps to move from <code>AA</code> at the outermost layer to <code>ZZ</code> at the outermost layer.</p>
 280 <p>In your maze, when accounting for recursion, <em>how many steps does it take to get from the open tile marked <code>AA</code> to the open tile marked <code>ZZ</code>, both at the outermost layer?</em></p>
 281 </article>
 282 <p>Your puzzle answer was <code>6532</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 283 <p>At this point, you should <a href="/2019">return to your Advent calendar</a> and try another puzzle.</p>
 284 <p>If you still want to see it, you can <a href="20/input" target="_blank">get your puzzle input</a>.</p>
 285 <p>You can also <span class="share">[Share<span class="share-content">on
 286   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Donut+Maze%22+%2D+Day+20+%2D+Advent+of+Code+2019&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F20&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 287   <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+%22Donut+Maze%22+%2D+Day+20+%2D+Advent+of+Code+2019+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F20'}else{return false;}" target="_blank">Mastodon</a
 288 ></span>]</span> this puzzle.</p>
 289 </main>
 290
 291 <!-- ga -->
 292 <script>
 293 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 294 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 295 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 296 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 297 ga('create', 'UA-69522494-1', 'auto');
 298 ga('set', 'anonymizeIp', true);
 299 ga('send', 'pageview');
 300 </script>
 301 <!-- /ga -->
 302 </body>
 303 </html>