Programming Praxis - Word Cube

This is my first solution for a Programming Praxis assignment, the Word Cube problem.

It's definitely not an elegant solution. It's almost as brute force as it can get, but I have only a negligible amount of training in this field so I'm satisfied for now with being able to find a solution at all.
It takes a few minutes to find all the possible words. I did however find quite a few more than the ones mentioned in the assignment.
Click here to see the source code.

After solving it I read the comments and discovered an (in hindsight) obvious better way of doing it.
Why check all possible permutations of the different combinations of the letters when you can just check every English word in the word file if it matches.
I tend to take assignments very literally (See the nested list to indicate a cube in my code? ;))...

At first it sounds like checking every word of the English language is way more than just checking the combinations of the given letters, since there are a huge amount of words in the English language, but actually the opposite is very true.

My word file contains 51248 words. Not exactly every word in the English language, but for this word cube problem it will suffice.
On the contrary we have all the permutations of the combinations of the different letters in the Cube.
(I'm sure that someone who's better at combinatorics than me who reads this will most likely have just received a heart attack because I'm sure there must be something wrong with that statement) Which comes out to, by a quick  alteration of my solution, 876624. More than ten times the words in the word file.

I'll now try to solve it following the newly discovered method :)

Source code:

[python] from re import findall
from itertools import combinations, permutations
from zipfile import ZipFile

def readWords():
data = ZipFile('enUS.zip').open('enUS.dic').read() return [word for word,crap in findall('''([^/s]+)(/.*)?''', data)]

bonnie, bunion, coin, concubine, conic, cubic, ennui, icon, nice, nine, nuncio, and union

cube = [
['n', 'c', 'b'], ['c', 'i', 'o'], ['u', 'n', 'e'] ] flatcube = [cube[x][y] for x in range(len(cube)) for y in range(len(cube[0]))]
middleIndex = len(flatcube)/2
obligatedChar = flatcube[middleIndex]
del flatcube[middleIndex]
words = readWords()

foundWords = set()
for wordLength in range(3, len(flatcube) + 1): #wordlength minus obligated char
for combination in combinations(flatcube, wordLength): x = [obligatedChar] x.extend(combination) for w in permutations(x): word = ''.join(w) if word in words and not word in foundWords: print word foundWords.add(word)

[/python]

Update

I tried solving it using the new method and came to this.
The improvement in speed is immense. My previous version used to take a couple of minutes to find all solutions, but this one does it in a fraction of a second.
Although I'm sure it can still be improved further.

And something else I found while browsing the Programming Praxis comments: http://www.stealthcopter.com/wordcube/

Jeroen Pelgrims

Software Developer developer in Antwerp working at Unbrace
Follow me on Twitter: @jeroenpelgrims