This week's challenge comes from listener Andrew Chaikin, of San Francisco. Think of a famous philosopher — first and last names. Change one letter in the first name to get a popular dish. Drop two letters from the last name and rearrange the result to get the kind of cuisine of this dish. What is it?
Oh boy, this one is kind of complicated. In fact, I've been working on it off and on for two days and haven't found a solution. This may be the first puzzle all year to stump me! I'm determined to keep chipping away at it, however.
Let's look at what we need:
- Lists:
- P: a list of philosophers with first and last names;
- D: a list of popular dishes;
- C: a list of cuisines;
- Functions:
- letter_swap(string, alphabet):
- for every letter l in string:
- for every letter a in alphabet:
- newstring = string.replace(l, a)
- in other words, generate all possible newstrings where one letter is replaced
- letter_drop(string, n):
- find every combination of n positions within string and drop the letters in those positions
- we'll use this to drop 2 letters from each philosopher's last name, then compare the results with C (the list of cuisines) to find a match;
- is_anagram(x, y):
- for strings x and y, convert to sorted strings:
- e.g., "italian" --> "aaiilnt"
- we'll use this to compare the output of letter_drop with C;
It doesn't look so bad, right?
I think I have working script... That is, when I add carefully crafted fake names to my list of philosophers, I get solutions, but I'm not finding any real solutions.
For example, I've added "Pavini Andoswitch" and "Falazel Koreegi", and I get "panini sandwich" and "falafel greek", so I think that some element is missing from one of my lists--a philosopher name, a cuisine or a dish.
The trouble with the lists in this puzzle is that they are all open classes. That is, there is no complete list of philosophers (even famous ones), or popular dishes, or cuisines. We're often dealing with closed classes, like states of the USA or cities with an NFL team, etc. We can easily collect the complete list for closed classes. With these open class lists, however, it's often a matter of simply dumping as many possible candidates as we can find into a list. Remember, we're more interested in recall than precision; for example, if we're looking for dishes and we include beverages (or any non-dishes) in our list, that's preferable to having a strict list that might not include our target word or words.
P, the list of philosophers, is probably the easiest here. It's taking some work, but I've scraped over 1000 philosopher names from Wikipedia and other websites. From there, it's non-trivial but relatively straightforward to convert that list into something we can work with--first name and last name for each, and no punctuation or funky (non-ascii) letters. There's a little bit of work involved in handling some "two name" last names; e.g., for "hermann von helmholtz", I want my final list to include "hermann vonhelmholtz" and "hermann helmholtz".
D, dishes, is probably the hardest here. First, many dishes have multi-word names, and it's not clear how those should be handled. Consider this list:
- nachos
- fried chicken
- shrimp scampi
What do we do with this? I think we just generate all reasonable possibilities (and then some), getting:
- nachos
- friedchicken
- fried
- chicken
- shrimpscampi
- shrimp
- scampi
Heck, we might even try a quick and dirty approach to include singular and plural forms: if the word ends in an 's' try deleting it; if the word doesn't end in 's', try adding an 's'. Obviously this doesn't work perfectly: "-y" --> "-ies"; "panino" --> "panini", etc.
Finally, C, cuisines. This is possibly the messiest. What even is a cuisine? Basically any name for an ethnic group or nationality can be a cuisine. But might it also include words like vegetarian, barbecue, pastry? I'm not sure, but as usual, I think it's best to err on the least restrictive side.
Well, good luck this week! I'll be back before Sunday to post a solution or hang my head in shame. :-)
--Levi
No comments:
Post a Comment