Director, anagram, film award

Welcome back to Natural Language Puzzling, the blog where we use natural language processing and linguistics to solve the Sunday Puzzle from NPR. Here's this week's puzzle:

This week's challenge comes from listener Bob Weisz. Take the name of a major film director. Drop the last six letters of his name, and rearrange what remains. You'll get the name of a major film award -- for which this director has been nominated six times. Who is he and what is the award?

Full disclosure---this one's probably pretty easy to solve with just your brain, assuming you know a little about movies and directors. Nonetheless, let's break this down and enumerate the data and functions we'll need in order to find a solution programmatically.

• D: a list of film directors
• note the "he"---we're looking for male directors;
• "drop the last six letters"---the name should probably be at least 10 letters so we have enough left over to spell an award;
• "this director has been nominated six times"---we can probably assume the six nominations represent six different movies, so this director has at least six movies to his credit;
• Options for acquiring this list:
• brainstorm our own
• search the web for a list of top directors
• ask an LLM to provide a list of directors that meet the above criteria
• This was my approach, and I got a pretty good list:
• ['Steven Spielberg', 'Martin Scorsese', 'Akira Kurosawa', 'Stanley Kubrick', 'Alfred Hitchcock', 'Quentin Tarantino', 'Ridley Scott', 'Francis Ford Coppola', 'Clint Eastwood', 'Woody Allen', 'Ingmar Bergman', 'Federico Fellini', 'Billy Wilder', 'Christopher Nolan', 'Pedro Almodóvar', 'Wes Anderson', 'Paul Thomas Anderson', 'David Fincher', 'Joel Coen', 'Ethan Coen', 'Ang Lee', 'Jean-Luc Godard', 'Robert Altman', 'John Ford', 'George Lucas', 'Frank Capra', 'Roman Polanski', 'Michael Haneke', 'Ken Loach', 'Spike Lee']
• A: a list of major film awards
• Our options for acquiring this list are the same; here's my list:
• ['Academy Award', 'Oscar', 'BAFTA', 'Golden Globe', 'Cannes Film Festival Award', 'Palme d Or', 'Directors Guild of America Award', 'Screen Actors Guild Award', 'Critics Choice Movie Award', 'Independent Spirit Award']
• Obviously, some of these are unlikely solutions---we probably won't find an anagram of 'Independent Spirit Award'. 
• anagram(word): a function for generating anagrams
• While we've done this before, it's typically when we aren't confident that we have complete lists for solving both sides of the equation, i.e., it's an open class problem. This technically is a closed class problem, because we can't ever be certain our lists of directors or awards is complete. However, I'm confident that our lists are adequate here. This means we don't actually need to form valid anagrams with our function---we don't need to confirm that the anagram string is a real word or name in some lexicon. So, let's instead take the following approach:
• compare(d,a):
• The function we need is simpler than anagramming. We need to lowercase the strings, remove any spaces, punctuation, and diacritics, and remove the final 6 letters. Python can handle all that easily, and I like to use a package called slugify for changing things like "ó" to "o". Our function here doesn't need to form valid words, just sort the letters alphabetically. When we have the solution, the sorted list of letters for the director will match the sorted list for the award.

Using the above approach, I've put together a python script that is spitting out the correct solution. Have you solved the puzzle? Check back here after Thursday's NPR submission deadline (no spoilers here!) and I'll link my script and post my solution. Good luck!

The deadline for NPR submissions has passed, so click the spoiler button below to see my solution, and click here to see my script.

PEDRO ALMODOVAR --> PEDROALM --> PALME D'OR

Country anagrams rhyming with "Spain"

Welcome back to Natural Language Puzzling, the blog where we use linguistics, natural language processing (NLP), language modeling, and artificial intelligence to solve the weekly challenge from NPR's Sunday Puzzle. Let's dive into the latest puzzle:

This week's challenge comes from Andrew Tuite, of Chicago. There are four countries whose names have one-syllable anagrams that rhyme with "Spain." What are they?

As usual, let's break this one down and determine what tools and resources we need to solve it.

• C: a list of countries
• This is a closed class---we can easily obtain a complete list.
• The United Nations recognizes 195 countries.
• We'll use some heuristic to filter this down to strings that can be anagrammed to a one-syllable word
• Wikipedia claims a handful of 10 and 11 letter words might be pronounced as one-syllable
• I'll limit my list of countries to those with seven or fewer letters
• Note that the anagram must be one-syllable, but the original string might be more than one syllable, as in MASTER --> STREAM
• Anagrammer: a function to anagram strings
• This will need a lexicon to ensure that the anagrams are real words.
• It will also need a pronunciation dictionary to ensure that the anagrams rhyme with Spain.
• We can simply use the pronunciation dictionary as the lexicon, too.
• As we've done in the past, I'll be using the CMU Pronouncing Dictionary.
• Python script: We'll need a bit of scripting to tie all this together:
• Iterate through the country names and filter out strings longer than seven letters;
• Generate possible anagrams and keep only those found in the dictionary;
• Look up pronunciations and determine if they rhyme with Spain. CMU uses Arpabet, which represents Spain as SP EY N
• We'll need to find any anagrams that end with -EY N.

That's the approach I'll be taking. Would you do it differently? Leave your comments below. And check back here after the NPR deadline for submissions on Thursday to see my solution. Happy Puzzling!

The deadline for NPR submissions has passed, so click the spoiler button below to see my solution, and click here to see my script.

CHINA --> CHAIN / CH EY N

IRAN --> RAIN / R EY N

NEPAL --> PLANE / P L EY N

NIGER --> REIGN / R EY N

Kinda neat that the solution includes homophones, huh?

Animal (5) --> bird (7) --> animal (9)

It's Monday Funday here at Natural Language Puzzling, the blog where we explore natural language processing (NLP), artificial intelligence (AI), language modeling and linguistics for the purposes of solving the weekly challenge from NPR's Sunday Puzzle. Welcome back! Let's take a crack at this week's challenge:

This week's challenge comes from Philip Goodman, of Binghamton, N.Y. Name an animal in five letters. Add two letters and rearrange the result to name a bird in seven letters. Then add two letters to that and rearrange the result to name another animal in nine letters. What creatures are these?

How should we approach this one? It basically follows the classic Sunday Puzzle pattern:

Take a thing from Class A and apply a transformation to yield a thing from Class B.

In this case, it's a little more complicated but really we're just adding a second transformation from Class B to Class C (which is similar to Class A, but the strings are nine letters instead of five).

As you can probably see, this one is relatively light on NLP, AI, and linguistics. We really just need good lists of birds and animals to start with, and it'll all be string and list manipulation from there.

Here's the approach I plan to take. I'll need these things:

• A: A big ol'  list of animals
• I've cobbled one together from lists on the web
• You could also ask your favorite LLM chatbot
• When we load the list to work with it in python, we'll filter it out into a list of five-letter words and another list of nine-letter words
• B: A big ol' list of birds
• Again, I found multiple different lists on the web and combined them, then removed duplicates, lowercased everything, etc.
• We'll filter this one and keep only the birds with seven-letter names
• check_letters: We need some kind of function to compare the letters in each of the strings in the above lists
• We can brute force this as it's not super computationally heavy and it's a one-off solution anyway.
• I'll take each five-letter animal (i.e., "for m in five_letter_animals:")
• split it into a list of letters
• take each (seven-letter) bird
• split it into a list of letters
• take each letter from the animal and try to remove it from the list of bird letters
• if only two letters remain in the bird letter list, we keep this pair as a possible solution
• Then we can more or less repeat this process, starting with the bird list and nine-letter animal list;
• Again, if we can remove all the letters from the shorter word and we're left with two letters from the longer word, we have a possible solution.
• We'll know the solution when we have a bird that is a possible solution in both of these comparisons

I'm happy to report that the approach above worked for me and I have the solution! I'll be keeping it (and my python script) to myself until after the Thursday 3pm ET deadline for submitting solutions to NPR, as I wouldn't want to get on host Will Shortz' naughty list for giving spoilers. But please check back after then if you'd like to see exactly how I solved it. Good luck, Puzzlers!

The deadline for NPR submissions has passed, so click the spoiler button below to see my solution, and click here to see my script.

LLAMA --> MALLARD --> ARMADILLO

European tourist site, planting medium

It's Monday, and you Puzzlers know what that means. Welcome back to Natural Language Puzzling, the blog where we use natural language programming (NLP), language models and tools and good old fashioned linguistics to solve the weekly Sunday Puzzle from NPR. Here is this week's puzzle:

This week's challenge comes from listener Jessica Popp, of Indiana, Pa. Name a famous European tourist site in nine letters. Rearrange its last four letters to name something that its first five letters can be planted in.

It's been a few weeks since we've had a "normal" puzzle like this one. It follows the pattern of many Sunday Puzzles: take thing from category A, apply a prescribed transformation, get thing from category B.

In these kinds of puzzles, we often start with lists: a list for Category A and/or a list for Category B. Then we need some kind of function to apply the transformation. Finally, we either check to see if the result is in our list for Category B; if we don't have a list for Category B, we use some kind of language model to evaluate each transformed candidate in an appropriate context and see how well it fits.

This time around, we'll need:

• E: a list of European tourist sites
• we can search the web for existing lists
• we can ask a chatbot LLM to generate a list for us
• we can try to cobble one together ourselves
• we'll need to filter this list to only nine-letter entries
• Note that LLMs are still not very good at returning words of specified length
• P: a list of things that some unknown thing can be planted in
• this one probably makes sense to ask chatbot LLM for
• we could also query a non-chatbot LLM to fill in blanks for us
• again, we'll need to filter this by length--for 4-letter words this time
• functions/tools:
• from my reading of the puzzle, the first five letters of the European tourist site should be something that can be planted; thus, the first five letters alone should be a common noun, so we could start with a function that takes the first five letters of each item in list E and checks to see if they make a valid word.
• if we find a valid word, we can:
• generate all the permutations of the last four letters
• keep only those that are valid words
• use a sentence template or templates with an LLM to see how likely the candidates are in context, e.g.:
• I know the perfect [BLANK] to plant the new [BLANK] in.
• In theory, the solution would be among the candidate pairs that result in the lowest perplexity score from the above sentence.

This is the approach I'll be taking. How would you do things differently? Share your thoughts in the comments. I'll be back with an update after the Thursday NPR submission deadline (no spoilers here!) to share my scripts and my solution (if I manage one). Good luck!

The deadline for NPR submissions has passed, so click the spoiler button below to see my solution.

ACROPOLIS --> ACROP, SOIL

Milk and Beef

Hello Puzzlers. We're almost at this week's NPR submission deadline, but let's get a quick solution posted for posterity.

If you're new to the blog, welcome! Join us here each week as we use Natural Language Processing (NLP), language modeling and linguistics to solve the Sunday Puzzle from NPR. Here's this week's puzzle:

This week's challenge comes from listener Andrew Chaikin, of San Francisco. Think of an 11-letter word that might describe milk. Change one letter in it to an A, and say the result out loud. You'll get a hyphenated word that might describe beef. What is it?

For this puzzle, the solution pretty quickly jumped out at me, and maybe it did for you too. Regardless, let's walk through how we can use our tools and skills to get a solution. Here's what we need:

•  M, a list of words that might describe milk
• We can ask an LLM directly for this list, or
• We can query an LLM to fill in blanks for us with the top candidates, e.g.:
• "Some milk is more BLANK than other milk."
• "Milk sold in stores must be BLANK."
• (I asked an LLM to give me a list, and I got a list of about 90 words)
• We'll need to filter this contain only 11-letter words (because LLMs are terrible about that)
• B, a list of words that might describe beef
• Ideally, we'll have a list for this side of the equation, too, then we'll check to see if we can apply the transformation to a word in M and match it to a word in B
• Alternatively, we can simply take each candidate in M, then apply the transformation ("change one letter in it to an A and say the result out loud") and evaluate the result in the context where it is describing beef.
• Of course this is tricky, because we're not matching strings, we're matching pronunciations; see the next point.
• transform(): We need a function to apply the prescribed transformation: "change one letter in it to an A and say the result out loud"
• How would we do this programmatically? We might need some guidelines to keep this manageable.
• Firstly, I think we probably want to restrict our replacement targets to other vowels.
• Secondly, the puzzle asks us to replace a letter with another letter (A), but we're only interested in the resulting pronunciation, not the resulting spelling. So we need to operate on pronunciations. We can use the CMU Pronouncing Dictionary as we have in past puzzles.
• The CMU dictionary uses ARPAbet symbols, so we need a list of all the ARPAbet symbols that an "A" can correspond to. Then we can generate new pronunciations by replacing each vowel sound in the pronunciation one by one with these various "A" vowel sounds.
• A few ARPAbet examples:
• AE T : "at"
• EY T : "ate"
• TH EY T A : "theta"
• Next we need a way to convert the pronunciation symbols back into a spelling ("phoneme-to-grapheme"). In our case, we'll probably simply want to query the CMU Dictionary to see if the new pronunciation exists in the dictionary, then we pull the corresponding spelling.
• One more twist: Note that the puzzle specifies we'll get a hyphenated word. The hyphenated word is probably not going to have its own entry in the pronunciation dictionary. This means we'll need to try tokenizing the new pronunciation; in other words, we need to split it in two, then try finding each of the two pronunciations in the dictionary. We could simply brute force this, trying the split at each possible location (between syllables).  
• evaluation: Let's imagine the above steps have gone well, and we've found a number of potential spellings for the "hyphenated word that might describe beef". Now we need a language model to evaluate each of the candidates in context. As we've done in the past, we can insert each candidate into a set of sentence templates and get a perplexity score for each, and ideally, the correct solution should have the lowest or near lowest perplexity. Our templates might be something like these:
• "That was some of the best [BLANK] beef I have ever had."
• "[BLANK] beef is expensive but usually high quality."
• "The supermarket is having a special on [BLANK] beef this week."

That's how I'd go about approaching this one systematically. In truth, it would be overkill for this easier-than-usual puzzle. Alternatively, we could simply start with M (our list of milk words) and from there, most people would spot the solution right away. I went ahead and did just that; if you'd like to give it a shot, or even flesh out the full approach described above, you can start by running my script to get a list of 11-letter milk-related words. It only returns 10 words, so I'm confident you'll recognize the solution.

The deadline for NPR submissions has passed, so click the spoiler button below to see my solution.

pasteurized --> *pasteurazed ("pasture-raised")

Smooth booth

It's Monday, Puzzlers, and you know what that means! Welcome to Natural Language Puzzling, the blog where we use natural language processing (NLP), linguistics, data science, language modeling, programming and our own noggins to solve the weekly Sunday Puzzle from NPR. Here's this week's puzzle:

This week's challenge comes from listener Dan Asimov, of Berkeley, Calif. In English the two-letter combination TH can be pronounced in two different ways: once as in the word "booth," the other as in "smooth." What is the only common English word, other than "smooth," that ends in the letters TH as pronounced in smooth?

Well, this is certainly a diversion from the usual Sunday Puzzle format, which involves taking one string of text, applying a prescribed transformation and generating another string of text.

So what do we need to solve this puzzle?

Really only one thing: a robust pronunciation dictionary. For that, we can turn to an old friend-- the Carnegie-Mellon University (CMU) Pronouncing Dictionary. You can read more about that on the project website, or simply download the file from GitHub.

Now that we have the dictionary, we can navigate to it from the command line. From that location, we can query the pronunciations for "booth" and "smooth".

Mac:cmudict-master puzzler$ grep 'smooth ' cmudict-dict.txt 

smooth S M UW1 DH

Mac:cmudict-master puzzler$ grep 'booth ' cmudict-dict.txt 

booth B UW1 TH

tollbooth T OW1 L B UW2 TH

This shows us how the phonemes in question are represented in the CMU Pronouncing Dictionary, which uses the ARPAbet symbols. We can see that "smooth" ends with the symbol "DH", so our target word (the only common English word, other than "smooth," that ends in the letters TH as pronounced in smooth) must also end with the symbol "DH".

The next step is simply to query the dictionary file for any pronunciations that end in "DH". For reference, here's what the body of the file looks like:

carousel K EH1 R AH0 S EH2 L

carousing K ER0 AW1 Z IH0 NG

carow K AE1 R OW0

carozza K ER0 AA1 Z AH0

carp K AA1 R P

carpal K AA1 R P AH0 L

We can use grep plus the "$" anchor to ensure that we find "DH" at the end of a line:

Mac:cmudict-master puzzler$ grep 'DH$' cmudict-dict.txt 

bathe B EY1 DH

blithe B L AY1 DH

blythe B L AY1 DH

boothe B UW1 DH

bothe B OW1 DH

breathe B R IY1 DH

clothe K L OW1 DH

...

I truncated the output so as not to spoil the solution. As we can see, the results shown all end in "-the", whereas the target word should end in "-th". In fact, there's only one word (other than "smooth") in the output of the grep query that fits the bill, so that must be the solution. I'll be back after NPR's Thursday deadline for submissions to share that solution. Good luck, Puzzlers!

The deadline for NPR submissions has passed, so click the spoiler button below to see my solution.

The CMU Pronouncing Dictionary gives these four pronunciations for "with". Two of them fit the bill:

with W IH1 DH

with(2) W IH1 DH

with(3) W IH0 TH

with(4) W IH0 DH

'Jon Stewart' & classic movies

Welcome back, Puzzlers! It's Monday Funday at Natural Language Puzzling, the blog where we use natural language processing, computational linguistics and data science to solve the weekly Sunday Puzzle from NPR. Here is this week's puzzle:

This week's challenge comes from listener Al Gori, of Cozy Lake, N.J. Take the name JON STEWART, as in the comedian and TV host. Rearrange the letters to spell the titles of three classic movies. One of the titles is its familiar shortened form.

 Let's break this down. Here's what we need:

• M: A list of "classic movies" to iterate through
• Find a list online
• Build a list ourselves
• Ask an LLM for a list
• I extracted a list of all the titles from this spreadsheet of every Oscar winner and nominee
• (We don't know for certain that the movies in the solution are Oscar winners or nominees, but it's a fairly safe bet and a good place to start.)
• fx(M): We need a function that can generate combinations of three movie titles from our list, such that:
• the total length of all 3 movie titles is 10 letters (len('jonstewart'))
• we can use this as a first filter
• then we check that the letters in the combined movie titles are the same as the letters in 'jonstewart'

Clearly, this puzzle is on the easier side, with minimal NLP required. The critical piece here is the starting list of movies. I have my solution, and I'll be back after the Thursday NPR deadline to share it along with my script. In the meantime, if you'd like to try this yourself, you can start from my list of about 3700 Oscar winners and nominees.

Update & Solution

The deadline for submissions has passed, so click the spoiler button below if you want to see my answer. Click here for my python script on GitHub. See you next week!

• JON STEWART --> JAWS, E.T., TRON
  

Singer/actress, dangerous object

Greetings, Puzzlers, and welcome back to Natural Language Puzzling, the blog where we use natural language processing, linguistics and data science to solve the Sunday Puzzle from NPR!

Here's this week's puzzle:

This week's challenge comes from listener Dennis Burnside, of Lincoln, Neb. Think of a famous singer and actress, first and last names, two syllables each. The second syllable of the last name followed by the first syllable of the first name spell something that can be dangerous to run into. What is it?

Let's break this down and determine how we'll approach solving the puzzle.

This is what I call a "Classic format" Sunday Puzzle: Take thing from Class A (singer/actress), apply transformation, yield thing from Class B (something dangerous to run into).

So here's what we'll need to solve it:

• A: list of singer/actresses
• This is an open class, so we'll need robust coverage
• We could try finding an existing list online, or cobbling one together from various lists and listicles
• We could ask a chatbot LLM like ChatGPT/Gemini/etc. to give us a list
• B: list of things that are dangerous to run into
• Also open class
• A little vague. Is it inherently dangerous, or only dangerous if you run into it?
• e.g., knife vs tree
• Is there wordplay here? (probably not)
• e.g., ex-spouse
• We don't actually need a list here a priori. We can iterate through list A and evaluate the resulting candidates for "something dangerous to run into".
• We simply need an LLM that can provide us with perplexity scores for sentences
• We use a sentence template:
• "Stay alert because running into [BLANK] can be very dangerous."
• We plug the string derived from combining the two syllables from the singer/actress into the blank, and get a score representing how (im)probable the resulting sentence is (i.e., its perplexity).
• Ideally, the correct solution will be among those ranked as most probable here.
• Functions:
• Syllabification:
• We need the ability to divide each string into syllables. This is for counting and for forming the "something dangerous" string.
• This seems simple but it can be messy...
• We're dealing with names, which can have highly variable orthography and phonology, and pronunciation dictionaries are certain to be missing lots of less frequent names.
• It's not always easy to determine syllables based on orthography. A sequence of vowels could be a single syllable (a diphthong as in train) or multiple syllables (a hiatus as in trivia)
• I'm going to rely on the CMU Pronouncing Dictionary, which we can call from within NLTK in Python. Because each syllable is marked with 0, 1 or 2 for stress, we can simply count the number of numeral digits in the pronunciation. For example, the pronunciation for trivia is given as ['T', 'R', 'IH1', 'V', 'IY0', 'AH0'].
• For strings that are out of vocabulary (OOV), I'll back off to a rule-based approach that tries to count syllables. I plan to use the syllapy library, as described here.
• String transformation:
• We also need a simple function to recombine the syllables as described: second syllable of the last name followed by the first syllable of the first name.
• We'll handle this in python as well.
• Perplexity scoring:
• As mentioned above, we'll need an LLM that can give us perplexity scores for sentences. I'm going to use a huggingface transformers implementation of a GPT model. (But stay tuned--I'm building implementations of several other LLMs and we'll be evaluating those in future puzzling!)

That more or less covers my approach. Would you handle this differently? Do you think an LLM could solve this puzzle outright? (So far, the ones I've tried have not managed a solution).

Please leave your comments and insights (but no spoilers please). I'll be back after NPR's Thursday deadline for submissions to share my solution and my implementation. Good luck!

Update & Solution

The deadline for submissions has passed, so click below if you want to see my answer. See you next week!

4.247	Barbra Streisand	Stay alert because running into a sandbar can be very dangerous.
4.943	Linda Ronstadt	Stay alert because running into a stadtlin can be very dangerous.
5.071	Dolly Parton	Stay alert because running into a tondol can be very dangerous.
5.116	Alanis Morissette	Stay alert because running into a setteala can be very dangerous.

I confess that I cheated here; I tried several syllabification/hyphenation tools, and none of them could return ['strei', 'sand'] for 'Streisand'. They would not recognize the string and thus return 'Streisand' unchanged.

I also tried using a grapheme-to-phoneme tool (https://github.com/Kyubyong/g2p) as a back-off for out of vocabulary (OOV) items that are not in the CMU dictionary (which most syllabification tools rely on). However, this tool and others like it return the phonemic transcription of the syllables, not the graphemic or orthographic transcription. So it could return ['STRAY1', 'ZAH0ND'], but not ['strei', 'sand'].

In other words, for OOVs, there's no tool to map from a g2p generated phonetic transcription of syllables back to an original orthographic spelling which is split into syllables. I suspect this won't be the last time we'll need to do this for the Sunday Puzzle, so I'm currently working on such a tool and I'll share it soon when it is ready.