Guest User

Untitled

a guest
Feb 26th, 2012
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2.  
  3. COLOR = True
  4. FIX_DEAD_CELLS = False
  5.  
  6. from bool_solve import *
  7. from sys import stderr
  8. from math import ceil, floor
  9. from copy import copy
  10.  
  11. try:
  12.     import psyco
  13.     psyco.full()
  14. except ImportError:
  15.     pass
  16.  
  17. O = True
  18. _ = False
  19.  
  20. if COLOR:
  21.     rep = { True : "\x1b[0;91m#\x1b[0m",
  22.             False: "-",
  23.             None : "\x1b[0;92m?\x1b[0m",
  24.           }
  25. else:
  26.     rep = { True : "#",
  27.             False: "-",
  28.             None : "?",
  29.           }    
  30.  
  31. from array import array
  32. class Matrix:
  33.     def __init__(self, width, height, default = None):
  34.         self.__width__ = width
  35.         self.__internal__ = [default] * (width * height)
  36.  
  37.     def __getitem__(self, (x, y)):
  38.         return self.__internal__[x + (y * self.__width__)]
  39.        
  40.     def __setitem__(self, (x, y), val):
  41.         self.__internal__[x + (y * self.__width__)] = val
  42.  
  43. '''
  44. state = [[ _, _, _, _, _ ],
  45.         [ _, _, O, _, _ ],
  46.         [ _, _, _, O, _ ],
  47.         [ _, O, O, O, _ ],
  48.         [ _, _, _, _, _ ]]
  49. '''
  50. #'''
  51. state = [[ _, _, _, _, _ ],
  52.          [ _, O, O, O, _ ],
  53.          [ _, O, _, O, _ ],
  54.          [ _, O, O, O, _ ],
  55.          [ _, _, _, _, _ ]]
  56. #'''
  57. '''
  58. state = [[ _, _, _, _ ],
  59.         [ _, O, _, _ ],
  60.         [ _, _, O, _ ],
  61.         [ _, _, _, _ ]]
  62. '''
  63. '''
  64. state = [[ _, _, _ ],
  65.         [ _, O, _ ],
  66.         [ _, _, _ ]]
  67. '''
  68.  
  69. def bool_fold(grid, fold_op, destroy = True):
  70.     if not destroy:
  71.         grid = copy(grid)
  72.    
  73.     assert(len(grid) > 0)
  74.     if len(grid) == 1:
  75.         return grid[0]
  76.  
  77.     h = len(grid) / 2.
  78.     hh = int(ceil(h))
  79.     hl = int(floor(h))
  80.    
  81.     root  = [fold_op, None, None]
  82.  
  83.  
  84.             # nodes to go in this branch
  85.                    # Parent
  86.                          # Index in the parent branch
  87.     stack = [(hh, root, 1), (hl, root, 2)]
  88.     while len(grid) > 0:
  89.         num, p, i = stack.pop()
  90.         if num == 1:
  91.             p[i] = grid.pop()
  92.  
  93.         else:
  94.             node  = [fold_op, None, None]
  95.             p[i] = node
  96.  
  97.             h = num / 2.
  98.             hh = int(ceil(h))
  99.             hl = int(floor(h))
  100.             stack.append((hh, node, 1))
  101.             stack.append((hl, node, 2))
  102.  
  103.     return root
  104.  
  105.  
  106. def get_true_tree(x, y, width, height):
  107.     sz = serialize
  108.     possibilities = []
  109.     combinations = []
  110.  
  111.     #################################################################
  112.     # Alive cell, two neighbours
  113.     for ix in xrange(-1, 2):
  114.         for iy in xrange(-1, 2):
  115.  
  116.             if (ix, iy) == (0, 0): continue
  117.          
  118.             for jx in xrange(-1, 2):
  119.                 for jy in xrange(-1, 2):
  120.                     if (jx, jy) == (ix, iy): continue
  121.                     if (jx, jy) == (0, 0)  : continue
  122.  
  123.                     combinations.append(((ix, iy), (jx, jy), True))
  124.  
  125.     #################################################################
  126.     # Three neighbours
  127.     for ix in xrange(-1, 2):
  128.         for iy in xrange(-1, 2):
  129.  
  130.             if (ix, iy) == (0, 0): continue
  131.          
  132.             for jx in xrange(-1, 2):
  133.                 for jy in xrange(-1, 2):
  134.                     if (jx, jy) == (ix, iy): continue
  135.                     if (jx, jy) == (0, 0)  : continue
  136.                    
  137.                     for kx in xrange(-1, 2):
  138.                         for ky in xrange(-1, 2):
  139.                             if (kx, ky) in ((ix, iy), (jx, jy)): continue
  140.                            
  141.                             if (kx, ky) == (0, 0): continue
  142.                            
  143.                             combinations.append(((ix, iy), (jx, jy), (kx, ky)))
  144.  
  145.     #################################################################
  146.     # Possibility resolution
  147.     for combination in combinations:
  148.         grid = []
  149.         if True in combination: grid = [sz(x, y)]
  150.         for _x in xrange(-1, 2):
  151.             for _y in xrange(-1, 2):
  152.                 if _x != 0 or _y != 0:                        
  153.                     data = sz((x + _x) % width, (y + _y) % height)
  154.                     if (_x, _y) in combination:
  155.                         grid.append(data)
  156.                     else:
  157.                         grid.append((NOT_OP, data))
  158.  
  159.         possibilities.append(bool_fold(grid, AND_OP))
  160.  
  161.     return bool_fold(possibilities, OR_OP)
  162.  
  163. def add_pairs(num, target, log = ()):
  164.     for ix in xrange(-1, 2):
  165.         for iy in xrange(-1, 2):
  166.  
  167.             if (ix, iy) in log: continue
  168.             elif num == 1: target.append(log + ((ix, iy),))
  169.             else:          add_pairs(num - 1, target, log + ((ix, iy),))
  170.  
  171. def get_false_tree(x, y, width, height):
  172.     sz = serialize
  173.  
  174.     possibilities = []  
  175.     combinations = []
  176.    
  177.     combinations.append( () ) # No neighbours
  178.  
  179.     # One neighbour
  180.     for ix in xrange(-1, 2):
  181.         for iy in xrange(-1, 2):
  182.  
  183.             if (ix, iy) == (0, 0): continue
  184.             combinations.append(((ix, iy), ))
  185.  
  186.     #################################################################
  187.     # Dead cell, two neighbours
  188.     add_pairs(2, combinations, (False, (0, 0)))
  189.  
  190.     # >3 neighbours
  191.     add_pairs(4, combinations, (False, ))
  192.  
  193.     # 5, 6, 7, 8
  194.     for i in xrange(5, 9):
  195.         add_pairs(9 - i, combinations)
  196.  
  197.     #################################################################
  198.     # Possibility resolution
  199.     for combination in combinations:
  200.         grid = []
  201.         inverted = False in combination
  202.         if (0, 0) in combination:
  203.             grid.append(sz(x, y))
  204.  
  205.         for _x in xrange(-1, 2):
  206.             for _y in xrange(-1, 2):
  207.                 if _x == 0 and _y == 0: continue
  208.                 data = sz((x + _x) % width, (y + _y) % height)
  209.                 if ((_x, _y) in combination) ^ inverted:
  210.                     grid.append(data)
  211.                 else:
  212.                     grid.append((NOT_OP, data))
  213.  
  214.         possibilities.append(bool_fold(grid, AND_OP))
  215.  
  216.     return bool_fold(possibilities, OR_OP)
  217.  
  218. # Assert rectangular field          
  219. def life_reverse(state, fix_dead = False):
  220.     print >>stderr, "Generating code..."
  221.    
  222.     requisites = []
  223.     height = len(state)
  224.     width  = len(state[0])
  225.     for y in xrange(height):
  226.         for x in xrange(width):
  227.             if   state[y][x] == True:
  228.                 requisites.append(get_true_tree(x, y, width, height))
  229.  
  230.             elif state[y][x] == False and fix_dead:
  231.                 requisites.append(get_false_tree(x, y, width, height))
  232.                 #requisites.append((NOT_OP, get_true_tree(x, y, width, height)))
  233.  
  234.     f = bool_fold(requisites, AND_OP)
  235.  
  236.     print >>stderr, "Solving equation..."
  237.     return get_solutions(f)
  238.  
  239.  
  240. def show_state(state):
  241.     for row in state:
  242.         for c in row:
  243.             if c: print "#",
  244.             else: print " ",
  245.         print ""
  246.  
  247.  
  248. def show_solution_state(state, width, height):
  249.     m = Matrix(width, height, None)
  250.     for s in state:
  251.         b = not s.inverted
  252.         x, y = unserialize(s.name)
  253.         m[x, y] = b
  254.        
  255.     for x in xrange(width):
  256.         for y in xrange(height):
  257.             c = m[x, y]
  258.             print rep[c],
  259.            
  260.         print ""
  261.  
  262. def serialize(row, col):
  263.     return "%s.%s" % (row, col)
  264.  
  265. def unserialize(s):
  266.     row, col = s.split(".")
  267.     return int(row), int(col)
  268.  
  269. solutions = life_reverse(state, FIX_DEAD_CELLS)
  270.  
  271. if not solutions:
  272.     print "Unreversable state"
  273.  
  274. else:
  275.     first = True
  276.  
  277.     for solution in solutions:
  278.         if not first: print "\x1b[0;93m" + ("-" * (len(state) * 2)) + "\x1b[0m"
  279.         else: first = False
  280.  
  281.         #print_solutions(solution)
  282.         #show_state(state)
  283.         show_solution_state(solution, len(state[0]), len(state))
  284.  
  285.     print len(solutions), "solutions"
RAW Paste Data