problems/day25-completed.html

   1 <!DOCTYPE html>
   2 <html lang="en-us">
   3 <head>
   4 <meta charset="utf-8"/>
   5 <title>Day 25 - 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">49*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;<span class="title-event-wrap">0.0.0.0:</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://xebia.com/community/advent-of-code" target="_blank" onclick="if(ga)ga('send','event','sponsor','click',this.href);" rel="noopener">Xebia</a> - Passionate consultants taking up IT challenges all year round</p></div>
  94 <p class="quiet">By popular demand, there are now AoC-themed objects available (until Jan. 3rd)! Get them shipped <a href="https://teespring.com/advent-of-code" target="_blank">from the US</a> or <a href="https://teespring.com/advent-of-code-eu" target="_blank">from Europe</a>.</p>
  95
  96 </div><!--/sidebar-->
  97
  98 <main>
  99 <article class="day-desc"><h2>--- Day 25: The Halting Problem ---</h2><p>Following the twisty passageways deeper and deeper into the CPU, you finally reach the <span title="Get it? CPU core?">core</span> of the computer. Here, in the expansive central chamber, you find a grand apparatus that fills the entire room, suspended nanometers above your head.</p>
 100 <p>You had always imagined CPUs to be noisy, chaotic places, bustling with activity. Instead, the room is quiet, motionless, and dark.</p>
 101 <p>Suddenly, you and the CPU's <em>garbage collector</em> startle each other. "It's not often we get  many visitors here!", he says. You inquire about the stopped machinery.</p>
 102 <p>"It stopped milliseconds ago; not sure why. I'm a garbage collector, not a doctor." You ask what the machine is for.</p>
 103 <p>"Programs these days, don't know their origins. That's the <em>Turing machine</em>! It's what makes the whole computer work." You try to explain that Turing machines are merely models of computation, but he cuts you off. "No, see, that's just what they <em>want</em> you to think. Ultimately, inside every CPU, there's a Turing machine driving the whole thing! Too bad this one's broken. <a href="https://www.youtube.com/watch?v=cTwZZz0HV8I">We're doomed!</a>"</p>
 104 <p>You ask how you can help. "Well, unfortunately, the only way to get the computer running again would be to create a whole new Turing machine from scratch, but there's no <em>way</em> you can-" He notices the look on your face, gives you a curious glance, shrugs, and goes back to sweeping the floor.</p>
 105 <p>You find the <em>Turing machine blueprints</em> (your puzzle input) on a tablet in a nearby pile of debris. Looking back up at the broken Turing machine above, you can start to identify its parts:</p>
 106 <ul>
 107 <li>A <em>tape</em> which contains <code>0</code> repeated infinitely to the left and right.</li>
 108 <li>A <em>cursor</em>, which can move left or right along the tape and read or write values at its current position.</li>
 109 <li>A set of <em>states</em>, each containing rules about what to do based on the current value under the cursor.</li>
 110 </ul>
 111 <p>Each slot on the tape has two possible values: <code>0</code> (the starting value for all slots) and <code>1</code>. Based on whether the cursor is pointing at a <code>0</code> or a <code>1</code>, the current state says <em>what value to write</em> at the current position of the cursor, whether to <em>move the cursor</em> left or right one slot, and <em>which state to use next</em>.</p>
 112 <p>For example, suppose you found the following blueprint:</p>
 113 <pre><code>Begin in state A.
 114 Perform a diagnostic checksum after 6 steps.
 115
 116 In state A:
 117   If the current value is 0:
 118     - Write the value 1.
 119     - Move one slot to the right.
 120     - Continue with state B.
 121   If the current value is 1:
 122     - Write the value 0.
 123     - Move one slot to the left.
 124     - Continue with state B.
 125
 126 In state B:
 127   If the current value is 0:
 128     - Write the value 1.
 129     - Move one slot to the left.
 130     - Continue with state A.
 131   If the current value is 1:
 132     - Write the value 1.
 133     - Move one slot to the right.
 134     - Continue with state A.
 135 </code></pre>
 136 <p>Running it until the number of steps required to take the listed <em>diagnostic checksum</em> would result in the following tape configurations (with the <em>cursor</em> marked in square brackets):</p>
 137 <pre><code>... 0  0  0 [0] 0  0 ... (before any steps; about to run state A)
 138 ... 0  0  0  1 [0] 0 ... (after 1 step;     about to run state B)
 139 ... 0  0  0 [1] 1  0 ... (after 2 steps;    about to run state A)
 140 ... 0  0 [0] 0  1  0 ... (after 3 steps;    about to run state B)
 141 ... 0 [0] 1  0  1  0 ... (after 4 steps;    about to run state A)
 142 ... 0  1 [1] 0  1  0 ... (after 5 steps;    about to run state B)
 143 ... 0  1  1 [0] 1  0 ... (after 6 steps;    about to run state A)
 144 </code></pre>
 145 <p>The CPU can confirm that the Turing machine is working by taking a <em>diagnostic checksum</em> after a specific number of steps (given in the blueprint). Once the specified number of steps have been executed, the Turing machine should pause; once it does, count the number of times <code>1</code> appears on the tape. In the above example, the <em>diagnostic checksum</em> is <em><code>3</code></em>.</p>
 146 <p>Recreate the Turing machine and save the computer! <em>What is the diagnostic checksum</em> it produces once it's working again?</p>
 147 </article>
 148 <p>Your puzzle answer was <code>2846</code>.</p><p class="day-success">The first half of this puzzle is complete! It provides one gold star: *</p>
 149 <article class="day-desc"><h2>--- Part Two ---</h2><p>The Turing machine, and soon the entire computer, springs back to life.  A console glows dimly nearby, awaiting your command.</p>
 150 <pre><code>&gt; reboot printer
 151 Error: That command requires <em>priority 50</em>. You currently have <em>priority 0</em>.
 152 You must deposit <em class="star">50 stars</em> to increase your priority to the required level.
 153 </code></pre>
 154 <p>The console flickers for a moment, and then prints another message:</p>
 155 <pre><code><em class="star">Star</em> accepted.
 156 You must deposit <em class="star">49 stars</em> to increase your priority to the required level.
 157 </code></pre>
 158 <p>The <em>garbage collector</em> winks at you, then continues sweeping.</p>
 159 </article>
 160 <form method="post" action="25/answer"><input type="hidden" name="level" value="2"/><input type="hidden" name="answer" value="0"/><p>You have enough stars to <input type="submit" value="[Reboot the Printer]"/>.</p></form>
 161 <p>You can also <span class="share">[Share<span class="share-content">on
 162   <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+Part+One+of+%22The+Halting+Problem%22+%2D+Day+25+%2D+Advent+of+Code+2017&amp;url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F25&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
 163   <a href="https://plus.google.com/share?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F25" target="_blank">Google+</a>
 164   <a href="http://www.reddit.com/submit?url=http%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F25&amp;title=I%27ve+completed+Part+One+of+%22The+Halting+Problem%22+%2D+Day+25+%2D+Advent+of+Code+2017" target="_blank">Reddit</a
 165 ></span>]</span> this puzzle.</p>
 166 </main>
 167
 168 <!-- ga -->
 169 <script>
 170 (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
 171 (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
 172 m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
 173 })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
 174 ga('create', 'UA-69522494-1', 'auto');
 175 ga('send', 'pageview');
 176 </script>
 177 <!-- /ga -->
 178 </body>
 179 </html>