Here’s this past week’s NPR puzzle:

Name a well-known movie of the past — two words, seven letters in total. These seven letters can be rearranged to spell the name of an animal plus the sound it makes. What animal is it?

Brute-forcing this puzzle is easy but ineffective. We can get a list of movies from IMDB and see which of the seven-letter ones can anagram into two words. But you don’t want to do this, because it will force you to sift through a ton of results. Can we do better? (Yes, we can.)

We don’t want to use *all* movies, and *all* words if we can avoid it. Can we get a list of “well-known” movies, animals, or animal sounds? The first is the easiest; instead of downloading the movies.list file from the IMDB link above, download the ratings.list file and only consider movies that have above a certain threshold of votes. I actually rated the movies on a scale of 1-100 using this method, so that the cutoffs make more sense. Now, how about the list of animals and animal sounds? Well, thanks to Python/NLTK and a terrific hint from Stack Overflow, we can actually get the members of any category. Check this out:

from nltk.corpus import wordnet as wn
def get_category_members(name):
    members = set()
    synsets = wn.synsets(name)
    for synset in synsets:
        members = members.union(set([w for s in synset.closure(lambda s:s.hyponyms(),depth=10) for w in s.lemma_names]))
    return members

Easy, right? If you type get_category_members('animal') it will give you everything that Wordnet thinks is an animal.

Animal sounds are a little harder to come by. Typing get_category_members('animal_sounds') gets you the empty set, so we have to be a little more creative. Let’s check out the hypernyms for a few animal sounds to give us an idea of what to do.

sounds = ('meow','moo','baa')
for s in sounds:
    syn = wn.synsets(s)
    for x in syn:
        print x, x.hypernyms()

Synset('meow.n.01') [Synset('cry.n.05')]
Synset('meow.v.01') [Synset('utter.v.02')]
Synset('moo.n.01') [Synset('cry.n.05')]
Synset('moo.v.01') [Synset('utter.v.02')]
Synset('baa.n.01') [Synset('cry.n.05')]
Synset('bleat.v.02') [Synset('utter.v.02')]

Now we’re on to something! Each of these of course can be a noun or a verb, but they all fall under the umbrella of “cry” or “utter.” So if we take category members of those two words — well, it’ll give us too much, but that’s okay. At least we should have all the relevant animal sounds in there.

Put it all together and you get something like this:

import re
from nltk.corpus import wordnet as wn

def is_good_movie(m):
    '''
    Count a movie as "good" if it only has 7 letters and one space
    '''
    m2 = re.sub(r'[^A-Za-z]+','',m)
    if len(m2) == 7 and m.count(' ') == 1:
        return True
    else:
        return False
        
def get_category_members(name):
    '''
    Use NLTK to get members of a category
    '''
    members = set()
    synsets = wn.synsets(name)
    for synset in synsets:
        members = members.union(set([w for s in synset.closure(lambda s:s.hyponyms(),depth=10) for w in s.lemma_names]))
    return members

def w1_in_w2(w1,w2):
    '''
    Return leftover letters if all the letters from w1 are in w2
    Return False otherwise
    '''
    for c in w1:
        if c not in w2:
            return False
        else:
            pos = w2.find(c)
            w2 = w2[:pos] + w2[pos+1:]
    return w2

# Get a set of movies
movies = []
with open('RankedMovies.txt','rb') as fid:
    for x in fid.readlines():
        x = x.rstrip('\r\n')
        movie, score = x.split('\t')
        score = int(score)
        if score >= 90:
            movie = movie[:-7] # Remove the year
            if is_good_movie(movie):
                movies.append(movie)

# Let's get a list of things that might be sounds
sounds_tmp = set()
for x in ('utter','cry'):
    sounds_tmp = sounds_tmp.union(get_category_members(x))
sounds = frozenset([z for z in sounds_tmp if len(z) < 7])
# Dictionary to help find anagrams
sorted_to_word = dict()
for word in sounds:
    s = ''.join(sorted(word))
    try:
        sorted_to_word[s].append(word)
    except KeyError:
        sorted_to_word[s] = [word]

# Get a set of animals
animals_tmp = get_category_members('animal')
animals = frozenset([y for y in animals_tmp if len(y) < 7])

# Go through and give results
for movie in movies:
    for animal in animals:
        leftover = w1_in_w2(animal,movie.lower())
        if leftover:
            l = leftover.replace(' ','')
            s = ''.join(sorted(l))    
            try:
                new_words = sorted_to_word[s]
            except KeyError:
                new_words = [] 
            for n in new_words:
                print "%s => %s %s" % (movie, animal, n)
                        

Which produces the following result:

Das Boot => toad sob
Red Dawn => wren add
Red Dawn => wren add
Big Stan => bat sign
Big Stan => bat sing
La Bamba => lamb baa
Rio Lobo => loir boo
Dear God => dog read
Rapa Nui => arui pan
Grey Owl => grey low

So there you have it. In about a second you get only 10 results and it’s easy to pick out the right one. I’m stoked about this new method to find members of a category; I sure wish I had it when I was working on the challenge to name a tree whose letters can be rearranged to spell two herbs or spices. It took me forever to get good lists for trees and herbs and spices, but with this approach the problem is completely trivialized.