<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2657.73">
<TITLE>Perl 'Expert' Quiz-of-the-Week #21</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>IMPORTANT: Please do not post solutions, hints, or other spoilers</FONT>
<BR><FONT SIZE=2> until at least 60 hours after the date of this message.</FONT>
<BR><FONT SIZE=2> Thanks.</FONT>
</P>
<P><FONT SIZE=2>IMPORTANTE: Por favor, no enviis soluciones, pistas, o cualquier otra</FONT>
<BR><FONT SIZE=2> cosa que pueda echar a perder la resolucin del problema hasta</FONT>
<BR><FONT SIZE=2> que hayan pasado por lo menos 60 horas desde el envo de este</FONT>
<BR><FONT SIZE=2> mensaje. Gracias.</FONT>
</P>
<P><FONT SIZE=2>IMPORTANT: S'il vous plat, attendez au minimum 60 heures aprs la</FONT>
<BR><FONT SIZE=2> date de ce message avant de poster solutions, indices ou autres</FONT>
<BR><FONT SIZE=2> rvlations. Merci.</FONT>
</P>
<P><FONT SIZE=2>Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60</FONT>
<BR><FONT SIZE=2> Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4</FONT>
<BR><FONT SIZE=2> Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4.</FONT>
</P>
<P><FONT SIZE=2>UWAGA: Prosimy nie publikowac rozwiazan, dodatkowych badz pomocniczych</FONT>
<BR> <FONT SIZE=2>informacjii przez co najmniej 60 godzin od daty tej wiadomosci.</FONT>
<BR> <FONT SIZE=2>Dziekuje.</FONT>
</P>
<P><FONT SIZE=2>----------------------------------------------------------------</FONT>
</P>
<P><FONT SIZE=2>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:</FONT></P>
<P><FONT SIZE=2> 1. They contain precisely the same letters, and</FONT>
<BR><FONT SIZE=2> 2. They both appear in Webster's Third International Dictionary.</FONT>
</P>
<P><FONT SIZE=2>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"</FONT></P>
<P><FONT SIZE=2>and "grmamar" and "gramamr" and "grmaamr".</FONT>
</P>
<P><FONT SIZE=2>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.</FONT></P>
<P><FONT SIZE=2>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".</FONT></P>
<P><FONT SIZE=2>The dictionary also has</FONT>
</P>
<P><FONT SIZE=2> dirten = rident</FONT>
</P>
<P><FONT SIZE=2>(No, I don't know what those mean.) Since "dir" = "rid" we have:</FONT>
</P>
<P><FONT SIZE=2> rident = dirent</FONT>
</P>
<P><FONT SIZE=2>and since "rident" = "dirten", </FONT>
</P>
<P><FONT SIZE=2> dirten = dirent</FONT>
</P>
<P><FONT SIZE=2>even though "dirent" is not a dictionary word. Cancelling the leading "dir" leaves:</FONT>
</P>
<P><FONT SIZE=2> ten = ent</FONT>
</P>
<P><FONT SIZE=2>but</FONT>
<BR><FONT SIZE=2> ten = net</FONT>
</P>
<P><FONT SIZE=2>because "ten" and "net" are dictionary words, so</FONT>
</P>
<P><FONT SIZE=2> ent = net</FONT>
</P>
<P><FONT SIZE=2>and, cancelling the "t", </FONT>
</P>
<P><FONT SIZE=2> en = ne</FONT>
</P>
<P><FONT SIZE=2>and we've just proved that "en" and "ne" commute. This fact might be useful in later proofs.</FONT>
</P>
<P><FONT SIZE=2>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.</FONT></P>
<P><FONT SIZE=2>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</FONT></P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/words/Web2.bz2" TARGET="_blank">http://perl.plover.com/qotw/words/Web2.bz2</A></FONT>
<BR><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/words/Web2.gz" TARGET="_blank">http://perl.plover.com/qotw/words/Web2.gz</A></FONT>
</P>
<BR>
<BR>
<BR>
<BR>
</BODY>
</HTML>