require_relative 'util'
# --- Day 25: The Halting Problem ---
# Following the twisty passageways deeper and deeper into the CPU, you
# finally reach the core of the computer. Here, in the expansive
# central chamber, you find a grand apparatus that fills the entire
# room, suspended nanometers above your head.
# You had always imagined CPUs to be noisy, chaotic places, bustling
# with activity. Instead, the room is quiet, motionless, and dark.
# Suddenly, you and the CPU's garbage collector startle each
# other. "It's not often we get many visitors here!", he says. You
# inquire about the stopped machinery.
# "It stopped milliseconds ago; not sure why. I'm a garbage collector,
# not a doctor." You ask what the machine is for.
# "Programs these days, don't know their origins. That's the Turing
# machine! 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 want you to
# think. Ultimately, inside every CPU, there's a Turing machine
# driving the whole thing! Too bad this one's broken. We're doomed!"
# 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 way you can-" He notices the
# look on your face, gives you a curious glance, shrugs, and goes back
# to sweeping the floor.
# You find the Turing machine blueprints (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:
# - A tape which contains 0 repeated infinitely to the left and right.
# - A cursor, which can move left or right along the tape and read or
# write values at its current position.
# - A set of states, each containing rules about what to do based on
# the current value under the cursor.
# Each slot on the tape has two possible values: 0 (the starting value
# for all slots) and 1. Based on whether the cursor is pointing at a 0
# or a 1, the current state says what value to write at the current
# position of the cursor, whether to move the cursor left or right one
# slot, and which state to use next.
# For example, suppose you found the following blueprint:
# 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.
# Running it until the number of steps required to take the listed
# diagnostic checksum would result in the following tape
# configurations (with the cursor marked in square brackets):
# ... 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)
# The CPU can confirm that the Turing machine is working by taking a
# diagnostic checksum 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 1 appears on the tape. In the above example, the diagnostic
# checksum is 3.
# Recreate the Turing machine and save the computer! What is the
# diagnostic checksum it produces once it's working again?
class TuringMachine
def initialize(state, rules)
@tape = Hash.new { |h, k| h[k] = 0 }
@index = 0
@state = state
@rules = rules
end
def step
value = @tape[@index]
new_value, direction, new_state = @rules[@state][value]
assert([:left, :right].include?(direction))
@tape[@index] = new_value
@index += direction == :left ? -1 : 1
@state = new_state
end
def checksum
@tape.values.sum
end
end
def parse(input)
prelude, *states = input.split("\n\n")
initial_state, steps = parse_prelude(prelude)
rules = states.map { |state| parse_state(state) }.to_h
[initial_state, steps, rules]
end
def parse_prelude(text)
lines = text.split("\n")
state = lines[0][/state (\w)/] && $1.downcase.to_sym
steps = lines[1][/(\d+)/] && $1.to_i
[state, steps]
end
def parse_state(text)
lines = text.split("\n")
state = lines[0][/state (\w)/] && $1.downcase.to_sym
rule = parse_rule(lines[2..4])
other = parse_rule(lines[6..8])
[state, [rule, other]]
end
def parse_rule(lines)
value = lines[0][/(\d)/] && $1.to_i
direction = lines[1][/(left|right)/] && $1.to_sym
state = lines[2][/state (\w)/] && $1.downcase.to_sym
[value, direction, state]
end
test_input = "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."
input = File.open('25.txt') { |f| f.read.chomp }
def easy(input)
initial_state, steps, rules = parse(input)
machine = TuringMachine.new(initial_state, rules)
steps.times { machine.step }
machine.checksum
end
assert(easy(test_input) == 3)
puts "easy(input): #{easy(input)}"