problems/day11.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 11 - Advent of Code 2021</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?26"/>
   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="/2021/about">[About]</a></li><li><a href="/2021/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2021/settings">[Settings]</a></li><li><a href="/2021/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2021/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">22*</span></div></div><div><h1 class="title-event">&nbsp;<span class="title-event-wrap">{&apos;year&apos;:</span><a href="/2021">2021</a><span class="title-event-wrap">}</span></h1><nav><ul><li><a href="/2021">[Calendar]</a></li><li><a href="/2021/support">[AoC++]</a></li><li><a href="/2021/sponsors">[Sponsors]</a></li><li><a href="/2021/leaderboard">[Leaderboard]</a></li><li><a href="/2021/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2021/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://2021-aoc-templates.util.repl.co/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Replit</a> - Code and host in your browser with no setup in Python, React, Kaboom.js, Java, C, Nix, you name it, even Solidity. Happy coding!</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 11: Dumbo Octopus ---</h2><p>You enter a large cavern full of rare bioluminescent <a href="https://www.youtube.com/watch?v=eih-VSaS2g0" target="_blank">dumbo octopuses</a>! They seem to not like the Christmas lights on your submarine, so you turn them off for now.</p>
  99 <p>There are 100 <span title="I know it's weird; I grew up saying 'octopi' too.">octopuses</span> arranged neatly in a 10 by 10 grid. Each octopus slowly gains <em>energy</em> over time and <em>flashes</em> brightly for a moment when its energy is full. Although your lights are off, maybe you could navigate through the cave without disturbing the octopuses if you could predict when the flashes of light will happen.</p>
 100 <p>Each octopus has an <em>energy level</em> - your submarine can remotely measure the energy level of each octopus (your puzzle input). For example:</p>
 101 <pre><code>5483143223
 102 2745854711
 103 5264556173
 104 6141336146
 105 6357385478
 106 4167524645
 107 2176841721
 108 6882881134
 109 4846848554
 110 5283751526
 111 </code></pre>
 112 <p>The energy level of each octopus is a value between <code>0</code> and <code>9</code>. Here, the top-left octopus has an energy level of <code>5</code>, the bottom-right one has an energy level of <code>6</code>, and so on.</p>
 113 <p>You can model the energy levels and flashes of light in <em>steps</em>. During a single step, the following occurs:</p>
 114 <ul>
 115 <li>First, the energy level of each octopus increases by <code>1</code>.</li>
 116 <li>Then, any octopus with an energy level greater than <code>9</code> <em>flashes</em>. This increases the energy level of all adjacent octopuses by <code>1</code>, including octopuses that are diagonally adjacent. If this causes an octopus to have an energy level greater than <code>9</code>, it <em>also flashes</em>. This process continues as long as new octopuses keep having their energy level increased beyond <code>9</code>. (An octopus can only flash <em>at most once per step</em>.)</li>
 117 <li>Finally, any octopus that flashed during this step has its energy level set to <code>0</code>, as it used all of its energy to flash.</li>
 118 </ul>
 119 <p>Adjacent flashes can cause an octopus to flash on a step even if it begins that step with very little energy. Consider the middle octopus with <code>1</code> energy in this situation:</p>
 120 <pre><code>Before any steps:
 121 11111
 122 19991
 123 19191
 124 19991
 125 11111
 126
 127 After step 1:
 128 34543
 129 4<em>000</em>4
 130 5<em>000</em>5
 131 4<em>000</em>4
 132 34543
 133
 134 After step 2:
 135 45654
 136 51115
 137 61116
 138 51115
 139 45654
 140 </code></pre>
 141 <p>An octopus is <em>highlighted</em> when it flashed during the given step.</p>
 142 <p>Here is how the larger example above progresses:</p>
 143 <pre><code>Before any steps:
 144 5483143223
 145 2745854711
 146 5264556173
 147 6141336146
 148 6357385478
 149 4167524645
 150 2176841721
 151 6882881134
 152 4846848554
 153 5283751526
 154
 155 After step 1:
 156 6594254334
 157 3856965822
 158 6375667284
 159 7252447257
 160 7468496589
 161 5278635756
 162 3287952832
 163 7993992245
 164 5957959665
 165 6394862637
 166
 167 After step 2:
 168 88<em>0</em>7476555
 169 5<em>0</em>89<em>0</em>87<em>0</em>54
 170 85978896<em>0</em>8
 171 84857696<em>00</em>
 172 87<em>00</em>9<em>0</em>88<em>00</em>
 173 66<em>000</em>88989
 174 68<em>0000</em>5943
 175 <em>000000</em>7456
 176 9<em>000000</em>876
 177 87<em>0000</em>6848
 178
 179 After step 3:
 180 <em>00</em>5<em>0</em>9<em>00</em>866
 181 85<em>00</em>8<em>00</em>575
 182 99<em>000000</em>39
 183 97<em>000000</em>41
 184 9935<em>0</em>8<em>00</em>63
 185 77123<em>00000</em>
 186 791125<em>000</em>9
 187 221113<em>0000</em>
 188 <em>0</em>421125<em>000</em>
 189 <em>00</em>21119<em>000</em>
 190
 191 After step 4:
 192 2263<em>0</em>31977
 193 <em>0</em>923<em>0</em>31697
 194 <em>00</em>3222115<em>0</em>
 195 <em>00</em>41111163
 196 <em>00</em>76191174
 197 <em>00</em>53411122
 198 <em>00</em>4236112<em>0</em>
 199 5532241122
 200 1532247211
 201 113223<em>0</em>211
 202
 203 After step 5:
 204 4484144<em>000</em>
 205 2<em>0</em>44144<em>000</em>
 206 2253333493
 207 1152333274
 208 11873<em>0</em>3285
 209 1164633233
 210 1153472231
 211 6643352233
 212 2643358322
 213 2243341322
 214
 215 After step 6:
 216 5595255111
 217 3155255222
 218 33644446<em>0</em>5
 219 2263444496
 220 2298414396
 221 2275744344
 222 2264583342
 223 7754463344
 224 3754469433
 225 3354452433
 226
 227 After step 7:
 228 67<em>0</em>7366222
 229 4377366333
 230 4475555827
 231 34966557<em>0</em>9
 232 35<em>00</em>6256<em>0</em>9
 233 35<em>0</em>9955566
 234 3486694453
 235 8865585555
 236 486558<em>0</em>644
 237 4465574644
 238
 239 After step 8:
 240 7818477333
 241 5488477444
 242 5697666949
 243 46<em>0</em>876683<em>0</em>
 244 473494673<em>0</em>
 245 474<em>00</em>97688
 246 69<em>0000</em>7564
 247 <em>000000</em>9666
 248 8<em>00000</em>4755
 249 68<em>0000</em>7755
 250
 251 After step 9:
 252 9<em>0</em>6<em>0000</em>644
 253 78<em>00000</em>976
 254 69<em>000000</em>8<em>0</em>
 255 584<em>00000</em>82
 256 5858<em>0000</em>93
 257 69624<em>00000</em>
 258 8<em>0</em>2125<em>000</em>9
 259 222113<em>000</em>9
 260 9111128<em>0</em>97
 261 7911119976
 262
 263 After step 10:
 264 <em>0</em>481112976
 265 <em>00</em>31112<em>00</em>9
 266 <em>00</em>411125<em>0</em>4
 267 <em>00</em>811114<em>0</em>6
 268 <em>00</em>991113<em>0</em>6
 269 <em>00</em>93511233
 270 <em>0</em>44236113<em>0</em>
 271 553225235<em>0</em>
 272 <em>0</em>53225<em>0</em>6<em>00</em>
 273 <em>00</em>3224<em>0000</em>
 274 </code></pre>
 275
 276 <p>After step 10, there have been a total of <code>204</code> flashes. Fast forwarding, here is the same configuration every 10 steps:</p>
 277
 278 <pre><code>After step 20:
 279 3936556452
 280 56865568<em>0</em>6
 281 449655569<em>0</em>
 282 444865558<em>0</em>
 283 445686557<em>0</em>
 284 568<em>00</em>86577
 285 7<em>00000</em>9896
 286 <em>0000000</em>344
 287 6<em>000000</em>364
 288 46<em>0000</em>9543
 289
 290 After step 30:
 291 <em>0</em>643334118
 292 4253334611
 293 3374333458
 294 2225333337
 295 2229333338
 296 2276733333
 297 2754574565
 298 5544458511
 299 9444447111
 300 7944446119
 301
 302 After step 40:
 303 6211111981
 304 <em>0</em>421111119
 305 <em>00</em>42111115
 306 <em>000</em>3111115
 307 <em>000</em>3111116
 308 <em>00</em>65611111
 309 <em>0</em>532351111
 310 3322234597
 311 2222222976
 312 2222222762
 313
 314 After step 50:
 315 9655556447
 316 48655568<em>0</em>5
 317 448655569<em>0</em>
 318 445865558<em>0</em>
 319 457486557<em>0</em>
 320 57<em>000</em>86566
 321 6<em>00000</em>9887
 322 8<em>000000</em>533
 323 68<em>00000</em>633
 324 568<em>0000</em>538
 325
 326 After step 60:
 327 25333342<em>00</em>
 328 274333464<em>0</em>
 329 2264333458
 330 2225333337
 331 2225333338
 332 2287833333
 333 3854573455
 334 1854458611
 335 1175447111
 336 1115446111
 337
 338 After step 70:
 339 8211111164
 340 <em>0</em>421111166
 341 <em>00</em>42111114
 342 <em>000</em>4211115
 343 <em>0000</em>211116
 344 <em>00</em>65611111
 345 <em>0</em>532351111
 346 7322235117
 347 5722223475
 348 4572222754
 349
 350 After step 80:
 351 1755555697
 352 59655556<em>0</em>9
 353 448655568<em>0</em>
 354 445865558<em>0</em>
 355 457<em>0</em>86557<em>0</em>
 356 57<em>000</em>86566
 357 7<em>00000</em>8666
 358 <em>0000000</em>99<em>0</em>
 359 <em>0000000</em>8<em>00</em>
 360 <em>0000000000</em>
 361
 362 After step 90:
 363 7433333522
 364 2643333522
 365 2264333458
 366 2226433337
 367 2222433338
 368 2287833333
 369 2854573333
 370 4854458333
 371 3387779333
 372 3333333333
 373
 374 After step 100:
 375 <em>0</em>397666866
 376 <em>0</em>749766918
 377 <em>00</em>53976933
 378 <em>000</em>4297822
 379 <em>000</em>4229892
 380 <em>00</em>53222877
 381 <em>0</em>532222966
 382 9322228966
 383 7922286866
 384 6789998766
 385 </code></pre>
 386 <p>After 100 steps, there have been a total of <code><em>1656</em></code> flashes.</p>
 387 <p>Given the starting energy levels of the dumbo octopuses in your cavern, simulate 100 steps. <em>How many total flashes are there after 100 steps?</em></p>
 388 </article>
 389 <p>Your puzzle answer was <code>1627</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>It seems like the individual flashes aren't bright enough to navigate. However, you might have a better option: the flashes seem to be <em>synchronizing</em>!</p>
 390 <p>In the example above, the first time all octopuses flash simultaneously is step <code><em>195</em></code>:</p>
 391 <pre><code>After step 193:
 392 5877777777
 393 8877777777
 394 7777777777
 395 7777777777
 396 7777777777
 397 7777777777
 398 7777777777
 399 7777777777
 400 7777777777
 401 7777777777
 402
 403 After step 194:
 404 6988888888
 405 9988888888
 406 8888888888
 407 8888888888
 408 8888888888
 409 8888888888
 410 8888888888
 411 8888888888
 412 8888888888
 413 8888888888
 414
 415 After step 195:
 416 <em>0000000000</em>
 417 <em>0000000000</em>
 418 <em>0000000000</em>
 419 <em>0000000000</em>
 420 <em>0000000000</em>
 421 <em>0000000000</em>
 422 <em>0000000000</em>
 423 <em>0000000000</em>
 424 <em>0000000000</em>
 425 <em>0000000000</em>
 426 </code></pre>
 427 <p>If you can calculate the exact moments when the octopuses will all flash simultaneously, you should be able to navigate through the cavern. <em>What is the first step during which all octopuses flash?</em></p>
 428 </article>
 429 <p>Your puzzle answer was <code>329</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 430 <p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
 431 <p>If you still want to see it, you can <a href="11/input" target="_blank">get your puzzle input</a>.</p>
 432 <p>You can also <span class="share">[Share<span class="share-content">on
 433   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Dumbo+Octopus%22+%2D+Day+11+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F11&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 434   <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+%22Dumbo+Octopus%22+%2D+Day+11+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F11'}else{return false;}" target="_blank">Mastodon</a
 435 ></span>]</span> this puzzle.</p>
 436 </main>
 437
 438 <!-- ga -->
 439 <script>
 440 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 441 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 442 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 443 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 444 ga('create', 'UA-69522494-1', 'auto');
 445 ga('set', 'anonymizeIp', true);
 446 ga('send', 'pageview');
 447 </script>
 448 <!-- /ga -->
 449 </body>
 450 </html>