Comments on World's Longest Palindrome?

Several notable readers have commented on my world's longest palindrome page:

Subject: Re: World's Longest Palindrome?
   From: Grady Ward
     To: Peter Norvig


Peter,

Brilliant and funny.

I like the NP pun echoing NP (complete) world of complexity.

Not too often you break the current world's record by well over
an order of magnitude.

I suspect that your record will not itself be broken by an order
of magnitude for a few years at least. <g>

You will start getting calls from Scientific American, The New
York Times, The New Yorker, The Times Literary Supplement,
and others who will widely publicize your achievement. It's a
way of showing an easily understood intersection between
computing and the demotic language.

If people want to try to beat you, Moby Lexicons are freely
available from Project Gutenberg http://promo.net/pg/ now,
as well as other sites on the net such as the University of Sheffield.

I don't know which of your page is the most brilliant: the palindrome
itself, your elegant approach to generating it, or your pleasant funny
commentary.

Thank you very much for sharing your achievement with me.

regards,
Grady Ward
                            (You just know that Grady has found the right niche
                            as a lexicographer when he uses words like demotic 
                            in one message and daedal in the next. And I didn't
                            think the Times would call, but they did, so I guess
                            Grady knows demotic language. 

                            However, in fairness to Dan Hoey, he was going for 
                            all proper noun phrases while I allowed names.  
                            Restricting to proper noun phrases I get only
                            2,211 words, a factor of four improvement, not
                            an order of magnitude. -- PN)
Subject: Re: palindromep
   From: Guy Steele
     To: Peter Norvig

Well, this is just completely ridiculous!
The best smile I've had in a while.  Thanks
for the whimsy (and the nice mention).

For 20:02 03/30 2002, consider expanding the grammar
slightly.  For example, besides the indefinite articles
"a" and "an" (which skew things towards words containing "a"),
consider an additional set of noun phrases, such as
"two Xs" and "the X of Y" and "an X that Vs Ys" (V a verb).

--Guy
Subject: Re: World's Longest Palindrome?
   From: Dan Hoey
     To: Peter Norvig

Very nice.  I was really thinking of sticking with noun phrases of the
form "<indefinite article> <noun>", and for that a somewhat better
program might be needed.  (I might even write it).

I'm sorry to say that you seem to have used 710 noun phrases twice
(arguably "Panama" is a 711th), and the phrase "a canal" three times.
Presumably it's minor bug that could be ironed out easily.  Perhaps
you just don't check for duplicates between the two halves of the
palindrome or against the "canal--Panama!" part. 

                            (This bug fixed It was exactly what
                            Dan said. -PN)

I was curious about how you figure out whether to put "a" or "an" in
front of singular nouns, since I once wrote a program to make that
decision.  I would disagree with "a honor" and "a rpm", for instance.
I'm suppose "an uranide" depends on your pronunciation.

                            (My rule -- "an" before vowels -- was intended 
                            to make quick decisions, not good ones. -PN)

Still, I'm impressed that you were able to pull this together so
quickly.  The prefix search program took me days to write, including a
B-tree package that I've never used since.  And I'm greatly indebted
for the pointer to the Moby lexicon, though I can't seem to get
through to the FTP site just now.

                            (I think there are two lessons from this:
                            (1) Simple data structures are better than 
                            complex ones (like B-trees) when you can afford
                            the memory. (2) You can afford a lot more memory
                            in 2002 than in 1984. -PN)

Dan
Subject: Re: World's Longest Palindrome?
   From: Jasvir Nagra
     To: Peter Norvig

Hi

A friend of mine just pointed me at your site as the source of the
world's longest palindrome.  I was quite impressed with your
palindrome and was inspired to check it (in the interest of peer
review you realise, not skepticism).

Attached is the quick piece of perl that finds these errors.  There
are three such locations (or six depending on how you).  Elimating all
punctuation these occur at offset:

1005 : p, o
14053: b, a
26014: d, c
28110: c, d
40071: a, b
53119: o, p

I had a quick glance at is_palindrome in your python generator but did
not see anything obviously incorrect.  All the errors seem off by one
which seems curious.  As a result, I am tempted to think this is
intentional on your part to "watermark" your answer. But this is
probably because my research area is in watermarking and I seem to see
everything tainted in this light. ;-)

#!/usr/bin/perl -w

local undef $/;
my $palindrome = <>;
my $reverse = reverse $palindrome;

while ( $palindrome =~ /([^a-z]*?)([a-z])/icg ) {
  my($plead, $pchar) = ($1,$2);

  $reverse =~ /([a-z])/icg;
  my $rchar = $1;

  if ( lc $pchar eq lc $rchar ) {
      print "$plead$pchar";
    } else {
      print "$plead($pchar|$rchar)";
    }
}

                 (It was a bug, not a watermark:
                 a boundary case in the dictionary lookup that occurred
                 about 3 out of 12,000 times, it seems.  I fixed it.
                 That should teach me not to try to develop on an
                 Extreme Programming schedule without writing sufficient
                 test cases. See also Josh Bloch on how hard it is to get 
                 a binary search right. -PN)

Subject: World's Longest Palindrome?
   From: Ken Seehof
     To: Peter Norvig

Hey, I got a slightly longer one... :-)

http://www.neuralintegrator.com/palindrome

- Ken

                    (This link has now died. It was a page full
                    of genomic bases, starting with "ACGT..." and ending
                    with "...TGCA". Those DNA-based lifeforms really
                    thrive on redundancy, don't they?  -PN)


Peter Norvig, 20:02 02/20 2002