7

Here is my first attempt to solve Jumble puzzle:

import argparse
from itertools import permutations


parser = argparse.ArgumentParser(description='Solver for Jumble')
parser.add_argument('jumbledwords', nargs='+',
                    help='One or more jumbled words')
argv = parser.parse_args()

# http://www-01.sil.org/linguistics/wordlists/english/wordlist/wordsEn.txt
words = [line.rstrip() for line in open('wordsEn.txt')]
for jumbledword in argv.jumbledwords:
    perms = set([''.join(p) for p in permutations(jumbledword)])
    legalwords = [word for word in perms if word in words]
    # print(len(perms))
    print(jumbledword, legalwords)

Any suggestions for improvement?

2 Answers 2

Reset to default
7

Close what you open

words = [line.rstrip() for line in open('wordsEn.txt')]

Here you opened a file but you did not close it! In fact I suggest to use with that will handle closing automagically.

with open('wordsEn.txt') as f:
    words = [line.rstrip() for line in f.read()]

Let the user change the file

You should let the user input as an optional arg his own filename, I may have my own wordlist that is not called exactly: 'wordsEn.txt', the dafault file should be None (You read directly from the webpage).

set built-in operations

If you change the below line to be:

words = set([line.rstrip() for line in f.read().splitlines()])

You can then use set intersection:

legalwords = perms & words

To enhance both clarity and performance.

Allowing long words

The complexity of finding all the permutations of a word is O(N!): for a mere 20 characters word that means 2.432 * 10**18 combinations, I suggest comparing the sorted words for better efficiency if you need to run the script with long words.

4
  • Thanks for your valuable inputs. FYI, 'wordsEn.txt' is already sorted and I think using list will maintain the order. Commented May 22, 2015 at 16:52
  • You are right that set intersection is better performance than list. I do not understand what you mean by sorted words because there are no order in set. Could you expound more? I will post the revised code as a new answer. Commented May 22, 2015 at 23:54
  • @inyoot I mean an unsorted collection of sorted words. Commented May 23, 2015 at 11:04
  • could you give example, @Caridorc ? Commented May 23, 2015 at 13:37
1

Here is my revised code. I fixed the unclosed file problem. I use set intersection instead of list.

import argparse
from itertools import permutations


parser = argparse.ArgumentParser(description='Solver for Jumble')
parser.add_argument('jumbledwords', nargs='+',
                    help='One or more jumbled words')
argv = parser.parse_args()

# http://www-01.sil.org/linguistics/wordlists/english/wordlist/wordsEn.txt
with open('wordsEn.txt') as f:
    words = {line.rstrip() for line in f}

for jumbledword in argv.jumbledwords:
    perms = set([''.join(p) for p in permutations(jumbledword)])
    legal_words = perms & words
    # print(len(perms))
    print(jumbledword, legal_words)

There is significant performance improvement by using set intersection instead of 'list'.

(list)$ time python jumble_puzzle.py nabando enegativ
nabando ['abandon']
enegativ ['negative']

real    1m5.735s
user    1m5.556s
sys     0m0.060s

(set)$ time python jumble_puzzle.py nabando enegativ
nabando {'abandon'}
enegativ {'negative'}

real    0m0.170s
user    0m0.153s
sys     0m0.016s
1
  • 1
    To mitigate the complexity of permuting long words, also consider using a dictionary/map, as outlined in the first algorithm here. Commented May 7 at 20:23

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.