from collections import defaultdict


def signature(s):
    """Returns the signature of this string.

    Signature is a string that contains all of the letters in order.

    s: string
    """
    t = list(s)
    t = ''.join(sorted(t))
    return t


def all_anagrams(filename):
    d = defaultdict(list)
    for line in open(filename):
        word = line.strip().lower()
        t = signature(word)

        # TODO: rewrite using defaultdict
        if t not in d:
            d[t] = [word]
        else:
            d[t].append(word)
    return d

def word_distance(word1, word2):
    assert len(word1) == len(word2)

    count = 0
    for c1, c2 in zip(word1, word2):
        if(c1 != c2):
            count += 1
    
    return count


def metathesis_pairs(d):
    """Print all pairs of words that differ by swapping two letters.
    d: map from word to list of anagrams
    """
    for anagrams in d.values():
        for word1 in anagrams:
            for word2 in anagrams:
                if word1 < word2 and word_distance(word1, word2) == 2:
                    print(word1, word2)


if __name__ == '__main__':
    sets = all_anagrams('words.txt')
    print(word_distance('conserve', 'converse'))
    metathesis_pairs(sets)