The Panama palindrome

By its true and real author, Dan Hoey

Copyright 2001 by Dan Hoey. 

Jim Saxe was perhaps the first person to put a cat in the canal.

A man, a plan, a cat, a canal; Panama!
-- Jim Saxe, plan file @ CMU, 9 October 1983

Guy Jacobson added several items later that year.

A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal--Panama!
-- Guy Jacobson, plan file @ CMU late 1983

Guy's palindrome appears on page 127 of Common Lisp, the Language (page 170 of the 2nd edition). The 2nd edition of Common Lisp, the Language also contains the remarkable:

A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, snipe, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal--Panama!

which is I'd guess is the work of Guy Steele, the book's author. But I haven't asked either of those Guys to make sure.

The appearance of the first two variants intrigued me, and I wondered just how much could be put into the canal. I wrote some code in 1984 to work with it using the Unix "spell" dictionary. By the time I had it working, I was mostly tired of the problem, so I settled for the fairly modest 543-word version that you see.

The problem of making the longest possible palindrome of this type is NP-complete, but there are approaches that I expect would generate palindromes many thousands of words long. A trickier problem is getting a good vocabulary, especially one with parts of speech. It took a lot of work to prune out the palindromes that were full of things like "a how, a do, a for, an ochre, a was, an of, ...." I was never quite sure whether I should have put in many of the things that I did. Just what would a myriad look like in a canal? Or a tort?

There's a short article on my approach in Expert C Programming: Deep C Secrets by Peter van der Linden. Unfortunately, when the book got reviewed by Stan Kelly-Bootle in Unix Review he included the palindrome but not only misspelled my name, but credited the algorithm to Jim Saxe.

As far as publication history goes, I put the palindrome in my plan file on host CMU-CS-A.ARPA on 26 July 1984. My recollection is that my program had produced it earlier that same day. In those days the plan files were collected and redistributed by email to a number of CMU and ex-CMU people, as well as being available by finger. On 29 Feb 1988 I gave permission for it to be posted to the Stanford bulletin board. I don't know of any Usenet appearance before I posted it in May, 1990. It was in January, 1992 that I first saw it posted without attribution, in a collection on rec.humor. I have sent a few dozen notices to people asking them to add attributions, but it's not terribly pleasant work--who likes to hear complaints?--so I'm not very reliable about letting people know. But that's led to even more unattributed reposting.