problems/day13.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 13 - 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">26*</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://smartystreets.com/aoc" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">SmartyStreets</a> - - -- Ridiculously - ----- Fast ------ ---- Address ---- -- Verification - ------ AND ------ ---- Rooftop ---- --- Geocoding ---</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 13: Shuttle Search ---</h2><p>Your ferry can make it safely to a nearby port, but it won't get much further. When you call to book another ship, you discover that no ships embark from that port to your vacation island. You'll need to get from the port to the nearest airport.</p>
  99 <p>Fortunately, a shuttle bus service is available to bring you from the sea port to the airport!  Each bus has an ID number that also indicates <em>how often the bus leaves for the airport</em>.</p>
 100 <p>Bus schedules are defined based on a <em>timestamp</em> that measures the <em>number of minutes</em> since some fixed reference point in the past. At timestamp <code>0</code>, every bus simultaneously departed from the sea port. After that, each bus travels to the airport, then various other locations, and finally returns to the sea port to repeat its journey forever.</p>
 101 <p>The time this loop takes a particular bus is also its ID number: the bus with ID <code>5</code> departs from the sea port at timestamps <code>0</code>, <code>5</code>, <code>10</code>, <code>15</code>, and so on. The bus with ID <code>11</code> departs at <code>0</code>, <code>11</code>, <code>22</code>, <code>33</code>, and so on. If you are there when the bus departs, you can ride that bus to the airport!</p>
 102 <p>Your notes (your puzzle input) consist of two lines.  The first line is your estimate of the <em>earliest timestamp you could depart on a bus</em>. The second line lists the bus IDs that are in service according to the shuttle company; entries that show <code>x</code> must be out of service, so you decide to ignore them.</p>
 103 <p>To save time once you arrive, your goal is to figure out <em>the earliest bus you can take to the airport</em>. (There will be exactly one such bus.)</p>
 104 <p>For example, suppose you have the following notes:</p>
 105 <pre><code>939
 106 7,13,x,x,59,x,31,19
 107 </code></pre>
 108 <p>Here, the earliest timestamp you could depart is <code>939</code>, and the bus IDs in service are <code>7</code>, <code>13</code>, <code>59</code>, <code>31</code>, and <code>19</code>. Near timestamp <code>939</code>, these bus IDs depart at the times marked <code>D</code>:</p>
 109 <pre><code>time   bus 7   bus 13  bus 59  bus 31  bus 19
 110 929      .       .       .       .       .
 111 930      .       .       .       D       .
 112 931      D       .       .       .       D
 113 932      .       .       .       .       .
 114 933      .       .       .       .       .
 115 934      .       .       .       .       .
 116 935      .       .       .       .       .
 117 936      .       D       .       .       .
 118 937      .       .       .       .       .
 119 938      D       .       .       .       .
 120 <em>939      .       .       .       .       .</em>
 121 940      .       .       .       .       .
 122 941      .       .       .       .       .
 123 942      .       .       .       .       .
 124 943      .       .       .       .       .
 125 <em>944      .       .       D       .       .</em>
 126 945      D       .       .       .       .
 127 946      .       .       .       .       .
 128 947      .       .       .       .       .
 129 948      .       .       .       .       .
 130 949      .       D       .       .       .
 131 </code></pre>
 132 <p>The earliest bus you could take is bus ID <code>59</code>. It doesn't depart until timestamp <code>944</code>, so you would need to wait <code>944 - 939 = 5</code> minutes before it departs. Multiplying the bus ID by the number of minutes you'd need to wait gives <em><code>295</code></em>.</p>
 133 <p><em>What is the ID of the earliest bus you can take to the airport multiplied by the number of minutes you'll need to wait for that bus?</em></p>
 134 </article>
 135 <p>Your puzzle answer was <code>115</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>The shuttle company is running a <span title="This is why you should never let me design a contest for a shuttle company.">contest</span>: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute. (The first line in your input is no longer relevant.)</p>
 136 <p>For example, suppose you have the same list of bus IDs as above:</p>
 137 <pre><code>7,13,x,x,59,x,31,19</code></pre>
 138 <p>An <code>x</code> in the schedule means there are no constraints on what bus IDs must depart at that time.</p>
 139 <p>This means you are looking for the earliest timestamp (called <code>t</code>) such that:</p>
 140 <ul>
 141 <li>Bus ID <code>7</code> departs at timestamp <code>t</code>.
 142 <li>Bus ID <code>13</code> departs one minute after timestamp <code>t</code>.</li>
 143 <li>There are no requirements or restrictions on departures at two or three minutes after timestamp <code>t</code>.</li>
 144 <li>Bus ID <code>59</code> departs four minutes after timestamp <code>t</code>.</li>
 145 <li>There are no requirements or restrictions on departures at five minutes after timestamp <code>t</code>.</li>
 146 <li>Bus ID <code>31</code> departs six minutes after timestamp <code>t</code>.</li>
 147 <li>Bus ID <code>19</code> departs seven minutes after timestamp <code>t</code>.</li>
 148 </ul>
 149 <p>The only bus departures that matter are the listed bus IDs at their specific offsets from <code>t</code>. Those bus IDs can depart at other times, and other bus IDs can depart at those times.  For example, in the list above, because bus ID <code>19</code> must depart seven minutes after the timestamp at which bus ID <code>7</code> departs, bus ID <code>7</code> will always <em>also</em> be departing with bus ID <code>19</code> at seven minutes after timestamp <code>t</code>.</p>
 150 <p>In this example, the earliest timestamp at which this occurs is <em><code>1068781</code></em>:</p>
 151 <pre><code>time     bus 7   bus 13  bus 59  bus 31  bus 19
 152 1068773    .       .       .       .       .
 153 1068774    D       .       .       .       .
 154 1068775    .       .       .       .       .
 155 1068776    .       .       .       .       .
 156 1068777    .       .       .       .       .
 157 1068778    .       .       .       .       .
 158 1068779    .       .       .       .       .
 159 1068780    .       .       .       .       .
 160 <em>1068781</em>    <em>D</em>       .       .       .       .
 161 <em>1068782</em>    .       <em>D</em>       .       .       .
 162 <em>1068783</em>    .       .       .       .       .
 163 <em>1068784</em>    .       .       .       .       .
 164 <em>1068785</em>    .       .       <em>D</em>       .       .
 165 <em>1068786</em>    .       .       .       .       .
 166 <em>1068787</em>    .       .       .       <em>D</em>       .
 167 <em>1068788</em>    D       .       .       .       <em>D</em>
 168 1068789    .       .       .       .       .
 169 1068790    .       .       .       .       .
 170 1068791    .       .       .       .       .
 171 1068792    .       .       .       .       .
 172 1068793    .       .       .       .       .
 173 1068794    .       .       .       .       .
 174 1068795    D       D       .       .       .
 175 1068796    .       .       .       .       .
 176 1068797    .       .       .       .       .
 177 </code></pre>
 178 <p>In the above example, bus ID <code>7</code> departs at timestamp <code>1068788</code> (seven minutes after <code>t</code>). This is fine; the only requirement on that minute is that bus ID <code>19</code> departs then, and it does.</p>
 179 <p>Here are some other examples:</p>
 180 <ul>
 181 <li>The earliest timestamp that matches the list <code>17,x,13,19</code> is <em><code>3417</code></em>.</li>
 182 <li><code>67,7,59,61</code> first occurs at timestamp <em><code>754018</code></em>.</li>
 183 <li><code>67,x,7,59,61</code> first occurs at timestamp <em><code>779210</code></em>.</li>
 184 <li><code>67,7,x,59,61</code> first occurs at timestamp <em><code>1261476</code></em>.</li>
 185 <li><code>1789,37,47,1889</code> first occurs at timestamp <em><code>1202161486</code></em>.</li>
 186 </ul>
 187 <p>However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than <code>100000000000000</code>!</p>
 188 <p><em>What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?</em></p>
 189 </article>
 190 <p>Your puzzle answer was <code>756261495958122</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 191 <p>At this point, you should <a href="/2020">return to your Advent calendar</a> and try another puzzle.</p>
 192 <p>If you still want to see it, you can <a href="13/input" target="_blank">get your puzzle input</a>.</p>
 193 <p>You can also <span class="share">[Share<span class="share-content">on
 194   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Shuttle+Search%22+%2D+Day+13+%2D+Advent+of+Code+2020&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F13&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 195   <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+%22Shuttle+Search%22+%2D+Day+13+%2D+Advent+of+Code+2020+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F13'}else{return false;}" target="_blank">Mastodon</a
 196 ></span>]</span> this puzzle.</p>
 197 </main>
 198
 199 <!-- ga -->
 200 <script>
 201 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 202 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 203 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 204 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 205 ga('create', 'UA-69522494-1', 'auto');
 206 ga('set', 'anonymizeIp', true);
 207 ga('send', 'pageview');
 208 </script>
 209 <!-- /ga -->
 210 </body>
 211 </html>