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"/>
16 Oh, hello! Funny seeing you here.
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.
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.
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
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!
35 If you'd like to hang out, I'm @ericwastl on Twitter.
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"> <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>
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&utm_medium=display&utm_campaign=advent2020" target=
"_blank" onclick=
"if(ga)ga('send','event','sponsor','sidebar',this.href);" rel=
"noopener">AuricVault®
</a> - Thieves can
't steal--what isn
't there! Protect your sensitive data. Simplify PCI, PII, CCPA
& GDPR compliance. FREE test credentials.
</div></div>
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>
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
123 Player
1 wins the round!
126 Player
1's deck:
2,
6,
3,
1,
9,
5
127 Player
2's deck:
8,
4,
7,
10
130 Player
2 wins the round!
133 Player
1's deck:
6,
3,
1,
9,
5
134 Player
2's deck:
4,
7,
10,
8,
2
137 Player
1 wins the round!
140 Player
1's deck:
3,
1,
9,
5,
6,
4
141 Player
2's deck:
7,
10,
8,
2
144 Player
2 wins the round!
147 Player
1's deck:
1,
9,
5,
6,
4
148 Player
2's deck:
10,
8,
2,
7,
3
151 Player
2 wins the round!
153 ...several more rounds pass...
156 Player
1's deck:
5,
4,
1
157 Player
2's deck:
8,
9,
7,
3,
2,
10,
6
160 Player
2 wins the round!
163 Player
1's deck:
4,
1
164 Player
2's deck:
9,
7,
3,
2,
10,
6,
8,
5
167 Player
2 wins the round!
171 Player
2's deck:
7,
3,
2,
10,
6,
8,
5,
9,
4
174 Player
2 wins the round!
177 == Post-game results ==
179 Player
2's deck:
3,
2,
10,
6,
8,
5,
9,
4,
7,
1
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>
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>
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>
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>
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>
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 ===
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
226 Player
1 wins round
1 of game
1!
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
233 Player
2 wins round
2 of game
1!
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
240 Player
1 wins round
3 of game
1!
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
247 Player
2 wins round
4 of game
1!
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
254 Player
2 wins round
5 of game
1!
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
261 Player
1 wins round
6 of game
1!
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
268 Player
1 wins round
7 of game
1!
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
275 Player
2 wins round
8 of game
1!
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
282 Playing a sub-game to determine the winner...
286 -- Round
1 (Game
2) --
287 Player
1's deck:
9,
8,
5,
2
288 Player
2's deck:
10,
1,
7
291 Player
2 wins round
1 of game
2!
293 -- Round
2 (Game
2) --
294 Player
1's deck:
8,
5,
2
295 Player
2's deck:
1,
7,
10,
9
298 Player
1 wins round
2 of game
2!
300 -- Round
3 (Game
2) --
301 Player
1's deck:
5,
2,
8,
1
302 Player
2's deck:
7,
10,
9
305 Player
2 wins round
3 of game
2!
307 -- Round
4 (Game
2) --
308 Player
1's deck:
2,
8,
1
309 Player
2's deck:
10,
9,
7,
5
312 Player
2 wins round
4 of game
2!
314 -- Round
5 (Game
2) --
315 Player
1's deck:
8,
1
316 Player
2's deck:
9,
7,
5,
10,
2
319 Player
2 wins round
5 of game
2!
321 -- Round
6 (Game
2) --
323 Player
2's deck:
7,
5,
10,
2,
9,
8
326 Player
2 wins round
6 of game
2!
327 The winner of game
2 is player
2!
329 ...anyway, back to game
1.
330 Player
2 wins round
9 of game
1!
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
337 Player
2 wins round
10 of game
1!
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
344 Player
1 wins round
11 of game
1!
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
351 Player
2 wins round
12 of game
1!
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
358 Playing a sub-game to determine the winner...
362 -- Round
1 (Game
3) --
363 Player
1's deck:
8,
1
364 Player
2's deck:
3,
4,
10,
9,
7,
5
367 Player
1 wins round
1 of game
3!
369 -- Round
2 (Game
3) --
370 Player
1's deck:
1,
8,
3
371 Player
2's deck:
4,
10,
9,
7,
5
374 Playing a sub-game to determine the winner...
378 -- Round
1 (Game
4) --
380 Player
2's deck:
10,
9,
7,
5
383 Player
2 wins round
1 of game
4!
384 The winner of game
4 is player
2!
386 ...anyway, back to game
3.
387 Player
2 wins round
2 of game
3!
389 -- Round
3 (Game
3) --
390 Player
1's deck:
8,
3
391 Player
2's deck:
10,
9,
7,
5,
4,
1
394 Player
2 wins round
3 of game
3!
396 -- Round
4 (Game
3) --
398 Player
2's deck:
9,
7,
5,
4,
1,
10,
8
401 Player
2 wins round
4 of game
3!
402 The winner of game
3 is player
2!
404 ...anyway, back to game
1.
405 Player
2 wins round
13 of game
1!
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
412 Player
1 wins round
14 of game
1!
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
419 Playing a sub-game to determine the winner...
423 -- Round
1 (Game
5) --
425 Player
2's deck:
10,
9,
7,
5
428 Player
2 wins round
1 of game
5!
429 The winner of game
5 is player
2!
431 ...anyway, back to game
1.
432 Player
2 wins round
15 of game
1!
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
439 Player
2 wins round
16 of game
1!
441 -- Round
17 (Game
1) --
443 Player
2's deck:
9,
7,
5,
6,
2,
4,
1,
10,
8
446 Player
2 wins round
17 of game
1!
447 The winner of game
1 is player
2!
450 == Post-game results ==
452 Player
2's deck:
7,
5,
6,
2,
4,
1,
10,
8,
9,
3
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>
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&url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F22&related=ericwastl&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>
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');