problems/day06.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 6 - 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?11"/>
   9 <link rel="shortcut icon" href="/favicon.ico?2"/>
  10 </head><!--
  11
  12
  13
  14
  15 Oh, hello!  Funny seeing you here.
  16
  17 I appreciate your enthusiasm, but you aren't going to find much down here.
  18 There certainly aren't clues to any of the puzzles.  The best surprises don't
  19 even appear in the source until you unlock them for real.
  20
  21 Please be careful with automated requests; I'm not Google, and I can only take
  22 so much traffic.  Please be considerate so that everyone gets to play.
  23
  24 If you're curious about how Advent of Code works, it's running on some custom
  25 Perl code. Other than a few integrations (auth, analytics, ads, social media),
  26 I built the whole thing myself, including the design, animations, prose, and
  27 all of the puzzles.
  28
  29 The puzzles probably took the longest; the easiest ones took an hour or two
  30 each, but the harder ones took 4-5 hours, and a few even longer than that. A
  31 lot of effort went into building this thing - I hope you're enjoying playing it
  32 as much as I enjoyed making it for you!
  33
  34 If you'd like to hang out, I'm @ericwastl on Twitter.
  35
  36 - Eric Wastl
  37
  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 <body>
  89 <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">12*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">$year=</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>
  90
  91 <div id="sidebar">
  92 <div id="sponsor"><div class="quiet">Our <a href="/2017/sponsors">sponsors</a> help make Advent of Code possible:</div><p><a href="http://www.novetta.com/careers?utm_campaign=Advent%20of%20Code%202017&amp;utm_source=www.adventofcode.com&amp;utm_medium=ad" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Novetta</a> - Unleash your imagination. Innovate at Novetta.</p></div>
  93 <div id="ad">
  94 <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
  95 <!-- Advent of Code Wide Skyscraper -->
  96 <ins class="adsbygoogle"
  97      style="display:inline-block;width:160px;height:600px"
  98      data-ad-client="ca-pub-9420604735624631"
  99      data-ad-slot="8014013294"></ins>
 100 <script>
 101 (adsbygoogle = window.adsbygoogle || []).push({});
 102 </script>
 103 </div><!--/ad-->
 104 </div><!--/sidebar-->
 105
 106 <main>
 107 <article class="day-desc"><h2>--- Day 6: Memory Reallocation ---</h2><p>A debugger program here is having an issue: it is trying to repair a memory reallocation routine, but it keeps getting stuck in an infinite loop.</p>
 108 <p>In this area, there are <span title="There are also five currency banks, two river banks, three airplanes banking, a banked billards shot, and a left bank.">sixteen memory banks</span>; each memory bank can hold any number of <em>blocks</em>. The goal of the reallocation routine is to balance the blocks between the memory banks.</p>
 109 <p>The reallocation routine operates in cycles. In each cycle, it finds the memory bank with the most blocks (ties won by the lowest-numbered memory bank) and redistributes those blocks among the banks. To do this, it removes all of the blocks from the selected bank, then moves to the next (by index) memory bank and inserts one of the blocks. It continues doing this until it runs out of blocks; if it reaches the last memory bank, it wraps around to the first one.</p>
 110 <p>The debugger would like to know how many redistributions can be done before a blocks-in-banks configuration is produced that <em>has been seen before</em>.</p>
 111 <p>For example, imagine a scenario with only four memory banks:</p>
 112 <ul>
 113 <li>The banks start with <code>0</code>, <code>2</code>, <code>7</code>, and <code>0</code> blocks. The third bank has the most blocks, so it is chosen for redistribution.</li>
 114 <li>Starting with the next bank (the fourth bank) and then continuing to the first bank, the second bank, and so on, the <code>7</code> blocks are spread out over the memory banks. The fourth, first, and second banks get two blocks each, and the third bank gets one back. The final result looks like this: <code>2 4 1 2</code>.</li>
 115 <li>Next, the second bank is chosen because it contains the most blocks (four). Because there are four memory banks, each gets one block. The result is: <code>3 1 2 3</code>.</li>
 116 <li>Now, there is a tie between the first and fourth memory banks, both of which have three blocks. The first bank wins the tie, and its three blocks are distributed evenly over the other three banks, leaving it with none: <code>0 2 3 4</code>.</li>
 117 <li>The fourth bank is chosen, and its four blocks are distributed such that each of the four banks receives one: <code>1 3 4 1</code>.</li>
 118 <li>The third bank is chosen, and the same thing happens: <code>2 4 1 2</code>.</li>
 119 </ul>
 120 <p>At this point, we've reached a state we've seen before: <code>2 4 1 2</code> was already seen. The infinite loop is detected after the fifth block redistribution cycle, and so the answer in this example is <code>5</code>.</p>
 121 <p>Given the initial block counts in your puzzle input, <em>how many redistribution cycles</em> must be completed before a configuration is produced that has been seen before?</p>
 122 </article>
 123 <p>Your puzzle answer was <code>7864</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>Out of curiosity, the debugger would also like to know the size of the loop: starting from a state that has already been seen, how many block redistribution cycles must be performed before that same state is seen again?</p>
 124 <p>In the example above, <code>2 4 1 2</code> is seen again after four cycles, and so the answer in that example would be <code>4</code>.</p>
 125 <p><em>How many cycles</em> are in the infinite loop that arises from the configuration in your puzzle input?</p>
 126 </article>
 127 <p>Your puzzle answer was <code>1695</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 128 <p>At this point, you should <a href="/2017">return to your advent calendar</a> and try another puzzle.</p>
 129 <p>If you still want to see it, you can <a href="6/input" target="_blank">get your puzzle input</a>.</p>
 130 <p>You can also <span class="share">[Share<span class="share-content">on
 131   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Memory+Reallocation%22+%2D+Day+6+%2D+Advent+of+Code+2017&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F6&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 132   <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F6" target="_blank">Google+</a>
 133   <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F6&amp;title=I%27ve+completed+%22Memory+Reallocation%22+%2D+Day+6+%2D+Advent+of+Code+2017" target="_blank">Reddit</a
 134 ></span>]</span> this puzzle.</p>
 135 </main>
 136
 137 <!-- ga -->
 138 <script>
 139 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 140 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 141 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 142 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 143 ga('create', 'UA-69522494-1', 'auto');
 144 ga('send', 'pageview');
 145 </script>
 146 <!-- /ga -->
 147 </body>
 148 </html>