Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Turing 4ever solution in Creative category for Funny Addition by Renelvon
from collections import deque
class Tape:
"""A self-extending tape for a Turing machine."""
_tape = None
_pos = None # Invariant: 0 <= _pos < len(_tape)
blank = 'b'
def __init__(self, contents=None, blank='b'):
"""
Initialize tape with a string.
Optionally specify the blank character.
Position head at leftmost character.
"""
self.blank = blank
if not contents:
self._tape = deque(self.blank)
else:
self._tape = deque(contents)
self._pos = 0
def move_left(self):
"""Move head one position left. Extend tape as needed."""
if self._pos > 0:
self._pos -= 1
else:
self._tape.appendleft(self.blank)
def move_right(self):
"""Move head one position right. Extend tape as needed."""
if self._pos == len(self._tape) - 1:
self._tape.append(self.blank)
self._pos += 1
def read(self):
"""Read symbol at current position."""
return self._tape[self._pos] # NOTE: Not O(1) because of deque
def set(self, value):
"""Set symbol at current position."""
self._tape[self._pos] = value
def contents(self, clear=False):
"""
Return tape contents as string.
Optionally strip blank characters.
"""
if clear:
return ''.join(self._tape).strip(self.blank)
return ''.join(self._tape)
def configuration(self):
"""Return tape contents with current head position highlighted."""
tapelist = list(self._tape)
tapelist[self._pos:self._pos + 1] = ['[', tapelist[self._pos], ']']
return ''.join(tapelist)
class Machine:
"""A generic Turing Machine."""
rules = None
state = None
tape = None
debug = False
@property
def blank(self):
return self.tape.blank
@property
def configuration(self):
return (self.state, self.tape.configuration())
def __init__(self, rules=None, state=0, contents=None,
blank='b', debug=False):
"""
Rules must be a map from (state, cur_symbol)
to (new_state, new_symbol, movement).
If debug is set, the machine outputs state and configuration
at each step.
"""
self.rules = rules
self.state = state
self.tape = Tape(contents=contents, blank=blank)
self.debug = debug
def step(self):
if self.debug:
print('State: %s, \tTape: %s' % self.configuration)
cur_symbol = self.tape.read()
new_state, new_symbol, movement = self.rules[(self.state, cur_symbol)]
self.state = new_state
self.tape.set(new_symbol)
if movement == 'L':
self.tape.move_left()
elif movement == 'R':
self.tape.move_right()
def exec(self, limit=-1):
i = 0
while self.state != 'halt' and i != limit:
self.step()
i += 1
class IncMachine(Machine):
"""
An incrementing machine. Accepts a binary number as string,
increments it and then halts. Number may be delimited with
blanks on each side both on input and on output.
For reference purposes only; not needed for solution.
"""
def __init__(self, **kwargs):
super(IncMachine, self).__init__(**kwargs)
bbb = self.blank
self.rules = {
# State 0; Initial state; Before MSB
(0, bbb): (0, bbb, 'R'),
(0, '0'): (1, '0', 'N'),
(0, '1'): (1, '1', 'N'),
# State 1; Moving towards LSB
(1, bbb): (2, bbb, 'L'),
(1, '0'): (1, '0', 'R'),
(1, '1'): (1, '1', 'R'),
# State 2; Moving towards MSB while incrementing
(2, bbb): (3, '1', 'L'),
(2, '0'): (3, '1', 'L'),
(2, '1'): (2, '0', 'L'),
# State 3; Moving towards MSB without incrementing
(3, bbb): ('halt', bbb, 'N'),
(3, '0'): (3, '0', 'L'),
(3, '1'): (3, '1', 'L')
}
class DecMachine(Machine):
"""
A decrementing machine. Accepts a binary number as string,
decrements it and then halts. Number may be delimited with blanks
on each side both on input and on output.
If number is zero, no decrementing happens.
For reference purposes only; not needed for solution.
"""
def __init__(self, **kwargs):
super(DecMachine, self).__init__(**kwargs)
bbb = self.blank
self.rules = {
# State 0; Initial state; Before MSB
(0, bbb): (0, bbb, 'R'),
(0, '0'): (1, '0', 'N'),
(0, '1'): (2, '1', 'N'),
# State 1; Moving towards LSB; no ace yet found
(1, bbb): (4, bbb, 'L'),
(1, '0'): (1, '0', 'R'),
(1, '1'): (2, '1', 'R'),
# State 2; Moving towards LSB; ace has been found
(2, bbb): (3, bbb, 'L'),
(2, '0'): (2, '0', 'R'),
(2, '1'): (2, '1', 'R'),
# State 3; Moving towards MSB while decrementing
(3, bbb): ('halt', bbb, 'N'), # NOTE: impossible transition
(3, '0'): (3, '1', 'L'),
(3, '1'): (4, '0', 'L'),
# State 4; Moving towards MSB without decrementing
(4, bbb): ('halt', bbb, 'N'),
(4, '0'): (4, '0', 'L'),
(4, '1'): (4, '1', 'L')
}
class AddMachine(Machine):
"""
An adding machine. Accepts two binary numbers as single string.
Repeatedly increments the first number and decrements the second number.
Halts when second number becomes zero.
Numbers may be delimited with blanks on each side both on input
and on output. Numbers *must* be separated with at least one blank on input.
"""
def __init__(self, **kwargs):
super(AddMachine, self).__init__(**kwargs)
bbb = self.blank
self.rules = {
# State 0; Initial state; Before MSB of first number
(0, bbb): (0, bbb, 'R'),
(0, '0'): (1, '0', 'N'),
(0, '1'): (1, '1', 'N'),
# State 1; Moving towards LSB of first number
(1, bbb): (2, bbb, 'N'),
(1, '0'): (1, '0', 'R'),
(1, '1'): (1, '1', 'R'),
# State 2; Before MSB of second number
(2, bbb): (2, bbb, 'R'),
(2, '0'): (3, '0', 'N'),
(2, '1'): (4, '1', 'N'),
# State 3; Move towards LSB of second number; no ace yet found
(3, bbb): ('halt', bbb, 'N'),
(3, '0'): (3, '0', 'R'),
(3, '1'): (4, '1', 'R'),
# State 4; Moving towards LSB of second number; ace has been found
(4, bbb): (5, bbb, 'L'),
(4, '0'): (4, '0', 'R'),
(4, '1'): (4, '1', 'R'),
# State 5; Moving towards MSB of second number while decrementing
(5, bbb): (7, bbb, 'N'), # NOTE: impossible transition
(5, '0'): (5, '1', 'L'),
(5, '1'): (6, '0', 'L'),
# State 6; Moving towards MSB of second number without decrementing
(6, bbb): (7, bbb, 'N'),
(6, '0'): (6, '0', 'L'),
(6, '1'): (6, '1', 'L'),
# State 7; Before LSB of first number
(7, bbb): (7, bbb, 'L'),
(7, '0'): (8, '0', 'N'),
(7, '1'): (8, '1', 'N'),
# State 8; Moving towards MSB of first number while incrementing
(8, bbb): (9, '1', 'L'),
(8, '0'): (9, '1', 'L'),
(8, '1'): (8, '0', 'L'),
# State 9; Moving towards MSB of first number without incrementing
(9, bbb): (0, bbb, 'N'), # Loop once more!
(9, '0'): (9, '0', 'L'),
(9, '1'): (9, '1', 'L')
}
def checkio(data):
a, b = data
blank = '_'
ba, bb = bin(a)[2:], bin(b)[2:]
m = AddMachine(contents=ba + blank + bb, blank=blank)
m.exec()
return int(m.tape.contents(clear=True).split(blank)[0], 2)
June 6, 2014
Comments:
