Here’s this past week’s NPR puzzle:<\/p>\n
Name a well-known movie of the past \u2014 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?<\/p><\/blockquote>\n
Brute-forcing this puzzle is easy but ineffective. We can get a list of movies from IMDB<\/a> 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.)
\n
\nWe 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<\/a>, we can actually get the members of any category. Check this out:
\n[python]
\nfrom nltk.corpus import wordnet as wn
\ndef get_category_members(name):
\n members = set()
\n synsets = wn.synsets(name)
\n for synset in synsets:
\n members = members.union(set([w for s in synset.closure(lambda s:s.hyponyms(),depth=10) for w in s.lemma_names]))
\n return members
\n[\/python]
\nEasy, right? If you typeget_category_members('animal')<\/code> it will give you everything that Wordnet thinks is an animal.<\/p>\nAnimal sounds are a little harder to come by. Typing
get_category_members('animal_sounds')<\/code> gets you the empty set, so we have to be a little more creative. Let’s check out the hypernyms<\/a> for a few animal sounds to give us an idea of what to do.
\n[python]
\nsounds = (‘meow’,’moo’,’baa’)
\nfor s in sounds:
\n syn = wn.synsets(s)
\n for x in syn:
\n print x, x.hypernyms()
\n[\/python]<\/p>\n\r\nSynset('meow.n.01') [Synset('cry.n.05')]\r\nSynset('meow.v.01') [Synset('utter.v.02')]\r\nSynset('moo.n.01') [Synset('cry.n.05')]\r\nSynset('moo.v.01') [Synset('utter.v.02')]\r\nSynset('baa.n.01') [Synset('cry.n.05')]\r\nSynset('bleat.v.02') [Synset('utter.v.02')]\r\n<\/pre>\nNow 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.<\/p>\n
Put it all together and you get something like this:
\n[python]
\nimport re
\nfrom nltk.corpus import wordnet as wn<\/p>\ndef is_good_movie(m):
\n ”’
\n Count a movie as “good” if it only has 7 letters and one space
\n ”’
\n m2 = re.sub(r'[^A-Za-z]+’,”,m)
\n if len(m2) == 7 and m.count(‘ ‘) == 1:
\n return True
\n else:
\n return False<\/p>\ndef get_category_members(name):
\n ”’
\n Use NLTK to get members of a category
\n ”’
\n members = set()
\n synsets = wn.synsets(name)
\n for synset in synsets:
\n members = members.union(set([w for s in synset.closure(lambda s:s.hyponyms(),depth=10) for w in s.lemma_names]))
\n return members<\/p>\ndef w1_in_w2(w1,w2):
\n ”’
\n Return leftover letters if all the letters from w1 are in w2
\n Return False otherwise
\n ”’
\n for c in w1:
\n if c not in w2:
\n return False
\n else:
\n pos = w2.find(c)
\n w2 = w2[:pos] + w2[pos+1:]
\n return w2<\/p>\n# Get a set of movies
\nmovies = []
\nwith open(‘RankedMovies.txt’,’rb’) as fid:
\n for x in fid.readlines():
\n x = x.rstrip(‘\\r\\n’)
\n movie, score = x.split(‘\\t’)
\n score = int(score)
\n if score >= 90:
\n movie = movie[:-7] # Remove the year
\n if is_good_movie(movie):
\n movies.append(movie)<\/p>\n# Let’s get a list of things that might be sounds
\nsounds_tmp = set()
\nfor x in (‘utter’,’cry’):
\n sounds_tmp = sounds_tmp.union(get_category_members(x))
\nsounds = frozenset([z for z in sounds_tmp if len(z) < 7])\n# Dictionary to help find anagrams\nsorted_to_word = dict()\nfor word in sounds:\n s = ''.join(sorted(word))\n try:\n sorted_to_word[s].append(word)\n except KeyError:\n sorted_to_word[s] = [word]\n\n# Get a set of animals\nanimals_tmp = get_category_members('animal')\nanimals = frozenset([y for y in animals_tmp if len(y) < 7])\n\n# Go through and give results\nfor movie in movies:\n for animal in animals:\n leftover = w1_in_w2(animal,movie.lower())\n if leftover:\n l = leftover.replace(' ','')\n s = ''.join(sorted(l)) \n try:\n new_words = sorted_to_word[s]\n except KeyError:\n new_words = [] \n for n in new_words:\n print \"%s => %s %s” % (movie, animal, n)<\/p>\n[\/python]
\nWhich produces the following result:<\/p>\n\r\nDas Boot => toad sob\r\nRed Dawn => wren add\r\nRed Dawn => wren add\r\nBig Stan => bat sign\r\nBig Stan => bat sing\r\nLa Bamba => lamb baa\r\nRio Lobo => loir boo\r\nDear God => dog read\r\nRapa Nui => arui pan\r\nGrey Owl => grey low\r\n<\/pre>\nSo 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.<\/a> It took me forever to get good lists for trees and herbs and spices, but with this approach the problem is completely trivialized<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Here’s this past week’s NPR puzzle: Name a well-known movie of the past \u2014 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 … Continue reading