AoC 2017 Day 25: Turing

Source: The Halting Problem

Part 1: Implement a Turing machine defined as such:

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.

...

What is the final number of 1s on the tape?

Most of this problem actually came down to reading the input:

# Map of (current state, current value, key) -> value
# key is one of value, offset, state
transitions = {}
breakpoint = 0
state = None
pointer = 0
one_bits = set()

for line in lib.input():
    line = line.strip('- ')
    arg = line.split()[-1][:-1]

    if arg == 'steps':
        arg = line.split()[-2]

    try:
        arg = int(arg)
    except:
        pass

    # Store values based on that argument
    if line.startswith('Begin'):
        state = arg
    elif line.startswith('Perform'):
        breakpoint = arg
    elif line.startswith('In'):
        current_state = arg
    elif line.startswith('If'):
        current_value = arg
    elif line.startswith('Write'):
        transitions[current_state, current_value, 'value'] = arg == 1
    elif line.startswith('Move'):
        transitions[current_state, current_value, 'offset'] = 1 if arg == 'right' else -1
    elif line.startswith('Continue'):
        transitions[current_state, current_value, 'state'] = arg

As we did in part 1 of day 22, we’ll use a set to store the current state (store 1, if an index is not in the set, it’s 0). That gives us the ability to grow unbounded (so long as we have enough RAM).

Once you have that, actually running the Turing machine is pretty straight forward:

for tick in range(breakpoint):
    value = 1 if pointer in one_bits else 0

    if value and not transitions[state, value, 'value']:
        one_bits.remove(pointer)
    elif not value and transitions[state, value, 'value']:
        one_bits.add(pointer)

    pointer += transitions[state, value, 'offset']
    state = transitions[state, value, 'state']

print(len(one_bits))

It’s not the fastest thing in the world, but it works well enough:

$ python3 run-all.py day-25

day-25  python3 turing.py input.txt     79.73910212516785       2870

Since it’s the last day, there’s only one part. A fun year. Check out the index post for a list of this year’s posts.

Merry Christmas! ⛄️