decode.py

#!/usr/bin/env python

import re

def step(pos, dir):
    x, y = pos
    if dir == 0:
        x -= 1
    elif dir == 1:
        y -= 1
    elif dir == 2:
        x += 1
    elif dir == 3:
        y += 1
    return x, y


def walk(grid, pos, dir):
    crosses = ((0, 0, 0, 2, 2, 2, 0, 2), (1, 3, 1, 1, 1, 3, 3, 3))

    pos = step(pos, dir)
    tape = ''
    while True:
        type, tile_dir = grid[20 * pos[1] + pos[0]]
        if type == ' ':
            return 'halt', pos, tape
        elif type in ('b', 'r', 'g', 'y'):
            tape += type
        elif type == 'i':
            tile_dir = crosses[dir % 2][tile_dir]
        elif type == 'c':
            pass
        elif type in ('p', 'q'):
            return 'trans', pos, tape
        elif type == 'X':
            return 'accept', pos, tape
        else:
            assert False

        pos, dir = step(pos, tile_dir), tile_dir


def decode(s):
    grid = [(' ', 0) for i in xrange(20 * 20)]

    def set(x, y, thing):
        grid[20 * y + x] = thing

    square_re = re.compile(r'^([cipqbrgy])(\d+):(\d+)f(\d+)$')

    for square in s[:-1].split(';'):
        match = square_re.match(square)
        type, x, y, dir = match.groups()
        x, y, dir = int(x), int(y), int(dir)

        if dir >= 4 and type != 'i':
            # print '>>>', type, (x, y), dir
            dir %= 4;

        grid[20 * y + x] = (type, dir)

    return grid

def states(grid, start):
    states = []
    for x in xrange(20):
        for y in xrange(20):
            if grid[20 * y + x][0] in ('p', 'q'):
                states.append((x, y))

    machine = {start: {'$': walk(grid, start, 3)}}
    for pos in states:
        type, dir = grid[20 * pos[1] + pos[0]]
        right = 'b' if type == 'p' else 'y'
        left = 'r' if type == 'p' else 'g'
        machine[pos] = {
            '$': walk(grid, pos, dir),
            right: walk(grid, pos, (dir + 1) % 4),
            left: walk(grid, pos, (dir + 3) % 4),
        }

    return machine



s = """p12:3f3;p10:3f0;c11:3f0;b10:2f3;c10:4f3;p10:5f3;r11:5f0;y12:2f3;c10:1f2;c11:1f3;c11:2f2;c12:4f3;c12:5f3;c12:6f3;c12:7f3;c12:8f3;c12:9f3;c12:10f3;c12:11f3;c12:12f3;c8:1f2;c8:2f1;c8:3f1;c8:4f1;q8:5f0;c9:1f2;b9:4f3;p9:5f0;"""


s = """g12:2f3;i12:3f1;p12:5f3;p9:7f3;p15:7f3;r16:7f0;r14:7f0;b10:7f2;b8:7f2;g15:8f3;b15:9f3;q15:10f3;p16:10f2;r16:9f3;b16:11f1;q17:10f3;c18:10f1;c18:9f1;c18:8f1;c18:7f1;c18:6f1;g12:4f3;i13:4f2;c14:4f0;c15:4f0;c16:4f0;c17:4f0;c18:5f1;i13:5f3;c14:5f2;c15:5f3;c15:6f3;c11:5f0;c10:5f0;c9:5f3;c9:6f3;r9:8f3;c9:12f3;c9:13f2;c10:13f2;c11:13f2;c9:4f3;c9:3f3;c10:3f0;c11:3f0;c13:3f0;i13:6f3;c11:7f1;c11:6f2;c12:6f2;c14:6f2;q9:11f0;b8:10f2;p9:10f3;r10:10f0;q9:9f0;c18:4f0;c13:7f1;"""

s = """r6:3f2;c7:2f3;p7:3f7;q7:4f3;c8:1f3;p8:2f4;b8:3f0;g8:4f2;c9:2f0;c9:3f1;c9:4f1;y10:2f0;c12:2f0;y11:2f0;y6:4f3;c6:5f3;c7:5f0;c8:5f0;c9:5f0;c6:6f3;c6:7f2;p7:7f2;r7:6f3;b7:8f1;q8:7f4;y8:6f3;g8:8f2;p9:8f2;q10:8f2;c9:7f1;c9:6f2;c10:6f2;q6:10f6;p7:10f0;b7:9f3;r7:11f1;y6:11f1;c9:9f0;c8:9f3;c8:10f0;c10:9f3;c10:10f3;c10:11f3;c10:12f3;c10:13f2;c11:13f2;c11:6f1;c11:5f1;q11:4f5;p11:3f3;b10:3f2;r12:3f0;y12:4f0;p13:7f2;c12:7f2;p13:6f1;p13:8f3;c12:6f3;c12:8f1;c14:8f3;c14:9f3;c14:10f3;c14:11f3;c14:12f3;c14:13f0;c13:13f0;y6:9f1;b6:8f1;y10:4f3;r10:5f0;c10:7f2;q11:7f7;"""

s = """b11:1f3;p11:2f0;y12:2f0;r11:3f1;c11:6f2;c12:6f2;c13:6f2;c13:4f0;p12:4f0;r12:5f1;b12:3f3;c11:4f0;c10:4f0;g9:2f3;y10:2f0;y11:5f3;y11:7f1;r10:5f2;b10:7f2;q9:5f2;q9:6f2;p10:6f2;c9:3f3;c9:4f3;y9:7f3;g13:3f3;r14:3f1;p14:2f0;q13:2f0;b14:1f3;r16:2f0;b16:6f0;y17:2f0;q17:3f0;y17:6f0;c18:4f0;c14:6f1;c14:5f1;c14:4f2;i15:4f3;c15:2f0;c15:6f1;c15:5f1;c15:3f1;c9:8f2;p9:9f0;c10:8f2;g10:9f0;q10:10f2;c11:8f2;b11:9f3;p11:10f0;r11:11f1;c12:8f3;c12:9f3;p12:10f3;c12:11f3;c13:8f0;r13:9f3;p13:10f2;b13:11f1;c14:8f0;g14:9f2;q14:10f2;c15:8f0;c7:11f1;c7:10f1;c7:9f1;c7:8f2;c8:8f2;c12:12f3;c16:8f0;p10:12f3;y10:11f3;c9:12f0;c8:12f0;c7:12f1;y14:11f3;p14:12f3;p15:9f2;c15:12f2;c16:12f2;c17:12f1;c17:11f1;c17:10f1;c17:9f1;c17:8f0;p17:4f2;c16:4f2;q17:5f2;r16:3f3;b18:5f1;"""

s = """y12:2f2;g13:2f2;p14:2f2;r14:1f3;b14:3f1;q15:2f2;g15:3f3;y15:4f3;p15:5f3;q15:6f3;r16:5f0;b14:5f2;p14:8f0;c16:6f3;c16:7f3;c16:8f0;c15:8f0;q13:8f0;i13:9f1;p13:11f3;q13:12f3;c12:12f3;b12:11f2;r14:11f0;r14:9f0;b14:7f0;g12:7f0;c12:9f1;c12:8f1;c13:7f0;p11:7f0;p8:2f2;q9:2f2;c14:4f2;c13:4f2;c12:4f2;c11:4f2;c11:3f3;g9:1f3;r8:1f3;b8:3f1;b7:3f1;r6:3f1;g7:4f1;g6:4f1;c7:2f2;c6:2f2;p9:6f0;q8:6f1;c7:6f1;c7:5f1;c6:5f1;c6:6f1;c6:7f1;c6:8f1;c6:9f1;c6:10f1;b9:5f3;b9:7f3;c7:11f0;q8:11f1;r9:10f1;p9:11f0;r9:12f1;c6:11f1;c11:8f3;c11:9f3;c11:10f3;c11:11f0;c10:11f0;c11:6f0;c10:6f0;c9:8f2;i10:8f3;c9:9f2;c10:9f1;c10:7f1;c9:3f2;c10:3f2;y13:10f3;"""


grid = decode(s)
grid[13 * 20 + 12] = ('X', 3)
# print walk(grid, (12, 3), 3)
machine = states(grid, (12, 1))

def to_dot(machine):
    colors = {'$': 'black', 'b': 'blue', 'r': 'red', 'g': 'green', 'y': 'yellow'}

    print "digraph G { "
    print "node [shape=circle];"
    print '"(12, 13)" [peripheries=2];'
    print '"(12, 1)" [label="", shape=plaintext];'
    for node, transitions in machine.iteritems():
        for match, (kind, to, tape) in transitions.iteritems():
            if kind != 'halt':
                # print '"%s" -> "%s" [ label="%s/%s" ];' % (`node`, `to`, match, tape)
                print '"%s" -> "%s" [ color="%s", label="%s" ];' % (`node`, `to`, colors[match], tape)
    print "}"

to_dot(machine)