Yet another boggle word game

TrustyTony 0 Tallied Votes 1K Views Share

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:
        boggle=raw_input('Give your boggle:').lower() ## CATXANTXTREEEBXY
        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 pyMod Team Colleague Featured Poster

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
    )

wordlist=open(DICT).read().split()
wantquit = False
while wantquit != 'q':
    boggle=''
    while not boggle:
        boggle=raw_input('Give your boggle:').lower() ## CATXANTXTREEEBXY
        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 pyMod Team Colleague Featured Poster

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.