-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathyear2017_day25_puzzle.html
165 lines (100 loc) · 7.76 KB
/
year2017_day25_puzzle.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
<!DOCTYPE html>
<html lang="en-us">
<head>
<meta charset="utf-8"/>
<title>Day 25 - Advent of Code 2017</title>
<link rel="stylesheet" type="text/css" href="/static/style.css?31"/>
<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?1" title="High Contrast"/>
<link rel="shortcut icon" href="/favicon.png"/>
<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>
</head><!--
Oh, hello! Funny seeing you here.
I appreciate your enthusiasm, but you aren't going to find much down here.
There certainly aren't clues to any of the puzzles. The best surprises don't
even appear in the source until you unlock them for real.
Please be careful with automated requests; I'm not a massive company, and I can
only take so much traffic. Please be considerate so that everyone gets to play.
If you're curious about how Advent of Code works, it's running on some custom
Perl code. Other than a few integrations (auth, analytics, social media), I
built the whole thing myself, including the design, animations, prose, and all
of the puzzles.
The puzzles are most of the work; preparing a new calendar and a new set of
puzzles each year takes all of my free time for 4-5 months. A lot of effort
went into building this thing - I hope you're enjoying playing it as much as I
enjoyed making it for you!
If you'd like to hang out, I'm @was.tl on Bluesky, @[email protected] on
Mastodon, and @ericwastl on Twitter.
- Eric Wastl
-->
<body>
<div id="sidebar">
</div><!--/sidebar-->
<main>
<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>
<p>You had always imagined CPUs to be noisy, chaotic places, bustling with activity. Instead, the room is quiet, motionless, and dark.</p>
<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>
<p>"It stopped milliseconds ago; not sure why. I'm a garbage collector, not a doctor." You ask what the machine is for.</p>
<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>
<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>
<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>
<ul>
<li>A <em>tape</em> which contains <code>0</code> repeated infinitely to the left and right.</li>
<li>A <em>cursor</em>, which can move left or right along the tape and read or write values at its current position.</li>
<li>A set of <em>states</em>, each containing rules about what to do based on the current value under the cursor.</li>
</ul>
<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>
<p>For example, suppose you found the following blueprint:</p>
<pre><code>Begin in state A.
Perform a diagnostic checksum after 6 steps.
In state A:
If the current value is 0:
- Write the value 1.
- Move one slot to the right.
- Continue with state B.
If the current value is 1:
- Write the value 0.
- Move one slot to the left.
- Continue with state B.
In state B:
If the current value is 0:
- Write the value 1.
- Move one slot to the left.
- Continue with state A.
If the current value is 1:
- Write the value 1.
- Move one slot to the right.
- Continue with state A.
</code></pre>
<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>
<pre><code>... 0 0 0 [0] 0 0 ... (before any steps; about to run state A)
... 0 0 0 1 [0] 0 ... (after 1 step; about to run state B)
... 0 0 0 [1] 1 0 ... (after 2 steps; about to run state A)
... 0 0 [0] 0 1 0 ... (after 3 steps; about to run state B)
... 0 [0] 1 0 1 0 ... (after 4 steps; about to run state A)
... 0 1 [1] 0 1 0 ... (after 5 steps; about to run state B)
... 0 1 1 [0] 1 0 ... (after 6 steps; about to run state A)
</code></pre>
<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>
<p>Recreate the Turing machine and save the computer! <em>What is the diagnostic checksum</em> it produces once it's working again?</p>
</article>
<p>To begin, <a href="25/input" target="_blank">get your puzzle input</a>.</p>
<form method="post" action="25/answer"><input type="hidden" name="level" value="1"/><p>Answer: <input type="text" name="answer" autocomplete="off"/> <input type="submit" value="[Submit]"/></p></form>
<p>You can also <span class="share">[Share<span class="share-content">on
<a href="https://bsky.app/intent/compose?text=%22The+Halting+Problem%22+%2D+Day+25+%2D+Advent+of+Code+2017+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F25" target="_blank">Bluesky</a>
<a href="https://twitter.com/intent/tweet?text=%22The+Halting+Problem%22+%2D+Day+25+%2D+Advent+of+Code+2017&url=https%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F25&related=ericwastl&hashtags=AdventOfCode" target="_blank">Twitter</a>
<a href="javascript:void(0);" onclick="var ms; try{ms=localStorage.getItem('mastodon.server')}finally{} if(typeof ms!=='string')ms=''; ms=prompt('Mastodon Server?',ms); if(typeof ms==='string' && ms.length){this.href='https://'+ms+'/share?text=%22The+Halting+Problem%22+%2D+Day+25+%2D+Advent+of+Code+2017+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2017%2Fday%2F25';try{localStorage.setItem('mastodon.server',ms);}finally{}}else{return false;}" target="_blank">Mastodon</a
></span>]</span> this puzzle.</p>
</main>
<!-- ga -->
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-69522494-1', 'auto');
ga('set', 'anonymizeIp', true);
ga('send', 'pageview');
</script>
<!-- /ga -->
</body>
</html>