# Yet another boggle word game

Here is my practise with boggle letter square non-overlapping word finder after some drastic debugging and cleaning.

I think it is reasonable speed also. Comments wellcome.

``````from time import clock

DICT = 'unixdict.txt'

def word_path(word,used=[],pos=None):
if word:
correct_neighbour = [neigh
for p,neigh in neighbour_set
if ((pos is None or pos==p) and
(neigh not in used) and
boggle[neigh]==word[0]
)
]
for i in correct_neighbour:
used_copy=used[:]+[i]
if len(word)==1:
if boggle[i]==word:
return (used_copy,)
else:
for solution in  word_path(word[1:],used_copy,pos=i):
if solution:
return (solution,)
return (False,)

neighbours=(
(-1,-1),    (-1,0), (-1,1), ## above line
(0,-1),             (0,1),  ## same line
(1,-1),     (1,0),  (1,1)   ## next line
)

wantquit = False
while wantquit != 'q':
boggle=''
while not boggle:
dimension=int(len(boggle)**0.5)
if dimension**2!=len(boggle):
print 'Not square boggle, give again!'
boggle=''

for i in range(dimension,len(boggle)+1,dimension):
print "%2i: %s" % (i-dimension,boggle[i-dimension:i])

neighbour_indexpairs = set(((i,j), (i+di,j+dj))
for i in range(dimension)
for j in range(dimension)
for di,dj in neighbours if  0<=dj+j<dimension and 0<=di+i<dimension
)

# change to one dimension
neighbour_set=set((a*dimension+b,c*dimension+d) for (a,b),(c,d) in neighbour_indexpairs)

t0=clock()

letterpairs = set((boggle[a]+boggle[b]) for a,b in neighbour_set)

words = set(word for word in open(DICT).read().split()
if (word.lower()==word and
len(word)>dimension-2 and
all((word[i]+word[i+1] in letterpairs) for i in range(len(word)-1))
)
)
print len(words),'candidates'
t1=clock()

result = [word for word in words
for solution in word_path(word)
if solution]
result.sort()
result.sort(key=len, reverse=True)
print "\nTotal", len(result),"solutions."
print "\nFound in %.3f ms" % (1000*(clock()-t0)),
print "of which final check took %.3f ms" % (1000*(clock()-t1))
print '\t'.join(result)
wantquit=raw_input('Ready! Push q to finish something to continue.\n').lower()``````
TrustyTony 888

I did little optimizing after it is working and got "slightly" better performance:
(with example box: CATXANTXTREEEBXY)
Previous version:
Found in 229.725 ms of which final check took 102.581 ms

First improvements (dictionary only split once etc):
Found in 168.441 ms of which final check took 46.105 ms

This version:
Found in 127.655 ms of which final check took 5.148 ms

``````from time import clock
DICT = 'unixdict.txt'

def word_path(word,used=[],pos=None):
if word:
correct_neighbour = [neigh
for neigh in (neighbourlist[pos] if pos else range(dimension*dimension))
if ((neigh not in used) and
boggle[neigh]==word[0])
]
for i in correct_neighbour:
used_copy=used[:]+[i]
if len(word)==1:
if boggle[i]==word:
return (used_copy,)
else:
for solution in  word_path(word[1:],used_copy,pos=i):
if solution:
return (solution,)
return (False,)

neighbours=(
(-1,-1),    (0,-1), (1,-1), ## left column
(-1,0),             (1,0),  ## same column
(-1,1),     (0,1),  (1,1)   ## next column
)

wantquit = False
while wantquit != 'q':
boggle=''
while not boggle:
dimension=int(len(boggle)**0.5)
if dimension**2!=len(boggle):
print 'Not square boggle, give again!'
boggle=''

for i in range(0,len(boggle)-dimension+1,dimension):
print "%2i: %s" % (i,boggle[i:i+dimension])

neighbour_indexpairs = set(((i,j), (i+di,j+dj))
for i in range(dimension)
for j in range(dimension)
for di,dj in neighbours if  0<=dj+j<dimension and 0<=di+i<dimension
)

# change to one dimension
neighbour_set=set((a*dimension+b,c*dimension+d) for (a,b),(c,d) in neighbour_indexpairs)

neighbourlist = [[] for _ in boggle]

[neighbourlist[char_index].append(b) for char_index,b in neighbour_set]

t0=clock()

letterpairs = set((boggle[a]+boggle[b]) for a,b in neighbour_set)

words = set(word for word in wordlist
if (word.lower()==word and
len(word)>dimension-2 and
all((word[i]+word[i+1] in letterpairs) for i in range(len(word)-1))
)
)
print len(words),'candidates'
t1=clock()

result = [word for word in words
for solution in word_path(word)
if solution]
result.sort()
result.sort(key=len, reverse=True)
print "\nTotal", len(result),"solutions."
print "\nFound in %.3f ms" % (1000*(clock()-t0)),
print "of which final check took %.3f ms" % (1000*(clock()-t1))
print '\t'.join(result)
wantquit=raw_input('Ready! Push q to finish something to continue.\n').lower()``````
TrustyTony 888

Line 7 should be

``for neigh in (neighbourlist[pos] if pos is not None else range(dimension*dimension))``

0 is valid index of neighbour list.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.