[Neworleans-pm] Fwd: Perl 'Expert' Quiz-of-the-Week #21

E. Strade, B.D. estrabd at yahoo.com
Thu Aug 12 07:29:46 CDT 2004




=====
http://www.brettsbsd.net/~estrabd

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com

----- Original message -----
From: "Mark Jason Dominus" <mjd at plover.com>
To: perl-qotw at plover.com
Date: Thu, 12 Aug 2004 07:44:11 -0400
Subject: Perl 'Expert' Quiz-of-the-Week #21


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, attendez au minimum 60 heures après la
        date de ce message avant de poster solutions, indices ou autres
        révélations. 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








More information about the NewOrleans-pm mailing list