minify_graph.py (1012B)
1 #!/usr/bin/python3 2 3 # minify a strategy tree 4 5 import sys 6 7 T = {} 8 M = {} 9 cache = {} 10 11 last = -1 12 13 def minify(v): 14 global T 15 if v not in T.keys(): 16 return -1 # leaf 17 if v in cache.keys(): 18 return cache[v] 19 # info about this configuration: moves to play and minified resulting config 20 info = tuple([(ip[0], ip[1], minify(ip[2])) for ip in T[v]]) 21 if info in M.keys(): 22 cache[v] = M[info] 23 return M[info] # node already known 24 # insert the new node and print its outgoing edges 25 idx = len(M.keys()) 26 M[info] = idx 27 # idx is not printed because the lines are sequential 28 print(" ".join(" ".join(str(inf) for inf in info[p]) for p in range(7))) 29 cache[v] = idx 30 return idx 31 32 for l in sys.stdin.readlines(): 33 ff = l.strip().split(' ') 34 f = int(ff[0]) 35 p = int(ff[1]) 36 r = int(ff[2]) 37 c = int(ff[3]) 38 t = int(ff[4]) 39 if f not in T.keys(): 40 T[f] = [-1] * 7 41 T[f][p] = (r, c, t) 42 last = f 43 44 assert(last >= 0) 45 minify(last)