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 2020</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?25"/>
   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="/2020/about">[About]</a></li><li><a href="/2020/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2020/settings">[Settings]</a></li><li><a href="/2020/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2020/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;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">/^</span><a href="/2020">2020</a><span class="title-event-wrap">$/</span></h1><nav><ul><li><a href="/2020">[Calendar]</a></li><li><a href="/2020/support">[AoC++]</a></li><li><a href="/2020/sponsors">[Sponsors]</a></li><li><a href="/2020/leaderboard">[Leaderboard]</a></li><li><a href="/2020/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2020/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://auricsystems.com/tokenize-almost-anything?utm_source=advent+of+code&amp;utm_medium=display&amp;utm_campaign=advent2020" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">AuricVault®</a> - Thieves can&apos;t steal--what isn&apos;t there! Protect your sensitive data. Simplify PCI, PII, CCPA &amp; GDPR compliance. FREE test credentials.</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 22: Crab Combat ---</h2><p>It only takes a few hours of sailing the ocean on a raft for boredom to sink in. Fortunately, you brought a small deck of <a href="/2019/day/22">space cards</a>! You'd like to play a game of <em>Combat</em>, and there's even an opponent available: a small crab that climbed aboard your raft before you left.</p>
  99 <p>Fortunately, it doesn't take long to teach the crab the rules.</p>
 100 <p>Before the game starts, split the cards so each player has their own deck (your puzzle input). Then, the game consists of a series of <em>rounds</em>: both players draw their top card, and the player with the higher-valued card wins the round. The winner keeps both cards, placing them on the bottom of their own deck so that the winner's card is above the other card. If this causes a player to have all of the cards, they win, and the game ends.</p>
 101 <p>For example, consider the following starting decks:</p>
 102 <pre><code>Player 1:
 103 9
 104 2
 105 6
 106 3
 107 1
 108
 109 Player 2:
 110 5
 111 8
 112 4
 113 7
 114 10
 115 </code></pre>
 116 <p>This arrangement means that player 1's deck contains 5 cards, with <code>9</code> on top and <code>1</code> on the bottom; player 2's deck also contains 5 cards, with <code>5</code> on top and <code>10</code> on the bottom.</p>
 117 <p>The first round begins with both players drawing the top card of their decks: <code>9</code> and <code>5</code>. Player 1 has the higher card, so both cards move to the bottom of player 1's deck such that <code>9</code> is above <code>5</code>. In total, it takes 29 rounds before a player has all of the cards:</p>
 118 <pre><code>-- Round 1 --
 119 Player 1's deck: 9, 2, 6, 3, 1
 120 Player 2's deck: 5, 8, 4, 7, 10
 121 Player 1 plays: 9
 122 Player 2 plays: 5
 123 Player 1 wins the round!
 124
 125 -- Round 2 --
 126 Player 1's deck: 2, 6, 3, 1, 9, 5
 127 Player 2's deck: 8, 4, 7, 10
 128 Player 1 plays: 2
 129 Player 2 plays: 8
 130 Player 2 wins the round!
 131
 132 -- Round 3 --
 133 Player 1's deck: 6, 3, 1, 9, 5
 134 Player 2's deck: 4, 7, 10, 8, 2
 135 Player 1 plays: 6
 136 Player 2 plays: 4
 137 Player 1 wins the round!
 138
 139 -- Round 4 --
 140 Player 1's deck: 3, 1, 9, 5, 6, 4
 141 Player 2's deck: 7, 10, 8, 2
 142 Player 1 plays: 3
 143 Player 2 plays: 7
 144 Player 2 wins the round!
 145
 146 -- Round 5 --
 147 Player 1's deck: 1, 9, 5, 6, 4
 148 Player 2's deck: 10, 8, 2, 7, 3
 149 Player 1 plays: 1
 150 Player 2 plays: 10
 151 Player 2 wins the round!
 152
 153 ...several more rounds pass...
 154
 155 -- Round 27 --
 156 Player 1's deck: 5, 4, 1
 157 Player 2's deck: 8, 9, 7, 3, 2, 10, 6
 158 Player 1 plays: 5
 159 Player 2 plays: 8
 160 Player 2 wins the round!
 161
 162 -- Round 28 --
 163 Player 1's deck: 4, 1
 164 Player 2's deck: 9, 7, 3, 2, 10, 6, 8, 5
 165 Player 1 plays: 4
 166 Player 2 plays: 9
 167 Player 2 wins the round!
 168
 169 -- Round 29 --
 170 Player 1's deck: 1
 171 Player 2's deck: 7, 3, 2, 10, 6, 8, 5, 9, 4
 172 Player 1 plays: 1
 173 Player 2 plays: 7
 174 Player 2 wins the round!
 175
 176
 177 == Post-game results ==
 178 Player 1's deck:
 179 Player 2's deck: 3, 2, 10, 6, 8, 5, 9, 4, 7, 1
 180 </code></pre>
 181 <p>Once the game ends, you can calculate the winning player's <em>score</em>. The bottom card in their deck is worth the value of the card multiplied by 1, the second-from-the-bottom card is worth the value of the card multiplied by 2, and so on. With 10 cards, the top card is worth the value on the card multiplied by 10. In this example, the winning player's score is:</p>
 182 <pre><code>   3 * 10
 183 +  2 *  9
 184 + 10 *  8
 185 +  6 *  7
 186 +  8 *  6
 187 +  5 *  5
 188 +  9 *  4
 189 +  4 *  3
 190 +  7 *  2
 191 +  1 *  1
 192 = 306
 193 </code></pre>
 194 <p>So, once the game ends, the winning player's score is <em><code>306</code></em>.</p>
 195 <p>Play the small crab in a game of Combat using the two decks you just dealt. <em>What is the winning player's score?</em></p>
 196 </article>
 197 <p>Your puzzle answer was <code>33925</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>You lost to the small crab! Fortunately, crabs aren't very good at recursion. To defend your honor as a Raft Captain, you challenge the small crab to a game of <em><span title="For some reason, nobody wants to play Recursive Twilight Imperium with me.">Recursive</span> Combat</em>.</p>
 198 <p>Recursive Combat still starts by splitting the cards into two decks (you offer to play with the same starting decks as before - it's only fair). Then, the game consists of a series of <em>rounds</em> with a few changes:</p>
 199 <ul>
 200 <li>Before either player deals a card, if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks, the <em>game</em> instantly ends in a win for player 1. Previous rounds from other games are not considered. (This prevents infinite games of Recursive Combat, which everyone agrees is a bad idea.)</li>
 201 <li>Otherwise, this round's cards must be in a new configuration; the players begin the round by each drawing the top card of their deck as normal.</li>
 202 <li>If both players have at least as many cards remaining in their deck as the value of the card they just drew, the winner of the round is determined by playing a new game of Recursive Combat (see below).</li>
 203 <li>Otherwise, at least one player must not have enough cards left in their deck to recurse; the winner of the round is the player with the higher-value card.</li>
 204 </ul>
 205 <p>As in regular Combat, the winner of the round (even if they won the round by winning a sub-game) takes the two cards dealt at the beginning of the round and places them on the bottom of their own deck (again so that the winner's card is above the other card). Note that the winner's card might be <em>the lower-valued of the two cards</em> if they won the round due to winning a sub-game. If collecting cards by winning the round causes a player to have all of the cards, they win, and the game ends.</p>
 206 <p>Here is an example of a small game that would loop forever without the infinite game prevention rule:</p>
 207 <pre><code>Player 1:
 208 43
 209 19
 210
 211 Player 2:
 212 2
 213 29
 214 14
 215 </code></pre>
 216 <p>During a round of Recursive Combat, if both players have at least as many cards in their own decks as the number on the card they just dealt, the winner of the round is determined by recursing into a sub-game of Recursive Combat. (For example, if player 1 draws the <code>3</code> card, and player 2 draws the <code>7</code> card, this would occur if player 1 has at least 3 cards left and player 2 has at least 7 cards left, not counting the <code>3</code> and <code>7</code> cards that were drawn.)</p>
 217 <p>To play a sub-game of Recursive Combat, each player creates a new deck by making a <em>copy</em> of the next cards in their deck (the quantity of cards copied is equal to the number on the card they drew to trigger the sub-game). During this sub-game, the game that triggered it is on hold and completely unaffected; no cards are removed from players' decks to form the sub-game. (For example, if player 1 drew the <code>3</code> card, their deck in the sub-game would be <em>copies</em> of the next three cards in their deck.)</p>
 218 <p>Here is a complete example of gameplay, where <code>Game 1</code> is the primary game of Recursive Combat:</p>
 219 <pre><code>=== Game 1 ===
 220
 221 -- Round 1 (Game 1) --
 222 Player 1's deck: 9, 2, 6, 3, 1
 223 Player 2's deck: 5, 8, 4, 7, 10
 224 Player 1 plays: 9
 225 Player 2 plays: 5
 226 Player 1 wins round 1 of game 1!
 227
 228 -- Round 2 (Game 1) --
 229 Player 1's deck: 2, 6, 3, 1, 9, 5
 230 Player 2's deck: 8, 4, 7, 10
 231 Player 1 plays: 2
 232 Player 2 plays: 8
 233 Player 2 wins round 2 of game 1!
 234
 235 -- Round 3 (Game 1) --
 236 Player 1's deck: 6, 3, 1, 9, 5
 237 Player 2's deck: 4, 7, 10, 8, 2
 238 Player 1 plays: 6
 239 Player 2 plays: 4
 240 Player 1 wins round 3 of game 1!
 241
 242 -- Round 4 (Game 1) --
 243 Player 1's deck: 3, 1, 9, 5, 6, 4
 244 Player 2's deck: 7, 10, 8, 2
 245 Player 1 plays: 3
 246 Player 2 plays: 7
 247 Player 2 wins round 4 of game 1!
 248
 249 -- Round 5 (Game 1) --
 250 Player 1's deck: 1, 9, 5, 6, 4
 251 Player 2's deck: 10, 8, 2, 7, 3
 252 Player 1 plays: 1
 253 Player 2 plays: 10
 254 Player 2 wins round 5 of game 1!
 255
 256 -- Round 6 (Game 1) --
 257 Player 1's deck: 9, 5, 6, 4
 258 Player 2's deck: 8, 2, 7, 3, 10, 1
 259 Player 1 plays: 9
 260 Player 2 plays: 8
 261 Player 1 wins round 6 of game 1!
 262
 263 -- Round 7 (Game 1) --
 264 Player 1's deck: 5, 6, 4, 9, 8
 265 Player 2's deck: 2, 7, 3, 10, 1
 266 Player 1 plays: 5
 267 Player 2 plays: 2
 268 Player 1 wins round 7 of game 1!
 269
 270 -- Round 8 (Game 1) --
 271 Player 1's deck: 6, 4, 9, 8, 5, 2
 272 Player 2's deck: 7, 3, 10, 1
 273 Player 1 plays: 6
 274 Player 2 plays: 7
 275 Player 2 wins round 8 of game 1!
 276
 277 -- Round 9 (Game 1) --
 278 Player 1's deck: 4, 9, 8, 5, 2
 279 Player 2's deck: 3, 10, 1, 7, 6
 280 Player 1 plays: 4
 281 Player 2 plays: 3
 282 Playing a sub-game to determine the winner...
 283
 284 === Game 2 ===
 285
 286 -- Round 1 (Game 2) --
 287 Player 1's deck: 9, 8, 5, 2
 288 Player 2's deck: 10, 1, 7
 289 Player 1 plays: 9
 290 Player 2 plays: 10
 291 Player 2 wins round 1 of game 2!
 292
 293 -- Round 2 (Game 2) --
 294 Player 1's deck: 8, 5, 2
 295 Player 2's deck: 1, 7, 10, 9
 296 Player 1 plays: 8
 297 Player 2 plays: 1
 298 Player 1 wins round 2 of game 2!
 299
 300 -- Round 3 (Game 2) --
 301 Player 1's deck: 5, 2, 8, 1
 302 Player 2's deck: 7, 10, 9
 303 Player 1 plays: 5
 304 Player 2 plays: 7
 305 Player 2 wins round 3 of game 2!
 306
 307 -- Round 4 (Game 2) --
 308 Player 1's deck: 2, 8, 1
 309 Player 2's deck: 10, 9, 7, 5
 310 Player 1 plays: 2
 311 Player 2 plays: 10
 312 Player 2 wins round 4 of game 2!
 313
 314 -- Round 5 (Game 2) --
 315 Player 1's deck: 8, 1
 316 Player 2's deck: 9, 7, 5, 10, 2
 317 Player 1 plays: 8
 318 Player 2 plays: 9
 319 Player 2 wins round 5 of game 2!
 320
 321 -- Round 6 (Game 2) --
 322 Player 1's deck: 1
 323 Player 2's deck: 7, 5, 10, 2, 9, 8
 324 Player 1 plays: 1
 325 Player 2 plays: 7
 326 Player 2 wins round 6 of game 2!
 327 The winner of game 2 is player 2!
 328
 329 ...anyway, back to game 1.
 330 Player 2 wins round 9 of game 1!
 331
 332 -- Round 10 (Game 1) --
 333 Player 1's deck: 9, 8, 5, 2
 334 Player 2's deck: 10, 1, 7, 6, 3, 4
 335 Player 1 plays: 9
 336 Player 2 plays: 10
 337 Player 2 wins round 10 of game 1!
 338
 339 -- Round 11 (Game 1) --
 340 Player 1's deck: 8, 5, 2
 341 Player 2's deck: 1, 7, 6, 3, 4, 10, 9
 342 Player 1 plays: 8
 343 Player 2 plays: 1
 344 Player 1 wins round 11 of game 1!
 345
 346 -- Round 12 (Game 1) --
 347 Player 1's deck: 5, 2, 8, 1
 348 Player 2's deck: 7, 6, 3, 4, 10, 9
 349 Player 1 plays: 5
 350 Player 2 plays: 7
 351 Player 2 wins round 12 of game 1!
 352
 353 -- Round 13 (Game 1) --
 354 Player 1's deck: 2, 8, 1
 355 Player 2's deck: 6, 3, 4, 10, 9, 7, 5
 356 Player 1 plays: 2
 357 Player 2 plays: 6
 358 Playing a sub-game to determine the winner...
 359
 360 === Game 3 ===
 361
 362 -- Round 1 (Game 3) --
 363 Player 1's deck: 8, 1
 364 Player 2's deck: 3, 4, 10, 9, 7, 5
 365 Player 1 plays: 8
 366 Player 2 plays: 3
 367 Player 1 wins round 1 of game 3!
 368
 369 -- Round 2 (Game 3) --
 370 Player 1's deck: 1, 8, 3
 371 Player 2's deck: 4, 10, 9, 7, 5
 372 Player 1 plays: 1
 373 Player 2 plays: 4
 374 Playing a sub-game to determine the winner...
 375
 376 === Game 4 ===
 377
 378 -- Round 1 (Game 4) --
 379 Player 1's deck: 8
 380 Player 2's deck: 10, 9, 7, 5
 381 Player 1 plays: 8
 382 Player 2 plays: 10
 383 Player 2 wins round 1 of game 4!
 384 The winner of game 4 is player 2!
 385
 386 ...anyway, back to game 3.
 387 Player 2 wins round 2 of game 3!
 388
 389 -- Round 3 (Game 3) --
 390 Player 1's deck: 8, 3
 391 Player 2's deck: 10, 9, 7, 5, 4, 1
 392 Player 1 plays: 8
 393 Player 2 plays: 10
 394 Player 2 wins round 3 of game 3!
 395
 396 -- Round 4 (Game 3) --
 397 Player 1's deck: 3
 398 Player 2's deck: 9, 7, 5, 4, 1, 10, 8
 399 Player 1 plays: 3
 400 Player 2 plays: 9
 401 Player 2 wins round 4 of game 3!
 402 The winner of game 3 is player 2!
 403
 404 ...anyway, back to game 1.
 405 Player 2 wins round 13 of game 1!
 406
 407 -- Round 14 (Game 1) --
 408 Player 1's deck: 8, 1
 409 Player 2's deck: 3, 4, 10, 9, 7, 5, 6, 2
 410 Player 1 plays: 8
 411 Player 2 plays: 3
 412 Player 1 wins round 14 of game 1!
 413
 414 -- Round 15 (Game 1) --
 415 Player 1's deck: 1, 8, 3
 416 Player 2's deck: 4, 10, 9, 7, 5, 6, 2
 417 Player 1 plays: 1
 418 Player 2 plays: 4
 419 Playing a sub-game to determine the winner...
 420
 421 === Game 5 ===
 422
 423 -- Round 1 (Game 5) --
 424 Player 1's deck: 8
 425 Player 2's deck: 10, 9, 7, 5
 426 Player 1 plays: 8
 427 Player 2 plays: 10
 428 Player 2 wins round 1 of game 5!
 429 The winner of game 5 is player 2!
 430
 431 ...anyway, back to game 1.
 432 Player 2 wins round 15 of game 1!
 433
 434 -- Round 16 (Game 1) --
 435 Player 1's deck: 8, 3
 436 Player 2's deck: 10, 9, 7, 5, 6, 2, 4, 1
 437 Player 1 plays: 8
 438 Player 2 plays: 10
 439 Player 2 wins round 16 of game 1!
 440
 441 -- Round 17 (Game 1) --
 442 Player 1's deck: 3
 443 Player 2's deck: 9, 7, 5, 6, 2, 4, 1, 10, 8
 444 Player 1 plays: 3
 445 Player 2 plays: 9
 446 Player 2 wins round 17 of game 1!
 447 The winner of game 1 is player 2!
 448
 449
 450 == Post-game results ==
 451 Player 1's deck:
 452 Player 2's deck: 7, 5, 6, 2, 4, 1, 10, 8, 9, 3
 453 </code></pre>
 454 <p>After the game, the winning player's score is calculated from the cards they have in their original deck using the same rules as regular Combat. In the above game, the winning player's score is <em><code>291</code></em>.</p>
 455 <p>Defend your honor as Raft Captain by playing the small crab in a game of Recursive Combat using the same two decks as before. <em>What is the winning player's score?</em></p>
 456 </article>
 457 <p>Your puzzle answer was <code>33441</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 458 <p>At this point, you should <a href="/2020">return to your Advent calendar</a> and try another puzzle.</p>
 459 <p>If you still want to see it, you can <a href="22/input" target="_blank">get your puzzle input</a>.</p>
 460 <p>You can also <span class="share">[Share<span class="share-content">on
 461   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Crab+Combat%22+%2D+Day+22+%2D+Advent+of+Code+2020&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F22&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 462   <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+%22Crab+Combat%22+%2D+Day+22+%2D+Advent+of+Code+2020+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F22'}else{return false;}" target="_blank">Mastodon</a
 463 ></span>]</span> this puzzle.</p>
 464 </main>
 465
 466 <!-- ga -->
 467 <script>
 468 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 469 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 470 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 471 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 472 ga('create', 'UA-69522494-1', 'auto');
 473 ga('set', 'anonymizeIp', true);
 474 ga('send', 'pageview');
 475 </script>
 476 <!-- /ga -->
 477 </body>
 478 </html>