[Kc] Perl 'Expert' Quiz-of-the-Week #21
Garrett Goebel
garrett at scriptpro.com
Thu Aug 12 11:00:20 CDT 2004
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 enviis soluciones, pistas, o cualquier otra
cosa que pueda echar a perder la resolucin del problema hasta
que hayan pasado por lo menos 60 horas desde el envo de este
mensaje. Gracias.
IMPORTANT: S'il vous plat, attendez au minimum 60 heures aprs la
date de ce message avant de poster solutions, indices ou autres
rvlations. Merci.
Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4.
UWAGA: Prosimy nie publikowac rozwiazan, dodatkowych badz pomocniczych
informacjii przez co najmniej 60 godzin od daty tej wiadomosci.
Dziekuje.
----------------------------------------------------------------
In the 1960's, the grad students at the University of Chicago math
department worked on a series of astoundingly useless and time-consuming
puzzles. One of these follows. Consider the set of all possible strings of
the alphabet ('a' .. 'z'). Let us agree to consider two strings
"equivalent" if the following conditions hold:
1. They contain precisely the same letters, and
2. They both appear in Webster's Third International Dictionary.
In such a case, the two strings are considered interchangeable in all
contexts. For example, "am" and "ma" are equivalent, and this also implies
that "amount" and "maount" are equivalent, as are "grammar"
and "grmamar" and "gramamr" and "grmaamr".
Moreover, equal letters can be cancelled from the front and back end of any
string. For example, "abby" and "baby" are equivalent, and, cancelling the
trailing "by", this implies that "ab" and "ba" are also equivalent, and can
be exchanged anywhere. When two letters can be exchanged in this way, we
say that they "commute". The third floor of the math building at UC had a
huge 26x26 chart; the square in column i and row j contained a proof that
letters i and j would commute.
Sometimes these proofs can be rather elaborate. For example, the dictionary
has "dire" and "ride", so, by cancelling the trailing "e"s, one has "dir" =
"rid".
The dictionary also has
dirten = rident
(No, I don't know what those mean.) Since "dir" = "rid" we have:
rident = dirent
and since "rident" = "dirten",
dirten = dirent
even though "dirent" is not a dictionary word. Cancelling the leading "dir"
leaves:
ten = ent
but
ten = net
because "ten" and "net" are dictionary words, so
ent = net
and, cancelling the "t",
en = ne
and we've just proved that "en" and "ne" commute. This fact might be useful
in later proofs.
What's the point of all this? Well, the goal is to find out which letters
commute with *every* other letter; such letters are said to be in the
"center" of the system. As for the *point*, I'm not sure there is one.
Apparently the math grads at UC didn't have enough to occupy their time.
The chart in the UC math building has since been lost, so your task is to
write a program whose input is a word list, with one word per line, and
which makes appropriate deductions and eventually computes the center of the
system. I don't have the headword list from Webster's Third, but I do have
the list from Webster's Second, so let's use that. You can get a copy from
http://perl.plover.com/qotw/words/Web2.bz2
http://perl.plover.com/qotw/words/Web2.gz
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/pipermail/kc/attachments/20040812/67f722ef/attachment-0001.htm
More information about the kc
mailing list