day16.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 16 - Advent of Code 2016</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?9"/>
   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 were around 45 minutes
  30 each, but the harder ones took 2-3 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="/2016/about">[About]</a></li><li><a href="/2016/support">[AoC++]</a></li><li><a href="/2016/events">[Events]</a></li><li><a href="/2016/settings">[Settings]</a></li><li><a href="/2016/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <span class="supporter">(AoC++)</span> <span class="star-count">32*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">int y=</span><a href="/2016">2016</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2016">[Calendar]</a></li><li><a href="/2016/leaderboard">[Leaderboard]</a></li><li><a href="/2016/stats">[Stats]</a></li><li><a href="/2016/sponsors">[Sponsors]</a></li></ul></nav></div></header>
  90
  91 <div id="sidebar">
  92 <div id="sponsor"><div class="quiet">Our <a href="/2016/sponsors">sponsors</a> help make AoC possible:</div><p><a href="http://www.aandkrentals.net/" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);">A&amp;K Rentals</a> - Affordable, high-quality homes just north of Kansas City.</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 16: Dragon Checksum ---</h2><p>You're done scanning this part of the network, but you've left traces of your presence. You need to <span title="If I ever find one of my disks overwritten with a dragon curve, I'll know it was you.">overwrite some disks</span> with random-looking data to cover your tracks and update the local security system with a new checksum for those disks.</p>
 108 <p>For the data to not be suspiscious, it needs to have certain properties; purely random data will be detected as tampering. To generate appropriate random data, you'll need to use a modified <a href="https://en.wikipedia.org/wiki/Dragon_curve">dragon curve</a>.</p>
 109 <p>Start with an appropriate initial state (your puzzle input). Then, so long as you don't have enough data yet to fill the disk, repeat the following steps:</p>
 110 <ul>
 111 <li>Call the data you have at this point "a".</li>
 112 <li>Make a copy of "a"; call this copy "b".</li>
 113 <li>Reverse the order of the characters in "b".</li>
 114 <li>In "b", replace all instances of <code>0</code> with <code>1</code> and all <code>1</code>s with <code>0</code>.</li>
 115 <li>The resulting data is "a", then a single <code>0</code>, then "b".</li>
 116 </ul>
 117 <p>For example, after a single step of this process,</p>
 118 <ul>
 119 <li><code>1</code> becomes <code>100</code>.</li>
 120 <li><code>0</code> becomes <code>001</code>.</li>
 121 <li><code>11111</code> becomes <code>11111000000</code>.</li>
 122 <li><code>111100001010</code> becomes <code>1111000010100101011110000</code>.</li>
 123 </ul>
 124 <p>Repeat these steps until you have enough data to fill the desired disk.</p>
 125 <p>Once the data has been generated, you also need to create a checksum of that data. Calculate the checksum <em>only</em> for the data that fits on the disk, even if you generated more data than that in the previous step.</p>
 126 <p>The checksum for some given data is created by considering each non-overlapping <em>pair</em> of characters in the input data.  If the two characters match (<code>00</code> or <code>11</code>), the next checksum character is a <code>1</code>.  If the characters do not match (<code>01</code> or <code>10</code>), the next checksum character is a <code>0</code>. This should produce a new string which is exactly half as long as the original. If the length of the checksum is <em>even</em>, repeat the process until you end up with a checksum with an <em>odd</em> length.</p>
 127 <p>For example, suppose we want to fill a disk of length <code>12</code>, and when we finally generate a string of at least length <code>12</code>, the first <code>12</code> characters are <code>110010110100</code>. To generate its checksum:</p>
 128 <ul>
 129 <li>Consider each pair: <code>11</code>, <code>00</code>, <code>10</code>, <code>11</code>, <code>01</code>, <code>00</code>.</li>
 130 <li>These are same, same, different, same, different, same, producing <code>110101</code>.</li>
 131 <li>The resulting string has length <code>6</code>, which is <em>even</em>, so we repeat the process.</li>
 132 <li>The pairs are <code>11</code> (same), <code>01</code> (different), <code>01</code> (different).</li>
 133 <li>This produces the checksum <code>100</code>, which has an <em>odd</em> length, so we stop.</li>
 134 </ul>
 135 <p>Therefore, the checksum for <code>110010110100</code> is <code>100</code>.</p>
 136 <p>Combining all of these steps together, suppose you want to fill a disk of length <code>20</code> using an initial state of <code>10000</code>:</p>
 137 <ul>
 138 <li>Because <code>10000</code> is too short, we first use the modified dragon curve to make it longer.</li>
 139 <li>After one round, it becomes <code>10000011110</code> (<code>11</code> characters), still too short.</li>
 140 <li>After two rounds, it becomes <code>10000011110010000111110</code> (<code>23</code> characters), which is enough.</li>
 141 <li>Since we only need <code>20</code>, but we have <code>23</code>, we get rid of all but the first <code>20</code> characters: <code>10000011110010000111</code>.</li>
 142 <li>Next, we start calculating the checksum; after one round, we have <code>0111110101</code>, which <code>10</code> characters long (<em>even</em>), so we continue.</li>
 143 <li>After two rounds, we have <code>01100</code>, which is <code>5</code> characters long (<em>odd</em>), so we are done.</li>
 144 </ul>
 145 <p>In this example, the correct checksum would therefore be <code>01100</code>.</p>
 146 <p>The first disk you have to fill has length <code>272</code>. Using the initial state in your puzzle input, <em>what is the correct checksum</em>?</p>
 147 </article>
 148 <p>Your puzzle answer was <code>10100011010101011</code>.</p><article class="day-desc"><h2>--- Part Two ---</h2><p>The second disk you have to fill has length <code>35651584</code>. Again using the initial state in your puzzle input, <em>what is the correct checksum</em> for this disk?</p>
 149 </article>
 150 <p>Your puzzle answer was <code>01010001101011001</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
 151 <p>At this point, you should <a href="/2016">return to your advent calendar</a> and try another puzzle.</p>
 152 <p>Your puzzle input was <code class="puzzle-input">11100010111110100</code>.</p>
 153 <p>You can also <span class="share">[Share<span class="share-content">on
 154   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Dragon+Checksum%22+%2D+Day+16+%2D+Advent+of+Code+2016&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F16&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 155   <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F16" target="_blank">Google+</a>
 156   <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2016%2Fday%2F16&amp;title=I%27ve+completed+%22Dragon+Checksum%22+%2D+Day+16+%2D+Advent+of+Code+2016" target="_blank">Reddit</a
 157 ></span>]</span> this puzzle.</p>
 158 </main>
 159
 160 <!-- ga -->
 161 <script>
 162 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 163 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 164 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 165 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 166 ga('create', 'UA-69522494-1', 'auto');
 167 ga('send', 'pageview');
 168 </script>
 169 <!-- /ga -->
 170 </body>
 171 </html>