Finding anagrams - Empires strike back

Question

Recently as part of a job interview I was given the following coding task:

Attached is a gzipped text file of about 100,000 English words. Write a Python, C or C++ program that finds all the anagrams of the word "empires" that exist in the words file (just a reminder: an anagram is the result of rearranging the letters of a word to form a new word).

Your program should ideally take only a few seconds at most to run on modern hardware. The only inputs to your program should be the "empires" string and the words file. Send back your Python source files. Your solution should reflect the quality of work you would deliver to a customer, so keep in mind things like unit/acceptance tests, comments, PEP8, etc.

I submitted two files; one with the code, and one with tests (code below). I didn't pass on to the next stage of the interview, but can't figure out what, if anything, is wrong with my code. Any critiques would be appreciated.

anagrams.py:

#!/usr/bin/env python
"""Find anagrams in a file.

Given a term and a filename, find the anagrams of the term within the file.
An anagram must use each of the letters in the term exactly once.
"""

import sys

def usage():
    """Print a usage message."""
    print "Usage:"
    print "anagrams.py <term> <wordfile>"

def count_letters(word):
    """Count the occurrances of each letter in a word."""
    counts = {}
    for letter in word:
        if letter in counts.keys():
            counts[letter] += 1
        else:
            counts[letter] = 1
    return counts

def main(argv=None):
    """Handle arguments and execute."""
    if argv is None:
        argv = sys.argv
    if len(argv) != 3:
        usage()
        return 2

    term = argv[1]
    wordfilename = argv[2]
    try:
        grams = find_anagrams(term, wordfilename)
        report_grams(grams, term, wordfilename)
        return 0
    except IOError:
        print "Unable to open %s" % wordfilename
        return 2

def find_anagrams(term, wordfilename):
    """Actually find the anagrams.

    We use three tests to identify anagrams:
    First, we check that the number of letters is the same. This will eliminate
    the bulk of the words in the list, which is good for efficiency.

    Second, for each word that has the right overall number of letters, we
    check that the set of letters is correct. If there are any repeated letters,
    this will result in some false positives.

    The third test is to actually count the occurrances of each letter in
    the word, and check it against the correct collection of letter counts.

    For the word list and term supplied for this task, there isn't a huge
    difference in computational load between tests two and three, and we could
    eliminate test two without problems, but as the size of the list and
    the size of the word to be anagrammed both get larger, the second test
    will offer some speedup.
    """
    termset = set(term)
    termcounts = count_letters(term)
    grams = []

    with open(wordfilename, 'r') as wordfile:
        for word in wordfile:
            word = word.rstrip()
            if len(word) == len(term):
                # quickest way; gets some false positives
                if set(word) == termset:
                    # eliminate false positives with letter counts
                    if count_letters(word) == termcounts:
                        grams.append(word)
    return grams

def report_grams(grams, term, wordfilename):
    """Output the results."""
    print "There are %d anagrams of %s in %s:" % (len(grams),
                                                  term, wordfilename)
    for gram in grams:
        print gram

if __name__ == '__main__':
    sys.exit(main())

anagram_tests.py:

#!/usr/bin/env python
"""Testing for the anagrams module."""

import unittest
import os

import anagrams


class TestAnagrams(unittest.TestCase):
    """Test cases for anagrams modoule."""

    def setUp(self):
        """Set up for anagram tests.

        Create a file with some anagrams and some edge cases. Specifically, we
        want some words that use the same letters but in different quantities,
        and words that are subsets or supersets of the test word.
        """

        self.testword = 'all'
        self.testlist = 'testwords.txt'
        self.actual_anagrams = ['all', 'lal', 'all']
        wordlist = ['all', # the word itself
                    'ball', # superset of the word
                    'aal', # same set of letters, different counts
                    'ale', # extra letter
                    'lal', # an anagram
                    'lala', # too long
                    'al', # too short
                    'aaa', # subset of letters
                    'all'] # the word itself again
        wordlistfile = open(self.testlist, "w")
        wordlistfile.write("\n".join(wordlist))
        wordlistfile.close()

    def tearDown(self):
        """Clean up.

        Delete the file created in the setup phase.
        """
        os.remove(self.testlist)

    def test_count_letters(self):
        """Make sure we're counting letters the right way."""
        self.assertEquals(anagrams.count_letters(self.testword), {'a':1, 'l':2})

    def test_find_anagrams(self):
        """Test that we're getting the right anagrams from a sample list."""
        analist = anagrams.find_anagrams(self.testword, self.testlist)
        self.assertEquals(self.actual_anagrams, analist)

if __name__ == '__main__':
    unittest.main()

Answer 1

You know, Your code is good.... the algorithm is not the best, but the code is well presented, clear, and really, it's good. For an interview I would personally have ranked you as "good attention to detail, well structured, consistent, good".

Then, I would have asked you why you chose the algorithm you used. let's break down your process:

1. pre-process the 'term', in to it's length, and the count of each letter.
2. read the entire words file
3. discard wrong-sized words
4. check that each letter in the right-size word is in the term
5. make sure the letters appear the right number of times
6. report the matches.

There are two things I would point out in that general process, though.

1. you should probably have used a generator (yielded the grams, instead of appending them to a list). A generator would have identified you as a better candidate
2. hmmm.... there really isn't a 2. Let me just repeat 1. Use a generator.

As a general observation, your comments are very comprehensive, and this may sway people in different ways. I looked at them and thought "tl;dr", and read the code instead. I still have not read your comments.

Algorithm

This is likely what would be noticed the most. Your algorithm is both advanced, and also not ideal. For an interview, I really would not hold your answer against you, but, for your interest, if you sort the letters in the term, and then sort the letters in the same-length words, if the resulting strings are the same, they are anagrams. This is much simpler than the dictionary, and set approach.

Note, I would not hold that against you in an interview, but others may. I would look at your implementation and think: huh, they've demonstrated good use of various data structures, and, if I suggested sorting the term/words I am pretty sure they could fix it in no time....

Good things

To expand on the good things:

• you handle input arguments well
• you handle exceptions (IO problems), and even have exit codes
• your documentation is on all methods
• variables and methods have good names
• you do File IO properly
• you have test cases

Answer 2

@rolfl's answer is good, but I thought you might like to see a model implementation of the anagram-finding part of the problem. The key is to spot that sorting the letters in a word preserves the "is an anagram of" property, but maps each word to a canonical representative that can be compared for equality:

def anagrams(file, pattern):
    """Generate the words in file that are anagrams of pattern."""
    pattern = sorted(pattern)
    for line in file:
        for word in line.split():
            if sorted(word) == pattern:
                yield word

With this code, the rest of the program is easy, for example:

>>> with open('/usr/share/dict/words') as f: print(*anagrams(f, 'empires'))
emprise imprese premise spireme

The approach in the post, of counting the number of occurrences of each letter, also turns each word into a canonical representative, but for typical word lengths it's slower than sorting (because it spends more time running slower Python bytecode and less time in the faster lower-level implementation). If you're going to go that way, then it makes sense to use the built-in collections.Counter to do the counting, like this:

from collections import Counter

def anagrams(file, pattern):
    """Generate the words in file that are anagrams of pattern."""
    pattern = Counter(pattern)
    for line in file:
        for word in line.split():
            if Counter(word) == pattern:
                yield word

but I find that this takes about four times as long as the version with sorted.

Answer 3

In addition to the other two solutions:

Your find_anagrams method itself contains the file IO as well as the actual logic for identifying anagrams.

While this is specifically what was asked for, an additional level of abstraction wouldn't have hurt in this case. Decoupling the logic from file IO provides better maintainability, should the customer ask for different data sources later on.

This also reflects in your test cases, as you can not differentiate between tests failed due to bad IO and faulty logic. In your case, even lacking write permission can cause the test suite to fail even though these permissions are not required for regular execution.

Your tests also omitted the third parameters for the asserts where you could have specified what the failure of a certain assert means.

What else didn't you cover? E.g. case conflicts, neither handled in your code nor covered in the unit tests.