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 2019</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="/2019/about">[About]</a></li><li><a href="/2019/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2019/settings">[Settings]</a></li><li><a href="/2019/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2019/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">0x0000|</span><a href="/2019">2019</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2019">[Calendar]</a></li><li><a href="/2019/support">[AoC++]</a></li><li><a href="/2019/sponsors">[Sponsors]</a></li><li><a href="/2019/leaderboard">[Leaderboard]</a></li><li><a href="/2019/stats">[Stats]</a></li></ul></nav></div></header>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2019/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://www.twilio.com/quest" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">TwilioQuest</a> - Play Advent of Code and earn rad loot in TwilioQuest, a developer RPG for Mac, Windows, and Linux. Learn JavaScript, Python, git, APIs for SMS, VoIP, or WhatsApp, and much more.</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 24: Planet of Discord ---</h2><p>You land on <a href="https://en.wikipedia.org/wiki/Eris_(dwarf_planet)">Eris</a>, your last stop before reaching Santa.  As soon as you do, your sensors start picking up strange life forms moving around: Eris is infested with <a href="https://www.nationalgeographic.org/thisday/sep9/worlds-first-computer-bug/">bugs</a>! With an <span title="For a sad version of this story, look up Voices of a Distant Star.">over 24-hour roundtrip</span> for messages between you and Earth, you'll have to deal with this problem on your own.</p>
  99 <p>Eris isn't a very large place; a scan of the entire area fits into a 5x5 grid (your puzzle input). The scan shows <em>bugs</em> (<code>#</code>) and <em>empty spaces</em> (<code>.</code>).</p>
 100 <p>Each <em>minute</em>, The bugs live and die based on the number of bugs in the <em>four adjacent tiles</em>:</p>
 101 <ul>
 102 <li>A bug <em>dies</em> (becoming an empty space) unless there is <em>exactly one</em> bug adjacent to it.</li>
 103 <li>An empty space <em>becomes infested</em> with a bug if <em>exactly one or two</em> bugs are adjacent to it.</li>
 104 </ul>
 105 <p>Otherwise, a bug or empty space remains the same.  (Tiles on the edges of the grid have fewer than four adjacent tiles; the missing tiles count as empty space.) This process happens in every location <em>simultaneously</em>; that is, within the same minute, the number of adjacent bugs is counted for every tile first, and then the tiles are updated.</p>
 106 <p>Here are the first few minutes of an example scenario:</p>
 107 <pre><code>Initial state:
 108 ....#
 109 #..#.
 110 #..##
 111 ..#..
 112 #....
 113
 114 After 1 minute:
 115 #..#.
 116 ####.
 117 ###.#
 118 ##.##
 119 .##..
 120
 121 After 2 minutes:
 122 #####
 123 ....#
 124 ....#
 125 ...#.
 126 #.###
 127
 128 After 3 minutes:
 129 #....
 130 ####.
 131 ...##
 132 #.##.
 133 .##.#
 134
 135 After 4 minutes:
 136 ####.
 137 ....#
 138 ##..#
 139 .....
 140 ##...
 141 </code></pre>
 142 <p>To understand the nature of the bugs, watch for the first time a layout of bugs and empty spaces <em>matches any previous layout</em>. In the example above, the first layout to appear twice is:</p>
 143 <pre><code>.....
 144 .....
 145 .....
 146 #....
 147 .#...
 148 </code></pre>
 149 <p>To calculate the <em>biodiversity rating</em> for this layout, consider each tile left-to-right in the top row, then left-to-right in the second row, and so on. Each of these tiles is worth biodiversity points equal to <em>increasing powers of two</em>: 1, 2, 4, 8, 16, 32, and so on.  Add up the biodiversity points for tiles with bugs; in this example, the 16th tile (<code>32768</code> points) and 22nd tile (<code>2097152</code> points) have bugs, a total biodiversity rating of <code><em>2129920</em></code>.</p>
 150 <p><em>What is the biodiversity rating for the first layout that appears twice?</em></p>
 151 </article>
 152 <p>Your puzzle answer was <code>17863711</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>After careful analysis, one thing is certain: <em>you have no idea where all these bugs are coming from</em>.</p>
 153 <p>Then, you remember: Eris is an old <a href="20">Plutonian</a> settlement! Clearly, the bugs are coming from recursively-folded space.</p>
 154 <p>This 5x5 grid is <em>only one</em> level in an <em>infinite</em> number of recursion levels. The tile in the middle of the grid is actually another 5x5 grid, the grid in your scan is contained as the middle tile of a larger 5x5 grid, and so on. Two levels of grids look like this:</p>
 155 <pre><code>     |     |         |     |
 156      |     |         |     |
 157      |     |         |     |
 158 -----+-----+---------+-----+-----
 159      |     |         |     |
 160      |     |         |     |
 161      |     |         |     |
 162 -----+-----+---------+-----+-----
 163      |     | | | | | |     |
 164      |     |-+-+-+-+-|     |
 165      |     | | | | | |     |
 166      |     |-+-+-+-+-|     |
 167      |     | | |?| | |     |
 168      |     |-+-+-+-+-|     |
 169      |     | | | | | |     |
 170      |     |-+-+-+-+-|     |
 171      |     | | | | | |     |
 172 -----+-----+---------+-----+-----
 173      |     |         |     |
 174      |     |         |     |
 175      |     |         |     |
 176 -----+-----+---------+-----+-----
 177      |     |         |     |
 178      |     |         |     |
 179      |     |         |     |
 180 </code></pre>
 181 <p>(To save space, some of the tiles are not drawn to scale.)  Remember, this is only a small part of the infinitely recursive grid; there is a 5x5 grid that contains this diagram, and a 5x5 grid that contains that one, and so on.  Also, the <code>?</code> in the diagram contains another 5x5 grid, which itself contains another 5x5 grid, and so on.</p>
 182 <p>The scan you took (your puzzle input) shows where the bugs are <em>on a single level</em> of this structure. The middle tile of your scan is empty to accommodate the recursive grids within it. Initially, no other levels contain bugs.</p>
 183 <p>Tiles still count as <em>adjacent</em> if they are directly <em>up, down, left, or right</em> of a given tile. Some tiles have adjacent tiles at a recursion level above or below its own level. For example:</p>
 184 <pre><code>     |     |         |     |
 185   1  |  2  |    3    |  4  |  5
 186      |     |         |     |
 187 -----+-----+---------+-----+-----
 188      |     |         |     |
 189   6  |  7  |    8    |  9  |  10
 190      |     |         |     |
 191 -----+-----+---------+-----+-----
 192      |     |A|B|C|D|E|     |
 193      |     |-+-+-+-+-|     |
 194      |     |F|G|H|I|J|     |
 195      |     |-+-+-+-+-|     |
 196  11  | 12  |K|L|?|N|O|  14 |  15
 197      |     |-+-+-+-+-|     |
 198      |     |P|Q|R|S|T|     |
 199      |     |-+-+-+-+-|     |
 200      |     |U|V|W|X|Y|     |
 201 -----+-----+---------+-----+-----
 202      |     |         |     |
 203  16  | 17  |    18   |  19 |  20
 204      |     |         |     |
 205 -----+-----+---------+-----+-----
 206      |     |         |     |
 207  21  | 22  |    23   |  24 |  25
 208      |     |         |     |
 209 </code></pre>
 210 <ul>
 211 <li>Tile 19 has four adjacent tiles: 14, 18, 20, and 24.</li>
 212 <li>Tile G has four adjacent tiles: B, F, H, and L.</li>
 213 <li>Tile D has four adjacent tiles: 8, C, E, and I.</li>
 214 <li>Tile E has four adjacent tiles: 8, D, 14, and J.</li>
 215 <li>Tile 14 has <em>eight</em> adjacent tiles: 9, E, J, O, T, Y, 15, and 19.</li>
 216 <li>Tile N has <em>eight</em> adjacent tiles: I, O, S, and five tiles within the sub-grid marked <code>?</code>.</li>
 217 </ul>
 218 <p>The rules about bugs living and dying are the same as before.</p>
 219 <p>For example, consider the same initial state as above:</p>
 220 <pre><code>....#
 221 #..#.
 222 #.?##
 223 ..#..
 224 #....
 225 </code></pre>
 226 <p>The center tile is drawn as <code>?</code> to indicate the next recursive grid. Call this level 0; the grid within this one is level 1, and the grid that contains this one is level -1.  Then, after <em>ten</em> minutes, the grid at each level would look like this:</p>
 227 <pre><code>Depth -5:
 228 ..#..
 229 .#.#.
 230 ..?.#
 231 .#.#.
 232 ..#..
 233
 234 Depth -4:
 235 ...#.
 236 ...##
 237 ..?..
 238 ...##
 239 ...#.
 240
 241 Depth -3:
 242 #.#..
 243 .#...
 244 ..?..
 245 .#...
 246 #.#..
 247
 248 Depth -2:
 249 .#.##
 250 ....#
 251 ..?.#
 252 ...##
 253 .###.
 254
 255 Depth -1:
 256 #..##
 257 ...##
 258 ..?..
 259 ...#.
 260 .####
 261
 262 Depth 0:
 263 .#...
 264 .#.##
 265 .#?..
 266 .....
 267 .....
 268
 269 Depth 1:
 270 .##..
 271 #..##
 272 ..?.#
 273 ##.##
 274 #####
 275
 276 Depth 2:
 277 ###..
 278 ##.#.
 279 #.?..
 280 .#.##
 281 #.#..
 282
 283 Depth 3:
 284 ..###
 285 .....
 286 #.?..
 287 #....
 288 #...#
 289
 290 Depth 4:
 291 .###.
 292 #..#.
 293 #.?..
 294 ##.#.
 295 .....
 296
 297 Depth 5:
 298 ####.
 299 #..#.
 300 #.?#.
 301 ####.
 302 .....
 303 </code></pre>
 304 <p>In this example, after 10 minutes, a total of <code><em>99</em></code> bugs are present.</p>
 305 <p>Starting with your scan, <em>how many bugs are present after 200 minutes?</em></p>
 306 </article>
 307 <p>Your puzzle answer was <code>1937</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 308 <p>At this point, you should <a href="/2019">return to your Advent calendar</a> and try another puzzle.</p>
 309 <p>If you still want to see it, you can <a href="24/input" target="_blank">get your puzzle input</a>.</p>
 310 <p>You can also <span class="share">[Share<span class="share-content">on
 311   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Planet+of+Discord%22+%2D+Day+24+%2D+Advent+of+Code+2019&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F24&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 312   <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+%22Planet+of+Discord%22+%2D+Day+24+%2D+Advent+of+Code+2019+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2019%2Fday%2F24'}else{return false;}" target="_blank">Mastodon</a
 313 ></span>]</span> this puzzle.</p>
 314 </main>
 315
 316 <!-- ga -->
 317 <script>
 318 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 319 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 320 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 321 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 322 ga('create', 'UA-69522494-1', 'auto');
 323 ga('set', 'anonymizeIp', true);
 324 ga('send', 'pageview');
 325 </script>
 326 <!-- /ga -->
 327 </body>
 328 </html>