Perl 'Expert' Quiz-of-the-Week #4

Mark Jason Dominus <[email protected]> Wed, 06 Nov 2002 18:22:59 -0500
Newsgroups gmane.comp.lang.perl.qotw.quiz-of-the-week
Organization Plover Systems
Message-ID <[email protected]>
IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.
        Thanks.

IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra
        cosa que pueda echar a perder la resolución del problema hasta
        que hayan pasado por lo menos 60 horas desde el envío de este
        mensaje. Gracias.


IMPORTANT: S'il vous plaît, ne postez pas de solutions, indices ou
        autre révélations jusqu'à au moins 60 heures après la date de
        ce message. Merci

WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für
        diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser
        Mail. Danke.

----------------------------------------------------------------


If you were to write a program to locate all the anagrams in a
dictionary, you would find a lot of very boring anagrams.  For
example, Webster's International Dictionary, Second Edition, yields


        glossolabiopharyngeal labioglossopharyngeal
        anatomicopathological pathologicoanatomical

and suchlike.  

Part of the problem with such 'anagrams' is that the words are
extremely obscure, specialized technical jargon.  But even well-known
words can fail to produce interesting anagrams:

        addresser readdress

The major reason these anagrams fail to be interesting is because they
really consist of rearrangements of words. not rearrangments of
letters.  Even technical jargon can be interesting if it's
sufficiently non-obvious; I'd submit that:

        protomagnesium spermatogonium

is reasonably interesting; when the words are more familiar, the
result can be spectacular:

        urogenital regulation

        ancestorial lacerations

This suggests the following heuristic for the 'interestingness' of a
pair of anagrammatic words:  If one word can be rearranged to form the
other after being broken into just a few chunks, it is probably not
very interesting.  If it must be broken into many chunks to be so
rearranged, it is likely to be more interesting.

Applying this heuristic to the examples above, we see that the two
'boring' examples are only two-, three- and four-chunk anagrams:

        address/er re/address
        glosso/labio/pharyngeal labio/glosso/pharyngeal
        anatomic/o/pathologic/al pathologic/o/anatomic/al

Whereas the 'reasonably interesting' example is a ten-chunk anagram:

        p/r/o/to/ma/g/n/e/s/ium s/p/e/r/ma/to/g/o/n/ium

As are the 'spectacular' examples:

        u/r/o/g/e/n/i/t/a/l r/e/g/u/l/a/t/i/o/n

        a/n/ce/s/t/o/r/i/a/l l/a/ce/r/a/t/i/o/n/s

(No simpler decompositions are possible.)

Note that this heuristic naturally favors long anagrams over short
ones; it is impossible that a three-letter anagram pair could get a
score higher than 3.  This is consistent with most peoples' judgement
of anagram quality: short words' anagrams are rarely or never
interesting.  

Write a function, 'min_chunks', whose arguments are two words which
are anagrams of one another, and which returns the minimum number of
chunks into which the first word must be divided before the chunks can
be rearranged to form the second word.

Use the function to generate interesting anagrams.