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 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">46*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;&nbsp;&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://github.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">GitHub</a> - We&apos;re hiring engineers to make GitHub fast. Interested? Email fast@github.com with details of exceptional performance work you&apos;ve done in the past.</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: Crab Cups ---</h2><p>The small crab challenges <em>you</em> to a game! The crab is going to mix up some cups, and you have to predict where they'll end up.</p>
  99 <p>The cups will be arranged in a circle and labeled <em>clockwise</em> (your puzzle input). For example, if your labeling were <code>32415</code>, there would be five cups in the circle; going clockwise around the circle from the first cup, the cups would be labeled <code>3</code>, <code>2</code>, <code>4</code>, <code>1</code>, <code>5</code>, and then back to <code>3</code> again.</p>
 100 <p>Before the crab starts, it will designate the first cup in your list as the <em>current cup</em>. The crab is then going to do <em>100 moves</em>.</p>
 101 <p>Each <em>move</em>, the crab does the following actions:</p>
 102 <ul>
 103 <li>The crab picks up the <em>three cups</em> that are immediately <em>clockwise</em> of the <em>current cup</em>. They are removed from the circle; cup spacing is adjusted as necessary to maintain the circle.</li>
 104 <li>The crab selects a <em>destination cup</em>: the cup with a <em>label</em> equal to the <em>current cup's</em> label minus one. If this would select one of the cups that was just picked up, the crab will keep subtracting one until it finds a cup that wasn't just picked up. If at any point in this process the value goes below the lowest value on any cup's label, it <em>wraps around</em> to the highest value on any cup's label instead.</li>
 105 <li>The crab places the cups it just picked up so that they are <em>immediately clockwise</em> of the destination cup. They keep the same order as when they were picked up.</li>
 106 <li>The crab selects a new <em>current cup</em>: the cup which is immediately clockwise of the current cup.</li>
 107 </ul>
 108 <p>For example, suppose your cup labeling were <code>389125467</code>. If the crab were to do merely 10 moves, the following changes would occur:</p>
 109 <pre><code>-- move 1 --
 110 cups: (3) 8  9  1  2  5  4  6  7
 111 pick up: 8, 9, 1
 112 destination: 2
 113
 114 -- move 2 --
 115 cups:  3 (2) 8  9  1  5  4  6  7
 116 pick up: 8, 9, 1
 117 destination: 7
 118
 119 -- move 3 --
 120 cups:  3  2 (5) 4  6  7  8  9  1
 121 pick up: 4, 6, 7
 122 destination: 3
 123
 124 -- move 4 --
 125 cups:  7  2  5 (8) 9  1  3  4  6
 126 pick up: 9, 1, 3
 127 destination: 7
 128
 129 -- move 5 --
 130 cups:  3  2  5  8 (4) 6  7  9  1
 131 pick up: 6, 7, 9
 132 destination: 3
 133
 134 -- move 6 --
 135 cups:  9  2  5  8  4 (1) 3  6  7
 136 pick up: 3, 6, 7
 137 destination: 9
 138
 139 -- move 7 --
 140 cups:  7  2  5  8  4  1 (9) 3  6
 141 pick up: 3, 6, 7
 142 destination: 8
 143
 144 -- move 8 --
 145 cups:  8  3  6  7  4  1  9 (2) 5
 146 pick up: 5, 8, 3
 147 destination: 1
 148
 149 -- move 9 --
 150 cups:  7  4  1  5  8  3  9  2 (6)
 151 pick up: 7, 4, 1
 152 destination: 5
 153
 154 -- move 10 --
 155 cups: (5) 7  4  1  8  3  9  2  6
 156 pick up: 7, 4, 1
 157 destination: 3
 158
 159 -- final --
 160 cups:  5 (8) 3  7  4  1  9  2  6
 161 </code></pre>
 162 <p>In the above example, the cups' values are the labels as they appear moving clockwise around the circle; the <em>current cup</em> is marked with <code>( )</code>.</p>
 163 <p>After the crab is done, what order will the cups be in? Starting <em>after the cup labeled <code>1</code></em>, collect the other cups' labels clockwise into a single string with no extra characters; each number except <code>1</code> should appear exactly once. In the above example, after 10 moves, the cups clockwise from <code>1</code> are labeled <code>9</code>, <code>2</code>, <code>6</code>, <code>5</code>, and so on, producing <em><code>92658374</code></em>. If the crab were to complete all 100 moves, the order after cup <code>1</code> would be <em><code>67384529</code></em>.</p>
 164 <p>Using your labeling, simulate 100 moves. <em>What are the labels on the cups after cup <code>1</code>?</em></p>
 165 </article>
 166 <p>Your puzzle answer was <code>54327968</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Due to what you can only assume is a mistranslation (you're <span title="If I were going for a programming language pun here, I'd say you were a little... RUSTy.">not exactly fluent in Crab</span>), you are quite surprised when the crab starts arranging <em>many</em> cups in a circle on your raft - <em>one million</em> (<code>1000000</code>) in total.</p>
 167 <p>Your labeling is still correct for the first few cups; after that, the remaining cups are just numbered in an increasing fashion starting from the number after the highest number in your list and proceeding one by one until one million is reached. (For example, if your labeling were <code>54321</code>, the cups would be numbered <code>5</code>, <code>4</code>, <code>3</code>, <code>2</code>, <code>1</code>, and then start counting up from <code>6</code> until one million is reached.) In this way, every number from one through one million is used exactly once.</p>
 168 <p>After discovering where you made the mistake in translating Crab Numbers, you realize the small crab isn't going to do merely 100 moves; the crab is going to do <em>ten million</em> (<code>10000000</code>) moves!</p>
 169 <p>The crab is going to hide your <em class="star">stars</em> - one each - under the <em>two cups that will end up immediately clockwise of cup <code>1</code></em>. You can have them if you predict what the labels on those cups will be when the crab is finished.</p>
 170 <p>In the above example (<code>389125467</code>), this would be <code>934001</code> and then <code>159792</code>; multiplying these together produces <em><code>149245887792</code></em>.</p>
 171 <p>Determine which two cups will end up immediately clockwise of cup <code>1</code>. <em>What do you get if you multiply their labels together?</em></p>
 172 </article>
 173 <p>Your puzzle answer was <code>157410423276</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 174 <p>At this point, you should <a href="/2020">return to your Advent calendar</a> and try another puzzle.</p>
 175 <p>Your puzzle input was <code class="puzzle-input">538914762</code>.</p>
 176 <p>You can also <span class="share">[Share<span class="share-content">on
 177   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Crab+Cups%22+%2D+Day+23+%2D+Advent+of+Code+2020&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F23&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 178   <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+Cups%22+%2D+Day+23+%2D+Advent+of+Code+2020+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F23'}else{return false;}" target="_blank">Mastodon</a
 179 ></span>]</span> this puzzle.</p>
 180 </main>
 181
 182 <!-- ga -->
 183 <script>
 184 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 185 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 186 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 187 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 188 ga('create', 'UA-69522494-1', 'auto');
 189 ga('set', 'anonymizeIp', true);
 190 ga('send', 'pageview');
 191 </script>
 192 <!-- /ga -->
 193 </body>
 194 </html>