# Untitled

a guest
Jul 11th, 2017
565
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from itertools import permutations
2.
3. def gcd(x,y):
4.     if y == 0: return x
5.     return gcd(y, x%y)
6.
7. counts = {}
8.
9. def conv(a):
10.     return a / 3, a % 3
11.
12. def iconv(a, b):
13.     return a*3 + b
14.
15. def canonical(ori,tgt, dx,dy):
16.     if ori < tgt:
17.         return (ori,dx,dy)
18.     return (tgt,-dx,-dy)
19.
20. for perm in permutations(range(9)):
21.     occ = []
22.     ok = True
23.     all_lines = []
24.
25.     for ori, tgt in zip(perm, perm[1:]):
26.         row_o, col_o = conv(ori)
27.         row_t, col_t = conv(tgt)
28.         dx = row_t - row_o
29.         dy = col_t - col_o
30.
31.         lines = [canonical(ori,tgt,dx,dy)]
32.         g = abs(gcd(dx,dy))
33.         if g != 1:
34.             dx /= g
35.             dy /= g
36.             mid = iconv(row_o + dx, col_o + dy)
37.             if mid not in occ:
38.                 ok = False
39.                 break
40.
41.             lines = [canonical(ori,mid,dx,dy), canonical(mid,tgt,dx,dy)]
42.
43.         all_lines.extend(lines)
44.         occ.append(ori)
45.
46.     if ok:
47.         lines_set = frozenset(all_lines)
48.         counts[lines_set] = counts.get(lines_set, 0) + 1
49.
50. res = counts.items()
51. res.sort(key=lambda x: x[1], reverse=True)
52. print res[0]
53. print res[1]
54. print res[2]