Guest User

Untitled

a guest
May 25th, 2018
90
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from itertools import product, permutations
  2.  
  3. def next_permutation(seq):
  4.     """Like C++ std::next_permutation() but implemented as
  5.    generator. Yields copies of seq."""
  6.     def reverse(seq, start, end):
  7.         # seq = seq[:start] + reversed(seq[start:end]) + \
  8.         #       seq[end:]
  9.         end -= 1
  10.         if end <= start:
  11.             return
  12.         while True:
  13.             seq[start], seq[end] = seq[end], seq[start]
  14.             if start == end or start+1 == end:
  15.                 return
  16.             start += 1
  17.             end -= 1
  18.     if not seq:
  19.         raise StopIteration
  20.     try:
  21.         seq[0]
  22.     except TypeError:
  23.         raise TypeError("seq must allow random access.")
  24.     first = 0
  25.     last = len(seq)
  26.     seq = seq[:]
  27.     # Yield input sequence as the STL version is often
  28.     # used inside do {} while.
  29.     yield seq[:]
  30.     if last == 1:
  31.         raise StopIteration
  32.     while True:
  33.         next = last - 1
  34.         while True:
  35.             # Step 1.
  36.             next1 = next
  37.             next -= 1
  38.             if seq[next] < seq[next1]:
  39.                 # Step 2.
  40.                 mid = last - 1
  41.                 while seq[next] >= seq[mid]:
  42.                     mid -= 1
  43.                 seq[next], seq[mid] = seq[mid], seq[next]
  44.                 # Step 3.
  45.                 reverse(seq, next1, last)
  46.                 # Change to yield references to get rid of
  47.                 # (at worst) |seq|! copy operations.
  48.                 yield seq[:]
  49.                 break
  50.             if next == first:
  51.                 raise StopIteration
  52.     raise StopIteration
  53.  
  54. pentomino_order = 'FILNPTUVWXYZ'
  55. #                  012345678901
  56.  
  57. # 61 50
  58. # 89 4 10
  59. # 7 11 23
  60. pentominos = '''
  61. .xx
  62. xx.
  63. .x.
  64.  
  65. xxxxx
  66.  
  67. ...x
  68. xxxx
  69.  
  70. xx..
  71. .xxx
  72.  
  73. xx.
  74. xxx
  75.  
  76. xxx
  77. .x.
  78. .x.
  79.  
  80. x.x
  81. xxx
  82.  
  83. x..
  84. x..
  85. xxx
  86.  
  87. x..
  88. xx.
  89. .xx
  90.  
  91. .x.
  92. xxx
  93. .x.
  94.  
  95. ..x.
  96. xxxx
  97.  
  98. xx.
  99. .x.
  100. .xx'''
  101.  
  102. def process(pp):
  103.     lines = pp.split()
  104.  
  105.     x = 0
  106.     y = lines[0].index('x')
  107.  
  108.     items = []
  109.     for i, line in enumerate(lines):
  110.         for j, char in enumerate(line):
  111.             if char == 'x':
  112.                 items.append((i-x, j-y))
  113.     return items
  114.  
  115. def normalize(P):
  116.     x = min(P)[0]
  117.     y = min(P, key=lambda t:t[1])[1]
  118.  
  119.     return tuple(sorted([(i-x, j-y) for (i,j) in P]))
  120.  
  121. def rotate(pp, off, swap):
  122.     if swap:
  123.         return [(dy*off[0], dx*off[1]) for (dx,dy) in pp]
  124.     else:
  125.         return [(dx*off[0], dy*off[1]) for (dx,dy) in pp]
  126.  
  127. def rotations(pp):
  128.     all_rots = [rotate(pp, x, swap) for x in product([-1,1], repeat=2) for swap in (False, True)]
  129.  
  130.     return set(normalize(x) for x in all_rots)
  131.  
  132. def place(pp, offx, offy):
  133.     return [(i+offx, j+offy) for (i,j) in pp]
  134.  
  135. def adjacent(p1, p2):
  136.     for k in p1:
  137.         for y in p2:
  138.             if abs(k[0]-y[0])+abs(k[1]-y[1]) == 1: return True
  139.     return False
  140.  
  141. def eliminate_rotations(solutions):
  142.     seen = set()
  143.     result = []
  144.  
  145.     for sol in solutions:
  146.         if sol not in seen:
  147.             result.append(sol)
  148.             for pp in rotations(sol):
  149.                 seen.add(pp)
  150.     return result
  151.  
  152.  
  153. pentominos = [process(x) for x in pentominos.split('\n\n')]
  154. rots = [rotations(x) for x in pentominos]
  155.  
  156. prods = {}
  157.  
  158. for p1 in range(12):
  159.     for p1rot in rots[p1]:
  160.         for p2 in range(12):
  161.             if p1 == p2: continue
  162.             for p2rot in rots[p2]:
  163.                 for p1y in range(6):
  164.                     p1placed = place(p1rot, 0, p1y)                        
  165.                     for p2x in range(6):
  166.                         for p2y in range(6):
  167.                             p2placed = place(p2rot, p2x, p2y)
  168.  
  169.                             if not (set(p1placed) & set(p2placed)) and adjacent(p1placed,p2placed):
  170.                                 prods.setdefault((min(p1,p2),max(p1,p2)), set()).add(normalize(p1placed+p2placed))
  171.  
  172. print("Part 1 done")
  173.  
  174. #uncomment the commented code below to get this list of partitions
  175. solutions = [[1, 1, 2, 2, 3, 1, 1, 2, 3, 3, 3, 2],
  176. [1, 2, 1, 3, 3, 2, 2, 3, 3, 1, 1, 2],
  177. [1, 2, 2, 2, 1, 1, 3, 3, 2, 3, 3, 1],
  178. [1, 2, 3, 1, 3, 2, 2, 1, 1, 3, 3, 2]]
  179.  
  180. can_match = set()
  181.  
  182. for s in solutions:
  183.     groups = [tuple([x for x in range(12) if s[x]==i]) for i in range(1,4)]
  184.  
  185.     print ("NEW SOLUTION")
  186.     for x in groups:
  187.         print(" ".join(pentomino_order[y] for y in x))
  188.  
  189.     for p1 in range(12):
  190.         for p2 in range(p1+1,12):
  191.             for p3 in range(p1+1,12):
  192.                 for p4 in range(p3+1,12):
  193.                     if len(set([p1,p2,p3,p4])) != 4: continue
  194.  
  195.                     if (p1,p2) in prods and (p3,p4) in prods:
  196.                         common = prods[p1,p2] & prods[p3,p4]
  197.                         if common:
  198.                             for x in permutations([p1,p2,p3,p4]):
  199.                                 if x in groups:
  200.                                     print("For group ", groups.index(x), "split", (pentomino_order[p1],pentomino_order[p2]), (pentomino_order[p3],pentomino_order[p4]), sep=' ')
  201.                                     print( '\n'.join(str(x) for x in eliminate_rotations(common)) )
  202.                                 #can_match.add(tuple(x))
  203.  
  204. # for k in next_permutation([1,1,1,1,2,2,2,2,3,3,3,3]):
  205. #   min1 = k.index(1)
  206. #   min2 = k.index(2)
  207. #   min3 = k.index(3)
  208. #   if not min1 < min2 < min3: continue
  209.  
  210. #   if all(tuple([x for x in range(12) if k[x]==i]) in can_match for i in range(1,4)):
  211. #       print(k)
RAW Paste Data