1

I'm doing a simple python project for school which involves the user trying to find the longest real word they can from a random pool of 9 letters in 30 seconds. It's easy enough to test if the user's answer is a real word, by looping through a file of many words in the English language (it has 114,000 words which probably doesn't include ALL of them). In fact, that took a split-second to run.

However, in order to check if there is a full 'solution' (9-letter real word) for the random pool of letters, I couldn't think of anything apart from testing for every single permutation of the 9-letter word pool against every word in the file. The problem is, that's really inefficient and took about 7 minutes. After all, considering that there are 9! (factorial) permutations of the anagram, and that the 'random' module does NOT rule out previous permutations, AND that there are many words in the file, the computer has to work through over 50 billion comparisons. At the end of it, the word (using an anagram of 'happiness') was not found. This is the code I tried:

# python 3.5.2

import random

anagram = ['p','s','h','a','i','s','n','p','e'] # anagram of hapiness


with open('wordlist.txt') as in_file:
    for line in in_file:
    line = line.rstrip() 
    shuffledList = random.sample(anagram, len(anagram)) # randomise order
    shuffledWord = ''.join(shuffledList) # make it a string
    if shuffledWord == line:
        print("YES") # (never happens)
        break

Apart from code that actually yields a solution, I'm looking for some sort of clever algorithmic solution/ threading technique/ absolutely anything, that could find the original word of a 9-letter anagram in 30 seconds or less. It seems really far-fetched but I thought it was worth a try. Any suggestions?

Parallax Sugar
  • 695
  • 9
  • 15
  • You have an answer to your anagram question, but for future reference, the itertools module has an efficient function for generating all permutations that's better than trying to do that by random shuffling. OTOH, itertools.permutations is a bit dumb when permuting a collection containing repeated items. To handle that situation properly please see http://stackoverflow.com/a/31678111/4014959 – PM 2Ring Feb 25 '17 at 16:28

1 Answers1

2

Here is the little clue with anagrams: they are the same list after you sort them. You can try something like that:

>>> def is_anagram(word_one, word_two):
...     return sorted(word_one) == sorted(word_two)
...
>>> print(is_anagram('ranagam', 'anagram'))
True
hashcode55
  • 5,622
  • 4
  • 27
  • 40
mdegis
  • 2,078
  • 2
  • 21
  • 39
  • Does that not return true for any pair of words? I got the output "True" when I tried 'print(is_anagram('pine', 'tree'))'. – Parallax Sugar Feb 25 '17 at 15:49
  • 1
    @LauraCookson Yeah right it will always return true because `.sort()` doesn't return anything which is `None` and `None` = `None` so it always prints true. What you need is `sorted(word_one)`. – hashcode55 Feb 25 '17 at 15:58