A "catalpa" (in case you're wondering) is a native American word for a type of tree. You can look up
axon and calamus for yourself. Dan commented that a little work on the search algorithm could make
it several times as long.
The search algorithm was ingenious—Dan programmed a finite state machine that evaluates a series
of partial palindromes. In each case, the state consists of the unmatched part of the palindrome.
Starting with the original palindrome, Dan noted that the "a ca" of "a canal" is right at the middle of
the phrase, so we can add anything we like after "a plan" as long as its reverse forms a word or part-
word when put after that.
To insert additional words after "a plan," just start by doubling the "a ca" in the middle. This gives us
"..., a plan, a ca... a canal,..." We could stop right there if "ca" was a word, but it's not. So find
something that completes the fragment on the left, and add the same thing spelled backwards on the
right, for example, "ret ... ter."
In each step, the end part of the word we add is spelled backwards, and becomes the beginning part of
the next word we look for. Table 4-2 shows the process:
Table 4-2. Building a Palindrome
State "-aca": "A man, a plan, ... a canal, Panama"
State "ret-": "... a plan, a caret, ... a canal, Panama"
State "-aba": "... a plan, a caret, ... a bater, a canal, ..."
State "n-": "... a caret, a ban, ... a bater, a canal, ..."
State "-adairyma": "... a caret, a ban, ... a dairyman, a bater, ..."
State "-a": "... a ban, a myriad, ... a dairyman, a bater, ..."The accepting states of the finite state machine are those where the unmatched part is itself
palindromic. In other words, at any point where the words just chosen are a palindrome in themselves,
you can stop. In this case, the palindrome "... a nag, a pagan, ..." is at the center, and putting in "-apa-
" terminated the algorithm.
Dan used a small word list that only contained nouns. If you don't do this you get a lot of "a how, a
running, a would, an expect, an and..." which is nonsensical. An alternative would be a real on-line
dictionary (not just word list) that indicates which words are nouns. That way, a really big palindrome
could be generated. But as Dan says, "if I got a 10,000 word palindrome, I wonder if anyone would
want it. I like this one, because it's small enough to pass around. And I've already done the work." You
can't argue with that!