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)}"