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],

• SylvainD: @Peilonrayz it does exist but only in Python 2 :'(
• Peilonrayz: @Josay Wat, :O So it does...
• Peilonrayz: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• katty: @Peilonrayz okay
• Eric Duminil: Your code doesn't even remotely solve the given problem. It's too early for CodeReview. You could look at dirkgorissen.com/2011/12/02/solving-boggle-with-python for an example how to solve Boggle.

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.

• Peilonrayz: I don't know why you're having a go at my answer, as if I said it was the perfect soloution... All I did was improve on the OP's code.

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.

• meshy: As for python 2, then end of the line is in 2020. Not long to go. \o/ pythonclock.org

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,

• katty: can u elaborate a little more about 'word_count & boggle == word_count' @Peilonrayz
• Peilonrayz: @KratiChaturvedi The simplest way to think of it is that it's checking that word_count is in boggle. This is as& performs an intersection, so it creates a new Counter with items that are in both word_count and boggle. It then checks that it's the same as word_count, as if any are missing, then they're not in the boggle board.
• Johnbot: Counter doesn't account for adjacency.
• Peilonrayz: @Johnbot Yes, however the OP didn't implement that. I'm not going to write that for them.

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".