secret
Created

  • Download Gist
decode.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
#!/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)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.