Advertisement
Guest User

Untitled

a guest
Jul 11th, 2017
563
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.17 KB | None | 0 0
  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]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement