Solving jumbled letters using a given dictionary

Question

Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters.
Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"}; 
       boggle[][]   = {{'G','I','Z'},  
                       {'U','E','K'},  
                       {'Q','S','E'}};

Output:  Following words of dictionary are present  
         GEEKS, QUIZ

Below is my code:

dictSize=int(raw_input())
dictionary=raw_input().split(' ')
m,n=map(int,raw_input().split(' '))
boggle=[[0 for x in range(n)] for y in range(m)]
#print dictionary

bString=raw_input().split()
for i in range(0,m):
    for j in range(0,n):
        boggle[i][j]=bString[(i*n)+j]
#print boggle


lookUp={}
for i in range(0,m):
    for j in range(0,n):
        lookUp[boggle[i][j]]=lookUp.get(boggle[i][j],0)+1

possibility=[]
flag=0
for i in range(0,len(dictionary)):
    for s in dictionary[i]:
        if(lookUp.has_key(s)):
            flag=0
        else:
            flag=1
    if(flag==0):
        possibility.append(dictionary[i])
#print possibility

for i in range(0,len(possibility)):
    print possibility[i],

Answer 1

Take another look at your problem description:

Find all possible words that can be formed by a sequence of adjacent characters.

Try the following input:

1
geeks
3 3
e e e a a a g k s

In the 3x3 board formed there is no connection between the first and last row and it's not possible to form geeks from adjacent characters:

e e e
a a a
g k s

Your solution only assert that each of the characters from the dictionary word exists in the board.

1
geeks
3 3
g e k s a a a a a

result in geeks.

The solution suggested by Peilonrayz only assert that each character exists at least the correct number of times .

Try to solve the problem as stated.

Answer 2

Loop like a native

I highly recommend Ned Batchelder's excellent talk called "Loop like a native".

for i in range(0,len(possibility)):
    print possibility[i],

can be rewritten:

for p in possibility:
    print p,

Python 2 in 2018

It is probably a bad idea to write new Python 2 code in 2018. You should try to write it in Python 3.

Answer 3

Your code is way more complex than it needs to be.

• boggle is only used to make lookUp.

  Which would be simpler to make without making boggle.

• You can use collections.Counter to create lookUp if you don't make boggle.

• Your for s in dictionary[i]: loop only checks if the last character in the dictionary is in the boggle grid.

  And this could be implemented simpler using Counter.

• You don't need to make the possibility list.

And so you could simplify to:

from collections import Counter

raw_input()
dictionary = raw_input().split(' ')
raw_input()
boggle = Counter(raw_input().split())

for word in dictionary:
    word_count = Counter(word)
    if word_count & boggle == word_count:
        print word,

Answer 4

I see three main ways of going this:

1. Generate list of boggle words, and check each one to see whether it's in the dictionary.
2. For each word in the dictionary, see whether it's in the boggle words.
3. Generate boggle words, but stop once you reach something that isn't the beginning of a word (for instance, if an actual human were playing boggle, and they saw ZK, they wouldn't try to find any words that starts with the sequence, because they would know there aren't any such English words.)

Which method to use depends on the size of the inputs. If you know that each word is at most five letters long, then you have N*M candidates for beginning letters, four more letters to find, and at most eight choices at each letter, so in this case that's an upper bound 9*8^4 = 36864, which is a large number but doable. For a larger board, and longer words, this can easily get unwieldy, though.

If the inputs given are representative, then with only four words in the dictionary, the fastest method is to just check each word. So, for instance, for the word "geeks", you would first get a list of places where the letter "g" appears in the boggle, and for each location you would get a list of adjacent "e"'s, and so on. Note that you will have to keep track of what letters you've used in a word; if one of the words in the dictionary were "gig", your program shouldn't use the same "g" twice.

As for your code, it doesn't seem to check multiplicities or adjacency, so the following is somewhat moot, but most of your code can be replaced by a single line:

possibility = [word for word in dictionary if all([letter in bString for letter in word])]

In English, this is "possibility is the list of all words in dictionary such that all letters in the word are in bString".