Remembering the past no guarantee of not repeating it

In February of 1992, Apple Computer flew me from Pittsburgh to California and put me up at the Cupertino Inn for a series of job interviews over a couple of days. I extended my stay in order to visit a few other companies too.

One of the companies on my list was a tiny e-mail startup in San Rafael called Z-Code. I was planning to visit them in the afternoon after spending the morning at a prominent computer magazine, interviewing for an editorial position. That visit went very well, and so had the interviews at Apple; and having driven from Cupertino to San Francisco for that interview, I now had a sense for how long the return drive would be, and how much farther out of the way a visit to Z-Code would take me.

If I hadn’t been such a Star Wars nerd I might have skipped it altogether. But I knew that Skywalker Ranch and Industrial Light and Magic were in San Rafael somewhere and I harbored a secret hope of spotting them as I navigated to my Z-Code visit. I visited Z-Code and, to my surprise, found that opportunity more compelling than the ones at Apple and at the magazine. Two months later I was living in California and working at Z-Code and the rest is history.

Now, almost a quarter century later, I’ve had a very similar experience. I interviewed successfully at a number of well-known medium-to-large-sized companies over the past several weeks but found a tiny startup – that I had almost dismissed, at first, as not worth my time – to be the most compelling. Tomorrow I begin at Chain.com.

Kill Ralphie! saved!

[Cross-posted at kill-ralphie.blogspot.com/2015/06/kill-ralphie-saved.html.]

In the 1980’s, students and faculty at Carnegie Mellon University were on the Internet, but there was no World Wide Web yet – no browsers, no websites, no Google, Facebook, or YouTube; in fact, no video and almost no graphics, just text. But there still existed social communities online, organized into discussion forums on numerous topics. Usenet was the biggest of these. Carnegie Mellon had its own internal collection of discussion forums called bboards.

One bboard was called “Kill Ralphie!” When someone posted to Kill Ralphie, they were contributing a chapter to an ongoing story about a hapless lad who is alternately placed in immediate mortal danger, then rescued, both in the most creative and entertaining ways possible. I was an enthusiastic participant back then, along with many others at CMU. Writing for an audience of fellow contributors was a formative experience for me that improved my prose and humor skills from “immature” to “slightly less immature.”

Well, guess what? Kill Ralphie! lives again! I’ve taken that old pastime and turned it into a fun new website. Please check it out, contribute chapters, and enjoy: kill-ralphie.com.

When you click a YouTube link

Earlier today I gave a presentation about YouTube to seventh graders for “career day” at Jonah’s middle school. (Actually I gave it six times in a row to rotating classroomsful of kids, with the result that (a) I’m totally shredded and (b) I have even more respect for what teachers do all day every day.) Coincidentally it’s the tenth anniversary of the first YouTube video.

I thought fifth grade would be my last chance to appear cool to Jonah’s classmates on his behalf (and I’ve now given that presentation to Archer’s class too), but it looks like I have some coolness left after all. He even allowed me to walk to school with him and his neighborhood friends this morning:

Me: OK if I walk to school with you in the morning?
Jonah, shrugging: Sure.
Me: OK. Just wanted to make sure I wasn’t cramping your style or anything.
Jonah: What style?

Maybe YouTube lends me a little extra middle-school cred. Anyway, the presentation was well-received by most of the kids. It involved soliciting sixteen volunteers per class to read different parts aloud in a short little play I wrote. Each volunteer got a copy of the script with his or her part individually highlighted (which I did by hand earlier this week for all ninety-six copies I needed to hand out – eight pages each – and this in the middle of April, because I’m a glutton for punishment). I was a little worried about getting enough volunteers in each class, but I need not have been; the kids were down with whatever the YouTube guy wanted to do. I gave out my bribes anyway: YouTube stickers and pens.

I was the narrator. Everyone in the class who didn’t volunteer for one of the other parts became “All the buttons and menus.” After we performed the scene, the teacher displayed a web page I had prepared containing a YouTube link and we watched – hopefully with a little better understanding now of what was going on behind the scenes – as she clicked it and Dramatic Chipmunk played. It took a split second to perform all the actions we’d just spent eight minutes dramatizing.

We didn’t get to the song I included at the end of the script. I didn’t expect to but included it anyway as a little lagniappe for the kids. I hope some of them are singing it now; I know I am.

After the sixth presentation, I thanked the teacher for hosting me. She complimented me on the scene I had written. “Thanks,” I said, “but after six repetitions the words have lost all meaning.” She replied, “Welcome to the world of teaching.”

We’re not fledgling

THIS ASSET PURCHASE AGREEMENT (this “Agreement”) is made and entered into as of and shall take effect on March 1, 2015 (the “Closing Date”), by and among [company that may not wish to be named quite yet], a California corporation (“Buyer”), ZANSHIN, a California corporation (“Seller”), and Seller’s principal shareholders, BARTON SCHAEFER, STEVE WEBSTER, GREGORY FOX, and ROBERT GLICKSTEIN (collectively the “Majority Shareholders”).

Thus ends, for all intents and purposes, the story of Zanshin, the company that my friends and I started in 1996 after resigning en masse from Z-Code. It will continue to exist in name and in certain administrative functions, but [unnamed company] is buying substantially all its assets and hiring away most of its employees.

Z-Code was the producer of an award-winning cross-platform e-mail client, Z-Mail. In 1994 Z-Code’s owner Dan Heller sold the company to Network Computing Devices (NCD), a hardware company. Much of Z-Code’s staff was baffled by the sale and considered it ill-advised. Indeed there followed a corporate comedy of errors as first Dan was let go and then NCD’s top leaders, Judy Estrin and Bill Carrico, were fired. As we’d predicted, NCD’s sales staff had no idea how to sell software. As the World Wide Web started gaining traction, we were alarmed when NCD’s clueless new CEO, Ed Marinaro, tried to repurpose Z-Code’s staff of e-mail software experts as developers of a new Windows-only web browser called Mariner. Meanwhile, we were denied opportunities to make badly needed improvements to Z-Mail, and finally, after a number of grassroots efforts to turn things around had failed, a bunch of us gave up and quit to start our own e-mail software company.

After considering and rejecting several names we settled on Zanshin, a Japanese word meaning some badass combination of “emotional intensity” and “follow-through.” We discovered it in this passage in Neal Stephenson’s novel Snow Crash, describing a swordfight between avatars in the high-resolution virtual reality called the “Metaverse”:

The businessman reaches across his body with his right hand, grips the handle of his sword just below the guard, draws it out, snaps it forward so it’s pointing at Hiro, then places his left hand on the grip just below the right. […]

The businessman turns out to have a lot of zanshin. Translating this concept into English is like translating “fuckface” into Nipponese, but it might translate into “emotional intensity” in football lingo. He charges directly at Hiro, hollering at the top of his lungs. […]

“Emotional intensity” doesn’t convey the half of it, of course. It is the kind of coarse and disappointing translation that makes the dismembered bodies of samurai warriors spin in their graves. The word “zanshin” is larded down with a lot of other folderol that you have to be Nipponese to understand.

And Hiro thinks, frankly, that most of it is pseudomystical crap, on the same level as his old high school football coach exhorting his men to play at 110 percent.

We incorporated with our own money (proceeds from selling NCD stock) and the help of a fancy Sand Hill Road lawyer. We rented a house in Petaluma where some of us lived and all of us worked on bringing to life our vision of a beautiful and functional e-mail manager built on the theory that, done right, e-mail could serve as the repository for all one’s private information and communications. In hindsight our plan was not sufficiently well-defined, and neither was our project development timeline. More than two years passed of writing code together every day, grappling with the early web and our ever-problematic dialup Internet access, pushing the boundaries of the IMAP e-mail protocol and the fledgling GNU C++ compiler, and taking turns cooking for one another, watching The Simpsons together, and generally not operating with an adequate sense of purpose or urgency. By the time our e-mail client, code-named Lawndart, finally began sparking to life, the entire e-mail landscape had changed beneath our feet. Free clients like Outlook Express and Eudora had become ubiquitous and were good enough for most people, and free web-based mail from Microsoft and Yahoo was starting to take off. Even if we had gotten Lawndart to market, no one would have cared.

The only software we ever released was a Lisp-like text-markup language called Latte (“Language for Transforming Text”) and its followup, Blatte (“Better Language for Transforming Text”), which we open-sourced and gave away as a kind of corporate calling card. Somehow or other this led to Zanshin getting an extended consulting gig with Amazon.com, for which a couple of us ended up traveling back and forth to Seattle a lot. Things I remember from that time:

  • Checking in and out and in and out of the Residence Inn on Lake Union week after week;
  • The offices in which we did our work, and several of the people we worked with;
  • Various meetings and meals;
  • Keeping in touch with my new wife via the late-90’s-vintage phone I carried on a belt clip;
  • Being extra fastidious about tracking my time, reporting my progress, and keeping expenses down

but I’m damned if I can remember the nature of any actual work we did for them. Nevertheless, the gig went so well that Amazon offered to relocate us all to Seattle and hire us. Andrea flew up to Seattle to get the vibe of the place. Together we decided it was definitely doable.

Back in California we had a few long talks about Zanshin’s prospects and how we all felt about packing it in and moving to Seattle. Some of us were in favor, some were opposed and felt that Zanshin had some life left in it. We recognized that our dream of a high-tech e-mail client was dead; but in those long-overdue discussions we started to conceive of some exciting new ideas for the server side of e-mail and, in the end, convinced ourselves to stick it out as a software startup. We turned Amazon down.

We began describing to ourselves, and then to some business consultants, a collection of server-side e-mail features that collectively we called “MSpace.” Zanshin moved out of rented houses and into actual offices, and we took a little extra investment to keep us going (including from the notorious Gary Kremen, owner of the sex.com domain).

One way and another, our plans for MSpace took a detour into the realm of e-mail marketing — spamming, essentially, but ethical spamming as we were always quick to point out, for reputable marketers only, never sharing e-mail lists, and always providing no-hassle opt-out. I wrote a high-performance e-mail delivery engine and the aforementioned Blatte language for creating dynamic customizable templates, and Zanshin, operating its e-mail marketing service under the name iPost, finally started earning money.

This whole time I had been moonlighting as a founding member of the Internet Movie Database. In 1998 Amazon.com bought the IMDb (a coincidence not related to Zanshin’s consulting gig) and early in 2001 they asked me to join full-time. Five years of earning first no salary and later only a token amount had taken its toll, particularly since Andrea and I were planning to start a family; and the e-mail marketing business, though it was taking off, failed to move me. After consulting with my partners we agreed that I’d wrap up work on iPost’s delivery engine and then be done.

However, Andrea had joined Zanshin a couple of years earlier herself and she remained even as I went on to work full-time for the IMDb, and later for other companies. The e-mail marketing business amassed a surprisingly healthy client list and collected enough revenue to pay competitive salaries to a growing staff of developers and salespeople. I returned for a couple of short contract gigs from time to time. But as the years passed, the margins got slimmer and slimmer and the industry consolidated behind a few ever-larger players. Two of the other original founders had also left. New-product ideas always came second to dealing with never-ending customer issues. There was still momentum in the business, but it was unclear for how much longer. The time for a change had come, and I am grateful to Andrea and my Zanshin partners for making it happen.


Postscript. The title of this post comes from an episode at Z-Code. When a magazine, in its review of our product, Z-Mail, called our company a fledgling startup, we bristled, having by then grown quite a bit and able to count companies like Chevron and Silicon Graphics among our business partners. I undertook to make a sign for the office reading, “Z-Code Software: We’re Not Fledgling,” and it became a frequently heard catchphrase.

A little of Andy lives on in me

In 1978, it was rare ever to encounter a computer, much less someone who had one at home. The “personal computer revolution” was only about a year old, with Apple, Commodore, and Radio Shack all introducing their first consumer models in 1977.

Of the people who did have computers at home, surely only a small fraction were so generous with them as to allow their sons’ twelve-year-old friends to spend afterschool hour after hour, day after day, month after month sitting at them, tapping in and trying out dumb little programs; and an even smaller fraction were also seasoned programming experts with the desire, ability, and patience to impart some of that expertise to receptive but very green ears.

This weekend I, one of those twelve-year-old friends in 1978, mourn the passing of Andy Kane, one of those generous and patient computer owners. Andy was one of the many reasons I was lucky to befriend his son Chuck in the seventh grade. He was a living example of the ability to make a career out of writing software and he contributed significantly to nurturing the then-embryonic skills that today support me and my family. My condolences to his; I will always be grateful.

Counting the bits at YouTube

Jonah is nearly done with fifth grade. In the fall he begins middle school. For years I’ve known that if I’m ever going to visit his classroom for a “what my dad does at work” presentation, it would have to be before middle school, which is when the coolness of “what my dad does at work” presentations falls off a cliff.

I made it just under the wire. For a long time all I had were good intentions and a half-started slide deck, work on which always took a backseat to this and that. Finally, a few weeks ago I gave his classroom the presentation below.

It was a hit. YouTube has a lot of cachet with 10-year-olds. It helped that I made some of the presentation interactive; there was a novelty factor to having the class work out some simple but enormous numbers. They stayed engaged for the full forty-five minutes, volunteering answers, laughing in the right places, and asking smart questions.

At the end I distributed light-up YouTube yo-yos to everyone, which was an even bigger hit. Hopefully it cemented Jonah’s reputation as the coolest kid to know. But his classmates were into the talk even before they knew there was swag coming.

I invite you to reuse or repurpose the slides below. I plan to give the talk again in two years when Archer is in fifth grade, so any constructive feedback that I can incorporate before then would be welcome.

How (and why) to program, part 2

This entry is part 2 of 2 in the series How (and why) to program

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:

print three_letter_words

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[0]. 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[0] + string)
    for string in recursive_result2:
      result.append(string2[0] + 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'])

Predicting the present

One day long ago, when the IBM PC was still new, my friend Mike asked me to imagine my ideal computer. I described something very like the IBM PC, but with more memory and a bigger hard drive — 50 megabytes, say, instead of 10 or 20. I couldn’t imagine any use for much more than that. (Today of course you can’t even buy a thumb drive that tiny.) I grudgingly allowed that a bitmap display might be more useful than the 80-column-by-24-line character terminal that PC’s had, but that was all I would consider adopting from the then-brand-new Apple Macintosh, which I dismissed as a silly toy unworthy of Real Programmers.

“Why?” I asked Mike. “What’s your ideal computer?”

Mike described something no bigger than an 8.5×11 sheet of paper and no more than an inch or so thick, whose entire surface was a full-color display. It could be carried in the hand or slipped into a backpack. “What about the CPU, where would that go?” I asked. I wasn’t getting it. Mike patiently explained that the whole system — CPU, RAM, video driver, power supply — was inside that little slab. I scoffed. Cramming everything into such a small space was obviously impossible, and no battery that could fit in such a thing would ever have enough power to spin a floppy disk drive for long. “Anyway, even if you could build it,” I told him, “it wouldn’t be as convenient as you’d like. You’d have to carry around a keyboard too and plug it in every time you wanted to use it.” No you wouldn’t, said Mike. The display could be touch-sensitive. The keyboard could be rendered on the screen as needed and input accepted that way.

This was 1984. What Mike described was pure science fiction. (In 1987 that became literally true, when the touch-controlled “padd” became a staple prop on Star Trek: The Next Generation.) Yet here I am, the proud new owner of a Nexus 7, the latest in high-powered touch-sensitive computing slabs that put even Mike’s audacious vision to shame.

It wasn’t the first time I’d had a failure of technological vision, nor was it the last.

Several years earlier, before even the IBM PC, I was spending a lot of afterschool hours at my friend Chuck’s house, and a lot of those hours on his dad’s home computer, one of the only ones then available: the beloved but now mostly forgotten Sol-20. (The TRS-80 and the Apple ][ were brand new and just about to steal the thunder from hobbyist models like the Sol-20.) It had a small black-and-white monitor that could display letters, numbers, typographical marks, and a few other special characters at a single intensity (i.e., it really was “black and white,” not greyscale). It looked like this:

The display was so adequate for my meager computing needs there in the late 1970’s that when the computer magazines I read started advertising things like Radio Shack’s new Color Computer (that’s what it was called — the “Color Computer”), I dismissed them as children’s toys.

Once, Chuck and I entertained the idea of making a little science fiction movie. A scene in Chuck’s script had a person’s face appearing on a computer monitor and speaking to the user. It was his plan to film this scene using his father’s computer. I said, “How are we going to make a face appear on a computer monitor?” I had only ever seen letters and numbers blockily rendered on it. Chuck pointed out that the monitor was really just a small TV. “Oh yeah,” I said, feeling stupid. It ought to be able to display anything a TV could. Of course we’d have to hook it up to a different source; obviously no computer could handle rendering full-motion video. Yet here I am, a software engineer at YouTube.

There’s more. In the mid 80’s, my sometime boss Gerald Zanetti, the commercial food photographer and computing technophile, once described his vision for composing and editing photographs on a high-resolution computer display. If a photograph included a bowl of fruit, he explained, he wanted to be able to adjust the position of an orange separately from the grapes and the bananas surrounding it. I said that such technology was far in the future. I’d seen graphics-editing programs by then, but they treated the image as a grid of undifferentiated pixels. Separating out a foreground piece of fruit from other items in the background simply was not feasible. Yet just a couple of years later Photoshop exactly realized Zanetti’s vision.

In the mid 90’s, when the web was new, my friend and mentor Nathaniel founded a new company, First Virtual, to handle credit card payments for Internet commerce. At the time there was no Internet commerce. Nathaniel and company invented some very clever mechanisms for keeping sensitive credit-card information entirely off the Internet while still enabling online payments. But I felt their system was too complicated to explain and to use, that people would prefer the familiarity and convenience of credit cards (turns out I was right about that), and that since no one would (or should!) ever trust the Internet with their credit card information, Internet commerce could never amount to much. Yet here I am, receiving a new shipment of something or other from Amazon.com every week or two.

Oh well. At least I’m in good company. I’m sensible enough finally to have learned that however gifted I may be as a technologist, I’m no visionary. Now when someone describes some fantastical new leap they imagine, I shut up and listen.

How (and why) to program, part 1

This entry is part 1 of 2 in the series How (and why) to program

This puzzle is a ripe one for solving (some might say cheating at…) by computer. All we need is a list of four-letter words and a way to test every combination of words in the grid for validity; so let’s get to it.

This entry is part 1 of 2 in the series How (and why) to program

On May 15th, listeners to the NPR program Weekend Edition were given this challenge by puzzlemaster Will Shortz:

Create a 4-by-4 crossword square with four four-letter words reading across and four different four-letter words reading down. Use the word “nags” at 1 across and the word “newt” at 1 down. All eight words must be common, uncapitalized words, and all 16 letters must be different.

Here is the starting grid as described by Will Shortz:

1 N 2 A 3 G 4 S
5 E
6 W
7 T

This puzzle is a ripe one for solving (some might say cheating at…) by computer. All we need is a list of four-letter words and a way to test every combination of words in the grid for validity; so let’s get to it. For this example I will use the Python programming language for its conciseness and readability.

First, the list of words. On Linux and Mac OS X (and most other Unix-based operating systems) there is a file called /usr/share/dict/words, or sometimes /usr/lib/dict/words or /usr/dict/words, which is nothing but a more-or-less comprehensive list of English words, one per line. We’ll read that file to get our list of four-letter words, discarding words that are shorter or longer. In fact, since we know that every word in the grid begins with the letters in NEWT and NAGS — namely, N, E, W, T, A, G, and S — we can even discard four-letter words not beginning with one of those seven letters. And we can discard N words too, because NEWT and NAGS are already given; we don’t need to search for N words. The words we keep will be stored in six different “sets,” one for each of the six remaining starting letters.

Here’s the first section of our code: creating our six empty word-sets and giving each one a name.

a_words = set()
g_words = set()
s_words = set()
e_words = set()
w_words = set()
t_words = set()

Now to get the words we want out of the “words” file. First we “open” the file to get a special placeholder we’ll call wordlist.

wordlist = open('/usr/share/dict/words')

We’re going to read one line of the file at a time. The placeholder remembers our position in the file in between reads.

To read one line of the file at a time and do something with it, we’ll write a “loop” that begins like this:

for word in wordlist:
  ...stuff...

This will do stuff once for each line of the file, with word referring to the contents of that line. Unfortunately the first line of that stuff is a necessary but confusing bookkeeping detail:

for word in wordlist:
  word = word[:-1]
  ...more stuff...

This confusing bit of code is here because each line of the file — each line of every file, in fact — ends with an invisible “newline” character that means “this line is over, start a new one.” Since we want to deal only with the visible content of the line while doing more stuff, we need to discard that newline character, and

word = word[:-1]

is how you do that. (For our purposes right now it’s not terribly important how that works, but you can read it roughly as, “replace word with everything-in-word-except-the-last-character.”)

We’ll begin more stuff with a test to make sure that the word we’re looking at is four letters long:

for word in wordlist:
  word = word[:-1]
  if len(word) == 4:
    ...the rest of the stuff...

Here, len(word) means “the length of word” (i.e., the number of characters it contains), and == is for testing whether two things are equal. (A single = means “make this equal that,” as we’ve already seen a few times.) The rest of the stuff will only happen if len(word) is 4.

If it is 4, then we want to save the word in the correct set — either the set of A words, or the set of G words, etc. Here’s what the complete loop looks like:

for word in wordlist:
  word = word[:-1]
  if len(word) == 4:
    first_letter = word[0]
    if first_letter == 'a':
      a_words.add(word)
    elif first_letter == 'g':
      g_words.add(word)
    elif first_letter == 's':
      s_words.add(word)
    elif first_letter == 'e':
      e_words.add(word)
    elif first_letter == 'w':
      w_words.add(word)
    elif first_letter == 't':
      t_words.add(word)

After determining that len(word) was 4, we gave the name first_letter to the first letter of word (which is written as word[0], because most things in programming are counted beginning at 0 rather than at 1). We then tested first_letter to see if it was a, and added it to a_words if it was; if it wasn’t, we tested it to see if it was g, and added it to g_words if so; etc. The strange word elif appearing in the code above is simply Python’s abbreviation for “else if.”

If first_letter isn’t one of the six we care about — or if word isn’t 4 characters long to begin with — then nothing happens and we loop back around to the for word in wordlist line to get the next word.

After reading all the lines from wordlist, the loop exits and the program does whatever comes next, which is:

wordlist.close()

This is the way to say we’re finished using that placeholder and don’t need it anymore. Doing so releases resources, such as memory space, that the computer can now use for other purposes. (In a little program like this, that doesn’t matter much, so it’s OK to leave out wordlist.close(). But in large programs you can “leak” memory and other resources if you do things like fail to close files when you’re finished with them.)

OK. We’ve got our lists of candidate A words, G words, S words, E words, W words, and T words. Now the strategy will be to try every possible combination of A, G, and S words for 2, 3, and 4 Down; and then, for each of those possible combinations, check that the resulting words in 5, 6, and 7 Across make sense; and additionally that no letter is repeated anywhere in the grid.

To try every combination of A, G, and S words, first we start by trying every A word:

for a_word in a_words:
  ...stuff...

As we’ve already seen, this is a loop that will do stuff once for each entry in a_words (with a_word referring to that entry each time through the loop). Now if we nest another loop inside this loop, like so:

for a_word in a_words:
  for g_word in g_words:
    ...more stuff...

then more stuff will happen once for each possible combination of a_word and g_word. That is, first a_word will be aced (let’s say), and while a_word is aced, g_word will range from gabs to gyro; and when the g_words loop is finished, a_word will advance to aces, and g_word will again range from gabs to gyro, and so on though all the four-letter A words, each one running through all of the four-letter G words, like the digits of an odometer.

From that you should be able to guess that we need to nest another loop inside our nested loop, this one for the S words.

for a_word in a_words:
  for g_word in g_words:
    for s_word in s_words:
      ...test this combination...

Now to test this combination once for each possible combination of A word, G word, and S word. The first test is to see whether the words created by placing a_word in 2 Down, g_word in 3 Down, and s_word in 4 Down result in sensible words at 5 Across, 6 Across, and 7 Across.

Let’s construct the word at 5 Across — the E word — from the second letters of a_word, g_word, and s_word.

e_word = 'e' + a_word[1] + g_word[1] + s_word[1]

(Remember that counting the letters in a word begins at 0, so the second letter of each word is numbered 1.)

Let’s construct the W word and the T word the same way — w_word from the third letter of each Down word, and t_word from each Down word’s fourth letter.

w_word = 'w' + a_word[2] + g_word[2] + s_word[2]
t_word = 't' + a_word[3] + g_word[3] + s_word[3]

Now if a_word is ammo and g_word is gulp and s_word is shot, then e_word will be emuh, w_word will be wmlo, and t_word will be topt, which don’t make sense! But we can easily check whether the Across words make sense by seeing if they can be found in the e_words, w_words, and t_words sets that we created earlier. So:

for a_word in a_words:
  for g_word in g_words:
    for s_word in s_words:
      e_word = 'e' + a_word[1] + g_word[1] + s_word[1]
      w_word = 'w' + a_word[2] + g_word[2] + s_word[2]
      t_word = 't' + a_word[3] + g_word[3] + s_word[3]
      if e_word in e_words and w_word in w_words and t_word in t_words:
        ...remaining test...

If we get as far as the remaining test (which is to ensure that no letter is duplicated anywhere in the grid), we know that e_word and w_word and t_word are real words.

We can ensure no letter is duplicated by using another set called letters_used. The plan: go through the letters of each Down word one by one, checking whether the letter is in the set. If it’s not, then add it to the set and move to the next letter. If it is, then we’ve already seen that letter once and it’s duplicated.

We know the first Down word is newt, so we can create our set with those letters in it.

letters_used = set(['n', 'e', 'w', 't'])

(We could also have created this set like this:

letters_used = set()
letters_used.add('n')
letters_used.add('e')
letters_used.add('w')
letters_used.add('t')

which matches the way we created and used the other sets above, but the first way does the same thing more concisely.)

Now to use that set to find duplicates.

any_duplicates = False
for letter in a_word + g_word + s_word:
  if letter in letters_used:
    any_duplicates = True
    break
  else:
    letters_used.add(letter)

Here, break means “leave the loop immediately.” There’s no need to keep looping once we know there are duplicates.

By the time the loop finishes, either we’ve looped through all the letters and found no duplicates, or we exited the loop with break because we did find duplicates. We check any_duplicates to see which of those two things happened. If it’s True there were duplicates; but if it’s False then we’ve found a valid solution and can print it to display it to the user.

if any_duplicates == False:
  print a_word, g_word, s_word, e_word, w_word, t_word

To recap, here’s the complete program.

a_words = set()
g_words = set()
s_words = set()
e_words = set()
w_words = set()
t_words = set()

wordlist = open('/usr/share/dict/words')

for word in wordlist:
  word = word[:-1]
  if len(word) == 4:
    first_letter = word[0]
    if first_letter == 'a':
      a_words.add(word)
    elif first_letter == 'g':
      g_words.add(word)
    elif first_letter == 's':
      s_words.add(word)
    elif first_letter == 'e':
      e_words.add(word)
    elif first_letter == 'w':
      w_words.add(word)
    elif first_letter == 't':
      t_words.add(word)

wordlist.close()

for a_word in a_words:
  for g_word in g_words:
    for s_word in s_words:
      e_word = 'e' + a_word[1] + g_word[1] + s_word[1]
      w_word = 'w' + a_word[2] + g_word[2] + s_word[2]
      t_word = 't' + a_word[3] + g_word[3] + s_word[3]
      if e_word in e_words and w_word in w_words and t_word in t_words:
        letters_used = set(['n', 'e', 'w', 't'])
        any_duplicates = False
        for letter in a_word + g_word + s_word:
          if letter in letters_used:
            any_duplicates = True
            break
          else:
            letters_used.add(letter)
        if any_duplicates == False:
          print a_word, g_word, s_word, e_word, w_word, t_word

Put this program in a file named puzzle.py and run it with python puzzle.py. On my computer, /usr/share/dict/words contains 470 four-letter words starting with a, 359 starting with g, and 634 starting with s, and it took about two minutes and a quarter for this program to test all of the 470×359×634 combinations. (We could make this program much faster, but at the expense of clarity and simplicity.) In the end it produced this solution:

achy grip sumo ecru whim typo

which is the same solution that Will Shortz gave on the air a week later.

(Actually, my computer produced two solutions, because /usr/share/dict/words includes a lot of questionable junk in its quest to be comprehensive. The other solution was “achy goup sld. ecol whud typ.”)

Update: As a couple of friends have pointed out, the Mac OS X version of /usr/share/dict/words does not include all the words needed to find the solution! I ran mine on Linux, which does.