problems/day15.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 15 - 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">30*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">int y=</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://careers.bolt.eu/positions?team=engineering&amp;utm_source=adventofcode&amp;utm_medium=banner&amp;utm_campaign=adventofcode_traffic" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Bolt</a> - Fastest growing mobility startup in Europe: distributed systems, microservices, ML, complex algorithms for demand prediction, and much more!</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 15: Rambunctious Recitation ---</h2><p>You catch the airport shuttle and try to book a new flight to your vacation island. Due to the storm, all direct flights have been cancelled, but a route is available to get around the storm. You take it.</p>
  99 <p>While you wait for your flight, you decide to check in with the Elves back at the North Pole. They're playing a <em>memory game</em> and are <span title="Of course they are.">ever so excited</span> to explain the rules!</p>
 100 <p>In this game, the players take turns saying <em>numbers</em>. They begin by taking turns reading from a list of <em>starting numbers</em> (your puzzle input). Then, each turn consists of considering the <em>most recently spoken number</em>:</p>
 101 <ul>
 102 <li>If that was the <em>first</em> time the number has been spoken, the current player says <em><code>0</code></em>.</li>
 103 <li>Otherwise, the number had been spoken before; the current player announces <em>how many turns apart</em> the number is from when it was previously spoken.</li>
 104 </ul>
 105 <p>So, after the starting numbers, each turn results in that player speaking aloud either <em><code>0</code></em> (if the last number is new) or an <em>age</em> (if the last number is a repeat).</p>
 106 <p>For example, suppose the starting numbers are <code>0,3,6</code>:</p>
 107 <ul>
 108 <li><em>Turn 1</em>: The <code>1</code>st number spoken is a starting number, <em><code>0</code></em>.</li>
 109 <li><em>Turn 2</em>: The <code>2</code>nd number spoken is a starting number, <em><code>3</code></em>.</li>
 110 <li><em>Turn 3</em>: The <code>3</code>rd number spoken is a starting number, <em><code>6</code></em>.</li>
 111 <li><em>Turn 4</em>: Now, consider the last number spoken, <code>6</code>. Since that was the first time the number had been spoken, the <code>4</code>th number spoken is <em><code>0</code></em>.</li>
 112 <li><em>Turn 5</em>: Next, again consider the last number spoken, <code>0</code>. Since it <em>had</em> been spoken before, the next number to speak is the difference between the turn number when it was last spoken (the previous turn, <code>4</code>) and the turn number of the time it was most recently spoken before then (turn <code>1</code>). Thus, the <code>5</code>th number spoken is <code>4 - 1</code>, <em><code>3</code></em>.</li>
 113 <li><em>Turn 6</em>: The last number spoken, <code>3</code> had also been spoken before, most recently on turns <code>5</code> and <code>2</code>. So, the <code>6</code>th number spoken is <code>5 - 2</code>, <em><code>3</code></em>.</li>
 114 <li><em>Turn 7</em>: Since <code>3</code> was just spoken twice in a row, and the last two turns are <code>1</code> turn apart, the <code>7</code>th number spoken is <em><code>1</code></em>.</li>
 115 <li><em>Turn 8</em>: Since <code>1</code> is new, the <code>8</code>th number spoken is <em><code>0</code></em>.</li>
 116 <li><em>Turn 9</em>: <code>0</code> was last spoken on turns <code>8</code> and <code>4</code>, so the <code>9</code>th number spoken is the difference between them, <em><code>4</code></em>.</li>
 117 <li><em>Turn 10</em>: <code>4</code> is new, so the <code>10</code>th number spoken is <em><code>0</code></em>.</li>
 118 </ul>
 119 <p>(The game ends when the Elves get sick of playing or dinner is ready, whichever comes first.)</p>
 120 <p>Their question for you is: what will be the <em><code>2020</code>th</em> number spoken? In the example above, the <code>2020</code>th number spoken will be <code>436</code>.</p>
 121 <p>Here are a few more examples:</p>
 122 <ul>
 123 <li>Given the starting numbers <code>1,3,2</code>, the <code>2020</code>th number spoken is <code>1</code>.</li>
 124 <li>Given the starting numbers <code>2,1,3</code>, the <code>2020</code>th number spoken is <code>10</code>.</li>
 125 <li>Given the starting numbers <code>1,2,3</code>, the <code>2020</code>th number spoken is <code>27</code>.</li>
 126 <li>Given the starting numbers <code>2,3,1</code>, the <code>2020</code>th number spoken is <code>78</code>.</li>
 127 <li>Given the starting numbers <code>3,2,1</code>, the <code>2020</code>th number spoken is <code>438</code>.</li>
 128 <li>Given the starting numbers <code>3,1,2</code>, the <code>2020</code>th number spoken is <code>1836</code>.</li>
 129 </ul>
 130 <p>Given your starting numbers, <em>what will be the <code>2020</code>th number spoken?</em></p>
 131 </article>
 132 <p>Your puzzle answer was <code>421</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Impressed, the Elves issue you a challenge: determine the <code>30000000</code>th number spoken. For example, given the same starting numbers as above:</p>
 133 <ul>
 134 <li>Given <code>0,3,6</code>, the <code>30000000</code>th number spoken is <code>175594</code>.</li>
 135 <li>Given <code>1,3,2</code>, the <code>30000000</code>th number spoken is <code>2578</code>.</li>
 136 <li>Given <code>2,1,3</code>, the <code>30000000</code>th number spoken is <code>3544142</code>.</li>
 137 <li>Given <code>1,2,3</code>, the <code>30000000</code>th number spoken is <code>261214</code>.</li>
 138 <li>Given <code>2,3,1</code>, the <code>30000000</code>th number spoken is <code>6895259</code>.</li>
 139 <li>Given <code>3,2,1</code>, the <code>30000000</code>th number spoken is <code>18</code>.</li>
 140 <li>Given <code>3,1,2</code>, the <code>30000000</code>th number spoken is <code>362</code>.</li>
 141 </ul>
 142 <p>Given your starting numbers, <em>what will be the <code>30000000</code>th number spoken?</em></p>
 143 </article>
 144 <p>Your puzzle answer was <code>436</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 145 <p>At this point, you should <a href="/2020">return to your Advent calendar</a> and try another puzzle.</p>
 146 <p>Your puzzle input was <code class="puzzle-input">20,0,1,11,6,3</code>.</p>
 147 <p>You can also <span class="share">[Share<span class="share-content">on
 148   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Rambunctious+Recitation%22+%2D+Day+15+%2D+Advent+of+Code+2020&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F15&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 149   <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+%22Rambunctious+Recitation%22+%2D+Day+15+%2D+Advent+of+Code+2020+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F15'}else{return false;}" target="_blank">Mastodon</a
 150 ></span>]</span> this puzzle.</p>
 151 </main>
 152
 153 <!-- ga -->
 154 <script>
 155 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 156 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 157 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 158 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 159 ga('create', 'UA-69522494-1', 'auto');
 160 ga('set', 'anonymizeIp', true);
 161 ga('send', 'pageview');
 162 </script>
 163 <!-- /ga -->
 164 </body>
 165 </html>