Instantly share code, notes, and snippets.

# kwaters/decode.pySecret Created Jun 1, 2012

 #!/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)
to join this conversation on GitHub. Already have an account? Sign in to comment