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 ) ] 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()
Are you able to help answer this sponsored question?
Questions asked by members who have earned a lot of community kudos are featured in order to give back and encourage quality replies.