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:
```python
# 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! ⛄