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 2018</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?20"/>
   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 Google, and I can only take
  23 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; the easiest ones take 3-4 hours each, but the
  31 harder ones take 6-8 hours, and a few even longer than that. 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="/2018/about">[About]</a></li><li><a href="/2018/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode-2019" target="_blank">[Shop]</a></li><li><a href="/2018/settings">[Settings]</a></li><li><a href="/2018/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2018/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">38*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">sub y{</span><a href="/2018">2018</a><span class="title-event-wrap">}</span></h1><nav><ul><li><a href="/2018">[Calendar]</a></li><li><a href="/2018/support">[AoC++]</a></li><li><a href="/2018/sponsors">[Sponsors]</a></li><li><a href="/2018/leaderboard">[Leaderboard]</a></li><li><a href="/2018/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2018/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://xebia.com/community/advent-of-code" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Xebia</a> - an international network of passionate technologists and craftspeople, dedicated to exploring and creating new frontiers in IT</div></div>
  94 </div><!--/sidebar-->
  95
  96 <main>
  97 <article class="day-desc"><h2>--- Day 20: A Regular Map ---</h2><p>While you were learning about instruction pointers, the Elves made considerable progress. When you look up, you discover that the North Pole base construction project has completely surrounded you.</p>
  98 <p>The area you are in is made up entirely of <em>rooms</em> and <em>doors</em>. The rooms are arranged in a grid, and rooms only connect to adjacent rooms when a door is present between them.</p>
  99 <p>For example, drawing rooms as <code>.</code>, walls as <code>#</code>, doors as <code>|</code> or <code>-</code>, your current position as <code>X</code>, and where north is up, the area you're in might look like this:</p>
 100 <pre><code>#####
 101 #.|.#
 102 #-###
 103 #.|X#
 104 #####
 105 </code></pre>
 106 <p>You get the attention of a passing construction Elf and ask for a map. "I don't have time to draw out a map of this place - it's <em>huge</em>. Instead, I can give you directions to <em>every room in the facility</em>!" He writes down some directions on a piece of parchment and runs off. In the example above, the instructions might have been <code>^WNE$</code>, a <a href="https://en.wikipedia.org/wiki/Regular_expression">regular expression</a> or "<em>regex</em>" (your puzzle input).</p>
 107 <p>The regex matches routes (like <code>WNE</code> for "west, north, east") that will take you from your current room through various doors in the facility. In aggregate, the routes will take you through <em>every door in the facility at least once</em>; mapping out all of these routes will let you build a proper map and find your way around.</p>
 108 <p><code>^</code> and <code>$</code> are at the beginning and end of your regex; these just mean that the regex doesn't match anything outside the routes it describes. (Specifically, <code>^</code> matches the start of the route, and <code>$</code> matches the end of it.) These characters will not appear elsewhere in the regex.</p>
 109 <p>The rest of the regex matches various sequences of the characters <code>N</code> (north), <code>S</code> (south), <code>E</code> (east), and <code>W</code> (west). In the example above, <code>^WNE$</code> matches only one route, <code>WNE</code>, which means you can move <em>west, then north, then east</em> from your current position. Sequences of letters like this always match that exact route in the same order.</p>
 110 <p>Sometimes, the route can <em>branch</em>. A branch is given by a <em>list of options</em> separated by pipes (<code>|</code>) and wrapped in parentheses. So, <code>^N(E|W)N$</code> contains a branch: after going north, you must choose to go <em>either east or west</em> before finishing your route by going north again. By tracing out the possible routes after branching, you can determine where the doors are and, therefore, where the rooms are in the facility.</p>
 111 <p>For example, consider this regex: <code>^ENWWW(NEEE|SSE(EE|N))$</code></p>
 112 <p>This regex begins with <code>ENWWW</code>, which means that from your current position, all routes must begin by moving east, north, and then west three times, in that order. After this, there is a branch.  Before you consider the branch, this is what you know about the map so far, with doors you aren't sure about marked with a <code>?</code>:</p>
 113 <pre><code>#?#?#?#?#
 114 ?.|.|.|.?
 115 #?#?#?#-#
 116     ?X|.?
 117     #?#?#
 118 </code></pre>
 119 <p>After this point, there is <code>(NEEE|SSE(EE|N))</code>. This gives you exactly two options: <code>NEEE</code> and <code>SSE(EE|N)</code>. By following <code>NEEE</code>, the map now looks like this:</p>
 120 <pre><code>#?#?#?#?#
 121 ?.|.|.|.?
 122 #-#?#?#?#
 123 ?.|.|.|.?
 124 #?#?#?#-#
 125     ?X|.?
 126     #?#?#
 127 </code></pre>
 128 <p>Now, only <code>SSE(EE|N)</code> remains. Because it is in the same parenthesized group as <code>NEEE</code>, it starts from the same room <code>NEEE</code> started in. It states that starting from that point, there exist doors which will allow you to move south twice, then east; this ends up at another branch. After that, you can either move east twice or north once. This information fills in the rest of the doors:</p>
 129 <pre><code>#?#?#?#?#
 130 ?.|.|.|.?
 131 #-#?#?#?#
 132 ?.|.|.|.?
 133 #-#?#?#-#
 134 ?.?.?X|.?
 135 #-#-#?#?#
 136 ?.|.|.|.?
 137 #?#?#?#?#
 138 </code></pre>
 139 <p>Once you've followed all possible routes, you know the remaining unknown parts are all walls, producing a finished map of the facility:</p>
 140 <pre><code>#########
 141 #.|.|.|.#
 142 #-#######
 143 #.|.|.|.#
 144 #-#####-#
 145 #.#.#X|.#
 146 #-#-#####
 147 #.|.|.|.#
 148 #########
 149 </code></pre>
 150 <p>Sometimes, a list of options can have an <em>empty option</em>, like <code>(NEWS|WNSE|)</code>. This means that routes at this point could effectively skip the options in parentheses and move on immediately.  For example, consider this regex and the corresponding map:</p>
 151 <pre><code>^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$
 152
 153 ###########
 154 #.|.#.|.#.#
 155 #-###-#-#-#
 156 #.|.|.#.#.#
 157 #-#####-#-#
 158 #.#.#X|.#.#
 159 #-#-#####-#
 160 #.#.|.|.|.#
 161 #-###-###-#
 162 #.|.|.#.|.#
 163 ###########
 164 </code></pre>
 165 <p>This regex has one main route which, at three locations, can optionally include additional detours and be valid: <code>(NEWS|)</code>, <code>(WNSE|)</code>, and <code>(SWEN|)</code>. Regardless of which option is taken, the route continues from the position it is left at after taking those steps. So, for example, this regex matches all of the following routes (and more that aren't listed here):</p>
 166 <ul>
 167 <li><code>ENNWSWWSSSEENEENNN</code></li>
 168 <li><code>ENNWSWW<em>NEWS</em>SSSEENEENNN</code></li>
 169 <li><code>ENNWSWW<em>NEWS</em>SSSEENEE<em>SWEN</em>NNN</code></li>
 170 <li><code>ENNWSWWSSSEEN<em>WNSE</em>EENNN</code></li>
 171 </ul>
 172 <p>By following the various routes the regex matches, a full map of all of the doors and rooms in the facility can be assembled.</p>
 173 <p>To get a sense for the size of this facility, you'd like to determine which room is <em>furthest</em> from you: specifically, you would like to find the room for which the <em>shortest path to that room would require passing through the most doors</em>.</p>
 174 <ul>
 175 <li>In the first example (<code>^WNE$</code>), this would be the north-east corner <code><em>3</em></code> doors away.</li>
 176 <li>In the second example (<code>^ENWWW(NEEE|SSE(EE|N))$</code>), this would be the south-east corner <code><em>10</em></code> doors away.</li>
 177 <li>In the third example (<code>^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$</code>), this would be the north-east corner <code><em>18</em></code> doors away.</li>
 178 </ul>
 179 <p>Here are a few more examples:</p>
 180 <pre><code>Regex: ^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$
 181 Furthest room requires passing 23 doors
 182
 183 #############
 184 #.|.|.|.|.|.#
 185 #-#####-###-#
 186 #.#.|.#.#.#.#
 187 #-#-###-#-#-#
 188 #.#.#.|.#.|.#
 189 #-#-#-#####-#
 190 #.#.#.#X|.#.#
 191 #-#-#-###-#-#
 192 #.|.#.|.#.#.#
 193 ###-#-###-#-#
 194 #.|.#.|.|.#.#
 195 #############
 196 </code></pre>
 197 <pre><code>Regex: ^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$
 198 Furthest room requires passing 31 doors
 199
 200 ###############
 201 #.|.|.|.#.|.|.#
 202 #-###-###-#-#-#
 203 #.|.#.|.|.#.#.#
 204 #-#########-#-#
 205 #.#.|.|.|.|.#.#
 206 #-#-#########-#
 207 #.#.#.|X#.|.#.#
 208 ###-#-###-#-#-#
 209 #.|.#.#.|.#.|.#
 210 #-###-#####-###
 211 #.|.#.|.|.#.#.#
 212 #-#-#####-#-#-#
 213 #.#.|.|.|.#.|.#
 214 ###############
 215 </code></pre>
 216 <p><em>What is the largest number of doors you would be required to pass through to reach a room?</em> That is, find the room for which the shortest path from your starting location to that room would require passing through the most doors; what is the fewest doors you can pass through to reach it?</p>
 217 </article>
 218 <p>To begin, <a href="20/input" target="_blank">get your puzzle input</a>.</p>
 219 <form method="post" action="20/answer"><input type="hidden" name="level" value="1"/><p>Answer: <input type="text" name="answer" autocomplete="off"/> <input type="submit" value="[Submit]"/></p></form>
 220 <p>You can also <span class="share">[Share<span class="share-content">on
 221   <a href="https://twitter.com/intent/tweet?text=%22A+Regular+Map%22+%2D+Day+20+%2D+Advent+of+Code+2018&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F20&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 222   <a href="http://www.reddit.com/submit?url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F20&amp;title=%22A+Regular+Map%22+%2D+Day+20+%2D+Advent+of+Code+2018" target="_blank">Reddit</a
 223 ></span>]</span> this puzzle.</p>
 224 </main>
 225
 226 <!-- ga -->
 227 <script>
 228 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 229 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 230 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 231 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 232 ga('create', 'UA-69522494-1', 'auto');
 233 ga('set', 'anonymizeIp', true);
 234 ga('send', 'pageview');
 235 </script>
 236 <!-- /ga -->
 237 </body>
 238 </html>