Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.28 KB | None | 0 0
  1. import random
  2. from copy import deepcopy
  3.  
  4.  
  5. def rls(n):
  6.     if n <= 0:
  7.         return []
  8.     else:
  9.         symbols = list(range(1, n+1))
  10.         square = _rls(symbols)
  11.         return _shuffle_transpose_shuffle(square)
  12.  
  13.  
  14. def _shuffle_transpose_shuffle(matrix):
  15.     square = deepcopy(matrix)
  16.     random.shuffle(square)
  17.     trans = list(zip(*square))
  18.     random.shuffle(trans)
  19.     return trans
  20.  
  21.  
  22. def _rls(symbols):
  23.     n = len(symbols)
  24.     if n == 1:
  25.         return [symbols]
  26.     else:
  27.         sym = random.choice(symbols)
  28.         symbols.remove(sym)
  29.         square = _rls(symbols)
  30.         square.append(square[0].copy())
  31.         for i in range(n):
  32.             square[i].insert(i, sym)
  33.         return square
  34.  
  35.  
  36. def _to_text(square):
  37.     if square:
  38.         width = max(len(str(sym)) for row in square for sym in row)
  39.         txt = '\n'.join(' '.join("{}".format(sym).rjust(width, " ") for sym in row)
  40.                         for row in square)
  41.     else:
  42.         txt = ''
  43.     return txt
  44.  
  45.  
  46. def _check(square):
  47.     transpose = list(zip(*square))
  48.     assert _check_rows(square) and _check_rows(transpose), \
  49.         "Not a Latin square"
  50.  
  51.  
  52. def _check_rows(square):
  53.     if not square:
  54.         return True
  55.     set_row0 = set(square[0])
  56.     return all(len(row) == len(set(row)) and set(row) == set_row0
  57.                for row in square)
  58.  
  59.  
  60. if __name__ == '__main__':
  61.     T = int(input().strip())
  62.  
  63.     resultArr = []
  64.  
  65.     for x in range(1, T+1):
  66.         n, k = list(map(int, input().strip().split()))
  67.  
  68.         arrayIDX = [n for idx in range(50)]
  69.  
  70.         ltsArr = []
  71.  
  72.         for i in arrayIDX:
  73.             square = rls(i)
  74.             ltsArr.append(square)
  75.             _check(square)
  76.  
  77.         # if possible to have lts of k
  78.         for lts in ltsArr:
  79.             temp = 0
  80.  
  81.             for rIDX in range(len(lts)):
  82.                 temp += lts[rIDX][rIDX]
  83.  
  84.             if temp == k:
  85.                 result = "POSSIBLE"
  86.                 break
  87.             else:
  88.                 result = "IMPOSSIBLE"
  89.  
  90.         if result == "POSSIBLE":
  91.             resultArr.append([x, result, _to_text(lts)])
  92.         else:
  93.             resultArr.append([x, result])
  94.  
  95.         print("Case #{}: {}".format(x, result))
  96.  
  97.         if result == "POSSIBLE":
  98.             print(_to_text(lts))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement