Guest User

Untitled

a guest
Apr 22nd, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.96 KB | None | 0 0
  1. ateeapyotinuedse
  2.  
  3. class Dictionary(object):
  4. def __init__(self, letters, diclist):
  5. self.idx = 0
  6. self.letters, self.diclist = letters, diclist
  7. self.allcouples = set()
  8. self.size = 0
  9. self.matrix = self.make_board(letters)
  10. self.diags = [self.matrix[::-1,:].diagonal(i) for i in range(-3, 4)]
  11. self.diags.extend(self.matrix.diagonal(i) for i in range(3, -4, -1))
  12. self.reduce()
  13. self.size_matters()
  14.  
  15. def __str__(self): return str(self.ws)
  16. def __iter__(self): return self
  17. def __next__(self):
  18. self.idx += 1
  19. try: return list(self.ws)[self.idx-1]
  20. except IndexError:
  21. self.idx = 0
  22. raise StopIteration
  23.  
  24. def make_board(self, letters, n=4):
  25. return np.array([list(letters[i:i+n]) for i in range(0, len(letters), n)])
  26.  
  27. def pairs(self, s):
  28. s1, s2 = s, s[::-1]
  29. return set([''.join(pair) for pair in zip(s[:-1], s[1:])] + [''.join(pair) for pair in zip(s2[:-1], s2[1:])])
  30.  
  31. def reduce(self):
  32. for row in self.matrix: self.allcouples |= (self.pairs("".join(row)))
  33. for i in range(4): self.allcouples |= (self.pairs("".join(np.concatenate(self.matrix[:,[i]]))))
  34. for n in self.diags:
  35. if len(n) > 1: self.allcouples |= (self.pairs("".join(list(n))))
  36.  
  37. board = set(self.letters)
  38.  
  39. self.ws = set([w for w in self.diclist if set(w) < board and w[:2] in self.allcouples])
  40. self.size = len(self.ws)
  41.  
  42. def size_matters(self):
  43. self.ws = [w for w in self.ws if all([w.count(l) <= self.letters.count(l) for l in w])]
  44. # print(len(self.ws))
  45.  
  46.  
  47.  
  48.  
  49. # ===================== Checker Class Start =================================
  50.  
  51. class Checker(object):
  52. def __init__(self, board):
  53. self.board, self.letters,self.adj_list = board, {}, {}
  54. ds = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
  55.  
  56. for i in range(4):
  57. for j in range(4):
  58. if board[i][j] not in self.letters: self.letters[board[i][j]] = []
  59. self.letters[board[i][j]].append((i, j))
  60. self.adj_list[(board[i][j], i, j)] = []
  61.  
  62. for d1, d2 in ds:
  63. k,l = i+d1, j+d2
  64. if k >= 0 and k < 4 and l >= 0 and l < 4:
  65. self.adj_list[(board[i][j], i, j)].append((board[k][l], k, l))
  66.  
  67. def dfs(self, word):
  68. if len(word) < 3 or word[0] not in self.letters: return False
  69. stack =[(word[0], word, (word[0], i, j), set([(i, j)])) for i, j in self.letters[word[0]]]
  70.  
  71. while len(stack) > 0:
  72. sub, word, let, positions = stack.pop()
  73. if sub == word: return True
  74. next_letter = word[len(sub)]
  75.  
  76. for l, i, j in self.adj_list[let]:
  77. if l == next_letter and (i, j) not in positions:
  78. p2 = copy.deepcopy(positions)
  79. p2.add((i, j))
  80. stack.append((sub+next_letter, word, (l, i, j), p2))
  81.  
  82. return False
  83.  
  84. # ======================== Classes End ===================================
  85.  
  86.  
  87.  
  88. def p(word):
  89. if len(word) < 8: return {'3':1,'4':1,'5':2,'6':3,'7':5}[str(len(word))]
  90. elif len(word) >= 8: return 11
  91. else: return 0
  92.  
  93. def its_boggle_time_baby(b):
  94. board = list(zip(*[iter(b)]*4))
  95. # print(board)
  96. g = Checker(board)
  97. words = [(word, p(word)) for word in d if g.dfs(word)]
  98. # for w in words: print(w)
  99. total_points = 0
  100. for word, points in words: total_points += points
  101. print("Possible points: {}".format(total_points))
  102.  
  103. def main():
  104.  
  105. t1 = time.time()
  106.  
  107. dic = [w.strip() for w in open(sys.argv[2]) if len(w.strip()) >= 3]
  108.  
  109. boardz = [bz.strip() for bz in open(sys.argv[1]).readlines()]
  110. for bz in boardz:
  111. global d
  112. d = Dictionary(bz, dic)
  113. its_boggle_time_baby(bz)
  114.  
  115. t2 = time.time()
  116. print(t2-t1)
  117.  
  118. # print(d)
  119. # for w in dic: print(w)
  120.  
  121. if __name__ == '__main__':
  122. main()<code>
Add Comment
Please, Sign In to add comment