Mercurial > hg > aoc

annotate 2017/day25/problem @ 34:049fb8e56025

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add problem statements and inputs
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 09 Jan 2018 21:51:44 -0500
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
34
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
1 --- Day 25: The Halting Problem ---
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
2
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
3 Following the twisty passageways deeper and deeper into the CPU, you
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
4 finally reach the core of the computer. Here, in the expansive central
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
5 chamber, you find a grand apparatus that fills the entire room,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
6 suspended nanometers above your head.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
7
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
8 You had always imagined CPUs to be noisy, chaotic places, bustling
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
9 with activity. Instead, the room is quiet, motionless, and dark.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
10
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
11 Suddenly, you and the CPU's garbage collector startle each other.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
12 "It's not often we get many visitors here!", he says. You inquire
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
13 about the stopped machinery.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
14
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
15 "It stopped milliseconds ago; not sure why. I'm a garbage collector,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
16 not a doctor." You ask what the machine is for.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
17
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
18 "Programs these days, don't know their origins. That's the Turing
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
19 machine! It's what makes the whole computer work." You try to explain
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
20 that Turing machines are merely models of computation, but he cuts you
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
21 off. "No, see, that's just what they want you to think. Ultimately,
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
22 inside every CPU, there's a Turing machine driving the whole thing!
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
23 Too bad this one's broken. We're doomed!"
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
24
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
25 You ask how you can help. "Well, unfortunately, the only way to get
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
26 the computer running again would be to create a whole new Turing
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
27 machine from scratch, but there's no way you can-" He notices the look
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
28 on your face, gives you a curious glance, shrugs, and goes back to
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
29 sweeping the floor.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
30
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
31 You find the Turing machine blueprints (your puzzle input) on a tablet
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
32 in a nearby pile of debris. Looking back up at the broken Turing
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
33 machine above, you can start to identify its parts:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
34
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
35 A tape which contains 0 repeated infinitely to the left and right.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
36
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
37 A cursor, which can move left or right along the tape and read or
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
38 write values at its current position.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
39
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
40 A set of states, each containing rules about what to do based on
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
41 the current value under the cursor.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
42
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
43
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
44 Each slot on the tape has two possible values: 0 (the starting value
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
45 for all slots) and 1. Based on whether the cursor is pointing at a 0
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
46 or a 1, the current state says what value to write at the current
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
47 position of the cursor, whether to move the cursor left or right one
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
48 slot, and which state to use next.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
49
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
50 For example, suppose you found the following blueprint:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
51
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
52 Begin in state A.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
53 Perform a diagnostic checksum after 6 steps.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
54
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
55 In state A:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
56 If the current value is 0:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
57 - Write the value 1.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
58 - Move one slot to the right.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
59 - Continue with state B.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
60 If the current value is 1:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
61 - Write the value 0.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
62 - Move one slot to the left.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
63 - Continue with state B.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
64
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
65 In state B:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
66 If the current value is 0:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
67 - Write the value 1.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
68 - Move one slot to the left.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
69 - Continue with state A.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
70 If the current value is 1:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
71 - Write the value 1.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
72 - Move one slot to the right.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
73 - Continue with state A.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
74
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
75 Running it until the number of steps required to take the listed
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
76 diagnostic checksum would result in the following tape configurations
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
77 (with the cursor marked in square brackets):
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
78
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
79 ... 0 0 0 [0] 0 0 ... (before any steps; about to run state A)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
80 ... 0 0 0 1 [0] 0 ... (after 1 step; about to run state B)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
81 ... 0 0 0 [1] 1 0 ... (after 2 steps; about to run state A)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
82 ... 0 0 [0] 0 1 0 ... (after 3 steps; about to run state B)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
83 ... 0 [0] 1 0 1 0 ... (after 4 steps; about to run state A)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
84 ... 0 1 [1] 0 1 0 ... (after 5 steps; about to run state B)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
85 ... 0 1 1 [0] 1 0 ... (after 6 steps; about to run state A)
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
86
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
87 The CPU can confirm that the Turing machine is working by taking a
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
88 diagnostic checksum after a specific number of steps (given in the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
89 blueprint). Once the specified number of steps have been executed, the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
90 Turing machine should pause; once it does, count the number of times 1
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
91 appears on the tape. In the above example, the diagnostic checksum is
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
92 3.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
93
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
94 Recreate the Turing machine and save the computer! What is the
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
95 diagnostic checksum it produces once it's working again?
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
96
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
97 Your puzzle answer was 2526.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
98
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
99 --- Part Two ---
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
100
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
101 The Turing machine, and soon the entire computer, springs back to
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
102 life. A console glows dimly nearby, awaiting your command.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
103
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
104 > reboot printer
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
105 Error: That command requires priority 50. You currently have priority 0.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
106 You must deposit 50 stars to increase your priority to the required level.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
107
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
108 The console flickers for a moment, and then prints another message:
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
109
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
110 Star accepted.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
111 You must deposit 49 stars to increase your priority to the required level.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
112
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
113 The garbage collector winks at you, then continues sweeping.
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
114
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
115 If you like, you can [Reboot the Printer Again].
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
116
049fb8e56025 Add problem statements and inputs
Jordi Gutiérrez Hermoso <jordigh@octave.org>
parents:
diff changeset
117 Both parts of this puzzle are complete! They provide two gold stars: **