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 2017</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?12"/>
   9 <link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
  10 <link rel="shortcut icon" href="/favicon.ico?2"/>
  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 Google, and I can only take
  23 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 probably took the longest; the easiest ones took an hour or two
  31 each, but the harder ones took 4-5 hours, and a few even longer than that. A
  32 lot of effort went into building this thing - I hope you're enjoying playing it
  33 as much as I 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="/2017/about">[About]</a></li><li><a href="/2017/support">[AoC++]</a></li><li><a href="/2017/events">[Events]</a></li><li><a href="/2017/settings">[Settings]</a></li><li><a href="/2017/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <span class="supporter">(AoC++)</span> <span class="star-count">26*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">λy.</span><a href="/2017">2017</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2017">[Calendar]</a></li><li><a href="/2017/leaderboard">[Leaderboard]</a></li><li><a href="/2017/stats">[Stats]</a></li><li><a href="/2017/sponsors">[Sponsors]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2017/sponsors">sponsors</a> help make Advent of Code possible:</div><p><a href="https://formlabs.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Formlabs</a> - We make powerful, affordable 3D printers for professionals.</p></div>
  94 <div id="ad">
  95 <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
  96 <!-- Advent of Code Wide Skyscraper -->
  97 <ins class="adsbygoogle"
  98      style="display:inline-block;width:160px;height:600px"
  99      data-ad-client="ca-pub-9420604735624631"
 100      data-ad-slot="8014013294"></ins>
 101 <script>
 102 (adsbygoogle = window.adsbygoogle || []).push({});
 103 </script>
 104 </div><!--/ad-->
 105 </div><!--/sidebar-->
 106
 107 <main>
 108 <article class="day-desc"><h2>--- Day 13: Packet Scanners ---</h2><p>You need to cross a vast <em>firewall</em>. The firewall consists of several layers, each with a <em>security scanner</em> that moves back and forth across the layer. To succeed, you must not be detected by a scanner.</p>
 109 <p>By studying the firewall briefly, you are able to record (in your puzzle input) the <em>depth</em> of each layer and the <em>range</em> of the scanning area for the scanner within it, written as <code>depth: range</code>. Each layer has a thickness of exactly <code>1</code>. A layer at depth <code>0</code> begins immediately inside the firewall; a layer at depth <code>1</code> would start immediately after that.</p>
 110 <p>For example, suppose you've recorded the following:</p>
 111 <pre><code>0: 3
 112 1: 2
 113 4: 4
 114 6: 4
 115 </code></pre>
 116 <p>This means that there is a layer immediately inside the firewall (with range <code>3</code>), a second layer immediately after that (with range <code>2</code>), a third layer which begins at depth <code>4</code> (with range <code>4</code>), and a fourth layer which begins at depth 6 (also with range <code>4</code>). Visually, it might look like this:</p>
 117 <pre><code> 0   1   2   3   4   5   6
 118 [ ] [ ] ... ... [ ] ... [ ]
 119 [ ] [ ]         [ ]     [ ]
 120 [ ]             [ ]     [ ]
 121                 [ ]     [ ]
 122 </code></pre>
 123 <p>Within each layer, a security scanner moves back and forth within its range. Each security scanner starts at the top and moves down until it reaches the bottom, then moves up until it reaches the top, and repeats. A security scanner takes <em>one picosecond</em> to move one step.  Drawing scanners as <code>S</code>, the first few picoseconds look like this:</p>
 124 <pre><code>
 125 Picosecond 0:
 126  0   1   2   3   4   5   6
 127 [S] [S] ... ... [S] ... [S]
 128 [ ] [ ]         [ ]     [ ]
 129 [ ]             [ ]     [ ]
 130                 [ ]     [ ]
 131
 132 Picosecond 1:
 133  0   1   2   3   4   5   6
 134 [ ] [ ] ... ... [ ] ... [ ]
 135 [S] [S]         [S]     [S]
 136 [ ]             [ ]     [ ]
 137                 [ ]     [ ]
 138
 139 Picosecond 2:
 140  0   1   2   3   4   5   6
 141 [ ] [S] ... ... [ ] ... [ ]
 142 [ ] [ ]         [ ]     [ ]
 143 [S]             [S]     [S]
 144                 [ ]     [ ]
 145
 146 Picosecond 3:
 147  0   1   2   3   4   5   6
 148 [ ] [ ] ... ... [ ] ... [ ]
 149 [S] [S]         [ ]     [ ]
 150 [ ]             [ ]     [ ]
 151                 [S]     [S]
 152 </code></pre>
 153 <p>Your plan is to hitch a ride on a packet about to move through the firewall.  The packet will travel along the top of each layer, and it moves at <em>one layer per picosecond</em>. Each picosecond, the packet moves one layer forward (its first move takes it into layer 0), and then the scanners move one step. If there is a scanner at the top of the layer <em>as your packet enters it</em>, you are <em>caught</em>. (If a scanner moves into the top of its layer while you are there, you are <em>not</em> caught: it doesn't have time to notice you before you leave.) If you were to do this in the configuration above, marking your current position with parentheses, your passage through the firewall would look like this:</p>
 154 <pre><code>Initial state:
 155  0   1   2   3   4   5   6
 156 [S] [S] ... ... [S] ... [S]
 157 [ ] [ ]         [ ]     [ ]
 158 [ ]             [ ]     [ ]
 159                 [ ]     [ ]
 160
 161 Picosecond 0:
 162  0   1   2   3   4   5   6
 163 (S) [S] ... ... [S] ... [S]
 164 [ ] [ ]         [ ]     [ ]
 165 [ ]             [ ]     [ ]
 166                 [ ]     [ ]
 167
 168  0   1   2   3   4   5   6
 169 ( ) [ ] ... ... [ ] ... [ ]
 170 [S] [S]         [S]     [S]
 171 [ ]             [ ]     [ ]
 172                 [ ]     [ ]
 173
 174
 175 Picosecond 1:
 176  0   1   2   3   4   5   6
 177 [ ] ( ) ... ... [ ] ... [ ]
 178 [S] [S]         [S]     [S]
 179 [ ]             [ ]     [ ]
 180                 [ ]     [ ]
 181
 182  0   1   2   3   4   5   6
 183 [ ] (S) ... ... [ ] ... [ ]
 184 [ ] [ ]         [ ]     [ ]
 185 [S]             [S]     [S]
 186                 [ ]     [ ]
 187
 188
 189 Picosecond 2:
 190  0   1   2   3   4   5   6
 191 [ ] [S] (.) ... [ ] ... [ ]
 192 [ ] [ ]         [ ]     [ ]
 193 [S]             [S]     [S]
 194                 [ ]     [ ]
 195
 196  0   1   2   3   4   5   6
 197 [ ] [ ] (.) ... [ ] ... [ ]
 198 [S] [S]         [ ]     [ ]
 199 [ ]             [ ]     [ ]
 200                 [S]     [S]
 201
 202
 203 Picosecond 3:
 204  0   1   2   3   4   5   6
 205 [ ] [ ] ... (.) [ ] ... [ ]
 206 [S] [S]         [ ]     [ ]
 207 [ ]             [ ]     [ ]
 208                 [S]     [S]
 209
 210  0   1   2   3   4   5   6
 211 [S] [S] ... (.) [ ] ... [ ]
 212 [ ] [ ]         [ ]     [ ]
 213 [ ]             [S]     [S]
 214                 [ ]     [ ]
 215
 216
 217 Picosecond 4:
 218  0   1   2   3   4   5   6
 219 [S] [S] ... ... ( ) ... [ ]
 220 [ ] [ ]         [ ]     [ ]
 221 [ ]             [S]     [S]
 222                 [ ]     [ ]
 223
 224  0   1   2   3   4   5   6
 225 [ ] [ ] ... ... ( ) ... [ ]
 226 [S] [S]         [S]     [S]
 227 [ ]             [ ]     [ ]
 228                 [ ]     [ ]
 229
 230
 231 Picosecond 5:
 232  0   1   2   3   4   5   6
 233 [ ] [ ] ... ... [ ] (.) [ ]
 234 [S] [S]         [S]     [S]
 235 [ ]             [ ]     [ ]
 236                 [ ]     [ ]
 237
 238  0   1   2   3   4   5   6
 239 [ ] [S] ... ... [S] (.) [S]
 240 [ ] [ ]         [ ]     [ ]
 241 [S]             [ ]     [ ]
 242                 [ ]     [ ]
 243
 244
 245 Picosecond 6:
 246  0   1   2   3   4   5   6
 247 [ ] [S] ... ... [S] ... (S)
 248 [ ] [ ]         [ ]     [ ]
 249 [S]             [ ]     [ ]
 250                 [ ]     [ ]
 251
 252  0   1   2   3   4   5   6
 253 [ ] [ ] ... ... [ ] ... ( )
 254 [S] [S]         [S]     [S]
 255 [ ]             [ ]     [ ]
 256                 [ ]     [ ]
 257 </code></pre>
 258 <p>In this situation, you are <em>caught</em> in layers <code>0</code> and <code>6</code>, because your packet entered the layer when its scanner was at the top when you entered it. You are <em>not</em> caught in layer <code>1</code>, since the scanner moved into the top of the layer once you were already there.</p>
 259 <p>The <em>severity</em> of getting caught on a layer is equal to its <em>depth</em> multiplied by its <em>range</em>. (Ignore layers in which you do not get caught.) The severity of the whole trip is the sum of these values.  In the example above, the trip severity is <code>0*3 + 6*4 = <em>24</em></code>.</p>
 260 <p>Given the details of the firewall you've recorded, if you leave immediately, <em>what is the severity of your whole trip</em>?</p>
 261 </article>
 262 <p>Your puzzle answer was <code>1904</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>Now, you need to pass through the firewall without being caught - easier said than done.</p>
 263 <p>You can't control the <span title="Seriously, what network stack doesn't let you adjust the speed of light?">speed of the packet</span>, but you can <em>delay</em> it any number of picoseconds. For each picosecond you delay the packet before beginning your trip, all security scanners move one step. You're not in the firewall during this time; you don't enter layer <code>0</code> until you stop delaying the packet.</p>
 264 <p>In the example above, if you delay <code>10</code> picoseconds (picoseconds <code>0</code> - <code>9</code>), you won't get caught:</p>
 265 <pre><code>State after delaying:
 266  0   1   2   3   4   5   6
 267 [ ] [S] ... ... [ ] ... [ ]
 268 [ ] [ ]         [ ]     [ ]
 269 [S]             [S]     [S]
 270                 [ ]     [ ]
 271
 272 Picosecond 10:
 273  0   1   2   3   4   5   6
 274 ( ) [S] ... ... [ ] ... [ ]
 275 [ ] [ ]         [ ]     [ ]
 276 [S]             [S]     [S]
 277                 [ ]     [ ]
 278
 279  0   1   2   3   4   5   6
 280 ( ) [ ] ... ... [ ] ... [ ]
 281 [S] [S]         [S]     [S]
 282 [ ]             [ ]     [ ]
 283                 [ ]     [ ]
 284
 285
 286 Picosecond 11:
 287  0   1   2   3   4   5   6
 288 [ ] ( ) ... ... [ ] ... [ ]
 289 [S] [S]         [S]     [S]
 290 [ ]             [ ]     [ ]
 291                 [ ]     [ ]
 292
 293  0   1   2   3   4   5   6
 294 [S] (S) ... ... [S] ... [S]
 295 [ ] [ ]         [ ]     [ ]
 296 [ ]             [ ]     [ ]
 297                 [ ]     [ ]
 298
 299
 300 Picosecond 12:
 301  0   1   2   3   4   5   6
 302 [S] [S] (.) ... [S] ... [S]
 303 [ ] [ ]         [ ]     [ ]
 304 [ ]             [ ]     [ ]
 305                 [ ]     [ ]
 306
 307  0   1   2   3   4   5   6
 308 [ ] [ ] (.) ... [ ] ... [ ]
 309 [S] [S]         [S]     [S]
 310 [ ]             [ ]     [ ]
 311                 [ ]     [ ]
 312
 313
 314 Picosecond 13:
 315  0   1   2   3   4   5   6
 316 [ ] [ ] ... (.) [ ] ... [ ]
 317 [S] [S]         [S]     [S]
 318 [ ]             [ ]     [ ]
 319                 [ ]     [ ]
 320
 321  0   1   2   3   4   5   6
 322 [ ] [S] ... (.) [ ] ... [ ]
 323 [ ] [ ]         [ ]     [ ]
 324 [S]             [S]     [S]
 325                 [ ]     [ ]
 326
 327
 328 Picosecond 14:
 329  0   1   2   3   4   5   6
 330 [ ] [S] ... ... ( ) ... [ ]
 331 [ ] [ ]         [ ]     [ ]
 332 [S]             [S]     [S]
 333                 [ ]     [ ]
 334
 335  0   1   2   3   4   5   6
 336 [ ] [ ] ... ... ( ) ... [ ]
 337 [S] [S]         [ ]     [ ]
 338 [ ]             [ ]     [ ]
 339                 [S]     [S]
 340
 341
 342 Picosecond 15:
 343  0   1   2   3   4   5   6
 344 [ ] [ ] ... ... [ ] (.) [ ]
 345 [S] [S]         [ ]     [ ]
 346 [ ]             [ ]     [ ]
 347                 [S]     [S]
 348
 349  0   1   2   3   4   5   6
 350 [S] [S] ... ... [ ] (.) [ ]
 351 [ ] [ ]         [ ]     [ ]
 352 [ ]             [S]     [S]
 353                 [ ]     [ ]
 354
 355
 356 Picosecond 16:
 357  0   1   2   3   4   5   6
 358 [S] [S] ... ... [ ] ... ( )
 359 [ ] [ ]         [ ]     [ ]
 360 [ ]             [S]     [S]
 361                 [ ]     [ ]
 362
 363  0   1   2   3   4   5   6
 364 [ ] [ ] ... ... [ ] ... ( )
 365 [S] [S]         [S]     [S]
 366 [ ]             [ ]     [ ]
 367                 [ ]     [ ]
 368 </code></pre>
 369 <p>Because all smaller delays would get you caught, the fewest number of picoseconds you would need to delay to get through safely is <code>10</code>.</p>
 370 <p><em>What is the fewest number of picoseconds</em> that you need to delay the packet to pass through the firewall without being caught?</p>
 371 </article>
 372 <p>Your puzzle answer was <code>3833504</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 373 <p>At this point, you should <a href="/2017">return to your advent calendar</a> and try another puzzle.</p>
 374 <p>If you still want to see it, you can <a href="13/input" target="_blank">get your puzzle input</a>.</p>
 375 <p>You can also <span class="share">[Share<span class="share-content">on
 376   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Packet+Scanners%22+%2D+Day+13+%2D+Advent+of+Code+2017&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F13&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 377   <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F13" target="_blank">Google+</a>
 378   <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F13&amp;title=I%27ve+completed+%22Packet+Scanners%22+%2D+Day+13+%2D+Advent+of+Code+2017" target="_blank">Reddit</a
 379 ></span>]</span> this puzzle.</p>
 380 </main>
 381
 382 <!-- ga -->
 383 <script>
 384 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 385 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 386 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 387 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 388 ga('create', 'UA-69522494-1', 'auto');
 389 ga('send', 'pageview');
 390 </script>
 391 <!-- /ga -->
 392 </body>
 393 </html>