problems/day22.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 22 - 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">44*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;<span class="title-event-wrap">{year=&gt;</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://www.wearedevelopers.com/world-congress/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">WeAreDevelopers</a> - Use &quot;AOC-25&quot;, save EUR 25 and join 10^4 devs on June 6-7 at the WeAreDevelopers World Congress in Berlin ticket.get(now)</div></div>
  94 </div><!--/sidebar-->
  95
  96 <main>
  97 <article class="day-desc"><h2>--- Day 22: Mode Maze ---</h2><p>This is it, your final stop: the year <span title="Yes, really: there is no year zero.">-483</span>. It's snowing and dark outside; the only light you can see is coming from a small cottage in the distance. You make your way there and knock on the door.</p>
  98 <p>A portly man with a large, white beard answers the door and invites you inside. For someone living near the North Pole in -483, he must not get many visitors, but he doesn't act surprised to see you. Instead, he offers you some milk and cookies.</p>
  99 <p>After talking for a while, he asks a favor of you. His friend hasn't come back in a few hours, and he's not sure where he is.  Scanning the region briefly, you discover one life signal in a cave system nearby; his friend must have taken shelter there.  The man asks if you can go there to retrieve his friend.</p>
 100 <p>The cave is divided into square <em>regions</em> which are either dominantly <em>rocky</em>, <em>narrow</em>, or <em>wet</em> (called its <em>type</em>). Each region occupies exactly one <em>coordinate</em> in <code>X,Y</code> format where <code>X</code> and <code>Y</code> are integers and zero or greater. (Adjacent regions can be the same type.)</p>
 101 <p>The scan (your puzzle input) is not very detailed: it only reveals the <em>depth</em> of the cave system and the <em>coordinates of the target</em>. However, it does not reveal the type of each region. The mouth of the cave is at <code>0,0</code>.</p>
 102 <p>The man explains that due to the unusual geology in the area, there is a method to determine any region's type based on its <em>erosion level</em>. The erosion level of a region can be determined from its <em>geologic index</em>. The geologic index can be determined using the first rule that applies from the list below:</p>
 103 <ul>
 104 <li>The region at <code>0,0</code> (the mouth of the cave) has a geologic index of <code>0</code>.</li>
 105 <li>The region at the coordinates of the target has a geologic index of <code>0</code>.</li>
 106 <li>If the region's <code>Y</code> coordinate is <code>0</code>, the geologic index is its <code>X</code> coordinate times <code>16807</code>.</li>
 107 <li>If the region's <code>X</code> coordinate is <code>0</code>, the geologic index is its <code>Y</code> coordinate times <code>48271</code>.</li>
 108 <li>Otherwise, the region's geologic index is the result of multiplying the erosion <em>levels</em> of the regions at <code>X-1,Y</code> and <code>X,Y-1</code>.</li>
 109 </ul>
 110 <p>A region's <em>erosion level</em> is its <em>geologic index</em> plus the cave system's <em>depth</em>, all <a href="https://en.wikipedia.org/wiki/Modulo_operation">modulo</a> <code>20183</code>. Then:</p>
 111 <ul>
 112 <li>If the <em>erosion level modulo <code>3</code></em> is <code>0</code>, the region's type is <em>rocky</em>.</li>
 113 <li>If the <em>erosion level modulo <code>3</code></em> is <code>1</code>, the region's type is <em>wet</em>.</li>
 114 <li>If the <em>erosion level modulo <code>3</code></em> is <code>2</code>, the region's type is <em>narrow</em>.</li>
 115 </ul>
 116 <p>For example, suppose the cave system's depth is <code>510</code> and the target's coordinates are <code>10,10</code>. Using <code>%</code> to represent the modulo operator, the cavern would look as follows:</p>
 117 <ul>
 118 <li>At <code>0,0</code>, the geologic index is <code>0</code>. The erosion level is <code>(0 + 510) % 20183 = 510</code>. The type is <code>510 % 3 = 0</code>, <em>rocky</em>.</li>
 119 <li>At <code>1,0</code>, because the <code>Y</code> coordinate is <code>0</code>, the geologic index is <code>1 * 16807 = 16807</code>. The erosion level is <code>(16807 + 510) % 20183 = 17317</code>. The type is <code>17317 % 3 = 1</code>, <em>wet</em>.</li>
 120 <li>At <code>0,1</code>, because the <code>X</code> coordinate is <code>0</code>, the geologic index is <code> 1 * 48271 = 48271</code>. The erosion level is <code>(48271 + 510) % 20183 = 8415</code>. The type is <code>8415 % 3 = 0</code>, <em>rocky</em>.</li>
 121 <li>At <code>1,1</code>, neither coordinate is <code>0</code> and it is not the coordinate of the target, so the geologic index is the erosion level of <code>0,1</code> (<code>8415</code>) times the erosion level of <code>1,0</code> (<code>17317</code>), <code>8415 * 17317 = 145722555</code>. The erosion level is <code>(145722555 + 510) % 20183 = 1805</code>. The type is <code>1805 % 3 = 2</code>, <em>narrow</em>.</li>
 122 <li>At <code>10,10</code>, because they are the target's coordinates, the geologic index is <code>0</code>. The erosion level is <code>(0 + 510) % 20183 = 510</code>. The type is <code>510 % 3 = 0</code>, <em>rocky</em>.</li>
 123 </ul>
 124 <p>Drawing this same cave system with rocky as <code>.</code>, wet as <code>=</code>, narrow as <code>|</code>, the mouth as <code>M</code>, the target as <code>T</code>, with <code>0,0</code> in the top-left corner, <code>X</code> increasing to the right, and <code>Y</code> increasing downward, the top-left corner of the map looks like this:</p>
 125 <pre><code><em>M</em>=.|=.|.|=.|=|=.
 126 .|=|=|||..|.=...
 127 .==|....||=..|==
 128 =.|....|.==.|==.
 129 =|..==...=.|==..
 130 =||.=.=||=|=..|=
 131 |.=.===|||..=..|
 132 |..==||=.|==|===
 133 .=..===..=|.|||.
 134 .======|||=|=.|=
 135 .===|=|===<em>T</em>===||
 136 =|||...|==..|=.|
 137 =.=|=.=..=.||==|
 138 ||=|=...|==.=|==
 139 |=.=||===.|||===
 140 ||.|==.|.|.||=||
 141 </code></pre>
 142 <p>Before you go in, you should determine the <em>risk level</em> of the area. For the rectangle that has a top-left corner of region <code>0,0</code> and a bottom-right corner of the region containing the target, add up the risk level of each individual region: <code>0</code> for rocky regions, <code>1</code> for wet regions, and <code>2</code> for narrow regions.</p>
 143 <p>In the cave system above, because the mouth is at <code>0,0</code> and the target is at <code>10,10</code>, adding up the risk level of all regions with an <code>X</code> coordinate from <code>0</code> to <code>10</code> and a <code>Y</code> coordinate from <code>0</code> to <code>10</code>, this total is <code><em>114</em></code>.</p>
 144 <p><em>What is the total risk level for the smallest rectangle that includes <code>0,0</code> and the target's coordinates?</em></p>
 145 </article>
 146 <p>Your puzzle answer was <code>8575</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Okay, it's time to go rescue the man's friend.</p>
 147 <p>As you leave, he hands you some tools: a <em>torch</em> and some <em>climbing gear</em>. You can't equip both tools at once, but you can choose to use <em>neither</em>.</p>
 148 <p>Tools can only be used in certain regions:</p>
 149 <ul>
 150 <li>In <em>rocky</em> regions, you can use the <em>climbing gear</em> or the <em>torch</em>. You cannot use <em>neither</em> (you'll likely slip and fall).</li>
 151 <li>In <em>wet</em> regions, you can use the <em>climbing gear</em> or <em>neither</em> tool. You cannot use the <em>torch</em> (if it gets wet, you won't have a light source).</li>
 152 <li>In <em>narrow</em> regions, you can use the <em>torch</em> or <em>neither</em> tool. You cannot use the <em>climbing gear</em> (it's too bulky to fit).</li>
 153 </ul>
 154 <p>You start at <code>0,0</code> (the mouth of the cave) with <em>the torch equipped</em> and must reach the target coordinates as quickly as possible. The regions with negative <code>X</code> or <code>Y</code> are solid rock and cannot be traversed. The fastest route might involve entering regions beyond the <code>X</code> or <code>Y</code> coordinate of the target.</p>
 155 <p>You can <em>move to an adjacent region</em> (up, down, left, or right; never diagonally) if your currently equipped tool allows you to enter that region. Moving to an adjacent region takes <em>one minute</em>. (For example, if you have the <em>torch</em> equipped, you can move between <em>rocky</em> and <em>narrow</em> regions, but cannot enter <em>wet</em> regions.)</p>
 156 <p>You can <em>change your currently equipped tool or put both away</em> if your new equipment would be valid for your current region. Switching to using the <em>climbing gear</em>, <em>torch</em>, or <em>neither</em> always takes <em>seven minutes</em>, regardless of which tools you start with. (For example, if you are in a <em>rocky</em> region, you can switch from the <em>torch</em> to the <em>climbing gear</em>, but you cannot switch to <em>neither</em>.)</p>
 157 <p>Finally, once you reach the target, you need the <em>torch</em> equipped before you can find him in the dark. The target is always in a <em>rocky</em> region, so if you arrive there with <em>climbing gear</em> equipped, you will need to spend seven minutes switching to your torch.</p>
 158 <p>For example, using the same cave system as above, starting in the top left corner (<code>0,0</code>) and moving to the bottom right corner (the target, <code>10,10</code>) as quickly as possible, one possible route is as follows, with your current position marked <code>X</code>:</p>
 159 <pre><code>Initially:
 160 <em>X</em>=.|=.|.|=.|=|=.
 161 .|=|=|||..|.=...
 162 .==|....||=..|==
 163 =.|....|.==.|==.
 164 =|..==...=.|==..
 165 =||.=.=||=|=..|=
 166 |.=.===|||..=..|
 167 |..==||=.|==|===
 168 .=..===..=|.|||.
 169 .======|||=|=.|=
 170 .===|=|===T===||
 171 =|||...|==..|=.|
 172 =.=|=.=..=.||==|
 173 ||=|=...|==.=|==
 174 |=.=||===.|||===
 175 ||.|==.|.|.||=||
 176
 177 Down:
 178 M=.|=.|.|=.|=|=.
 179 <em>X</em>|=|=|||..|.=...
 180 .==|....||=..|==
 181 =.|....|.==.|==.
 182 =|..==...=.|==..
 183 =||.=.=||=|=..|=
 184 |.=.===|||..=..|
 185 |..==||=.|==|===
 186 .=..===..=|.|||.
 187 .======|||=|=.|=
 188 .===|=|===T===||
 189 =|||...|==..|=.|
 190 =.=|=.=..=.||==|
 191 ||=|=...|==.=|==
 192 |=.=||===.|||===
 193 ||.|==.|.|.||=||
 194
 195 Right:
 196 M=.|=.|.|=.|=|=.
 197 .<em>X</em>=|=|||..|.=...
 198 .==|....||=..|==
 199 =.|....|.==.|==.
 200 =|..==...=.|==..
 201 =||.=.=||=|=..|=
 202 |.=.===|||..=..|
 203 |..==||=.|==|===
 204 .=..===..=|.|||.
 205 .======|||=|=.|=
 206 .===|=|===T===||
 207 =|||...|==..|=.|
 208 =.=|=.=..=.||==|
 209 ||=|=...|==.=|==
 210 |=.=||===.|||===
 211 ||.|==.|.|.||=||
 212
 213 Switch from using the torch to neither tool:
 214 M=.|=.|.|=.|=|=.
 215 .<em>X</em>=|=|||..|.=...
 216 .==|....||=..|==
 217 =.|....|.==.|==.
 218 =|..==...=.|==..
 219 =||.=.=||=|=..|=
 220 |.=.===|||..=..|
 221 |..==||=.|==|===
 222 .=..===..=|.|||.
 223 .======|||=|=.|=
 224 .===|=|===T===||
 225 =|||...|==..|=.|
 226 =.=|=.=..=.||==|
 227 ||=|=...|==.=|==
 228 |=.=||===.|||===
 229 ||.|==.|.|.||=||
 230
 231 Right 3:
 232 M=.|=.|.|=.|=|=.
 233 .|=|<em>X</em>|||..|.=...
 234 .==|....||=..|==
 235 =.|....|.==.|==.
 236 =|..==...=.|==..
 237 =||.=.=||=|=..|=
 238 |.=.===|||..=..|
 239 |..==||=.|==|===
 240 .=..===..=|.|||.
 241 .======|||=|=.|=
 242 .===|=|===T===||
 243 =|||...|==..|=.|
 244 =.=|=.=..=.||==|
 245 ||=|=...|==.=|==
 246 |=.=||===.|||===
 247 ||.|==.|.|.||=||
 248
 249 Switch from using neither tool to the climbing gear:
 250 M=.|=.|.|=.|=|=.
 251 .|=|<em>X</em>|||..|.=...
 252 .==|....||=..|==
 253 =.|....|.==.|==.
 254 =|..==...=.|==..
 255 =||.=.=||=|=..|=
 256 |.=.===|||..=..|
 257 |..==||=.|==|===
 258 .=..===..=|.|||.
 259 .======|||=|=.|=
 260 .===|=|===T===||
 261 =|||...|==..|=.|
 262 =.=|=.=..=.||==|
 263 ||=|=...|==.=|==
 264 |=.=||===.|||===
 265 ||.|==.|.|.||=||
 266
 267 Down 7:
 268 M=.|=.|.|=.|=|=.
 269 .|=|=|||..|.=...
 270 .==|....||=..|==
 271 =.|....|.==.|==.
 272 =|..==...=.|==..
 273 =||.=.=||=|=..|=
 274 |.=.===|||..=..|
 275 |..==||=.|==|===
 276 .=..<em>X</em>==..=|.|||.
 277 .======|||=|=.|=
 278 .===|=|===T===||
 279 =|||...|==..|=.|
 280 =.=|=.=..=.||==|
 281 ||=|=...|==.=|==
 282 |=.=||===.|||===
 283 ||.|==.|.|.||=||
 284
 285 Right:
 286 M=.|=.|.|=.|=|=.
 287 .|=|=|||..|.=...
 288 .==|....||=..|==
 289 =.|....|.==.|==.
 290 =|..==...=.|==..
 291 =||.=.=||=|=..|=
 292 |.=.===|||..=..|
 293 |..==||=.|==|===
 294 .=..=<em>X</em>=..=|.|||.
 295 .======|||=|=.|=
 296 .===|=|===T===||
 297 =|||...|==..|=.|
 298 =.=|=.=..=.||==|
 299 ||=|=...|==.=|==
 300 |=.=||===.|||===
 301 ||.|==.|.|.||=||
 302
 303 Down 3:
 304 M=.|=.|.|=.|=|=.
 305 .|=|=|||..|.=...
 306 .==|....||=..|==
 307 =.|....|.==.|==.
 308 =|..==...=.|==..
 309 =||.=.=||=|=..|=
 310 |.=.===|||..=..|
 311 |..==||=.|==|===
 312 .=..===..=|.|||.
 313 .======|||=|=.|=
 314 .===|=|===T===||
 315 =|||.<em>X</em>.|==..|=.|
 316 =.=|=.=..=.||==|
 317 ||=|=...|==.=|==
 318 |=.=||===.|||===
 319 ||.|==.|.|.||=||
 320
 321 Right:
 322 M=.|=.|.|=.|=|=.
 323 .|=|=|||..|.=...
 324 .==|....||=..|==
 325 =.|....|.==.|==.
 326 =|..==...=.|==..
 327 =||.=.=||=|=..|=
 328 |.=.===|||..=..|
 329 |..==||=.|==|===
 330 .=..===..=|.|||.
 331 .======|||=|=.|=
 332 .===|=|===T===||
 333 =|||..<em>X</em>|==..|=.|
 334 =.=|=.=..=.||==|
 335 ||=|=...|==.=|==
 336 |=.=||===.|||===
 337 ||.|==.|.|.||=||
 338
 339 Down:
 340 M=.|=.|.|=.|=|=.
 341 .|=|=|||..|.=...
 342 .==|....||=..|==
 343 =.|....|.==.|==.
 344 =|..==...=.|==..
 345 =||.=.=||=|=..|=
 346 |.=.===|||..=..|
 347 |..==||=.|==|===
 348 .=..===..=|.|||.
 349 .======|||=|=.|=
 350 .===|=|===T===||
 351 =|||...|==..|=.|
 352 =.=|=.<em>X</em>..=.||==|
 353 ||=|=...|==.=|==
 354 |=.=||===.|||===
 355 ||.|==.|.|.||=||
 356
 357 Right 4:
 358 M=.|=.|.|=.|=|=.
 359 .|=|=|||..|.=...
 360 .==|....||=..|==
 361 =.|....|.==.|==.
 362 =|..==...=.|==..
 363 =||.=.=||=|=..|=
 364 |.=.===|||..=..|
 365 |..==||=.|==|===
 366 .=..===..=|.|||.
 367 .======|||=|=.|=
 368 .===|=|===T===||
 369 =|||...|==..|=.|
 370 =.=|=.=..=<em>X</em>||==|
 371 ||=|=...|==.=|==
 372 |=.=||===.|||===
 373 ||.|==.|.|.||=||
 374
 375 Up 2:
 376 M=.|=.|.|=.|=|=.
 377 .|=|=|||..|.=...
 378 .==|....||=..|==
 379 =.|....|.==.|==.
 380 =|..==...=.|==..
 381 =||.=.=||=|=..|=
 382 |.=.===|||..=..|
 383 |..==||=.|==|===
 384 .=..===..=|.|||.
 385 .======|||=|=.|=
 386 .===|=|===<em>X</em>===||
 387 =|||...|==..|=.|
 388 =.=|=.=..=.||==|
 389 ||=|=...|==.=|==
 390 |=.=||===.|||===
 391 ||.|==.|.|.||=||
 392
 393 Switch from using the climbing gear to the torch:
 394 M=.|=.|.|=.|=|=.
 395 .|=|=|||..|.=...
 396 .==|....||=..|==
 397 =.|....|.==.|==.
 398 =|..==...=.|==..
 399 =||.=.=||=|=..|=
 400 |.=.===|||..=..|
 401 |..==||=.|==|===
 402 .=..===..=|.|||.
 403 .======|||=|=.|=
 404 .===|=|===<em>X</em>===||
 405 =|||...|==..|=.|
 406 =.=|=.=..=.||==|
 407 ||=|=...|==.=|==
 408 |=.=||===.|||===
 409 ||.|==.|.|.||=||
 410 </code></pre>
 411 <p>This is tied with other routes as the <em>fastest way to reach the target</em>: <code><em>45</em></code> minutes. In it, <code>21</code> minutes are spent switching tools (three times, seven minutes each) and the remaining <code>24</code> minutes are spent moving.</p>
 412 <p><em>What is the fewest number of minutes you can take to reach the target?</em></p>
 413 </article>
 414 <p>Your puzzle answer was <code>999</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 415 <p>At this point, you should <a href="/2018">return to your Advent calendar</a> and try another puzzle.</p>
 416 <p>If you still want to see it, you can <a href="22/input" target="_blank">get your puzzle input</a>.</p>
 417 <p>You can also <span class="share">[Share<span class="share-content">on
 418   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Mode+Maze%22+%2D+Day+22+%2D+Advent+of+Code+2018&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F22&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 419   <a href="http://www.reddit.com/submit?url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F22&amp;title=I%27ve+completed+%22Mode+Maze%22+%2D+Day+22+%2D+Advent+of+Code+2018" target="_blank">Reddit</a
 420 ></span>]</span> this puzzle.</p>
 421 </main>
 422
 423 <!-- ga -->
 424 <script>
 425 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 426 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 427 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 428 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 429 ga('create', 'UA-69522494-1', 'auto');
 430 ga('set', 'anonymizeIp', true);
 431 ga('send', 'pageview');
 432 </script>
 433 <!-- /ga -->
 434 </body>
 435 </html>