World's Longest Palindrome? - The Algorithm

The algorithm I used to create the world's longest palindrome (?) is as follows:
(1) Start off with the following seed text, divided into a left and right half:
A man, a plan, a canal, Panama

(2) Find the bit that is not palindromic; that is, not matched by text on the other side. Call that the remainder and color it red: aca. Since the remainder is itself a palindrome, the whole enchilada must be a palindrome. Record it as such, but keep going to try and find a longer one.
A man, a plan, a canal, Panama

(3) Look in the dictionary for words or phrases that begin with aca. Randomly choose one and add it to the left. Remember the others for later. In my example, the program chose a caddy. Identify the remainder again, namely ddy:
A man, a plan, a caddy, a canal, Panama

(4) Now find in the dictionary a word that ends with ydd (the reverse of ddy). The program found Roydd, which is a male first name (although far from a common one). Add it to the right, leaving the remainder Ro:
A man, a plan, a caddy, Roydd, a canal, Panama

(5) Now we need a word starting with or (the reverse of Ro) on the left. The program chose Ore. The remainder, e, is a palindrome, so again we've got a winner. Print it to a file and move on.
A man, a plan, a caddy, Ore, Roydd, a canal, Panama

(6) Keep going back and forth in this fashion, until you have 10 or 15 thousand words. However, at some point we may need to backtrack. For example, suppose the program next chose Belize:
A man, a plan, a caddy, Ore, Belize, Roydd, a canal, Panama

(7) We need a word on the left that starts with zileb, but there is no such word in my dictionary. So we backtrack, erasing Belize and trying another word that ends in e. Fortunately, there are many of these. If there were not, we would have to backtrack another step and erase Ore, replacing it with another word that starts with or.

There are a few more technical details. For example, whenever I choose a word, I need to record it so that I don't use it again (but un-record it when backtracking over it). For the other details, see the program listing, or go back to the palindrome itself.


Peter Norvig, 20:02 02/20 2002 See some comments on this page.