- [After a visit to New York.] If I lived in Manhattan I’d eat at Grey’s Papaya for lunch every goddamned day.
- Is it my imagination, or did bananas used to be easier to begin peeling?
- Who is the mad genius who first came up with chicken-fried bacon?
- Tonight I had the opportunity to say, “I remember Husker Du.” But no one got the joke.
- Once again I am near a drug store and can’t for the life of me remember what I’m supposed to pick up at the drugstore.
- When I shave, the beard goes first, then the mustache. The sides of the mustache go before the middle. There’s always a moment of micropanic: “If I’m interrupted RIGHT NOW, I’ll look like Hitler.”
- The Arby’s on El Camino in South San Francisco is straight out of a David Lynch movie.
- When I start a band, our first album will be called, “Reboot the Franchise.”
- Of all the songs to get stuck in my head — “Non Dimenticar”? Really?
- If I ever open a beauty salon, I’m calling it Fiat Looks.
- Is anyone else troubled by the fact that Anonymous is now a name?
- Nothing against Donald Sutherland, but Robert Culp would have made a _perfect_ President Snow.
- What are some things that have made you say, “Now I’ve seen everything”? For me, one was seeing competitive goat-pantying at the Arizona Gay Rodeo Association rodeo this past weekend. Yes: a team of two gay rodeo cowboys putting panties on a goat as fast as they can.
- [When Rush Limbaugh called a woman a slut for wanting contraceptives covered by her health plan.] Outspoken conservative blowhard says something outrageous. Entire liberal world goes apeshit — playing right into his hand. What else is new.
- I can just imagine Limbaugh’s latest performance review. “We haven’t had a major dust-up in a while, Rush. Come up with something quick, and it better be a good one.”
- Here’s my problem with Mission: Impossible: Ghost Protocol (besides too many colons in the title). The premise is, the team’s on a mission that goes horribly wrong, so they’re “disavowed” and are then completely on their own for completing it, as if that’s a big deal. But that’s the normal state of affairs for the Impossible Mission Force. “If any of your team is caught or killed, the Secretary will disavow any knowledge of your actions” means you’re ALREADY ON YOUR OWN.
- I spent decades joking that I ought to start needing glasses any day now, like all the other people around me who spend all their time on computers. Now that I finally actually _do_ need glasses, I’m experiencing outrage every time I can’t see something clearly just by pointing my eyes at it like I’ve always done.
- Though Geraldine played hard to get, Geraldo knew he’d woo her yet.
- New txting shorthand: LOLMCWWU. (Laughing out loud making coworkers wonder what’s up.) Help spread it!
- Lessons of middle age: you can eat after 9pm, or you can sleep through the night, but not both.
- Paid for coffee and croissant at Peet’s with my phone. Magic! Japan says: welcome to the 90’s.
- Today’s puzzle-of-the-day-calendar puzzle was an algebra word problem: some friends have to chip in for a cake, but then some back out and the remaining friends have to pay more, etc. I read it to my kids and asked, “Does either of you know how to approach this problem?” Archer didn’t miss a beat: “Sneak up on it from behind.”
- Nowadays every night / Flashes by at the speed of light
- I’m a muppet of a man [Followed by one of my favorite-ever status replies: “I KNEW it!”]
- I holler, you holler, we all holler for challah bread.
- The latest craze at home: vintage Gilligan’s Island episodes on Amazon Prime. I didn’t remember just how sweet Mary Ann was on Gilligan, or how much Ginger teased the Professor. Hot stuff!
- The eternal paradox: the number of different keys in which a group of people sing Happy Birthday together is always greater than the number of people singing.
- The law of conservation of behavior: When one child is in big trouble, the other one behaves himself really well.
- Five years no mom.
- Of course I’m thrilled that Obama came out in support of gay marriage. But if he fails to tie that support to a broader narrative about fairness and justice, he’ll be missing a real opportunity to educate a nation that wouldn’t recognize civics if it ran up and bit them on the ass.
- Thanks Joss, that was awesome.
- I was deeply unhappy after seeing 2010’s deplorable “Piranha 3D.” But I gotta hand it to the filmmakers, they got the sequel name right: “Piranha 3DD.”
- A paradox: the man who knows he’s no better than anyone else, actually is.
- Folding cardboard “gable-top” milk and juice cartons: They worked fine for generations, and were biodegradable to boot. Adding a plastic spout to them is like mounting a steering wheel on the back of a horse’s head. Yes, it works; yes, it makes one device resemble a similar but more modern one. But what problem does it solve, exactly?
- Superficially, Moonrise Kingdom sounds a lot like 1979’s Rich Kids: 12-year-old lovers spy on/flee from clueless parents whose relationships are in shambles.
- Every Tuesday there’s a meeting. If the president names someone at that meeting, that person dies. Tell me again why we rebelled against King George III?
- Goodbye Ray Bradbury. Thanks for the mind-expanding dreams and nightmares both.
- [For my nephew.] Your twenty-first birthday today! / But drinking would be so cliche / So I recommend / Surprising your friends / By having a cafe au lait
- I keep waiting for star systems to start slipping through the fingers of the tightening grip of conservatism, and it keeps not happening.
- “I know all about yer standards and if ye don’t mind my sayin’ so there’s not a man alive who could hope to measure up to that blend o’ Paul Bunyan, Saint Pat, and Noah Webster ye’ve concocted for yerself out o’ yer Irish imagination, yer Iowa stubbornness, and yer liberry full o’ books.”
- Two episodes in on “The Legend of Korra” (on Amazon Instant Video). To my pleasant surprise it is shaping up to be a worthy successor to “Avatar: The Last Airbender.”
- Prometheus: among the worst movies I’ve ever seen. I don’t get that many date nights with the wife. Why was I not duly and unambiguously warned? Film critique profession, you have failed me.
- [For my niece.] Birthday limerick! “There once was a girl named Mckenna / Who wanted to visit Vienna / The airfare was high / So rather than fly / She sent herself there by antenna.” Happy birthday Mckenna!
- A couple of days ago, Andrea did something out of character for her: she started humming a TV theme song. It was the theme from The Andy Griffith Show. Today Andy Griffith died. For $50,000 she will hum another TV theme song of your choice.
- Saw Rocky again last night, first time in forever. No wonder it launched Stallone into stardom. Considering what followed, it’s a surprisingly sincere, authentic, big-hearted character drama. Everything’s fresh, nothing’s cliche (yet). The best friend is actually a jerk. The slimy loan shark is actually sympathetic. The wise old trainer is actually just an embittered opportunist. Even the training montage isn’t just a training montage — it was THE ORIGINAL training montage, included because it helped show character development, not depict mere training like all the training montages that have come since (including in Rocky sequels).
- Goodbye to Donald Sobol, the man who taught me that opposite faces on a standard die always add up to 7 (and who figured out how to hang a mystery on that fact).
- This must be a milestone of some sort: while Jonah was drinking a glass of milk yesterday, Archer got him to spit it onto the table with the well-timed display of his cartoon drawing “lady with big naked boobs.”
- All those damn seeds in my teeth. How does anyone like raspberries?
- [After the movie-theater shooting spree in Colorado.] One of the great sorrows of life is having to learn how to live in a world where events like the Aurora shooting not only can happen, but do with some regularity.
- No one is allowed to make movie sequels ever, except for James Cameron and Christopher Nolan.
- [More about Aurora.] I have a GREAT idea. Every now and then, when a handful of our young people are senselessly murdered and maimed, let’s give the killer all the notoriety he was seeking, let’s utter the same platitudes and rote expressions of grief as the last time, and let’s change nothing at all. Because America’s perfect just as it is!
- How many lovely afternoon naps have been ruined by a telemarketer or a wrong number? And yet do I ever silence the ringer? No, of course not, because that would mean I was actually thinking.
- It’s too much to hope that if I’m thinking enough to silence the ringer before my next afternoon nap, I will also be thinking enough to turn it back on when I wake up.
- Thanks Suzanne Glickstein, you were right: Safety Not Guaranteed was a great movie.
- Oh my God does “Weird Al” Yankovic put on a good show.
- Archer just performed as Don John in Act I, Scene 3 of Much Ado About Nothing at the conclusion of three weeks of Shakespeare camp. He was amazing.
- The word “iconic” is hereby off limits. You all just can’t be trusted with it.
- [After watching the season 5 episode, “Dead Freight.”] The writers of Breaking Bad are twisted and brilliant.
- Have seen all three of the Marin Shakespeare Company’s productions for this season (kids too!) and have loved them so much we’re about to see one of them again.
- “There _is_ no William Windom.” “DON’T YOU THINK I KNOW THAT? THERE WAS, BUT NOT ANYMORE!”
- In. Stop. Park. Walk. Yield. Enter. Exit. One way. Jane Street. Jones Street. Park Avenue. No right turn. No left turn. What can he do? Gas. Car wash. Subway. Don’t walk. No parking. Tow-away zone. Uptown. Downtown. First Avenue. Home sweet home!
- Recently I was craving a bottle of beer, only the phrase that kept popping into my head was the old-timey expression, “I could murder a bottle of beer.” What’s up with that?
- If I ever open a pho restaurant, I’m going to call it Pho-nom-e-nom.
- [After reading the Vanity Fair article about the stunning craziness surrounding Tom Cruise and his marriages.] Just imagine all the stories about Scientology that don’t leak.
- “Keep, ancient lands, your storied pomp!” cries she
With silent lips.
- One great thing about the vastness of space: years and years of “Voyager nearing the edge of the solar system” articles, and all of them are right.
- Huh. Varicose veins. Getting older is awesome. [Andrea later informed me they’re merely spider veins.]
- Since hearing the news about Neil Armstrong I have had an irresistible craving for Tang.
- [On 9/11/2012.]A detail I remember from 9/11/2001: a majority (or so it seemed) of the eyewitnesses lacked any language for describing the sight of the catastrophe other than variations of, “It was just like a movie.”
- [For my friend Joelle.] I wanted to write something clever for your birthday but couldn’t think of anything. J’oh well.
- The BBC’s “Sherlock,” apart from being excellent in itself, really rewards viewers who are familiar with the original canon.
- Even an outlandish premise can make for a good movie, if the internal logic is coherent and the other elements add up; and I’m a willing suspender of disbelief. Afterward, if the movie was crap, I will gladly blame its stupid premise if it’s warranted; but it’s the rare film whose premise I can’t grant up front. So help me, I just cannot make myself pretend to believe in cars and trucks that turn into giant battling anthropomorphic robots. [Followed by another great status reply: “But they turn into giant robots that fight! Did you not get that?”]
- Which one of us is the one we can’t trust? You say “I think it’s you,” but I don’t agree with that.
- Earlier, someone asked me if today’s date was the fourth of October. In confirming that it was, I failed to answer, “10-4.” #regret
- The International terminal at San Francisco Airport has six main entrances. They are prominently labeled “DOOR 01” through “DOOR 06.” What exactly are the leading zeroes accomplishing there?
- Guys: When you get a Facebook friend request from a hot-looking woman you don’t know, whose Friends List is all men, and you accept it, be aware that the Friends List is really a gallery of pathetic losers, and now you’re on it too.
- In 1988, I was annoyed that the movie “Beetlejuice” used dumbed-down spelling in its title because audiences would have had no idea how to pronounce Betelgeuse. Now I work for “Google.”
- [On my birthday.] So this is 46. I have GOT to learn to stop asking my knees to do things they haven’t been capable of for years.
- [Also on my birthday: the Giants won the pennant.] What a nice birthday gift the Giants just gave to me, personally!
- Everyone who knows comedy agrees that Bob Newhart was a groundbreaking comic genius. That may be true, and I have my own fond memories of being entertained by him, but don’t make the mistake I made, of putting those memories to the test by watching a 1972 episode of The Bob Newhart Show. Unwatchable with 2012 eyes.
- My most vivid fantasy is to spend a weekend with a reincarnated scientific luminary from the past, bringing him up to date on advances in science and technology that he’s missed. Does that make me weird?
- With John Michael Higgins’ performance in Pitch Perfect, this generation has finally found its Fred Willard.
- [Birthday limerick for my friend Greg.] “About a fine fellow named Greg / Folks said he’s a pretty good egg / There most men would end / But women append: / I wish he would show some more leg.”
- [Hurricane Sandy struck while my sister Suzanne was visiting from NY.] It’s Suzanne’s birthday, and if you ever doubted how awesome my sister is, I direct your attention to the tantrum that New York is throwing due to her absence for a mere day. Other people leave the city now and then, and they don’t shut down the subway!
- [On Suzanne’s birthday.] The Giants won the pennant for my birthday. They won the World Series for Suzanne Glickstein’s birthday. Happy birthday, sis!
- [After Disney acquired LucasArts.] OK Disney, this is your big chance to get on the fans’ good side. GREEDO DID NOT SHOOT FIRST. Make it right. The power is yours.
- Stupid Subway. I asked for a 6″ Cold Cut Combo with mustard, mayo, and lettuce, not a 6″ Cold Cut Combo with mustard, mayo, lettuce, and bacteria.
- [In the aftermath of Hurricane Sandy.] In nine months there are going to be so many babies.
- [Election day.] Think of that big idiot you know, the one with the deplorable politics. The responsibility for canceling out that dummy’s misguided vote — by casting your own tomorrow — is yours and yours alone. Everyone else has their own idiot to cancel.
- [The next day.] It’s almost like the whole campaign never happened. (*checks shower for Patrick Duffy*)
- [Hostess bankruptcy.] Be honest. How many Twinkies have you bought lately? It’s all your fault.
- [Almost identical to a sentiment posted earlier in the year. I must have really meant it.] Opportunities for sleeping in are so few. You’d think I’d have learned by now to unplug the phone before bed.
- I know more than I ever cared or expected to know about Transformers — names, personalities, capabilities — and it occurred to me, this is not very different from the days I knew more than I ever cared or expected to know about Thomas the Tank Engine. Transforming trainbots battling for control of the island of Sodor — that’s something I’d pay to see.
- Sir Tophamus Hattron: “You have caused confusion and delay. Prepare to be destroyed!”
- That frisson of outrage when Angry Birds ends your level just as the last pig is about to fall.
- Help me, children of the 70’s: a memory popped into my head today of a watery orange drink we used to get all the time from the school cafeteria and/or ice cream trucks. It wasn’t orange juice, it wasn’t Tang, and it wasn’t soda. It probably came in half-pint cartons. What was it? [One friend came through: It was Sun-Dew. Another replied, “I just had a total sense memory when I read the name Sun-Dew. It was not a good feeling.”]
- I am below [symbolic weight threshold] for the first time in years. Eliminating sweets, soda, and salty snacks actually works — like, immediately. Who knew?
- Just spent a fair chunk of my Sunday going back through the Facebook timeline of Steven Stern, curator par excellence, building a YouTube playlist out of all the videos he’s ever shared.
- [After the shooting spree in Newtown, Connecticut.] Back-of-the-envelope calculation: if the federal government offered to purchase every privately owned firearm for its fair market value plus $1,000, and if 50% of gun owners took advantage of this offer, it would cost about 100 billion dollars, or about 11% of what we already spend on national security.
- [More about Newtown.] Somewhere in America, right now, NRA lobbyists are hard at work, calculating how to contain the damage, keep lawmakers in line, and fan the suspicious belligerence of their base.
- That they are in crisis mode right now is a testament to the great job they did last time around.
- Today I am fully one month ahead-of-plan toward my weight-loss goal. I am *not* going to celebrate with a cupcake.
- All these interview candidates with impressive CS degrees and high-powered-sounding programming jobs at big companies you’ve heard of, and barely one in twenty can code worth a damn.
- …which is what I call “job security.”
- Here’s what bothers me about the latest idea in pop cosmology: that we’re living inside a giant computer simulation. First, it suffers from if-the-only-tool-you-have-is-a-hammer problem: in our modern age we are inclined to see computers everywhere. But more importantly, it does nothing to answer the question, “What is the nature of reality?” I mean, if _our_ reality is in some cosmic information processing device somewhere, it only begs the question, what is the nature of the reality containing that device?
- I’m not the same man I used to be. Time was, the line from It’s a Wonderful Life that best spoke to me was George Bailey railing against the forces keeping him in Bedford Falls: “I want to do what *I* want to do!” Now, merely contemplating watching that movie again, the thought of hearing Mary say, “Remember the night we broke the windows in this old house? This is what I wished for” causes my throat to close right up and my vision to go all watery. I blame Andrea Glickstein.
- [On 12/21/2012, which we now know wasn’t the end of the world.] Eating like there is a tomorrow.
- It is better to give than to receive. Proof: as happy as my childhood memories of Christmas are, they’re nothing compared to the feeling I get from making new happy childhood Christmas memories for my kids.
Ewe bed err knock rye
Ewe bed err notch out
I’m telling you eye
Sand two glosses car mint to town
He’s may king’ll list
Shaking it wise
Khan a fine tout who’s
Gnaw tea and ice
Sand two glosses car mint to town
He seize hue in yours leaping
He no swan euro ache
He no sieve you’ve bin batter could
Soapy good fur could nose ache
Ewe bed err war shout
Ewe bed err knock rye
Ewe bed err notch out
I’m telling you eye
Sand two glosses car mint to town
It happened on my birthday, of all days, a year ago. The boys were seven-and-a-half and nine-and-a-half. For a few months prior, whenever Santa Claus came up in conversation, whichever boy was speaking would cast me or my wife a sidelong glance and say pointedly, “a.k.a. Mom and Dad!” and the conversation would continue without further comment. So the bubble had already burst, they just lacked official confirmation — which notably they didn’t explicitly seek until we were sitting all together in the living room, getting ready to watch my birthday movie selection. When they did, I asked if they really wanted to know the truth. Archer, who is younger, just barely did, in my judgment. Jonah was burning for it.
So I opened the Wikipedia page about the real St. Nicholas and talked about him for a bit, and how he became renowned as a gift-giver. He was an ordinary man, so of course he died; but the gift-giving idea lived on.
Today, around Christmas every year, the spirit of St. Nicholas takes hold of parents everywhere. So although there’s no guy with a magical sleigh, and other parts of the story certainly are made up, still, in a very real way — and I told them this is honestly exactly what I believe — there is a Santa Claus, and Santa Claus is the idea of giving, and he/it really does travel around the whole world in a single night! He just needs us parents to do his work for him. You’ve heard of Santa’s elves? We’re it.
The boys seemed pretty happy with this explanation. Jonah, for his part, was happy merely to have Santa Claus officially debunked. I repeated my point about the reality of Santa Claus, and Archer said, “I half-believe you and I half-believe Jonah.” “Making up your own mind. I love that,” I told him.
Soon after that we let the boys see Batman Begins, despite some concerns about age-appropriateness. There’s the scene where Bruce Wayne decides he has to have a costumed alter ego:
“As a man, I’m flesh and blood. I can be ignored. I can be destroyed. But as a symbol? As a symbol I can be incorruptible. I can be everlasting.” The point being that if Bruce Wayne is ever injured or killed (or grows too old, which is the premise of Batman Beyond), someone else can don the suit and take over as Batman. In a way this is exactly what happened with St. Nicholas — the Bruce Wayne of gift-giving. Now that was a Santa explanation the kids could relate to.
It’s National Computer Science Education Week! That must mean it’s time for part 2 of my How (And Why) To Program series. Today I will discuss a tricky but powerful concept in computer science: recursion.
Briefly, recursion means accomplishing a task by performing it in terms of smaller versions of the same task. For example, each morning I execute my “drive to work” routine, which is really my “drive from point A to point B” routine, where point A is home and point B is work. To do that, I first do “drive from point A to point B” where point A is home and point B is the Golden Gate Bridge (which is about halfway to work for me), followed by “drive from point A to point B” where point A is now the Golden Gate Bridge and point B is work. Each of those steps, of course, can be decomposed into smaller “drive from point A to point B” tasks.
One classic example for illustrating recursion in computer code is the Fibonacci sequence — the mathematical sequence in which each number is the sum of the two before it. You might already see the weakness in that definition: what can the first and second numbers in the sequence be, if they don’t have two numbers before them that can be added together? This is a key feature of recursive functions: at some point they reduce the problem into parts so small that they reach the “base case,” where the recursive rule breaks down. It happens that the base case of the Fibonacci sequence says the first two numbers are 0 and 1. From there, the recursive rule takes over to give the numbers that follow: 1, 2, 3, 5, 8, 13, 21, 34, and so on.
Let’s look at a “function,” which is the computer programming equivalent of a recipe: you give it some inputs, and it gives you an output, the result of processing the inputs in specific ways. Our function is called fibonacci and it takes one input, or “argument”: a number, which we’ll call n. The result of fibonacci(n) will be the nth number in the Fibonacci sequence, where the first two numbers — fibonacci(0) and fibonacci(1) (recall that in programming, lists and sequences of things are almost always numbered beginning at zero) — are 0 and 1.
As before, code samples are presented in the Python programming language, though the same concepts we’re discussing apply to most other programming languages too.
def fibonacci(n): if n == 0 or n == 1: return n else: return fibonacci(n-1) + fibonacci(n-2)
We start with “def fibonacci(n),” which simply means “define a function named fibonacci taking one argument called n.” The body of the function follows. First it checks for the base case: does the caller (whoever is invoking this function) want one of the first two Fibonacci numbers? If so, the function simply “returns” (or hands back to the caller) the value of n, since by coincidence the value of fibonacci(n) is n when n is 0 or 1.
If it’s not the base case, the function returns a different value: the sum of invoking fibonacci first on n-1 and then on n-2. Those recursive calls give the two prior Fibonacci numbers. For instance, if we invoke fibonacci(9), then n is 9 and fibonacci(n-1) is fibonacci(8), which is 21; and fibonacci(n-2) is fibonacci(7), which is 13. Adding those together gives 34, which is the correct result for fibonacci(9).
Enough about the Fibonacci sequence. It’s a contrived example and, though it explains recursion pretty well, it doesn’t demonstrate the real-world applicability of the technique. (It also happens that, for reasons I won’t go into here, recursion is a terribly inefficient way to compute Fibonacci numbers compared to other possibilities like iteration.)
A few days ago, my Mensa Puzzle-a-Day Calendar presented this riddle:
The letters of a certain three-letter word can be added in sequential order (though not necessarily with all three letters together in the same place) to each of the letter strings below to form common, uncapitalized English words. You don’t need to rearrange any of the letters below. Simply add the three needed letters in sequential order. What is the three-letter word, and what are the nine new words formed?
1. alp 2. wl 3. marit 4. ealus 5. urneman 6. cke 7. disintedl 8. traectr 9. epard
(To illustrate the puzzle: the letters of what three-letter word can be inserted in both “hoyde” and “ckear” to produce common English words? The answer is “new,” to produce “honeydew” and “neckwear.”)
Staring at the puzzle for a while, I was unable to solve it. So I sat down and wrote a program to solve it for me. How’s that for real-world applicability?
Once again I relied on the file /usr/share/dict/words (or sometimes /usr/dict/words, or /usr/lib/dict/words) that is a standard feature of some operating systems; it’s simply a list of many common English words (and many uncommon ones, plus some frankly questionable ones), one per line. Reading that file, I produced two sets of words: one set of all the words, and one set of all three-letter words. Here’s how that looks:
three_letter_words = set() all_words = set() wordlist = open('/usr/share/dict/words') for word in wordlist: word = word[:-1] all_words.add(word) if len(word) == 3: three_letter_words.add(word) wordlist.close()
(Very similar code is explained in detail in part 1 of this series.)
With those two word sets in hand, and the nine letter-strings from the puzzle, this was my strategy: try all possible ways of inserting the letters of all the three-letter words in each of the letter-strings. For any three-letter word, if none of its combinations with a given letter-string produces a valid word, remove the three-letter word from further consideration. In other words, beginning with all possible three-letter words, we whittle them away as they become disqualified. In the end, the only three-letter words left should be ones that combine, one way or another, with all of the nine letter-strings to produce valid words.
So, for example, the three-letter words “see” and “era” both can be added to the letter-string “alp” to produce valid words (“asleep” and “earlap”). But the three-letter word “new” can’t be, so after running through all the three-letter words on the letter-string “alp,” “see” and “era” will still be in the set three_letter_words, but “new” won’t be.
Here’s how that strategy looks:
for string in ("alp", "wl", "marit", "ealus", "urneman", "cke", "disintedl", "traectr", "epard"):
This starts a loop that will run nine times, once for each letter-string, giving each letter-string the name “string” on its turn through the body of the loop.
three_letter_words_to_discard = list()
This creates an empty list called three_letter_words_to_discard. It’s empty now but as we progress we will fill it with words to remove from the three_letter_words set.
(If you’re wondering why I sometimes use lists for collections of things, and sometimes use sets, gold star! The answer is that they are two different kinds of data structure, each one good at some things and bad at others. A set is very fast at telling you whether a certain item is in it or not; a list is slow at that. On the other hand, a list keeps things in the same order in which you added them; a set doesn’t do that at all.)
for three_letter_word in three_letter_words:
This starts a nested loop. It’ll run through the complete list of three_letter_words each of the nine times that the outer loop runs.
combinations = combine(three_letter_word, string)
Here we presume there’s a function called combine that takes the current three-letter word and the current letter string, and produces the complete list of ways that the letters of three_letter_word can be interspersed with the letters of string. For example, combine(“abc”, “def”) should produce the list [“abcdef”, “abdcef”, “abdecf”, “abdefc”, “adbcef”, “adbecf”, “adbefc”, “adebcf”, “adebfc”, “adefbc”, “dabcef”, “dabecf”, “dabefc”, “daebcf”, “daebfc”, “daefbc”, “deabcf”, “deabfc”, “deafbc”, “defabc”]. That’s where recursion is going to come into play. We’ll get to writing the combine function in a moment.
good_combinations = list() for combination in combinations: if combination in all_words: good_combinations.append(combination)
With the list of combinations in hand, we now look through them to see which of them are valid words, if any. We set good_combinations to be a new empty list where we’ll accumulate the valid words we find. We loop through the combinations, testing each one to see if it’s a member of the set all_words. If one is, we add it to the list good_combinations.
if good_combinations: print three_letter_word, "+", string, "=", good_combinations else: three_letter_words_to_discard.append(three_letter_word)
After the “for combination in combinations” loop, we check to see whether good_combinations has anything in it. (“If good_combinations” is true if the list has something in it, and false otherwise.) If it does, we print out the current three-letter word, the current letter-string, and the list of valid words they make. If it doesn’t, then three_letter_word goes into our list of three-letter words to discard.
for word in three_letter_words_to_discard: three_letter_words.remove(word)
After the “for three_letter_word in three_letter_words” loop, this small loop does the discarding of disqualified three-letter words.
Why not simply discard those words from three_letter_words in the preceding loop, as we run across them? Why save them up to remove them later? The answer is that when you’re looping through the contents of a data structure, it’s a bad idea to add to or remove from the data structure. The loop can get confused and lose its place in the structure. It may end up running twice with the same list member, or skip a member entirely. It’s safe to make changes to the membership of the data structure only after the loop finishes.
Finally, after the outermost loop has finished, it’s time to see which three-letter words remain in our set:
And that’s all! All except the tricky part: the combine function. Here is how it starts:
def combine(string1, string2):
It takes two strings. We’ll give them generic names, string1 and string2, so as not to assume that either one is a three-letter word. As you’ll see, often neither one is.
Now, how to approach writing a recursive function? It’s usually a safe bet to start with the base case, the conditions under which combine isn’t recursive. The recursive step will involve passing shorter and shorter strings to combine, so the base case is when one or both of the strings is empty. Obviously if either string is empty, the result should be the other string — or more precisely, the list containing the other string as its one member (since we’ve already stipulated that the result of combine is a list of strings). In other words, combine(“”, “def”) should produce the list [“def”] — which after all is the result of interspersing the letters of “” among the letters of “def” — and combine(“abc”, “”) should produce [“abc”].
So here’s the body of combine so far. It’s just the base case:
if len(string1) == 0: return [string2] elif len(string2) == 0: return [string1]
(Recall that “elif” is Python’s abbreviation for “else if.”)
Now for the case where string1 and string2 are both non-empty; the recursive case. The key to writing the recursive step of a function like this is figuring out (a) how to make the problem the same but smaller, and then (b) what to do with the result of computing the smaller solution.
One way to make the problem smaller is to lop off the first letter of string1. So if combine were originally invoked with the strings “abc” and “def,” the recursive call would invoke it with “bc” and “def.” Presuming combine works correctly — which is the counterintuitive assumption you must always make about the recursive step in a function like this — we’ll get back the list [“bcdef”, “bdcef”, “bdecf”, “bdefc”, “dbcef”, “dbecf”, “dbefc”, “debcf”, “debfc”, “defbc”]. None of those belongs in the result list of combine(“abc”, “def”); but if we now restore to the beginning of each of those strings the same letter we lopped off, we get [“abcdef”, “abdcef”, “abdecf”, “abdefc”, “adbcef”, “adbecf”, “adbefc”, “adebcf”, “adebfc”, “adefbc”]. This is halfway to the complete answer: it’s all the strings in the result list that begin with the first letter of string1. We only need to add all the strings in the result list that begin with the first letter of string2, and we’re done. We do this by treating string2 the same way we just treated string1: we lop off its first letter in another recursive call to combine, then paste it back on to each string in the result. Continuing the example, this means calling combine(“abc”, “ef”), which produces [“abcef”, “abecf”, “abefc”, “aebcf”, “aebfc”, “aefbc”, “eabcf”, “eabfc”, “eafbc”, “efabc”]. Sticking the “d” back onto the beginning of each of those strings gives [“dabcef”, “dabecf”, “dabefc”, “daebcf”, “daebfc”, “daefbc”, “deabcf”, “deabfc”, “deafbc”, “defabc”], and adding this list to the list from the first recursive call gives the complete solution.
In Python, the first letter of string is denoted string. The rest of string, without its first letter, is denoted string[1:]. So here’s the complete version of combine, with the (double) recursive step added in.
def combine(string1, string2): if len(string1) == 0: return [string2] elif len(string2) == 0: return [string1] else: recursive_result1 = combine(string1[1:], string2) recursive_result2 = combine(string1, string2[1:]) result =  for string in recursive_result1: result.append(string1 + string) for string in recursive_result2: result.append(string2 + string) return result
This is the crazy magic of recursion: at each step, you simply assume the next-smaller step is going to work and give you the result you need. All you have to get right is the base case and the way to process the recursive result, and — well, look:
hol + alp = ['alphol'] has + alp = ['alphas'] sae + alp = ['salpae'] her + alp = ['halper'] see + alp = ['asleep'] eta + alp = ['aletap'] era + alp = ['earlap'] soe + alp = ['aslope'] yin + alp = ['alypin'] pus + alp = ['palpus'] een + alp = ['alpeen'] kas + alp = ['kalpas'] ecu + alp = ['alecup'] ist + alp = ['alpist'] doh + alp = ['adolph'] pal + alp = ['palpal'] cul + alp = ['calpul'] ped + alp = ['palped'] Moe + alp = ['Malope'] clo + alp = ['callop', 'callop'] gos + alp = ['galops'] tid + alp = ['talpid'] yum + alp = ['alypum'] pon + alp = ['palpon'] hin + alp = ['alphin'] joy + alp = ['jalopy'] hol + wl = ['wholl', 'wholl'] sae + wl = ['swale'] soe + wl = ['sowel', 'sowle'] joy + wl = ['jowly'] joy + marit = ['majority'] joy + ealus = ['jealousy'] joy + urneman = ['journeyman'] joy + cke = ['jockey'] joy + disintedl = ['disjointedly'] joy + traectr = ['trajectory'] joy + epard = ['jeopardy'] set(['joy'])