CarTalk's Homophones Puzzler: A Programmatic Solution

The puzzler:

This was sent in by a fellow named Dan O'Leary. He came upon a common one-syllable, five-letter word recently that has the following unique property. When you remove the first letter, the remaining letters form a homophone of the original word, that is a word that sounds exactly the same. Replace the first letter, that is, put it back and remove the second letter and the result is yet another homophone of the original word. And the question is, what's the word?

Now I'm going to give you an example that doesn't work. Let's look at the five-letter word, 'wrack.' W-R-A-C-K, you know like to 'wrack with pain.' If I remove the first letter, I am left with a four-letter word, 'R-A-C-K.' As in, 'Holy cow, did you see the rack on that buck! It must have been a nine-pointer!' It's a perfect homophone. If you put the 'w' back, and remove the 'r,' instead, you're left with the word, 'wack,' which is a real word, it's just not a homophone of the other two words.

I've used CMU Pronouncing Dictionary and modified it (manually) to keep alphabetical strings only.

My code:

def read_dict(file_path):
"""Reads 'CMU Pronouncing Dictionary' text file.

returns: dict mapping from a word to a string describing
its pronounciation

file_path: str
"""
fin = open(file_path)
pron_dict = {}

for line in fin:
index = line.find(' ')  # e.g. "AA  EY2 EY1"
word = line[:index]
pron = line[index+2:]
pron_dict[word] = pron

return pron_dict

def are_homophones(pron_dict, word1, word2, word3):
"""Returns whether 3 words are homophones.

pron_dict: dict
"""

for word in [word1, word2, word3]:
if not word in pron_dict:
return False

return pron_dict[word1] == pron_dict[word2] == pron_dict[word3]

def find_homophones_words(pron_dict):
"""Returns a list of words, where:

* word
* word with the first item omitted
* word with the second item omitted

are all homophones and existing in pron_dict.

pron_dict: dict
"""

homophones = []

for word in pron_dict:
first_word = word[1:]  # word with the first letter omitted
second_word = word[0] + word[2:] # word with the second letter omitted
if are_homophones(pron_dict, word, first_word, second_word):
homophones.append(word)

return homophones

homophones = find_homophones_words(pron_dict)

for word in homophones:
print([word, word[1:], word[0] + word[2:]])


Notes:

• I haven't, strictly, followed the puzzler. The code finds words satisfying the main requirements, except that the word is "one-syllable and five-letters".

• I'm a hobbyist and a beginner.

• I don't only want to optimize the code, but also my skills and style. Therefore any notes, advice and suggestions aren't only welcomed, but also encouraged!

• So, did you find the word this way? :) – Graipher Aug 22 '16 at 20:41
• @Graipher Oh! You are right, it's originally, an exercise from "Think Python". The author wanted us to list words satisfying these requirements. I think I should search the list to find only one-syllable ,five-letters words. :) – Mahmood Muhammad Nageeb Aug 22 '16 at 20:46

There's an efficiency improvement you could make to are_homophones: As is, you check that all three words are in pron_dict before checking that they're the same. However, it's better practice to catch errors using try blocks rather than trying to prevent them from happening (see this Stack Overflow post). A cleaner/faster way way to write this would be

def are_homophones(pron_dict, word1, word2, word3):
try:
return pron_dict[word1] == pron_dict[word2] == pron_dict[word3]
except KeyError:
return False


It's also good practice to use with blocks to open files so that Python automatically handles closing the file. With this change, read_dict becomes

def read_dict(file_path):
pron_dict = {}

with open(file_path) as fin:
for line in fin:
index = line.find(' ')  # e.g. "AA  EY2 EY1"
word = line[:index]
pron = line[index+2:]
pron_dict[word] = pron

return pron_dict

• That's good, I'll implement it. Thank you! :) – Mahmood Muhammad Nageeb Aug 22 '16 at 21:29

Some of your names are on the edge. They are descriptive enough that there is no problem with this short script, but it could be difficult in a longer script. For example, fin is what a fish has. Yes, I understand that it is file-in, but even that isn't very descriptive. I would try to find a name that describes what the file is for.

In read_dict(), you have an overly-complicated way to find the word and pronunciation. There is a format for the file. It has a word, two spaces, then its pronunciation. The easy way to do it is to use the built-in partition() method:

word, _, pron = line.partition("  ")


The _ is there because .partition() includes the separator in what it returns, but we are ignoring it.

When opening files, it is a good idea to use a with block. That takes care of closing the file if something bad happens.

find_puzzler_words() doesn't need to return a list. All you need is something that will give a for loop the right values. The more memory-efficient solution is to use a generator function. That means, instead of appending each word to res, yield it:

def find_puzzler_words(d):
...
# res = []  can be deleted now

for word in d:
...
if ...:
if ...:
yield word  # Instead of res.append(word)


It is shorter and more memory-efficient.

Note: I have attempted to put this in beginner language, but I'm afraid I probably didn't do a very good job. If you don't understand it now, I am open to answering any questions you may have.

Your program leaves out some things such as multiple pronunciations of the same word. A slight difficulty is that the duplicate words are something like "UPDATE(1)", where "(1)" isn't really part of the word. You can use a regular expression for this:

[^($$\d+$$)]*


Which means:

[^...]*  -> Anything except ... any number of times.  The ... is:
(...) -> A group which is:
$$-> A literal ( \d+ -> A number one or more times$$ -> A literal )


That way, the first word is matched as all normal characters except the group of characters such as (1), (2), (10), etc. You can then compile that regex and test each word with it. Now we have "UPDATE" and "UPDATE(1)" going under the same dictionary entry. Since we are now accounting for multiple pronunciations, we need a container for those pronunciations. I suggest a set. To make the dictionary create the sets automatically as they are needed, use collections.defaultdict:

from collections import default
import re

"""Reads 'CMU Pronouncing Dictionary' text file.

returns: dict mapping from a word to a set of strings describing
its pronunciations

path: str
"""

regex = re.compile(r"[^($$\d+$$)]*")
result = defaultdict(set)

with open(path) as f_in:
for line in f_in:
t = line.split()
word = regex.match(t[0].lower()).group()
pron = ' '.join(t[1:])

return result


Now that we have multiple pronunciations, we need to account for that in are_homophones(). That's actually very simple. Just change:

if d[word] == d[f_o_word] == d[s_o_word]:


to:

if d[word] & d[f_o_word] & d[s_o_word]:


You see, & (when used between sets) creates a new set of where the two sets intersect. If an intersection of all three sets still has something in it, we append word to res.

• I've refactored the code, after deleting the old question. And I don't use any single-character variable names anymore. Can you re-read it, if it doesn't bother you. I appreciate your review. – Mahmood Muhammad Nageeb Aug 22 '16 at 22:25
• I did re-read your question, but I didn't catch that. I have taken that out, and I also added a little bit more. – zondo Aug 22 '16 at 22:47