Mercurial > hg > aoc

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