Find scrambled words within word list

Question

I'm just getting started with Python -- completing a simple exercise from a practice website. My code works -- just looking for feedback on better ways to achieve the goal.

Goal:

Find the original (unscrambled) words, which were randomly taken from a wordlist. Send a comma separated list of the original words, in the same order as in the list below.

I stored the scrambled words in words.txt and the wordlist in wordlist.txt

#!/usr/bin/env python3

# open word files
wordlist = open("wordlist.txt", "r").read().split()
words = open("words.txt", "r").read().split() 

s = list()

# loop through scrambled words
for word in words:
    # break scrambled word into characters
    chars = list(word)
    # loop through comparison list
    for compare in wordlist:
        # break compare word into characters
        compare_chars = list(compare)
        # make copy of scrambled characters
        char_list = chars[:]
        # loop through scrambled word characters
        for char in chars:
            # if character not in compare word go to next compare word
            if not char in compare_chars:
                break
            # if character found remove it (in case character exists more than once)
            compare_chars.remove(char)
            char_list.remove(char)
        # if all compare characters exhausted we *may* have found the word
        if not compare_chars:
            # if all scrambled characters are utilized then we have the right word
            if not char_list:
                s.append(compare)
            else:
                s.append('???')
            break

# create comma separated list of words
print(",".join(s))

Answer 1

I'm not a Python programmer but I would take this approach, as if I understand the problem correctly, it seems like an easy solution. Along side that I believe it makes us of the language features also.

#!/usr/bin/env python3

# open word files
wordlist = open("wordlist.txt", "r").read().split()
words = open("words.txt", "r").read().split() 

s = list()

# loop through scrambled words
for word in words:
    # break scrambled word into characters
    chars = sorted(list(word))
    # loop through comparison list
    for compare in wordlist:
        if sorted(list(compare)) == chars:
            s.append(compare)

# create comma separated list of words
print(",".join(s))

This works on the bases that we do not care for order, so an ordered list of each will be a good check.

I have not broken out of the inner loop, as it is unclear weather multiple words could match and all of those words should be returned or not.

This is untested, as stated, I'm not a Python programmer.

Answer 2

Welcome to CodeReview! First, congratulations on writing a working Python program that is clean, straightforward, and easy to understand.

Now let's see if we can make it better!

Style

There are two things I think you could improve stylistically. First, your comments are a little too much. I know people encourage you to write comments. But you need to be careful of the kind of comments you write.

Comments should be used to provide extra information. When you have code like this:

# open word files
wordlist = open("wordlist.txt", "r").read().split()
words = open("words.txt", "r").read().split() 

Is the comment really adding value? A comment that states in English what your code states in Python is a wasted comment. You want to explain what you are doing rather than focus on how you do it. And you should only explain things that don't already have a set of names explaining it. If you're calling an open function, you don't need to explain that you are opening something. If you're storing data into a variable called wordlist, you probably don't need to explain that you are reading a word list. Use a light touch with your commentary.

Second, it's very much preferred in Python 3 to use the context manager features of file objects. If you are going to read in the entire contents of a file, use a with block to open, read, and close the file safely.

with open("wordlist.txt", 'r') as wlist:
    wordlist = wlist.read().split()

Since you do this twice, you might write a function to do it for you. (You say you're a beginner, so I'm not sure if you've learned functions yet.)

Performance

Looking at the "skeleton" of your code:

for word in words:
    for compare in wordlist:
        for char in word:

Your performance is going to be \$O(m \times n \times o)\$ where m is the number of scrambled words, n is the number of words in the master wordlist, and o is the average word length.

The phrasing of the problem statements suggests that the scrambled words are a small subset of the inputs. But the worst case is that the scrambled words are the entire wordlist, making your worst-case performance \$O(n^2)\$ which will really hurt for large values of n.

You can improve this performance by converting \$m \times n\$ into \$m + n\$. Make a pass through one list computing a "signature" for each word. Store the signatures in a Python dict (dictionary) object mapping the signature to the original word(s) with that signature. Then make a pass through the second list, computing a "signature" for those words that can compare with the first signature. Check each word in the second list to see if its signature is in the dictionary, and store the results if so.

This process, if you can find the right signature, will work for a large number of problems.

You want a signature that does not depend on the ordering of the letters, since by definition one set of letters is scrambled. One easy mechanism would be to sort the letters into ASCII order, so that "banana" -> "aaabnn" for example.

Your code would then look like this:

signatures = dict()

for word in wordlist:
    sig = ''.join(sorted(word))
    signatures[sig] = word

found_words = []

for dwro in scrambled_words:
    sig = ''.join(sorted(dwro))
    if sig in signatures:
        found_words.append(signatures[sig])

Note: There's a potential issue, in that words like "keep" and "peek" are going to have the same signature, since they have all the same letters. You will have to decide how to handle that, but if you decide to maintain a list of all possible words for a signature, you should look at collections.defaultdict.