/r/dailyprogrammer #208 hard

turing_machine.py

# -*- coding: utf-8 -*-
# /r/dailyprogrammer #208 hard
# https://www.reddit.com/r/dailyprogrammer/comments/31aja8/
# Title: [2015-04-03] Challenge #208 [Hard] The Universal Machine
""" The Universal Machine (Generator approach)

 -- (2015) Dave J (https://github.com/DaveAtGit)
"""

class TuringMachine:
    """TuringMachine
    """
    def __init__(self, input_lines):
        alph, states, self.start, self.end, tape, *rules = input_lines.strip().splitlines()
        self.alphabet = list(alph + '_')
        self.states = states.split()
        self._tape = list(tape)
        self.rules = dict()

        self.current_state = self.start
        self.tape = self._tape[:]
        self.position = 0
        self.offset = 0

        self._parse_rules(rules)

    def _parse_rules(self, rules):
        for line in rules:
            state_old, symb_old, _, state_new, symb_new, direction = line.split()
            self.rules[(state_old, symb_old)] = (state_new, symb_new, direction)

    def __iter__(self):
        # Initializing the new iter-object.
        self.current_state = self.start
        self.position = 0
        self.offset = 0
        self.tape = self._tape[:]
        return self

    def __next__(self):
        if self.current_state == self.end:
            raise StopIteration
        rl = (self.current_state, self.tape[self.position + self.offset])
        if rl[0] not in self.states:
            raise Exception("Unknown state '{}'.".format(rl[0]))
        if rl[1] not in self.alphabet:
            raise Exception("Unknown symbol '{}'.".format(rl[1]))
        if rl not in self.rules:
            raise Exception("Unknown rule '{}'.".format(rl))
        s, y, d = self.rules[rl]
        self.current_state = s
        self.tape[self.position + self.offset] = y
        self.position += (1, -1)[d == '<']
        if self.position < 0:
            self.offset += 1
            self.tape.insert(0, '_')
        elif self.position >= len(self.tape):
            self.tape.append('_')

        return self

    def __str__(self):
        # cleaning:
        while self.tape[0] == "_" and self.offset > 0:
            self.tape = self.tape[1:]
            self.offset -= 1
        self.tape = list(''.join(self.tape).rstrip('_'))

        indicators = [' ' for _ in range(len(self.tape))]
        indicators[self.position + self.offset] = '^'
        indicators[self.offset] = '|'
        return ''.join(self.tape) + '\n' + ''.join(indicators).rstrip()


def tests():
    cases = {"""\
01
Mov B Bi OK
Mov
OK
01100100
Mov 0 = Mov 0 >
Mov 1 = Mov 1 >
Mov _ = B _ <
B 0 = B 0 <
B 1 = Bi 1 <
B _ = OK _ >
Bi 0 = Bi 1 <
Bi 1 = Bi 0 <
Bi _ = OK _ >
""": """\
10011100
|""",
"""\
./k
Init Mdot MDash Ret OK
Init
OK
/././../.../..../k
Init _ = Init _ >
Init . = Mdot _ >
Init / = MDash _ >
Init k = OK k >
Mdot . = Mdot . >
Mdot / = Mdot / >
Mdot k = Mdot k >
Mdot _ = Ret . <
MDash . = MDash . >
MDash / = MDash / >
MDash k = MDash k >
MDash _ = Ret / <
Ret . = Ret . <
Ret / = Ret / <
Ret k = Ret k <
Ret _ = Init _ >
""": """\
_________________k/././../.../..../
|                 ^""",
"""\
01xy#
C0 C1 Ret Search OK
Search
OK
0110100#
Search 0 = C0 x >
Search 1 = C1 y >
Search # = OK # >
C0 0 = C0 0 >
C0 1 = C0 1 >
C0 # = C0 # >
C0 _ = Ret 0 <
C1 0 = C1 0 >
C1 1 = C1 1 >
C1 # = C1 # >
C1 _ = Ret 1 <
Ret 0 = Ret 0 <
Ret 1 = Ret 1 <
Ret # = Ret # <
Ret x = Search 0 >
Ret y = Search 1 >
""": """\
0110100#0110100
|       ^"""}

    for inp, out in cases.items():
        tm = TuringMachine(inp)
        for output in tm:
            # we could print each state of the machine here.
            pass
        print(output)
        assert str(output) == out

if __name__ == '__main__':
    tests()

unversal_machine.py

# -*- coding: utf-8 -*-
# /r/dailyprogrammer #208 hard
# https://www.reddit.com/r/dailyprogrammer/comments/31aja8/
# Title: [2015-04-03] Challenge #208 [Hard] The Universal Machine
""" The Universal Machine

 -- (2015) Dave J (https://github.com/DaveAtGit)
"""


def machine(string):
    """machine(string)

    The Universal Machine.
    No printing done here.

    :param string:      The input-string, as defined by the challenge.

    :return:            The output-string, as defined by the challenge.
    """
    lines = string.strip().splitlines()
    # alphabet = list(lines[0])    # never needed...
    states = lines[1].split()
    start_state, end_state = lines[2:4]
    tape = list(lines[4])
    offset = position = 0
    state = start_state
    transitions = {s: dict() for s in states if s != end_state}
    for line in lines[5:]:
        state_b, symb_b, _, state_a, symb_a, d = line.split()
        transitions[state_b][symb_b] = (state_a, symb_a, d)

    # actual action:
    while state != end_state:
        new_state, new_symbol, d = transitions[state][tape[position]]
        tape[position] = new_symbol
        position += (1, -1)[d == '<']
        if position < 0:
            tape.insert(0, '_')
            offset += 1
            position += 1
        elif position >= len(tape):
            tape.append('_')
        state = new_state

    # cleaning tape:
    l = len(tape)
    tape = ''.join(tape).lstrip('_')
    nl = len(tape)
    l_diff = l - nl
    position -= l_diff
    offset -= l_diff
    if offset < 0:
        roff = offset * -1
        tape = '_' * roff + tape
        position += roff
        offset = 0
    tape = tape.rstrip('_')

    # create position-symbols:
    pos_arr = [' ' for _ in range(len(tape))]
    pos_arr[position] = '^'
    pos_arr[offset] = '|'

    return ''.join(tape) + '\n' + ''.join(pos_arr).strip()
    # __import__("pprint").pprint(locals())


def main():
    """unviersal_machine.py file

    :param file:        The file, containing the required data.
    """
    # can be extended to read from stdin
    import sys
    with open(sys.argv[1], 'r') as f:
        out = machine(f.read())
    print(out)


def tests():
    # Test-Case 1
    c1_in, c1_out = case_1 = """\
01
Mov B Bi OK
Mov
OK
01100100
Mov 0 = Mov 0 >
Mov 1 = Mov 1 >
Mov _ = B _ <
B 0 = B 0 <
B 1 = Bi 1 <
B _ = OK _ >
Bi 0 = Bi 1 <
Bi 1 = Bi 0 <
Bi _ = OK _ >
""", """\
10011100
|"""
    c1_out_actual = machine(c1_in)
    print(c1_out_actual)
    assert c1_out_actual == c1_out

    # Test-Case 2
    c2_in, c2_out = case_2 = """\
./k
Init Mdot MDash Ret OK
Init
OK
/././../.../..../k
Init _ = Init _ >
Init . = Mdot _ >
Init / = MDash _ >
Init k = OK k >
Mdot . = Mdot . >
Mdot / = Mdot / >
Mdot k = Mdot k >
Mdot _ = Ret . <
MDash . = MDash . >
MDash / = MDash / >
MDash k = MDash k >
MDash _ = Ret / <
Ret . = Ret . <
Ret / = Ret / <
Ret k = Ret k <
Ret _ = Init _ >
""", """\
_________________k/././../.../..../
|                 ^"""
    c2_out_actual = machine(c2_in)
    print(c2_out_actual)
    assert c2_out_actual == c2_out

    # Test-Case 3
    c3_in, c3_out = case_3 = """\
01xy#
C0 C1 Ret Search OK
Search
OK
0110100#
Search 0 = C0 x >
Search 1 = C1 y >
Search # = OK # >
C0 0 = C0 0 >
C0 1 = C0 1 >
C0 # = C0 # >
C0 _ = Ret 0 <
C1 0 = C1 0 >
C1 1 = C1 1 >
C1 # = C1 # >
C1 _ = Ret 1 <
Ret 0 = Ret 0 <
Ret 1 = Ret 1 <
Ret # = Ret # <
Ret x = Search 0 >
Ret y = Search 1 >
""", """\
0110100#0110100
|       ^"""
    c3_out_actual = machine(c3_in)
    print(c3_out_actual)
    assert c3_out_actual == c3_out

if __name__ == '__main__':
    main()