problems/day23.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 23 - 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">46*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">//</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://www.americanexpress.com/techcareers" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">American Express</a> - Work with the latest tech and back the engineering community through open source. Find your place in tech on #TeamAmex.</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 23: Amphipod ---</h2><p>A group of <a href="https://en.wikipedia.org/wiki/Amphipoda" target="_blank">amphipods</a> notice your fancy submarine and flag you down. "With such an impressive shell," one amphipod <span title="What? You didn't know amphipods can talk?">says</span>, "surely you can help us with a question that has stumped our best scientists."</p>
  99 <p>They go on to explain that a group of timid, stubborn amphipods live in a nearby burrow. Four types of amphipods live there: <em>Amber</em> (<code>A</code>), <em>Bronze</em> (<code>B</code>), <em>Copper</em> (<code>C</code>), and <em>Desert</em> (<code>D</code>). They live in a burrow that consists of a <em>hallway</em> and four <em>side rooms</em>. The side rooms are initially full of amphipods, and the hallway is initially empty.</p>
 100 <p>They give you a <em>diagram of the situation</em> (your puzzle input), including locations of each amphipod (<code>A</code>, <code>B</code>, <code>C</code>, or <code>D</code>, each of which is occupying an otherwise open space), walls (<code>#</code>), and open space (<code>.</code>).</p>
 101 <p>For example:</p>
 102 <pre><code>#############
 103 #...........#
 104 ###B#C#B#D###
 105   #A#D#C#A#
 106   #########
 107 </code></pre>
 108 <p>The amphipods would like a method to organize every amphipod into side rooms so that each side room contains one type of amphipod and the types are sorted <code>A</code>-<code>D</code> going left to right, like this:</p>
 109 <pre><code>#############
 110 #...........#
 111 ###A#B#C#D###
 112   #A#B#C#D#
 113   #########
 114 </code></pre>
 115 <p>Amphipods can move up, down, left, or right so long as they are moving into an unoccupied open space. Each type of amphipod requires a different amount of <em>energy</em> to move one step: Amber amphipods require <code>1</code> energy per step, Bronze amphipods require <code>10</code> energy, Copper amphipods require <code>100</code>, and Desert ones require <code>1000</code>. The amphipods would like you to find a way to organize the amphipods that requires the <em>least total energy</em>.</p>
 116 <p>However, because they are timid and stubborn, the amphipods have some extra rules:</p>
 117 <ul>
 118 <li>Amphipods will never <em>stop on the space immediately outside any room</em>. They can move into that space so long as they immediately continue moving. (Specifically, this refers to the four open spaces in the hallway that are directly above an amphipod starting position.)</li>
 119 <li>Amphipods will never <em>move from the hallway into a room</em> unless that room is their destination room <em>and</em> that room contains no amphipods which do not also have that room as their own destination. If an amphipod's starting room is not its destination room, it can stay in that room until it leaves the room. (For example, an Amber amphipod will not move from the hallway into the right three rooms, and will only move into the leftmost room if that room is empty or if it only contains other Amber amphipods.)</li>
 120 <li>Once an amphipod stops moving in the hallway, <em>it will stay in that spot until it can move into a room</em>. (That is, once any amphipod starts moving, any other amphipods currently in the hallway are locked in place and will not move again until they can move fully into a room.)</li>
 121 </ul>
 122 <p>In the above example, the amphipods can be organized using a minimum of <code><em>12521</em></code> energy. One way to do this is shown below.</p>
 123 <p>Starting configuration:</p>
 124 <pre><code>#############
 125 #...........#
 126 ###B#C#B#D###
 127   #A#D#C#A#
 128   #########
 129 </code></pre>
 130 <p>One Bronze amphipod moves into the hallway, taking 4 steps and using <code>40</code> energy:</p>
 131 <pre><code>#############
 132 #...B.......#
 133 ###B#C#.#D###
 134   #A#D#C#A#
 135   #########
 136 </code></pre>
 137 <p>The only Copper amphipod not in its side room moves there, taking 4 steps and using <code>400</code> energy:</p>
 138 <pre><code>#############
 139 #...B.......#
 140 ###B#.#C#D###
 141   #A#D#C#A#
 142   #########
 143 </code></pre>
 144 <p>A Desert amphipod moves out of the way, taking 3 steps and using <code>3000</code> energy, and then the Bronze amphipod takes its place, taking 3 steps and using <code>30</code> energy:</p>
 145 <pre><code>#############
 146 #.....D.....#
 147 ###B#.#C#D###
 148   #A#B#C#A#
 149   #########
 150 </code></pre>
 151 <p>The leftmost Bronze amphipod moves to its room using <code>40</code> energy:</p>
 152 <pre><code>#############
 153 #.....D.....#
 154 ###.#B#C#D###
 155   #A#B#C#A#
 156   #########
 157 </code></pre>
 158 <p>Both amphipods in the rightmost room move into the hallway, using <code>2003</code> energy in total:</p>
 159 <pre><code>#############
 160 #.....D.D.A.#
 161 ###.#B#C#.###
 162   #A#B#C#.#
 163   #########
 164 </code></pre>
 165 <p>Both Desert amphipods move into the rightmost room using <code>7000</code> energy:</p>
 166 <pre><code>#############
 167 #.........A.#
 168 ###.#B#C#D###
 169   #A#B#C#D#
 170   #########
 171 </code></pre>
 172 <p>Finally, the last Amber amphipod moves into its room, using <code>8</code> energy:</p>
 173 <pre><code>#############
 174 #...........#
 175 ###A#B#C#D###
 176   #A#B#C#D#
 177   #########
 178 </code></pre>
 179 <p><em>What is the least energy required to organize the amphipods?</em></p>
 180 </article>
 181 <p>Your puzzle answer was <code>14460</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>As you prepare to give the amphipods your solution, you notice that the diagram they handed you was actually folded up. As you unfold it, you discover an extra part of the diagram.</p>
 182 <p>Between the first and second lines of text that contain amphipod starting positions, insert the following lines:</p>
 183 <pre><code>  #D#C#B#A#
 184   #D#B#A#C#
 185 </code></pre>
 186 <p>So, the above example now becomes:</p>
 187 <pre><code>#############
 188 #...........#
 189 ###B#C#B#D###
 190   <em>#D#C#B#A#
 191   #D#B#A#C#</em>
 192   #A#D#C#A#
 193   #########
 194 </code></pre>
 195 <p>The amphipods still want to be organized into rooms similar to before:</p>
 196 <pre><code>#############
 197 #...........#
 198 ###A#B#C#D###
 199   #A#B#C#D#
 200   #A#B#C#D#
 201   #A#B#C#D#
 202   #########
 203 </code></pre>
 204 <p>In this updated example, the least energy required to organize these amphipods is <code><em>44169</em></code>:</p>
 205 <pre><code>#############
 206 #...........#
 207 ###B#C#B#D###
 208   #D#C#B#A#
 209   #D#B#A#C#
 210   #A#D#C#A#
 211   #########
 212
 213 #############
 214 #..........D#
 215 ###B#C#B#.###
 216   #D#C#B#A#
 217   #D#B#A#C#
 218   #A#D#C#A#
 219   #########
 220
 221 #############
 222 #A.........D#
 223 ###B#C#B#.###
 224   #D#C#B#.#
 225   #D#B#A#C#
 226   #A#D#C#A#
 227   #########
 228
 229 #############
 230 #A........BD#
 231 ###B#C#.#.###
 232   #D#C#B#.#
 233   #D#B#A#C#
 234   #A#D#C#A#
 235   #########
 236
 237 #############
 238 #A......B.BD#
 239 ###B#C#.#.###
 240   #D#C#.#.#
 241   #D#B#A#C#
 242   #A#D#C#A#
 243   #########
 244
 245 #############
 246 #AA.....B.BD#
 247 ###B#C#.#.###
 248   #D#C#.#.#
 249   #D#B#.#C#
 250   #A#D#C#A#
 251   #########
 252
 253 #############
 254 #AA.....B.BD#
 255 ###B#.#.#.###
 256   #D#C#.#.#
 257   #D#B#C#C#
 258   #A#D#C#A#
 259   #########
 260
 261 #############
 262 #AA.....B.BD#
 263 ###B#.#.#.###
 264   #D#.#C#.#
 265   #D#B#C#C#
 266   #A#D#C#A#
 267   #########
 268
 269 #############
 270 #AA...B.B.BD#
 271 ###B#.#.#.###
 272   #D#.#C#.#
 273   #D#.#C#C#
 274   #A#D#C#A#
 275   #########
 276
 277 #############
 278 #AA.D.B.B.BD#
 279 ###B#.#.#.###
 280   #D#.#C#.#
 281   #D#.#C#C#
 282   #A#.#C#A#
 283   #########
 284
 285 #############
 286 #AA.D...B.BD#
 287 ###B#.#.#.###
 288   #D#.#C#.#
 289   #D#.#C#C#
 290   #A#B#C#A#
 291   #########
 292
 293 #############
 294 #AA.D.....BD#
 295 ###B#.#.#.###
 296   #D#.#C#.#
 297   #D#B#C#C#
 298   #A#B#C#A#
 299   #########
 300
 301 #############
 302 #AA.D......D#
 303 ###B#.#.#.###
 304   #D#B#C#.#
 305   #D#B#C#C#
 306   #A#B#C#A#
 307   #########
 308
 309 #############
 310 #AA.D......D#
 311 ###B#.#C#.###
 312   #D#B#C#.#
 313   #D#B#C#.#
 314   #A#B#C#A#
 315   #########
 316
 317 #############
 318 #AA.D.....AD#
 319 ###B#.#C#.###
 320   #D#B#C#.#
 321   #D#B#C#.#
 322   #A#B#C#.#
 323   #########
 324
 325 #############
 326 #AA.......AD#
 327 ###B#.#C#.###
 328   #D#B#C#.#
 329   #D#B#C#.#
 330   #A#B#C#D#
 331   #########
 332
 333 #############
 334 #AA.......AD#
 335 ###.#B#C#.###
 336   #D#B#C#.#
 337   #D#B#C#.#
 338   #A#B#C#D#
 339   #########
 340
 341 #############
 342 #AA.......AD#
 343 ###.#B#C#.###
 344   #.#B#C#.#
 345   #D#B#C#D#
 346   #A#B#C#D#
 347   #########
 348
 349 #############
 350 #AA.D.....AD#
 351 ###.#B#C#.###
 352   #.#B#C#.#
 353   #.#B#C#D#
 354   #A#B#C#D#
 355   #########
 356
 357 #############
 358 #A..D.....AD#
 359 ###.#B#C#.###
 360   #.#B#C#.#
 361   #A#B#C#D#
 362   #A#B#C#D#
 363   #########
 364
 365 #############
 366 #...D.....AD#
 367 ###.#B#C#.###
 368   #A#B#C#.#
 369   #A#B#C#D#
 370   #A#B#C#D#
 371   #########
 372
 373 #############
 374 #.........AD#
 375 ###.#B#C#.###
 376   #A#B#C#D#
 377   #A#B#C#D#
 378   #A#B#C#D#
 379   #########
 380
 381 #############
 382 #..........D#
 383 ###A#B#C#.###
 384   #A#B#C#D#
 385   #A#B#C#D#
 386   #A#B#C#D#
 387   #########
 388
 389 #############
 390 #...........#
 391 ###A#B#C#D###
 392   #A#B#C#D#
 393   #A#B#C#D#
 394   #A#B#C#D#
 395   #########
 396 </code></pre>
 397 <p>Using the initial configuration from the full diagram, <em>what is the least energy required to organize the amphipods?</em></p>
 398 </article>
 399 <p>Your puzzle answer was <code>41366</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 400 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 401 <p>If you still want to see it, you can <a href="23/input" target="_blank">get your puzzle input</a>.</p>
 402 <p>You can also <span class="share">[Share<span class="share-content">on
 403   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Amphipod%22+%2D+Day+23+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F23&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 404   <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+%22Amphipod%22+%2D+Day+23+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F23'}else{return false;}" target="_blank">Mastodon</a
 405 ></span>]</span> this puzzle.</p>
 406 </main>
 407
 408 <!-- ga -->
 409 <script>
 410 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 411 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 412 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 413 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 414 ga('create', 'UA-69522494-1', 'auto');
 415 ga('set', 'anonymizeIp', true);
 416 ga('send', 'pageview');
 417 </script>
 418 <!-- /ga -->
 419 </body>
 420 </html>