Given 3 cubes, each cube has 3 different letters(other sides have pictures and numbers - they can be ignored for the purposes of this program). Find all valid words that can be made by arranging these cubes.

Cube A = 'A', 'J' and 'N'; Cube B = 'B', 'K' and 'O'; Cube C = 'C', 'L' and 'P'

import re
from itertools import permutations

a = ['A','J','N']
b = ['B','K','O']
c = ['C','L','P']

combinationsList = []#list of all possible variations of 3 letter words
for a_letter in range(len(a)):
    for b_letter in range(len(b)):
        for c_letter in range(len(c)):
            word = a[a_letter] + b[b_letter] + c[c_letter]
print len(combinationsList)

permutationsList = []#list of all permutations of the combinations list [changing positions of the cubes to form different words]
for word in combinationsList:
    perms = [''.join(p) for p in permutations(word)]
    permutationsList += perms

print len(permutationsList)

dictionList = []#list of all valid words found that match the length of number of cubes (in this scenario there are 3 cubes)
with open("/usr/share/dict/words", "r") as diction:
    for line in diction:
        word = line.strip()
        if re.match('.{3}$', word) != None:#improve regex search to only find words in the valid character setw
print len(dictionList)

match = []

for word in permutationsList:
    if dictionList.count(word) > 0:#compares all word permutations with all words in diction for matches
print match
  1. It's just as easy to iterate over the characters in a string as over the elements in a list, so the initialization of the cubes can be simplified:

    a, b, c = 'AJN BKO CLP'.split()
  2. combinationsList can be computed using itertools.product:

    combinationsList = list(itertools.product(a, b, c))
  3. Instead of using a regular expression:

    if re.match('.{3}$', word) != None:

    just check the length:

    if len(word) == 3:

    (But once you have an efficient membership test, as discussed below, you can skip this check.)

  4. The code checks for membership in a list by counting the number of occurrences:

    if dictionList.count(word) > 0:

    but it would be simpler to use the in operator:

    if word in dictionList:
  5. Testing for membership in a list is expensive — Python has to compare word with every member of dictionList in turn. It would be more efficient to use a set, which has a fast membership test.

  6. The code in the post constructs a collection of dictionary words and checks each candidate word to see if it's in the dictionary. But because there are only 162 candidate words, and hundreds of thousands of entries in the dictionary, it would be more memory-efficient to do the operation the other way round — that is, to check each dictionary word to see if it's a candidate. That way, you wouldn't have to build a collection of dictionary words, you could just iterate over them one by one.

Revised code:

from itertools import permutations, product
cubes = 'AJN BKO CLP'.split()
candidate_words = {
    for letters in product(*cubes)
    for permutation in permutations(letters)
valid_words = set()
with open('/usr/share/dict/words') as dictionary:
    for line in dictionary:
        word = line.strip().upper()
        if word in candidate_words:
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.