problems/day15.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 15 - Advent of Code 2021</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?26"/>
   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, social media), I
  27 built the whole thing myself, including the design, animations, prose, and all
  28 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="/2021/about">[About]</a></li><li><a href="/2021/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2021/settings">[Settings]</a></li><li><a href="/2021/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2021/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">30*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">sub y{</span><a href="/2021">2021</a><span class="title-event-wrap">}</span></h1><nav><ul><li><a href="/2021">[Calendar]</a></li><li><a href="/2021/support">[AoC++]</a></li><li><a href="/2021/sponsors">[Sponsors]</a></li><li><a href="/2021/leaderboard">[Leaderboard]</a></li><li><a href="/2021/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2021/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://rick379856.typeform.com/to/oQ0e2jpi?utm_source=event&amp;utm_medium=ad&amp;utm_campaign=adventofcode2021" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Honeycomb</a> - You like performant, correct code. So do we. Distributed systems should be easy to understand. Use Honeycomb for free to debug your distributed systems and get a free shirt. Download our white papers and watch our demo.</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 15: Chiton ---</h2><p>You've almost reached the exit of the cave, but the walls are getting closer together. Your submarine can barely still fit, though; the main problem is that the walls of the cave are covered in <a href="https://en.wikipedia.org/wiki/Chiton" target="_blank">chitons</a>, and it would be best not to bump any of them.</p>
  99 <p>The cavern is large, but has a very low ceiling, restricting your motion to two dimensions. The shape of the cavern resembles a square; a quick scan of chiton density produces a map of <em>risk level</em> throughout the cave (your puzzle input). For example:</p>
 100 <pre><code>1163751742
 101 1381373672
 102 2136511328
 103 3694931569
 104 7463417111
 105 1319128137
 106 1359912421
 107 3125421639
 108 1293138521
 109 2311944581
 110 </code></pre>
 111 <p>You start in the top left position, your destination is the bottom right position, and you <span title="Can't go diagonal until we can repair the caterpillar unit. Could be the liquid helium or the superconductors.">cannot move diagonally</span>. The number at each position is its <em>risk level</em>; to determine the total risk of an entire path, add up the risk levels of each position you <em>enter</em> (that is, don't count the risk level of your starting position unless you enter it; leaving it adds no risk to your total).</p>
 112 <p>Your goal is to find a path with the <em>lowest total risk</em>. In this example, a path with the lowest total risk is highlighted here:</p>
 113 <pre><code><em>1</em>163751742
 114 <em>1</em>381373672
 115 <em>2136511</em>328
 116 369493<em>15</em>69
 117 7463417<em>1</em>11
 118 1319128<em>13</em>7
 119 13599124<em>2</em>1
 120 31254216<em>3</em>9
 121 12931385<em>21</em>
 122 231194458<em>1</em>
 123 </code></pre>
 124 <p>The total risk of this path is <code><em>40</em></code> (the starting position is never entered, so its risk is not counted).</p>
 125 <p><em>What is the lowest total risk of any path from the top left to the bottom right?</em></p>
 126 </article>
 127 <p>Your puzzle answer was <code>503</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Now that you know how to find low-risk paths in the cave, you can try to find your way out.</p>
 128 <p>The entire cave is actually <em>five times larger in both dimensions</em> than you thought; the area you originally scanned is just one tile in a 5x5 tile area that forms the full map. Your original map tile repeats to the right and downward; each time the tile repeats to the right or downward, all of its risk levels <em>are 1 higher</em> than the tile immediately up or left of it. However, risk levels above <code>9</code> wrap back around to <code>1</code>. So, if your original map had some position with a risk level of <code>8</code>, then that same position on each of the 25 total tiles would be as follows:</p>
 129 <pre><code>8 9 1 2 3
 130 9 1 2 3 4
 131 1 2 3 4 5
 132 2 3 4 5 6
 133 3 4 5 6 7
 134 </code></pre>
 135 <p>Each single digit above corresponds to the example position with a value of <code>8</code> on the top-left tile. Because the full map is actually five times larger in both dimensions, that position appears a total of 25 times, once in each duplicated tile, with the values shown above.</p>
 136 <p>Here is the full five-times-as-large version of the first example above, with the original map in the top left corner highlighted:</p>
 137 <pre><code><em>1163751742</em>2274862853338597396444961841755517295286
 138 <em>1381373672</em>2492484783351359589446246169155735727126
 139 <em>2136511328</em>3247622439435873354154698446526571955763
 140 <em>3694931569</em>4715142671582625378269373648937148475914
 141 <em>7463417111</em>8574528222968563933317967414442817852555
 142 <em>1319128137</em>2421239248353234135946434524615754563572
 143 <em>1359912421</em>2461123532357223464346833457545794456865
 144 <em>3125421639</em>4236532741534764385264587549637569865174
 145 <em>1293138521</em>2314249632342535174345364628545647573965
 146 <em>2311944581</em>3422155692453326671356443778246755488935
 147 22748628533385973964449618417555172952866628316397
 148 24924847833513595894462461691557357271266846838237
 149 32476224394358733541546984465265719557637682166874
 150 47151426715826253782693736489371484759148259586125
 151 85745282229685639333179674144428178525553928963666
 152 24212392483532341359464345246157545635726865674683
 153 24611235323572234643468334575457944568656815567976
 154 42365327415347643852645875496375698651748671976285
 155 23142496323425351743453646285456475739656758684176
 156 34221556924533266713564437782467554889357866599146
 157 33859739644496184175551729528666283163977739427418
 158 35135958944624616915573572712668468382377957949348
 159 43587335415469844652657195576376821668748793277985
 160 58262537826937364893714847591482595861259361697236
 161 96856393331796741444281785255539289636664139174777
 162 35323413594643452461575456357268656746837976785794
 163 35722346434683345754579445686568155679767926678187
 164 53476438526458754963756986517486719762859782187396
 165 34253517434536462854564757396567586841767869795287
 166 45332667135644377824675548893578665991468977611257
 167 44961841755517295286662831639777394274188841538529
 168 46246169155735727126684683823779579493488168151459
 169 54698446526571955763768216687487932779859814388196
 170 69373648937148475914825958612593616972361472718347
 171 17967414442817852555392896366641391747775241285888
 172 46434524615754563572686567468379767857948187896815
 173 46833457545794456865681556797679266781878137789298
 174 64587549637569865174867197628597821873961893298417
 175 45364628545647573965675868417678697952878971816398
 176 56443778246755488935786659914689776112579188722368
 177 55172952866628316397773942741888415385299952649631
 178 57357271266846838237795794934881681514599279262561
 179 65719557637682166874879327798598143881961925499217
 180 71484759148259586125936169723614727183472583829458
 181 28178525553928963666413917477752412858886352396999
 182 57545635726865674683797678579481878968159298917926
 183 57944568656815567976792667818781377892989248891319
 184 75698651748671976285978218739618932984172914319528
 185 56475739656758684176786979528789718163989182927419
 186 67554889357866599146897761125791887223681299833479
 187 </code></pre>
 188 <p>Equipped with the full map, you can now find a path from the top left corner to the bottom right corner with the lowest total risk:</p>
 189 <pre><code><em>1</em>1637517422274862853338597396444961841755517295286
 190 <em>1</em>3813736722492484783351359589446246169155735727126
 191 <em>2</em>1365113283247622439435873354154698446526571955763
 192 <em>3</em>6949315694715142671582625378269373648937148475914
 193 <em>7</em>4634171118574528222968563933317967414442817852555
 194 <em>1</em>3191281372421239248353234135946434524615754563572
 195 <em>1</em>3599124212461123532357223464346833457545794456865
 196 <em>3</em>1254216394236532741534764385264587549637569865174
 197 <em>1</em>2931385212314249632342535174345364628545647573965
 198 <em>2</em>3119445813422155692453326671356443778246755488935
 199 <em>2</em>2748628533385973964449618417555172952866628316397
 200 <em>2</em>4924847833513595894462461691557357271266846838237
 201 <em>324</em>76224394358733541546984465265719557637682166874
 202 47<em>15</em>1426715826253782693736489371484759148259586125
 203 857<em>4</em>5282229685639333179674144428178525553928963666
 204 242<em>1</em>2392483532341359464345246157545635726865674683
 205 246<em>1123532</em>3572234643468334575457944568656815567976
 206 423653274<em>1</em>5347643852645875496375698651748671976285
 207 231424963<em>2342</em>5351743453646285456475739656758684176
 208 342215569245<em>332</em>66713564437782467554889357866599146
 209 33859739644496<em>1</em>84175551729528666283163977739427418
 210 35135958944624<em>61</em>6915573572712668468382377957949348
 211 435873354154698<em>44</em>652657195576376821668748793277985
 212 5826253782693736<em>4</em>893714847591482595861259361697236
 213 9685639333179674<em>1</em>444281785255539289636664139174777
 214 3532341359464345<em>2461</em>575456357268656746837976785794
 215 3572234643468334575<em>4</em>579445686568155679767926678187
 216 5347643852645875496<em>3</em>756986517486719762859782187396
 217 3425351743453646285<em>4564</em>757396567586841767869795287
 218 4533266713564437782467<em>554</em>8893578665991468977611257
 219 449618417555172952866628<em>3163</em>9777394274188841538529
 220 462461691557357271266846838<em>2</em>3779579493488168151459
 221 546984465265719557637682166<em>8</em>7487932779859814388196
 222 693736489371484759148259586<em>125</em>93616972361472718347
 223 17967414442817852555392896366<em>6413</em>91747775241285888
 224 46434524615754563572686567468379<em>7</em>67857948187896815
 225 46833457545794456865681556797679<em>26</em>6781878137789298
 226 645875496375698651748671976285978<em>21</em>873961893298417
 227 4536462854564757396567586841767869<em>7</em>952878971816398
 228 5644377824675548893578665991468977<em>6112</em>579188722368
 229 5517295286662831639777394274188841538<em>5</em>299952649631
 230 5735727126684683823779579493488168151<em>4</em>599279262561
 231 6571955763768216687487932779859814388<em>1</em>961925499217
 232 7148475914825958612593616972361472718<em>34725</em>83829458
 233 28178525553928963666413917477752412858886<em>3</em>52396999
 234 57545635726865674683797678579481878968159<em>2</em>98917926
 235 57944568656815567976792667818781377892989<em>24</em>8891319
 236 756986517486719762859782187396189329841729<em>1431</em>9528
 237 564757396567586841767869795287897181639891829<em>2</em>7419
 238 675548893578665991468977611257918872236812998<em>33479</em>
 239 </code></pre>
 240 <p>The total risk of this path is <code><em>315</em></code> (the starting position is still never entered, so its risk is not counted).</p>
 241 <p>Using the full map, <em>what is the lowest total risk of any path from the top left to the bottom right?</em></p>
 242 </article>
 243 <p>Your puzzle answer was <code>2853</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 244 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 245 <p>If you still want to see it, you can <a href="15/input" target="_blank">get your puzzle input</a>.</p>
 246 <p>You can also <span class="share">[Share<span class="share-content">on
 247   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Chiton%22+%2D+Day+15+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F15&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 248   <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+%22Chiton%22+%2D+Day+15+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F15'}else{return false;}" target="_blank">Mastodon</a
 249 ></span>]</span> this puzzle.</p>
 250 </main>
 251
 252 <!-- ga -->
 253 <script>
 254 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 255 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 256 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 257 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 258 ga('create', 'UA-69522494-1', 'auto');
 259 ga('set', 'anonymizeIp', true);
 260 ga('send', 'pageview');
 261 </script>
 262 <!-- /ga -->
 263 </body>
 264 </html>