problems/day14.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 14 - 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?12"/>
   9 <link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
  10 <link rel="shortcut icon" href="/favicon.ico?2"/>
  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 probably took the longest; the easiest ones took an hour or two
  31 each, but the harder ones took 4-5 hours, and a few even longer than that. A
  32 lot of effort went into building this thing - I hope you're enjoying playing it
  33 as much as I 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="/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">30*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">sub y{</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>
  91
  92 <div id="sidebar">
  93 <div id="sponsor"><div class="quiet">Our <a href="/2017/sponsors">sponsors</a> help make Advent of Code possible:</div><p><a href="http://winton.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Winton</a> - a data science and investment management company</p></div>
  94 <div id="ad">
  95 <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
  96 <!-- Advent of Code Wide Skyscraper -->
  97 <ins class="adsbygoogle"
  98      style="display:inline-block;width:160px;height:600px"
  99      data-ad-client="ca-pub-9420604735624631"
 100      data-ad-slot="8014013294"></ins>
 101 <script>
 102 (adsbygoogle = window.adsbygoogle || []).push({});
 103 </script>
 104 </div><!--/ad-->
 105 </div><!--/sidebar-->
 106
 107 <main>
 108 <article class="day-desc"><h2>--- Day 14: Disk Defragmentation ---</h2><p>Suddenly, a scheduled job activates the system's <a href="https://en.wikipedia.org/wiki/Defragmentation">disk defragmenter</a>. Were the situation different, you might <a href="https://www.youtube.com/watch?v=kPv1gQ5Rs8A&t=37">sit and watch it for a while</a>, but today, you just don't have that kind of time. It's soaking up valuable system resources that are needed elsewhere, and so the only option is to help it finish its task as soon as possible.</p>
 109 <p>The disk in question consists of a 128x128 grid; each square of the grid is either <em>free</em> or <em>used</em>. On this disk, the state of the grid is tracked by the bits in a sequence of <a href="10">knot hashes</a>.</p>
 110 <p>A total of 128 knot hashes are calculated, each corresponding to a single row in the grid; each hash contains 128 bits which correspond to individual grid squares. Each bit of a hash indicates whether that square is <em>free</em> (<code>0</code>) or <em>used</em> (<code>1</code>).</p>
 111 <p>The hash inputs are a key string (your puzzle input), a dash, and a number from <code>0</code> to <code>127</code> corresponding to the row.  For example, if your key string were <code>flqrgnkx</code>, then the first row would be given by the bits of the knot hash of <code>flqrgnkx-0</code>, the second row from the bits of the knot hash of <code>flqrgnkx-1</code>, and so on until the last row, <code>flqrgnkx-127</code>.</p>
 112 <p>The output of a knot hash is traditionally represented by 32 hexadecimal digits; each of these digits correspond to 4 bits, for a total of <code>4 * 32 = 128</code> bits. To convert to bits, turn each hexadecimal digit to its equivalent binary value, high-bit first: <code>0</code> becomes <code>0000</code>, <code>1</code> becomes <code>0001</code>, <code>e</code> becomes <code>1110</code>, <code>f</code> becomes <code>1111</code>, and so on; a hash that begins with <code>a0c2017...</code> in hexadecimal would begin with <code>10100000110000100000000101110000...</code> in binary.</p>
 113 <p>Continuing this process, the <em>first 8 rows and columns</em> for key <code>flqrgnkx</code> appear as follows, using <code>#</code> to denote used squares, and <code>.</code> to denote free ones:</p>
 114 <pre><code>##.#.#..-->
 115 .#.#.#.#
 116 ....#.#.
 117 #.#.##.#
 118 .##.#...
 119 ##..#..#
 120 .#...#..
 121 ##.#.##.-->
 122 |      |
 123 V      V
 124 </code></pre>
 125 <p>In this example, <code>8108</code> squares are used across the entire 128x128 grid.</p>
 126 <p>Given your actual key string, <em>how many squares are used</em>?</p>
 127 </article>
 128 <p>Your puzzle answer was <code>8204</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>Now, <span title="This is exactly how it works in real life.">all the defragmenter needs to know</span> is the number of <em>regions</em>. A region is a group of <em>used</em> squares that are all <em>adjacent</em>, not including diagonals. Every used square is in exactly one region: lone used squares form their own isolated regions, while several adjacent squares all count as a single region.</p>
 129 <p>In the example above, the following nine regions are visible, each marked with a distinct digit:</p>
 130 <pre><code>11.2.3..-->
 131 .1.2.3.4
 132 ....5.6.
 133 7.8.55.9
 134 .88.5...
 135 88..5..8
 136 .8...8..
 137 88.8.88.-->
 138 |      |
 139 V      V
 140 </code></pre>
 141 <p>Of particular interest is the region marked <code>8</code>; while it does not appear contiguous in this small view, all of the squares marked <code>8</code> are connected when considering the whole 128x128 grid. In total, in this example, <code>1242</code> regions are present.</p>
 142 <p><em>How many regions</em> are present given your key string?</p>
 143 </article>
 144 <p>Your puzzle answer was <code>1089</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 145 <p>At this point, you should <a href="/2017">return to your advent calendar</a> and try another puzzle.</p>
 146 <p>Your puzzle input was <code class="puzzle-input">xlqgujun</code>.</p>
 147 <p>You can also <span class="share">[Share<span class="share-content">on
 148   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Disk+Defragmentation%22+%2D+Day+14+%2D+Advent+of+Code+2017&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F14&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 149   <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F14" target="_blank">Google+</a>
 150   <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F14&amp;title=I%27ve+completed+%22Disk+Defragmentation%22+%2D+Day+14+%2D+Advent+of+Code+2017" target="_blank">Reddit</a
 151 ></span>]</span> this puzzle.</p>
 152 </main>
 153
 154 <!-- ga -->
 155 <script>
 156 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 157 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 158 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 159 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 160 ga('create', 'UA-69522494-1', 'auto');
 161 ga('send', 'pageview');
 162 </script>
 163 <!-- /ga -->
 164 </body>
 165 </html>