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 2019</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?24"/>
   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, 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; 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="/2019/about">[About]</a></li><li><a href="/2019/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode-2019" target="_blank">[Shop]</a></li><li><a href="/2019/settings">[Settings]</a></li><li><a href="/2019/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2019/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;<span class="title-event-wrap">&lt;y&gt;</span><a href="/2019">2019</a><span class="title-event-wrap">&lt;/y&gt;</span></h1><nav><ul><li><a href="/2019">[Calendar]</a></li><li><a href="/2019/support">[AoC++]</a></li><li><a href="/2019/sponsors">[Sponsors]</a></li><li><a href="/2019/leaderboard">[Leaderboard]</a></li><li><a href="/2019/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2019/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://xebia.com/community/advent-of-code" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Xebia</a> - an international network of passionate technologists and craftspeople, dedicated to exploring and creating new frontiers in IT</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: Slam Shuffle ---</h2><p>There isn't much to do while you wait for the droids to repair your ship.  At least you're drifting in the right direction.  You decide to practice a new <a href="https://en.wikipedia.org/wiki/Shuffling">card shuffle</a> you've been working on.</p>
  99 <p>Digging through the ship's storage, you find a deck of <em>space cards</em>! Just like <span title="What do you mean, you've never heard of space cards? They're all the rage in Zozo.">any deck of space cards</span>, there are 10007 cards in the deck numbered <code>0</code> through <code>10006</code>. The deck must be new - they're still in <em>factory order</em>, with <code>0</code> on the top, then <code>1</code>, then <code>2</code>, and so on, all the way through to <code>10006</code> on the bottom.</p>
 100 <p>You've been practicing three different <em>techniques</em> that you use while shuffling. Suppose you have a deck of only 10 cards (numbered <code>0</code> through <code>9</code>):</p>
 101 <p><em>To <code>deal into new stack</code></em>, create a new stack of cards by dealing the top card of the deck onto the top of the new stack repeatedly until you run out of cards:</p>
 102 <pre><code>Top          Bottom
 103 0 1 2 3 4 5 6 7 8 9   Your deck
 104                       New stack
 105
 106   1 2 3 4 5 6 7 8 9   Your deck
 107                   0   New stack
 108
 109     2 3 4 5 6 7 8 9   Your deck
 110                 1 0   New stack
 111
 112       3 4 5 6 7 8 9   Your deck
 113               2 1 0   New stack
 114
 115 Several steps later...
 116
 117                   9   Your deck
 118   8 7 6 5 4 3 2 1 0   New stack
 119
 120                       Your deck
 121 9 8 7 6 5 4 3 2 1 0   New stack
 122 </code></pre>
 123 <p>Finally, pick up the new stack you've just created and use it as the deck for the next technique.</p>
 124 <p><em>To <code>cut N</code> cards</em>, take the top <code>N</code> cards off the top of the deck and move them as a single unit to the bottom of the deck, retaining their order. For example, to <code>cut 3</code>:</p>
 125 <pre><code>Top          Bottom
 126 0 1 2 3 4 5 6 7 8 9   Your deck
 127
 128       3 4 5 6 7 8 9   Your deck
 129 0 1 2                 Cut cards
 130
 131 3 4 5 6 7 8 9         Your deck
 132               0 1 2   Cut cards
 133
 134 3 4 5 6 7 8 9 0 1 2   Your deck
 135 </code></pre>
 136 <p>You've also been getting pretty good at a version of this technique where <code>N</code> is negative! In that case, cut (the absolute value of) <code>N</code> cards from the bottom of the deck onto the top.  For example, to <code>cut -4</code>:</p>
 137 <pre><code>Top          Bottom
 138 0 1 2 3 4 5 6 7 8 9   Your deck
 139
 140 0 1 2 3 4 5           Your deck
 141             6 7 8 9   Cut cards
 142
 143         0 1 2 3 4 5   Your deck
 144 6 7 8 9               Cut cards
 145
 146 6 7 8 9 0 1 2 3 4 5   Your deck
 147 </code></pre>
 148 <p><em>To <code>deal with increment N</code></em>, start by clearing enough space on your table to lay out all of the cards individually in a long line.  Deal the top card into the leftmost position. Then, move <code>N</code> positions to the right and deal the next card there. If you would move into a position past the end of the space on your table, wrap around and keep counting from the leftmost card again.  Continue this process until you run out of cards.</p>
 149 <p>For example, to <code>deal with increment 3</code>:</p>
 150 <pre><code>
 151 0 1 2 3 4 5 6 7 8 9   Your deck
 152 . . . . . . . . . .   Space on table
 153 ^                     Current position
 154
 155 Deal the top card to the current position:
 156
 157   1 2 3 4 5 6 7 8 9   Your deck
 158 0 . . . . . . . . .   Space on table
 159 ^                     Current position
 160
 161 Move the current position right 3:
 162
 163   1 2 3 4 5 6 7 8 9   Your deck
 164 0 . . . . . . . . .   Space on table
 165       ^               Current position
 166
 167 Deal the top card:
 168
 169     2 3 4 5 6 7 8 9   Your deck
 170 0 . . 1 . . . . . .   Space on table
 171       ^               Current position
 172
 173 Move right 3 and deal:
 174
 175       3 4 5 6 7 8 9   Your deck
 176 0 . . 1 . . 2 . . .   Space on table
 177             ^         Current position
 178
 179 Move right 3 and deal:
 180
 181         4 5 6 7 8 9   Your deck
 182 0 . . 1 . . 2 . . 3   Space on table
 183                   ^   Current position
 184
 185 Move right 3, wrapping around, and deal:
 186
 187           5 6 7 8 9   Your deck
 188 0 . 4 1 . . 2 . . 3   Space on table
 189     ^                 Current position
 190
 191 And so on:
 192
 193 0 7 4 1 8 5 2 9 6 3   Space on table
 194 </code></pre>
 195 <p>Positions on the table which already contain cards are still counted; they're not skipped.  Of course, this technique is carefully designed so it will never put two cards in the same position or leave a position empty.</p>
 196 <p>Finally, collect the cards on the table so that the leftmost card ends up at the top of your deck, the card to its right ends up just below the top card, and so on, until the rightmost card ends up at the bottom of the deck.</p>
 197 <p>The complete shuffle process (your puzzle input) consists of applying many of these techniques.  Here are some examples that combine techniques; they all start with a <em>factory order</em> deck of 10 cards:</p>
 198 <pre><code>deal with increment 7
 199 deal into new stack
 200 deal into new stack
 201 Result: 0 3 6 9 2 5 8 1 4 7
 202 </code></pre>
 203 <pre><code>cut 6
 204 deal with increment 7
 205 deal into new stack
 206 Result: 3 0 7 4 1 8 5 2 9 6
 207 </code></pre>
 208 <pre><code>deal with increment 7
 209 deal with increment 9
 210 cut -2
 211 Result: 6 3 0 7 4 1 8 5 2 9
 212 </code></pre>
 213 <pre><code>deal into new stack
 214 cut -2
 215 deal with increment 7
 216 cut 8
 217 cut -4
 218 deal with increment 7
 219 cut 3
 220 deal with increment 9
 221 deal with increment 3
 222 cut -1
 223 Result: 9 2 5 8 1 4 7 0 3 6
 224 </code></pre>
 225 <p>Positions within the deck count from <code>0</code> at the top, then <code>1</code> for the card immediately below the top card, and so on to the bottom.  (That is, cards start in the position matching their number.)</p>
 226 <p>After shuffling your <em>factory order</em> deck of 10007 cards, <em>what is the position of card <code>2019</code>?</em></p>
 227 </article>
 228 <p>Your puzzle answer was <code>2480</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>After a while, you realize your shuffling skill won't improve much more with merely a single deck of cards.  You ask every 3D printer on the ship to make you some more cards while you check on the ship repairs.  While reviewing the work the droids have finished so far, you think you see <a href="https://en.wikipedia.org/wiki/Halley%27s_Comet">Halley's Comet</a> fly past!</p>
 229 <p>When you get back, you discover that the 3D printers have combined their power to create for you a single, giant, brand new, <em>factory order</em> deck of <em><code>119315717514047</code> space cards</em>.</p>
 230 <p>Finally, a deck of cards worthy of shuffling!</p>
 231 <p>You decide to apply your complete shuffle process (your puzzle input) to the deck <em><code>101741582076661</code> times in a row</em>.</p>
 232 <p>You'll need to be careful, though - one wrong move with this many cards and you might <em>overflow</em> your entire ship!</p>
 233 <p>After shuffling your new, giant, <em>factory order</em> deck that many times, <em>what number is on the card that ends up in position <code>2020</code>?</em></p>
 234 </article>
 235 <p>Your puzzle answer was <code>62416301438548</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 236 <p>At this point, you should <a href="/2019">return to your Advent calendar</a> and try another puzzle.</p>
 237 <p>If you still want to see it, you can <a href="22/input" target="_blank">get your puzzle input</a>.</p>
 238 <p>You can also <span class="share">[Share<span class="share-content">on
 239   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Slam+Shuffle%22+%2D+Day+22+%2D+Advent+of+Code+2019&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F22&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 240   <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+%22Slam+Shuffle%22+%2D+Day+22+%2D+Advent+of+Code+2019+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F22'}else{return false;}" target="_blank">Mastodon</a
 241 ></span>]</span> this puzzle.</p>
 242 </main>
 243
 244 <!-- ga -->
 245 <script>
 246 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 247 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 248 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 249 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 250 ga('create', 'UA-69522494-1', 'auto');
 251 ga('set', 'anonymizeIp', true);
 252 ga('send', 'pageview');
 253 </script>
 254 <!-- /ga -->
 255 </body>
 256 </html>