Sean McLemon | Advent of Code

2017-12-25 - The Halting Problem

(original .ipynb)

test_input_str = """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."""

puzzle_input_str = open("puzzle_input/day25.txt").read()

def parse_intro(intro_str):
    begin_line, terminate_line = intro_str.split("\n")
    begin_state = begin_line.removeprefix("Begin in state ").removesuffix(".")
    steps = int(terminate_line.removeprefix("Perform a diagnostic checksum after ").removesuffix(" steps."))
    return begin_state, steps


def parse_state(state_str):
    state_lines = state_str.split("\n")
    state_name = state_lines[0].removeprefix("In state ").removesuffix(":")
    
    zero_rule = parse_rule(state_lines[1:][1:4])
    one_rule = parse_rule(state_lines[1:][5:])
    
    return (state_name, zero_rule, one_rule)


def parse_rule(rule_lines):
    write_value = int(rule_lines[0].removeprefix("    - Write the value ").removesuffix("."))
    direction = rule_lines[1].removeprefix("    - Move one slot to the ").removesuffix(".")
    next_state = rule_lines[2].removeprefix("    - Continue with state ").removesuffix(".")

    return (write_value, direction, next_state)


def parse_input(input_str):
    sections = input_str.split("\n\n")
    intro_str = sections[0]
    state_sections = sections[1:]
    
    begin_state, steps = parse_intro(intro_str)
    states = {}
    
    for state_section_str in state_sections:
        state_name, zero_rule, one_rule = parse_state(state_section_str)
        states[state_name] = [
            zero_rule,
            one_rule
        ]
        
    return begin_state, steps, states


def move(cursor, tape, direction):
    moves = {
        "left": -1,
        "right": 1
    }
    
    cursor += moves[direction]
    
    if cursor < 0:
        tape.insert(0, 0)
        cursor = 0
    elif cursor >= len(tape):
        tape.append(0)
        
    return cursor
    

def part_one(input_str):
    current_state, steps, states = parse_input(input_str)
    cursor = 0
    tape = [0]
    
    while steps > 0:
        write_value, direction, next_state = states[current_state][tape[cursor]]
        tape[cursor] = write_value
        cursor = move(cursor, tape, direction)
        current_state = next_state
        steps -= 1
        
    return sum(tape)


assert 3 == part_one(test_input_str)

print("part one:", part_one(puzzle_input_str))

part one: 2794