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.