Musical composition, music store purchase (Preview)

Happy Tuesday, Puzzlers. Let's get cracking on the latest Sunday Puzzle from NPR:

This week's challenge comes from listener Ari Carr, of Madison, Wis. Name a form of musical composition. If you say the word quickly, you'll name something, in two words, that you might buy in a music store. What is it?

Oh boy, this one seems a little more challenging than some of the string manipulation type puzzles we often deal with here. The good news is that we'll probably want to dip a little deeper into our NLP toolbox to solve it.

Let's break down what we need and how we might obtain it here:

• C: a list of forms of musical composition;
• I'm assuming this means things like concerto, aria, song, hymn, symphony.
• How do we get this list?
• We might find one on Wikipedia or elsewhere online; it's worth searching for.
• We can generate one by querying Word2Vec for similar words to concerto, etc.
• We can use BERT or SBERT in mask mode, where it fills in a blank ("[MASK]"). So we'd feed it some sentences like:
• The prolific composer wrote more dozens of [MASK] in his lifetime.
• I could hear an upbeat [MASK] playing softly over the stereo downstairs.
• B: a list of things one can buy in a music store, in two words;
• Potential pitfalls:
• What's a "music store"? A record store? A musical instrument store? I think we'd better assume it could be either.
• "in two words": This looks tricky, because it could mean terms like "bass guitar" but it could also include things like "a guitar".
• We can try the Word2Vec and SBERT methods for this list too (I need to check that I can get two word terms from these tools).
• "If you say the word (in C) quickly, you'll name something, in two words" in B.
• This is the transformation function, like we see in about 90% of these puzzles.
• This time, however, the transformation applies not to the spelling string but its corresponding pronunciation string. In other words, we need a pronunciation dictionary.
• Here's an example of a past post where we've used the CMU Pronouncing Dictionary. I plan to use it again for this puzzle.
• Regarding the "say the word quickly" bit, I plan to simply ignore the vowels in the pronunciation strings, so we'll also want a function like strip_vowels(pronunciation).

That covers the setup. Assuming we have the resources above, let's look at how we'd use them to arrive at a solution. Here's some pseudo code:

• for x in C:
• qp_x = pronunciation[x]  #"qp" for "quick pronunciation"
• qp_x = strip_vowels(qp_x)
• for y in B:
• qp_y = pronunciation[y]
• qp_y = strip_vowels(qp_y)
• if qp_y == qp_x:
• print(x, y)

It's possible we'll get some false positives here, so we'll print out any matches and see if they make sense. If we don't get any matches, we may want to relax the matching. Instead of looking for a perfect match, maybe we want something more like an edit distance. I'll probably keep it simple---check that most of the phonemes (minus vowels) in x also appears in y (and vice versa).

Good luck! I'll be back with the solution and my approach implemented in python after the Thursday deadline for submissions.

--Levi

US city, cardinal number, ordinal number (Solution)

Ready to solve this week's Sunday Puzzle from NPR? Spoiler alert---I'll reveal my solution at the end of this post. Here's the puzzle again:

This week's challenge comes from listener Ben Austin, of Dobbs Ferry, N.Y. Take the name of a major American city. Move one of its letters three spaces later in the alphabet. Embedded in the resulting string of letters, reading left to right, is a cardinal number. Remove that number, and the remaining letters, reading left to right, spell an ordinal number. What city is it, and what are the numbers?

In my preview post, I spelled out the basic approach I'd use: iterate through city names, iterate through their letters, shifting each letter forward alphabetically three places; iterate through cardinal numbers ("one" through "one hundred") and see if it's embedded in the "shifted" city; if so, remove it and see if the remaining string is in our list of ordinal numbers. Pretty straightforward.

Well, I assembled the necessary lists and implemented my approach in a solver script, and it worked like a charm. I found and used a CSV of the 1,000 biggest cities in the USA, which you can download here. I uploaded the rest to the GitHub for this puzzle blog: cardinal numbers list, ordinal numbers list, and the solver script.

How about you? Did you solve this one?

Okay, spoilers ahead! Keep scrolling to see my answer:

SOLUTION: 'Fort Worth' --> 'foutworth', which contains 'two'; removing 'two' yields 'fourth'

US city, cardinal number, ordinal number (Preview)

After giving us the last week off, Will Shortz is back with this week with a new Sunday Puzzle from NPR:

This week's challenge comes from listener Ben Austin, of Dobbs Ferry, N.Y. Take the name of a major American city. Move one of its letters three spaces later in the alphabet. Embedded in the resulting string of letters, reading left to right, is a cardinal number. Remove that number, and the remaining letters, reading left to right, spell an ordinal number. What city is it, and what are the numbers?

What do we need to solve this puzzle?

• M: a list of major American cities;
• Does "American" mean "USA" here? Maybe this list needs major cities from throughout North and South America;
• C: a list of cardinal numbers spelled out in letters; probably 0-100 should be enough;
• O: a list of ordinal numbers spelled out in letters; probably 1-100 should be enough;
• shift_letter_3: a function that shifts a letter 3 places later in the alphabet;

First, for M, C, and O, we'll want to clean up the text:

1. lowercase
2. remove spaces
3. remove non-letters
4. convert accented characters to simple ASCII

Next, the processing is pretty simple:

• for city in M:
• for letter in city:
• shifted_city = shift_letter_3(city)
• for cardinal in C:
• if cardinal in shifted_city:
• short_city = shifted_city.replace(cardinal, "")
• for ordinal in O:
• if ordinal in short_city:
• print("Solution: ", city, cardinal, ordinal)

That should do it. Good luck, and I'll be back after the Thursday NPR submission deadline to present my solution.

--Levi

No Sunday Puzzle??

 Well, Puzzlers, this is odd….

The Sunday Puzzle hasn’t been posted all day, and as far as I can tell from the streaming apps, it didn’t air today either. I’m keeping my fingers crossed that it will be posted tomorrow and that all is well for our beloved Puzzlemaster Will Shortz and Weekend Edition host Lulu Garcia-Navarro. I’ll be back as soon there’s a puzzle to crack. Cheers!

Moving vertically, horizontally (Solution)

Welcome back, Puzzlers! (Spoiler alert!) I'm back with a solution to this week's Sunday Puzzle from NPR:

This week's challenge: It comes from listener Ed Pegg Jr. Think of something that gets people moving vertically. Remove the middle two letters, and you get something that moves people horizontally. What two things are these?

In the preview post, I presented some ideas about how to approach this puzzle. In particular, I suggested using SBERT in masking mode to generate candidate words for the "something that gets people moving vertically." Well, I did manage to solve the puzzle (trampoline --> tram line), but unfortunately not by using NLP tools. The solution was sufficiently tricky that my SBERT queries did not turn up the correct candidate. I didn't upload a solver script this time, but in my SBERT queries I used verbs like ride, carry, and lift; naturally, these are not sufficiently likely to occur with trampoline.

Instead, I did this one the old fashioned way. I sat and brainstormed a list of things that move a person vertically, and eventually I landed (pun intended!) on trampoline, applied the "remove the middle two letters" transformation and recognized tram line. This was a neat puzzle. Next time I'll need to think more outside the box to ensure a language modeling tool like SBERT can turn up what I'm looking for. Probably adding a verb like bounce or launch would do the trick.

Okay, that's all for now. I'll see you tomorrow for the newest puzzle!

--Levi King

Moving vertically, horizontally (Preview)

Well Puzzlers, after a big fat fail last week (LOO --> 007; really??), I'm back with a breakdown of this week's Sunday Puzzle from NPR, and I'm feeling optimistic about this one:

This week's challenge: It comes from listener Ed Pegg Jr. Think of something that gets people moving vertically. Remove the middle two letters, and you get something that moves people horizontally. What two things are these?

Starting off, let's note some suspicious wording here: "something that gets people moving vertically". Why not just say "something that moves people vertically"? Especially given that we later have "something that moves people horizontally". This clue has me wondering if it could be something a bit tricky or figurative. Alarm clock? Coffee? A fall? None of those work, but you get the idea.

Next, we're removing the middle two letters. That tells us right away that we need an even number of letters, because a word with an odd number of letters will only have one letter in the middle. Also, obviously, we know we're dealing with letters, so no sneaky numerals like last time.

Beyond that, we need to find candidate words. This is a classic transformation(string_a) = string_b puzzle, and in this case, string_a and string_b are both open class. Moreover, I don't think we're likely to find appropriate lists already assembled online, as the classes are rather vague. Instead, I suggest we assemble our own lists of candidate words, using Word2Vec, as we did in this past puzzle, which was a favorite. This means providing a list of seed words, like elevator and balloon for the string_a, and subway and bicycle for string_b. And if that doesn't do the trick, we can use SBERT in masking mode and ask it to fill in the blanks for sentences like I rode the [MASK] to the rooftop (for string_a) and It takes 15 minutes to reach the library by [MASK] (for string_b). In assembling these lists, we can reject any word that doesn't contain an even number of characters.

Once we've assembled our lists of candidate words, we can iterate through list A, applying the transformation---removing the middle two letters. Then we can check if the resulting string appears in list B. If so, we've most likely found our string_a and string_b.

I'll be back after the NPR submission deadline (Thursdays at 3pm ET) with my solution. Good luck, Puzzlers!

Britishisms and Heroes (Preview)

Hello, Puzzlers! Another Sunday, another Sunday Puzzle from NPR Puzzlemaster Will Shortz:

This week's challenge: This week's challenge comes from listener Chad Graham, of Philadelphia. Think of a common Britishism — a word that the British use that's not common in the U.S. Write it in all capital letters. Turn it upside-down (that is, rotate it 180 degrees). The result is a famous hero of books and movies. Who is it?

Let's begin with our usual breakdown of the puzzle. Note that it's a variation on the most common type of puzzle we see here: transform_fx(string1) = string2. In other words, we are solving for string1 and string2, where applying some transformation to string1 yields string2. In this case, we have some general "class" information about the two strings, as well as a defined transformation function. Note that the "rotate 180 degrees" part of this puzzle also occurred in a puzzle we solved just this June. However, in that case, we were rotating letter by letter, but this time, we're rotating the whole word. When we rotate a whole word, the last letter becomes the first letter (upside-down now), and vice versa. We can account for this in our solver script by reversing the order of the letters, then using our dictionary to rotate each letter in place.

As usual with this kind of puzzle, we'll want to start with a long list of candidates for string1 and a long list of candidates for string2. We'll iterate through the first list, applying the transformation to each string and checking if the resulting string appears in the second list.

So what do we need for this puzzle?

• B: a list of "Britishisms";
• H: a list of heroes from books and movies;
• R180: A dictionary mapping of capital letters that can be rotated 180 degrees to form a new letter, e.g., {'M': 'W', ...};

We have a rotation dictionary (R180) we can start with, in this script. However, that puzzle called only for capital letters. In this case, the puzzle doesn't specify upper or lowercase, so we'll probably need to expand this dictionary to include lowercase. I'm not sure if the solution strings will mix upper and lowercase, but we probably want to allow for the possibility; Will can be tricky.

For B, I suspect our best bet is to spend a few minutes searching the web for such a list. Surely some anglophile has produced one on the web for other purposes already. Otherwise, we could theoretically do something like:

1. Find/assemble a large corpus of British English;
1. It could be a challenge to find a corpus for both written (e.g., newspaper) and spoken or vernacular English that contains exclusively British English;
2. Find/assemble a large corpus of American English;
1. Same challenge here;
3. Calculate the relative frequency of each word type in the British corpus;
4. Calculate the relative frequency of each word type in the American corpus;
5. For each word type in the British corpus, keep the word if it is significantly more frequent in the British corpus than in the American corpus;
1. This would take some trial and error to determine just how large the difference in frequency should be;

That certainly could be done, but it might be more than we want to take on for a hobby blog. For that reason, I think searching for an existing list of Britishisms is our best bet.

For H, we can probably find a suitable list around the web somewhere. If not we can probably get a pretty good list just by brainstorming for a few minutes. Crucially, I'm under the assumption that string1 and string2 are each single words, no spaces. So that should narrow it down a bit. We're probably also looking for fairly short strings, simply because the probability that a word will form a legitimate word when we rotate it 180 degrees is going to decrease for longer words. The fact that we're interested in a hero from books and movies may also help limit our list.

Okay, Puzzlers, I'm going to poke at this for a couple days and hopefully I'll have a solution to show for it later this week. Cheers!

--Levi King