Please excuse my poor styling and/or code. I need this to run faster, but I have little knowledge of how to do that.
Here is a bit of an explanation about boggle, however you can find more online.
It takes the board as a 1 line input (argv[1]
) and a list of words (argv[2]
) as a dictionary. My solution is to make a dictionary specific to each board, excluding words that cannot be made before checking the board. It works relatively well for small test cases (see example below), however takes a long time when it comes to larger ones.
If anyone could please give me some pointers that would be much appreciated. I am not looking to completely change the code I have already, but I want to make it faster.
Inputs: argv[1]
:
ateeapyotinuedse
import sys, copy, time
import numpy as np
# ===================== Dictionary Class Start =================================
class Dictionary(object):
def __init__(self, letters, diclist):
self.idx = 0
self.letters, self.diclist = letters, diclist
self.allcouples = set()
self.size = 0
self.matrix = self.make_board(letters)
self.diags = [self.matrix[::-1,:].diagonal(i) for i in range(-3, 4)]
self.diags.extend(self.matrix.diagonal(i) for i in range(3, -4, -1))
self.reduce()
self.size_matters()
def __str__(self): return str(self.ws)
def __iter__(self): return self
def __next__(self):
self.idx += 1
try: return list(self.ws)[self.idx-1]
except IndexError:
self.idx = 0
raise StopIteration
def make_board(self, letters, n=4):
return np.array([list(letters[i:i+n]) for i in range(0, len(letters), n)])
def pairs(self, s):
s1, s2 = s, s[::-1]
return set([''.join(pair) for pair in zip(s[:-1], s[1:])] + [''.join(pair) for pair in zip(s2[:-1], s2[1:])])
def reduce(self):
for row in self.matrix: self.allcouples |= (self.pairs("".join(row)))
for i in range(4): self.allcouples |= (self.pairs("".join(np.concatenate(self.matrix[:,[i]]))))
for n in self.diags:
if len(n) > 1: self.allcouples |= (self.pairs("".join(list(n))))
board = set(self.letters)
self.ws = set([w for w in self.diclist if set(w) < board and w[:2] in self.allcouples])
self.size = len(self.ws)
def size_matters(self):
self.ws = [w for w in self.ws if all([w.count(l) <= self.letters.count(l) for l in w])]
# print(len(self.ws))
# ===================== Checker Class Start =================================
class Checker(object):
def __init__(self, board):
self.board, self.letters,self.adj_list = board, {}, {}
ds = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
for i in range(4):
for j in range(4):
if board[i][j] not in self.letters: self.letters[board[i][j]] = []
self.letters[board[i][j]].append((i, j))
self.adj_list[(board[i][j], i, j)] = []
for d1, d2 in ds:
k,l = i+d1, j+d2
if k >= 0 and k < 4 and l >= 0 and l < 4:
self.adj_list[(board[i][j], i, j)].append((board[k][l], k, l))
def dfs(self, word):
if len(word) < 3 or word[0] not in self.letters: return False
stack =[(word[0], word, (word[0], i, j), set([(i, j)])) for i, j in self.letters[word[0]]]
while len(stack) > 0:
sub, word, let, positions = stack.pop()
if sub == word: return True
next_letter = word[len(sub)]
for l, i, j in self.adj_list[let]:
if l == next_letter and (i, j) not in positions:
p2 = copy.deepcopy(positions)
p2.add((i, j))
stack.append((sub+next_letter, word, (l, i, j), p2))
return False
# ======================== Classes End ===================================
def p(word):
if len(word) < 8: return {'3':1,'4':1,'5':2,'6':3,'7':5}[str(len(word))]
elif len(word) >= 8: return 11
else: return 0
def its_boggle_time_baby(b):
board = list(zip(*[iter(b)]*4))
# print(board)
g = Checker(board)
words = [(word, p(word)) for word in d if g.dfs(word)]
# for w in words: print(w)
total_points = 0
for word, points in words: total_points += points
print("Possible points: {}".format(total_points))
def main():
t1 = time.time()
dic = [w.strip() for w in open(sys.argv[2]) if len(w.strip()) >= 3]
boardz = [bz.strip() for bz in open(sys.argv[1]).readlines()]
for bz in boardz:
global d
d = Dictionary(bz, dic)
its_boggle_time_baby(bz)
t2 = time.time()
print(t2-t1)
# print(d)
# for w in dic: print(w)
if __name__ == '__main__':
main()
Here is the cProfile. I can see it spends a lot of time on the listcomps but don't know how to shorten them.
IndexError: too many indices for array
(line 14) when running this with the input from your example. Help? \$\endgroup\$python3 <board setup file> <dictionary file>
. Python 3.6. \$\endgroup\$python3 boggle_solver.py board.txt dict.txt
, where board.txt and dict.txt are your example inputs. If you want I can paste the full traceback on pastebin and add a link? \$\endgroup\$