problems/day24.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 24 - Advent of Code 2018</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?20"/>
   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 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 are most of the work; the easiest ones take 3-4 hours each, but the
  31 harder ones take 6-8 hours, and a few even longer than that. 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="/2018/about">[About]</a></li><li><a href="/2018/events">[Events]</a></li><li><a href="https://teespring.com/adventofcode-2019" target="_blank">[Shop]</a></li><li><a href="/2018/settings">[Settings]</a></li><li><a href="/2018/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2018/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">48*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">int y=</span><a href="/2018">2018</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2018">[Calendar]</a></li><li><a href="/2018/support">[AoC++]</a></li><li><a href="/2018/sponsors">[Sponsors]</a></li><li><a href="/2018/leaderboard">[Leaderboard]</a></li><li><a href="/2018/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2018/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','click',this.href);" rel="noopener">SmartyStreets</a> - Global address validation made by developers, for developers</div></div>
  94 </div><!--/sidebar-->
  95
  96 <main>
  97 <article class="day-desc"><h2>--- Day 24: Immune System Simulator 20XX ---</h2><p>After <a href="https://www.youtube.com/watch?v=NDVjLt_QHL8&t=7" target="_blank">a weird buzzing noise</a>, you appear back at the man's cottage. He seems relieved to see his friend, but quickly notices that the little reindeer caught some kind of cold while out exploring.</p>
  98 <p>The portly man explains that this reindeer's immune system isn't similar to regular reindeer immune systems:</p>
  99 <p>The <em>immune system</em> and the <em>infection</em> each have <span title="On second thought, it's pretty similar to regular reindeer immune systems.">an army</span> made up of several <em>groups</em>; each <em>group</em> consists of one or more identical <em>units</em>.  The armies repeatedly <em>fight</em> until only one army has units remaining.</p>
 100 <p><em>Units</em> within a group all have the same <em>hit points</em> (amount of damage a unit can take before it is destroyed), <em>attack damage</em> (the amount of damage each unit deals), an <em>attack type</em>, an <em>initiative</em> (higher initiative units attack first and win ties), and sometimes <em>weaknesses</em> or <em>immunities</em>. Here is an example group:</p>
 101 <pre><code>18 units each with 729 hit points (weak to fire; immune to cold, slashing)
 102  with an attack that does 8 radiation damage at initiative 10
 103 </code></pre>
 104 <p>Each group also has an <em>effective power</em>: the number of units in that group multiplied by their attack damage. The above group has an effective power of <code>18 * 8 = 144</code>. Groups never have zero or negative units; instead, the group is removed from combat.</p>
 105 <p>Each <em>fight</em> consists of two phases: <em>target selection</em> and <em>attacking</em>.</p>
 106 <p>During the <em>target selection</em> phase, each group attempts to choose one target. In decreasing order of effective power, groups choose their targets; in a tie, the group with the higher initiative chooses first. The attacking group chooses to target the group in the enemy army to which it would deal the most damage (after accounting for weaknesses and immunities, but not accounting for whether the defending group has enough units to actually receive all of that damage).</p>
 107 <p>If an attacking group is considering two defending groups to which it would deal equal damage, it chooses to target the defending group with the largest effective power; if there is still a tie, it chooses the defending group with the highest initiative.  If it cannot deal any defending groups damage, it does not choose a target.  Defending groups can only be chosen as a target by one attacking group.</p>
 108 <p>At the end of the target selection phase, each group has selected zero or one groups to attack, and each group is being attacked by zero or one groups.</p>
 109 <p>During the <em>attacking</em> phase, each group deals damage to the target it selected, if any. Groups attack in decreasing order of initiative, regardless of whether they are part of the infection or the immune system. (If a group contains no units, it cannot attack.)</p>
 110 <p>The damage an attacking group deals to a defending group depends on the attacking group's attack type and the defending group's immunities and weaknesses.  By default, an attacking group would deal damage equal to its <em>effective power</em> to the defending group.  However, if the defending group is <em>immune</em> to the attacking group's attack type, the defending group instead takes <em>no damage</em>; if the defending group is <em>weak</em> to the attacking group's attack type, the defending group instead takes <em>double damage</em>.</p>
 111 <p>The defending group only loses <em>whole units</em> from damage; damage is always dealt in such a way that it kills the most units possible, and any remaining damage to a unit that does not immediately kill it is ignored. For example, if a defending group contains <code>10</code> units with <code>10</code> hit points each and receives <code>75</code> damage, it loses exactly <code>7</code> units and is left with <code>3</code> units at full health.</p>
 112 <p>After the fight is over, if both armies still contain units, a new fight begins; combat only ends once one army has lost all of its units.</p>
 113 <p>For example, consider the following armies:</p>
 114 <pre><code>Immune System:
 115 17 units each with 5390 hit points (weak to radiation, bludgeoning) with
 116  an attack that does 4507 fire damage at initiative 2
 117 989 units each with 1274 hit points (immune to fire; weak to bludgeoning,
 118  slashing) with an attack that does 25 slashing damage at initiative 3
 119
 120 Infection:
 121 801 units each with 4706 hit points (weak to radiation) with an attack
 122  that does 116 bludgeoning damage at initiative 1
 123 4485 units each with 2961 hit points (immune to radiation; weak to fire,
 124  cold) with an attack that does 12 slashing damage at initiative 4
 125 </code></pre>
 126 <p>If these armies were to enter combat, the following fights, including details during the target selection and attacking phases, would take place:</p>
 127 <pre><code>Immune System:
 128 Group 1 contains 17 units
 129 Group 2 contains 989 units
 130 Infection:
 131 Group 1 contains 801 units
 132 Group 2 contains 4485 units
 133
 134 Infection group 1 would deal defending group 1 185832 damage
 135 Infection group 1 would deal defending group 2 185832 damage
 136 Infection group 2 would deal defending group 2 107640 damage
 137 Immune System group 1 would deal defending group 1 76619 damage
 138 Immune System group 1 would deal defending group 2 153238 damage
 139 Immune System group 2 would deal defending group 1 24725 damage
 140
 141 Infection group 2 attacks defending group 2, killing 84 units
 142 Immune System group 2 attacks defending group 1, killing 4 units
 143 Immune System group 1 attacks defending group 2, killing 51 units
 144 Infection group 1 attacks defending group 1, killing 17 units
 145 </code></pre>
 146 <pre><code>Immune System:
 147 Group 2 contains 905 units
 148 Infection:
 149 Group 1 contains 797 units
 150 Group 2 contains 4434 units
 151
 152 Infection group 1 would deal defending group 2 184904 damage
 153 Immune System group 2 would deal defending group 1 22625 damage
 154 Immune System group 2 would deal defending group 2 22625 damage
 155
 156 Immune System group 2 attacks defending group 1, killing 4 units
 157 Infection group 1 attacks defending group 2, killing 144 units
 158 </code></pre>
 159 <pre><code>Immune System:
 160 Group 2 contains 761 units
 161 Infection:
 162 Group 1 contains 793 units
 163 Group 2 contains 4434 units
 164
 165 Infection group 1 would deal defending group 2 183976 damage
 166 Immune System group 2 would deal defending group 1 19025 damage
 167 Immune System group 2 would deal defending group 2 19025 damage
 168
 169 Immune System group 2 attacks defending group 1, killing 4 units
 170 Infection group 1 attacks defending group 2, killing 143 units
 171 </code></pre>
 172 <pre><code>Immune System:
 173 Group 2 contains 618 units
 174 Infection:
 175 Group 1 contains 789 units
 176 Group 2 contains 4434 units
 177
 178 Infection group 1 would deal defending group 2 183048 damage
 179 Immune System group 2 would deal defending group 1 15450 damage
 180 Immune System group 2 would deal defending group 2 15450 damage
 181
 182 Immune System group 2 attacks defending group 1, killing 3 units
 183 Infection group 1 attacks defending group 2, killing 143 units
 184 </code></pre>
 185 <pre><code>Immune System:
 186 Group 2 contains 475 units
 187 Infection:
 188 Group 1 contains 786 units
 189 Group 2 contains 4434 units
 190
 191 Infection group 1 would deal defending group 2 182352 damage
 192 Immune System group 2 would deal defending group 1 11875 damage
 193 Immune System group 2 would deal defending group 2 11875 damage
 194
 195 Immune System group 2 attacks defending group 1, killing 2 units
 196 Infection group 1 attacks defending group 2, killing 142 units
 197 </code></pre>
 198 <pre><code>Immune System:
 199 Group 2 contains 333 units
 200 Infection:
 201 Group 1 contains 784 units
 202 Group 2 contains 4434 units
 203
 204 Infection group 1 would deal defending group 2 181888 damage
 205 Immune System group 2 would deal defending group 1 8325 damage
 206 Immune System group 2 would deal defending group 2 8325 damage
 207
 208 Immune System group 2 attacks defending group 1, killing 1 unit
 209 Infection group 1 attacks defending group 2, killing 142 units
 210 </code></pre>
 211 <pre><code>Immune System:
 212 Group 2 contains 191 units
 213 Infection:
 214 Group 1 contains 783 units
 215 Group 2 contains 4434 units
 216
 217 Infection group 1 would deal defending group 2 181656 damage
 218 Immune System group 2 would deal defending group 1 4775 damage
 219 Immune System group 2 would deal defending group 2 4775 damage
 220
 221 Immune System group 2 attacks defending group 1, killing 1 unit
 222 Infection group 1 attacks defending group 2, killing 142 units
 223 </code></pre>
 224 <pre><code>Immune System:
 225 Group 2 contains 49 units
 226 Infection:
 227 Group 1 contains 782 units
 228 Group 2 contains 4434 units
 229
 230 Infection group 1 would deal defending group 2 181424 damage
 231 Immune System group 2 would deal defending group 1 1225 damage
 232 Immune System group 2 would deal defending group 2 1225 damage
 233
 234 Immune System group 2 attacks defending group 1, killing 0 units
 235 Infection group 1 attacks defending group 2, killing 49 units
 236 </code></pre>
 237 <pre><code>Immune System:
 238 No groups remain.
 239 Infection:
 240 Group 1 contains 782 units
 241 Group 2 contains 4434 units
 242 </code></pre>
 243 <p>In the example above, the winning army ends up with <code>782 + 4434 = <em>5216</em></code> units.</p>
 244 <p>You scan the reindeer's condition (your puzzle input); the white-bearded man looks nervous.  As it stands now, <em>how many units would the winning army have</em>?</p>
 245 </article>
 246 <p>Your puzzle answer was <code>15493</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Things aren't looking good for the reindeer. The man asks whether more milk and cookies would help you think.</p>
 247 <p>If only you could give the reindeer's immune system a boost, you might be able to change the outcome of the combat.</p>
 248 <p>A <em>boost</em> is an integer increase in immune system units' attack damage. For example, if you were to boost the above example's immune system's units by <code>1570</code>, the armies would instead look like this:</p>
 249 <pre><code>Immune System:
 250 17 units each with 5390 hit points (weak to radiation, bludgeoning) with
 251  an attack that does <em>6077</em> fire damage at initiative 2
 252 989 units each with 1274 hit points (immune to fire; weak to bludgeoning,
 253  slashing) with an attack that does <em>1595</em> slashing damage at initiative 3
 254
 255 Infection:
 256 801 units each with 4706 hit points (weak to radiation) with an attack
 257  that does 116 bludgeoning damage at initiative 1
 258 4485 units each with 2961 hit points (immune to radiation; weak to fire,
 259  cold) with an attack that does 12 slashing damage at initiative 4
 260 </code></pre>
 261 <p>With this boost, the combat proceeds differently:</p>
 262 <pre><code>Immune System:
 263 Group 2 contains 989 units
 264 Group 1 contains 17 units
 265 Infection:
 266 Group 1 contains 801 units
 267 Group 2 contains 4485 units
 268
 269 Infection group 1 would deal defending group 2 185832 damage
 270 Infection group 1 would deal defending group 1 185832 damage
 271 Infection group 2 would deal defending group 1 53820 damage
 272 Immune System group 2 would deal defending group 1 1577455 damage
 273 Immune System group 2 would deal defending group 2 1577455 damage
 274 Immune System group 1 would deal defending group 2 206618 damage
 275
 276 Infection group 2 attacks defending group 1, killing 9 units
 277 Immune System group 2 attacks defending group 1, killing 335 units
 278 Immune System group 1 attacks defending group 2, killing 32 units
 279 Infection group 1 attacks defending group 2, killing 84 units
 280 </code></pre>
 281 <pre><code>Immune System:
 282 Group 2 contains 905 units
 283 Group 1 contains 8 units
 284 Infection:
 285 Group 1 contains 466 units
 286 Group 2 contains 4453 units
 287
 288 Infection group 1 would deal defending group 2 108112 damage
 289 Infection group 1 would deal defending group 1 108112 damage
 290 Infection group 2 would deal defending group 1 53436 damage
 291 Immune System group 2 would deal defending group 1 1443475 damage
 292 Immune System group 2 would deal defending group 2 1443475 damage
 293 Immune System group 1 would deal defending group 2 97232 damage
 294
 295 Infection group 2 attacks defending group 1, killing 8 units
 296 Immune System group 2 attacks defending group 1, killing 306 units
 297 Infection group 1 attacks defending group 2, killing 29 units
 298 </code></pre>
 299 <pre><code>Immune System:
 300 Group 2 contains 876 units
 301 Infection:
 302 Group 2 contains 4453 units
 303 Group 1 contains 160 units
 304
 305 Infection group 2 would deal defending group 2 106872 damage
 306 Immune System group 2 would deal defending group 2 1397220 damage
 307 Immune System group 2 would deal defending group 1 1397220 damage
 308
 309 Infection group 2 attacks defending group 2, killing 83 units
 310 Immune System group 2 attacks defending group 2, killing 427 units
 311 </code></pre>
 312 <p>After a few fights...</p>
 313 <pre><code>Immune System:
 314 Group 2 contains 64 units
 315 Infection:
 316 Group 2 contains 214 units
 317 Group 1 contains 19 units
 318
 319 Infection group 2 would deal defending group 2 5136 damage
 320 Immune System group 2 would deal defending group 2 102080 damage
 321 Immune System group 2 would deal defending group 1 102080 damage
 322
 323 Infection group 2 attacks defending group 2, killing 4 units
 324 Immune System group 2 attacks defending group 2, killing 32 units
 325 </code></pre>
 326 <pre><code>Immune System:
 327 Group 2 contains 60 units
 328 Infection:
 329 Group 1 contains 19 units
 330 Group 2 contains 182 units
 331
 332 Infection group 1 would deal defending group 2 4408 damage
 333 Immune System group 2 would deal defending group 1 95700 damage
 334 Immune System group 2 would deal defending group 2 95700 damage
 335
 336 Immune System group 2 attacks defending group 1, killing 19 units
 337 </code></pre>
 338 <pre><code>Immune System:
 339 Group 2 contains 60 units
 340 Infection:
 341 Group 2 contains 182 units
 342
 343 Infection group 2 would deal defending group 2 4368 damage
 344 Immune System group 2 would deal defending group 2 95700 damage
 345
 346 Infection group 2 attacks defending group 2, killing 3 units
 347 Immune System group 2 attacks defending group 2, killing 30 units
 348 </code></pre>
 349 <p>After a few more fights...</p>
 350 <pre><code>Immune System:
 351 Group 2 contains 51 units
 352 Infection:
 353 Group 2 contains 40 units
 354
 355 Infection group 2 would deal defending group 2 960 damage
 356 Immune System group 2 would deal defending group 2 81345 damage
 357
 358 Infection group 2 attacks defending group 2, killing 0 units
 359 Immune System group 2 attacks defending group 2, killing 27 units
 360 </code></pre>
 361 <pre><code>Immune System:
 362 Group 2 contains 51 units
 363 Infection:
 364 Group 2 contains 13 units
 365
 366 Infection group 2 would deal defending group 2 312 damage
 367 Immune System group 2 would deal defending group 2 81345 damage
 368
 369 Infection group 2 attacks defending group 2, killing 0 units
 370 Immune System group 2 attacks defending group 2, killing 13 units
 371 </code></pre>
 372 <pre><code>Immune System:
 373 Group 2 contains 51 units
 374 Infection:
 375 No groups remain.
 376 </code></pre>
 377 <p>This boost would allow the immune system's armies to win! It would be left with <code><em>51</em></code> units.</p>
 378 <p>You don't even know <em>how</em> you could boost the reindeer's immune system or what effect it might have, so you need to be cautious and find the <em>smallest boost</em> that would allow the immune system to win.</p>
 379 <p><em>How many units does the immune system have left</em> after getting the smallest boost it needs to win?</p>
 380 </article>
 381 <p>Your puzzle answer was <code>1045</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 382 <p>At this point, you should <a href="/2018">return to your Advent calendar</a> and try another puzzle.</p>
 383 <p>If you still want to see it, you can <a href="24/input" target="_blank">get your puzzle input</a>.</p>
 384 <p>You can also <span class="share">[Share<span class="share-content">on
 385   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Immune+System+Simulator+20XX%22+%2D+Day+24+%2D+Advent+of+Code+2018&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F24&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 386   <a href="http://www.reddit.com/submit?url=https%3A%2F%2Fadventofcode%2Ecom%2F2018%2Fday%2F24&amp;title=I%27ve+completed+%22Immune+System+Simulator+20XX%22+%2D+Day+24+%2D+Advent+of+Code+2018" target="_blank">Reddit</a
 387 ></span>]</span> this puzzle.</p>
 388 </main>
 389
 390 <!-- ga -->
 391 <script>
 392 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 393 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 394 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 395 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 396 ga('create', 'UA-69522494-1', 'auto');
 397 ga('set', 'anonymizeIp', true);
 398 ga('send', 'pageview');
 399 </script>
 400 <!-- /ga -->
 401 </body>
 402 </html>