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 2022</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?30"/>
   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 <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>
  12 </head><!--
  13
  14
  15
  16
  17 Oh, hello!  Funny seeing you here.
  18
  19 I appreciate your enthusiasm, but you aren't going to find much down here.
  20 There certainly aren't clues to any of the puzzles.  The best surprises don't
  21 even appear in the source until you unlock them for real.
  22
  23 Please be careful with automated requests; I'm not a massive company, and I can
  24 only take so much traffic.  Please be considerate so that everyone gets to play.
  25
  26 If you're curious about how Advent of Code works, it's running on some custom
  27 Perl code. Other than a few integrations (auth, analytics, social media), I
  28 built the whole thing myself, including the design, animations, prose, and all
  29 of the puzzles.
  30
  31 The puzzles are most of the work; preparing a new calendar and a new set of
  32 puzzles each year takes all of my free time for 4-5 months. A lot of effort
  33 went into building this thing - I hope you're enjoying playing it as much as I
  34 enjoyed making it for you!
  35
  36 If you'd like to hang out, I'm @ericwastl on Twitter.
  37
  38 - Eric Wastl
  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 -->
  90 <body>
  91 <header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2022/about">[About]</a></li><li><a href="/2022/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2022/settings">[Settings]</a></li><li><a href="/2022/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2022/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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">/*</span><a href="/2022">2022</a><span class="title-event-wrap">*/</span></h1><nav><ul><li><a href="/2022">[Calendar]</a></li><li><a href="/2022/support">[AoC++]</a></li><li><a href="/2022/sponsors">[Sponsors]</a></li><li><a href="/2022/leaderboard">[Leaderboard]</a></li><li><a href="/2022/stats">[Stats]</a></li></ul></nav></div></header>
  92
  93 <div id="sidebar">
  94 <div id="sponsor"><div class="quiet">Our <a href="/2022/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://www.exoscale.com/products/?utm_source=adventofcode&amp;utm_medium=referrer&amp;utm_campaign=ref-advent-2023" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">Exoscale</a> - Where to host your next application? Discover our simple and secure European cloud platform and get started in seconds. Happy coding!</div></div>
  95 </div><!--/sidebar-->
  96
  97 <main>
  98 <article class="day-desc"><h2>--- Day 11: Monkey in the Middle ---</h2><p>As you finally start making your way upriver, you realize your pack is much lighter than you remember. Just then, one of the items from your pack goes flying overhead. Monkeys are playing <a href="https://en.wikipedia.org/wiki/Keep_away" target="_blank">Keep Away</a> with your missing things!</p>
  99 <p>To get your stuff back, you need to be able to predict where the monkeys will throw your items. After some careful observation, you realize the monkeys operate based on <em>how worried you are about each item</em>.</p>
 100 <p>You take some notes (your puzzle input) on the items each monkey currently has, how worried you are about those items, and how the monkey makes decisions based on your worry level. For example:</p>
 101 <pre><code>Monkey 0:
 102   Starting items: 79, 98
 103   Operation: new = old * 19
 104   Test: divisible by 23
 105     If true: throw to monkey 2
 106     If false: throw to monkey 3
 107
 108 Monkey 1:
 109   Starting items: 54, 65, 75, 74
 110   Operation: new = old + 6
 111   Test: divisible by 19
 112     If true: throw to monkey 2
 113     If false: throw to monkey 0
 114
 115 Monkey 2:
 116   Starting items: 79, 60, 97
 117   Operation: new = old * old
 118   Test: divisible by 13
 119     If true: throw to monkey 1
 120     If false: throw to monkey 3
 121
 122 Monkey 3:
 123   Starting items: 74
 124   Operation: new = old + 3
 125   Test: divisible by 17
 126     If true: throw to monkey 0
 127     If false: throw to monkey 1
 128 </code></pre>
 129 <p>Each monkey has several attributes:</p>
 130 <ul>
 131 <li><code>Starting items</code> lists your <em>worry level</em> for each item the monkey is currently holding in the order they will be inspected.</li>
 132 <li><code>Operation</code> shows how your worry level changes as that monkey inspects an item. (An operation like <code>new = old * 5</code> means that your worry level after the monkey inspected the item is five times whatever your worry level was before inspection.)</li>
 133 <li><code>Test</code> shows how the monkey uses your worry level to decide where to throw an item next.
 134   <ul>
 135   <li><code>If true</code> shows what happens with an item if the <code>Test</code> was true.</li>
 136   <li><code>If false</code> shows what happens with an item if the <code>Test</code> was false.</li>
 137   </ul>
 138 </li>
 139 </ul>
 140 <p>After each monkey inspects an item but before it tests your worry level, your relief that the monkey's inspection didn't damage the item causes your worry level to be <em>divided by three</em> and rounded down to the nearest integer.</p>
 141 <p>The monkeys take turns inspecting and throwing items. On a single monkey's <em>turn</em>, it inspects and throws all of the items it is holding one at a time and in the order listed. Monkey <code>0</code> goes first, then monkey <code>1</code>, and so on until each monkey has had one turn. The process of each monkey taking a single turn is called a <em>round</em>.</p>
 142 <p>When a monkey throws an item to another monkey, the item goes on the <em>end</em> of the recipient monkey's list. A monkey that starts a round with no items could end up inspecting and throwing many items by the time its turn comes around. If a monkey is holding no items at the start of its turn, its turn ends.</p>
 143 <p>In the above example, the first round proceeds as follows:</p>
 144 <pre><code>Monkey 0:
 145   Monkey inspects an item with a worry level of 79.
 146     Worry level is multiplied by 19 to 1501.
 147     Monkey gets bored with item. Worry level is divided by 3 to 500.
 148     Current worry level is not divisible by 23.
 149     Item with worry level 500 is thrown to monkey 3.
 150   Monkey inspects an item with a worry level of 98.
 151     Worry level is multiplied by 19 to 1862.
 152     Monkey gets bored with item. Worry level is divided by 3 to 620.
 153     Current worry level is not divisible by 23.
 154     Item with worry level 620 is thrown to monkey 3.
 155 Monkey 1:
 156   Monkey inspects an item with a worry level of 54.
 157     Worry level increases by 6 to 60.
 158     Monkey gets bored with item. Worry level is divided by 3 to 20.
 159     Current worry level is not divisible by 19.
 160     Item with worry level 20 is thrown to monkey 0.
 161   Monkey inspects an item with a worry level of 65.
 162     Worry level increases by 6 to 71.
 163     Monkey gets bored with item. Worry level is divided by 3 to 23.
 164     Current worry level is not divisible by 19.
 165     Item with worry level 23 is thrown to monkey 0.
 166   Monkey inspects an item with a worry level of 75.
 167     Worry level increases by 6 to 81.
 168     Monkey gets bored with item. Worry level is divided by 3 to 27.
 169     Current worry level is not divisible by 19.
 170     Item with worry level 27 is thrown to monkey 0.
 171   Monkey inspects an item with a worry level of 74.
 172     Worry level increases by 6 to 80.
 173     Monkey gets bored with item. Worry level is divided by 3 to 26.
 174     Current worry level is not divisible by 19.
 175     Item with worry level 26 is thrown to monkey 0.
 176 Monkey 2:
 177   Monkey inspects an item with a worry level of 79.
 178     Worry level is multiplied by itself to 6241.
 179     Monkey gets bored with item. Worry level is divided by 3 to 2080.
 180     Current worry level is divisible by 13.
 181     Item with worry level 2080 is thrown to monkey 1.
 182   Monkey inspects an item with a worry level of 60.
 183     Worry level is multiplied by itself to 3600.
 184     Monkey gets bored with item. Worry level is divided by 3 to 1200.
 185     Current worry level is not divisible by 13.
 186     Item with worry level 1200 is thrown to monkey 3.
 187   Monkey inspects an item with a worry level of 97.
 188     Worry level is multiplied by itself to 9409.
 189     Monkey gets bored with item. Worry level is divided by 3 to 3136.
 190     Current worry level is not divisible by 13.
 191     Item with worry level 3136 is thrown to monkey 3.
 192 Monkey 3:
 193   Monkey inspects an item with a worry level of 74.
 194     Worry level increases by 3 to 77.
 195     Monkey gets bored with item. Worry level is divided by 3 to 25.
 196     Current worry level is not divisible by 17.
 197     Item with worry level 25 is thrown to monkey 1.
 198   Monkey inspects an item with a worry level of 500.
 199     Worry level increases by 3 to 503.
 200     Monkey gets bored with item. Worry level is divided by 3 to 167.
 201     Current worry level is not divisible by 17.
 202     Item with worry level 167 is thrown to monkey 1.
 203   Monkey inspects an item with a worry level of 620.
 204     Worry level increases by 3 to 623.
 205     Monkey gets bored with item. Worry level is divided by 3 to 207.
 206     Current worry level is not divisible by 17.
 207     Item with worry level 207 is thrown to monkey 1.
 208   Monkey inspects an item with a worry level of 1200.
 209     Worry level increases by 3 to 1203.
 210     Monkey gets bored with item. Worry level is divided by 3 to 401.
 211     Current worry level is not divisible by 17.
 212     Item with worry level 401 is thrown to monkey 1.
 213   Monkey inspects an item with a worry level of 3136.
 214     Worry level increases by 3 to 3139.
 215     Monkey gets bored with item. Worry level is divided by 3 to 1046.
 216     Current worry level is not divisible by 17.
 217     Item with worry level 1046 is thrown to monkey 1.
 218 </code></pre>
 219 <p>After round 1, the monkeys are holding items with these worry levels:</p>
 220 <pre><code>Monkey 0: 20, 23, 27, 26
 221 Monkey 1: 2080, 25, 167, 207, 401, 1046
 222 Monkey 2:
 223 Monkey 3:
 224 </code></pre>
 225 <p>Monkeys 2 and 3 aren't holding any items at the end of the round; they both inspected items during the round and threw them all before the round ended.</p>
 226 <p>This process continues for a few more rounds:</p>
 227 <pre><code>After round 2, the monkeys are holding items with these worry levels:
 228 Monkey 0: 695, 10, 71, 135, 350
 229 Monkey 1: 43, 49, 58, 55, 362
 230 Monkey 2:
 231 Monkey 3:
 232
 233 After round 3, the monkeys are holding items with these worry levels:
 234 Monkey 0: 16, 18, 21, 20, 122
 235 Monkey 1: 1468, 22, 150, 286, 739
 236 Monkey 2:
 237 Monkey 3:
 238
 239 After round 4, the monkeys are holding items with these worry levels:
 240 Monkey 0: 491, 9, 52, 97, 248, 34
 241 Monkey 1: 39, 45, 43, 258
 242 Monkey 2:
 243 Monkey 3:
 244
 245 After round 5, the monkeys are holding items with these worry levels:
 246 Monkey 0: 15, 17, 16, 88, 1037
 247 Monkey 1: 20, 110, 205, 524, 72
 248 Monkey 2:
 249 Monkey 3:
 250
 251 After round 6, the monkeys are holding items with these worry levels:
 252 Monkey 0: 8, 70, 176, 26, 34
 253 Monkey 1: 481, 32, 36, 186, 2190
 254 Monkey 2:
 255 Monkey 3:
 256
 257 After round 7, the monkeys are holding items with these worry levels:
 258 Monkey 0: 162, 12, 14, 64, 732, 17
 259 Monkey 1: 148, 372, 55, 72
 260 Monkey 2:
 261 Monkey 3:
 262
 263 After round 8, the monkeys are holding items with these worry levels:
 264 Monkey 0: 51, 126, 20, 26, 136
 265 Monkey 1: 343, 26, 30, 1546, 36
 266 Monkey 2:
 267 Monkey 3:
 268
 269 After round 9, the monkeys are holding items with these worry levels:
 270 Monkey 0: 116, 10, 12, 517, 14
 271 Monkey 1: 108, 267, 43, 55, 288
 272 Monkey 2:
 273 Monkey 3:
 274
 275 After round 10, the monkeys are holding items with these worry levels:
 276 Monkey 0: 91, 16, 20, 98
 277 Monkey 1: 481, 245, 22, 26, 1092, 30
 278 Monkey 2:
 279 Monkey 3:
 280
 281 ...
 282
 283 After round 15, the monkeys are holding items with these worry levels:
 284 Monkey 0: 83, 44, 8, 184, 9, 20, 26, 102
 285 Monkey 1: 110, 36
 286 Monkey 2:
 287 Monkey 3:
 288
 289 ...
 290
 291 After round 20, the monkeys are holding items with these worry levels:
 292 Monkey 0: 10, 12, 14, 26, 34
 293 Monkey 1: 245, 93, 53, 199, 115
 294 Monkey 2:
 295 Monkey 3:
 296 </code></pre>
 297 <p>Chasing all of the monkeys at once is impossible; you're going to have to focus on the <em>two most active</em> monkeys if you want any hope of getting your stuff back. Count the <em>total number of times each monkey inspects items</em> over 20 rounds:</p>
 298 <pre><code><em>Monkey 0 inspected items 101 times.</em>
 299 Monkey 1 inspected items 95 times.
 300 Monkey 2 inspected items 7 times.
 301 <em>Monkey 3 inspected items 105 times.</em>
 302 </code></pre>
 303 <p>In this example, the two most active monkeys inspected items 101 and 105 times. The level of <em>monkey business</em> in this situation can be found by multiplying these together: <code><em>10605</em></code>.</p>
 304 <p>Figure out which monkeys to chase by counting how many items they inspect over 20 rounds. <em>What is the level of monkey business after 20 rounds of stuff-slinging simian shenanigans?</em></p>
 305 </article>
 306 <p>Your puzzle answer was <code>112815</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>You're worried you might not ever get your items back. So worried, in fact, that your relief that a monkey's inspection didn't damage an item <em>no longer causes your worry level to be divided by three</em>.</p>
 307 <p>Unfortunately, that relief was all that was keeping your worry levels from reaching <em>ridiculous levels</em>. You'll need to <em>find another way to keep your worry levels manageable</em>.</p>
 308 <p>At this rate, you might be putting up with these monkeys for a <em>very long time</em> - possibly <em><code>10000</code> rounds</em>!</p>
 309 <p>With these new rules, you can still figure out the <span title="Monkey business monkey business monkey business, monkey numbers... is this working?">monkey business</span> after 10000 rounds. Using the same example above:</p>
 310 <pre><code>== After round 1 ==
 311 Monkey 0 inspected items 2 times.
 312 Monkey 1 inspected items 4 times.
 313 Monkey 2 inspected items 3 times.
 314 Monkey 3 inspected items 6 times.
 315
 316 == After round 20 ==
 317 Monkey 0 inspected items 99 times.
 318 Monkey 1 inspected items 97 times.
 319 Monkey 2 inspected items 8 times.
 320 Monkey 3 inspected items 103 times.
 321
 322 == After round 1000 ==
 323 Monkey 0 inspected items 5204 times.
 324 Monkey 1 inspected items 4792 times.
 325 Monkey 2 inspected items 199 times.
 326 Monkey 3 inspected items 5192 times.
 327
 328 == After round 2000 ==
 329 Monkey 0 inspected items 10419 times.
 330 Monkey 1 inspected items 9577 times.
 331 Monkey 2 inspected items 392 times.
 332 Monkey 3 inspected items 10391 times.
 333
 334 == After round 3000 ==
 335 Monkey 0 inspected items 15638 times.
 336 Monkey 1 inspected items 14358 times.
 337 Monkey 2 inspected items 587 times.
 338 Monkey 3 inspected items 15593 times.
 339
 340 == After round 4000 ==
 341 Monkey 0 inspected items 20858 times.
 342 Monkey 1 inspected items 19138 times.
 343 Monkey 2 inspected items 780 times.
 344 Monkey 3 inspected items 20797 times.
 345
 346 == After round 5000 ==
 347 Monkey 0 inspected items 26075 times.
 348 Monkey 1 inspected items 23921 times.
 349 Monkey 2 inspected items 974 times.
 350 Monkey 3 inspected items 26000 times.
 351
 352 == After round 6000 ==
 353 Monkey 0 inspected items 31294 times.
 354 Monkey 1 inspected items 28702 times.
 355 Monkey 2 inspected items 1165 times.
 356 Monkey 3 inspected items 31204 times.
 357
 358 == After round 7000 ==
 359 Monkey 0 inspected items 36508 times.
 360 Monkey 1 inspected items 33488 times.
 361 Monkey 2 inspected items 1360 times.
 362 Monkey 3 inspected items 36400 times.
 363
 364 == After round 8000 ==
 365 Monkey 0 inspected items 41728 times.
 366 Monkey 1 inspected items 38268 times.
 367 Monkey 2 inspected items 1553 times.
 368 Monkey 3 inspected items 41606 times.
 369
 370 == After round 9000 ==
 371 Monkey 0 inspected items 46945 times.
 372 Monkey 1 inspected items 43051 times.
 373 Monkey 2 inspected items 1746 times.
 374 Monkey 3 inspected items 46807 times.
 375
 376 == After round 10000 ==
 377 <em>Monkey 0 inspected items 52166 times.</em>
 378 Monkey 1 inspected items 47830 times.
 379 Monkey 2 inspected items 1938 times.
 380 <em>Monkey 3 inspected items 52013 times.</em>
 381 </code></pre>
 382 <p>After 10000 rounds, the two most active monkeys inspected items 52166 and 52013 times. Multiplying these together, the level of <em>monkey business</em> in this situation is now <code><em>2713310158</em></code>.</p>
 383 <p>Worry levels are no longer divided by three after each item is inspected; you'll need to find another way to keep your worry levels manageable. Starting again from the initial state in your puzzle input, <em>what is the level of monkey business after 10000 rounds?</em></p>
 384 </article>
 385 <p>Your puzzle answer was <code>25738411485</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 386 <p>At this point, you should <a href="/2022">return to your Advent calendar</a> and try another puzzle.</p>
 387 <p>If you still want to see it, you can <a href="11/input" target="_blank">get your puzzle input</a>.</p>
 388 <p>You can also <span class="share">[Share<span class="share-content">on
 389   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Monkey+in+the+Middle%22+%2D+Day+11+%2D+Advent+of+Code+2022&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2022%2Fday%2F11&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 390   <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+%22Monkey+in+the+Middle%22+%2D+Day+11+%2D+Advent+of+Code+2022+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2022%2Fday%2F11'}else{return false;}" target="_blank">Mastodon</a
 391 ></span>]</span> this puzzle.</p>
 392 </main>
 393
 394 <!-- ga -->
 395 <script>
 396 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 397 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 398 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 399 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 400 ga('create', 'UA-69522494-1', 'auto');
 401 ga('set', 'anonymizeIp', true);
 402 ga('send', 'pageview');
 403 </script>
 404 <!-- /ga -->
 405 </body>
 406 </html>