﻿

# 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.
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):
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):
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)) )
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