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 :)
from re import findall from itertools import combinations, permutations from zipfile import ZipFile def readWords(): data = ZipFile('en_US.zip').open('en_US.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))] 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)
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/