258 lines
10 KiB
HTML
258 lines
10 KiB
HTML
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
|
||
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
|
||
|
|
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
|
||
|
|
<head>
|
||
|
|
<title>ICFP Programming Contest, 2006 : Contest Materials and Task</title>
|
||
|
|
<link rel="stylesheet" type="text/css" href="icfp.css" title="ICFP" />
|
||
|
|
<!-- try to fix pngs on ie -->
|
||
|
|
<!--[if gte IE 5.5000]>
|
||
|
|
<script type="text/javascript" src="pngfix.js"></script>
|
||
|
|
<![endif]-->
|
||
|
|
</head>
|
||
|
|
<body style="background: #123456">
|
||
|
|
|
||
|
|
<div style="align: center ; width: 600px ; padding: 0px ; margin : 0px">
|
||
|
|
<!-- header -->
|
||
|
|
<div style="padding : 4px ; width: 600px ; background : #234567 ; border: 1px solid #012345">
|
||
|
|
<div class="headingsmall">Ninth annual</div><div class="heading">ICFP Programming Contest</div>
|
||
|
|
<div style="font-size : 10px ; padding : 1px ; color : #AAAACC ; background : #2A4C6F ; text-align : right ; margin-top : -4px ">Hosted by <a href="http://www.cs.cmu.edu/" style="text-decoration : none ; font-weight : normal">Carnegie Mellon University</a>'s <a style="text-decoration: none ; font-weight : normal" href="http://www.cs.cmu.edu/afs/cs/Web/Groups/pop/pop.html">POP Group</a></div>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
|
||
|
|
<!-- sidebar -->
|
||
|
|
<table border="0" cellpadding="0" cellspacing="0" style="border : 0px ; margin : 0px ; padding : 0px">
|
||
|
|
<tr><td valign="top">
|
||
|
|
<div class="sidebar">
|
||
|
|
<a class="button" href="/index.shtml">Home</a>
|
||
|
|
<a class="button" href="/task.shtml">Task</a>
|
||
|
|
<a class="button" href="/rulesfaq.shtml">Rules/FAQ</a>
|
||
|
|
<!--
|
||
|
|
<a class="button" href="/register.shtml">Register</a>
|
||
|
|
-->
|
||
|
|
<a class="button" href="/teams.shtml">Teams</a>
|
||
|
|
<a class="button" href="/scoreboard.shtml">Scoreboard</a>
|
||
|
|
<a class="button" href="/code.shtml">Source Code</a>
|
||
|
|
<!--
|
||
|
|
<a class="button" href="/submit.shtml">Submit</a>
|
||
|
|
<a class="button" href="/results.shtml">Results</a>
|
||
|
|
-->
|
||
|
|
<a class="button" href="/contact.shtml">Contact</a>
|
||
|
|
<a class="button" href="/previous.shtml">Past Years</a>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
</td>
|
||
|
|
<!-- content area -->
|
||
|
|
<td valign="top">
|
||
|
|
<div class="content">
|
||
|
|
|
||
|
|
<h1>An Urgent Appeal</h1>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
Dear Colleague:
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
In 1967, during excavation for the construction of a new shopping
|
||
|
|
center in Monroeville, Pennsylvania, workers uncovered a vault
|
||
|
|
containing a cache of ancient scrolls. Most were severely damaged,
|
||
|
|
but those that could be recovered confirmed the existence of a secret
|
||
|
|
society long suspected to have been active in the region around the
|
||
|
|
year 200 BC.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
Based on a translation of these documents, we now know that the
|
||
|
|
society, the Cult of the Bound Variable, was devoted to the careful
|
||
|
|
study of computation, over two millennia before the invention of the
|
||
|
|
digital computer.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
While the Monroeville scrolls make reference to computing machines
|
||
|
|
made of sandstone, most researchers believed this to be a poetic
|
||
|
|
metaphor and that the "computers" were in fact the initiates
|
||
|
|
themselves, carrying out the unimaginably tedious steps of their
|
||
|
|
computations with reed pens on parchment. A few have conjectured a
|
||
|
|
city-sized machine powered by falling sand, but no physical evidence
|
||
|
|
of such a device has been discovered.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
Among the documents found intact in the Monroeville collection was a
|
||
|
|
lengthy codex, written in no known language and inscribed with
|
||
|
|
superhuman precision. It is believed to be the masterwork of the
|
||
|
|
Cult's scholarship, and as such it carries immense potential to
|
||
|
|
advance our understanding of history—and possibly of computing as
|
||
|
|
well. Unfortunately, the codex eluded interpretation, and over the
|
||
|
|
decades, study of the Monroeville scrolls has slipped into obscurity.
|
||
|
|
Since 1978, the codex has been stored in the basement of the Carnegie
|
||
|
|
Museum of Natural History.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<img src="spec.png" style="float : right ; padding : 4px 0px 4px 12px" />
|
||
|
|
<p>
|
||
|
|
Two weeks ago, during a visit to the excavation site for a new
|
||
|
|
computer science building at CMU, workers discovered a set of
|
||
|
|
inscribed tablets that proved to be the Rosetta Stone for interpreting
|
||
|
|
the Monroeville codex. The tablets precisely specify the Cult's
|
||
|
|
computing device, known to initiates as the "Universal Machine."
|
||
|
|
Although there is still no evidence that the cult succeeded in
|
||
|
|
constructing their machine, it is a reasonably simple task to emulate
|
||
|
|
it on modern hardware.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
We can now say with certainty that the codex is in fact a program,
|
||
|
|
intended for execution on the Universal Machine. Our initial
|
||
|
|
exploration of the codex suggests that the Cult's ideas about
|
||
|
|
programming were very sophisticated, if somewhat peculiar to the
|
||
|
|
modern eye. One cannot help but wonder what the Cult might have
|
||
|
|
achieved had they had access to modern electronics and type theory.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
I have enlisted the help of the CMU Principles of Programming group in
|
||
|
|
creating a venue for study of the codex. We invite you to participate
|
||
|
|
in this investigation. The codex and a translation of the Universal
|
||
|
|
Machine (UM) specification are available for <a
|
||
|
|
href="#materials">download</a> from our web site. We encourage you to
|
||
|
|
implement the UM and begin your own exploration of the codex. When
|
||
|
|
you are prompted to enter a decryption key, type the following string:
|
||
|
|
<span class="hexstring"> (\b.bb)(\v.vv)06FHPVboundvarHRAk </span>
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
The Cult's scholarly publications are of particular interest to us.
|
||
|
|
Because the Cult's journals were circulated on sandstone tablets,
|
||
|
|
editors imposed very strict length limitations. Consequently, authors
|
||
|
|
aggressively compressed their articles. A typical publication would
|
||
|
|
have the following form:
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<center><span class="publication">PUZZL.TSK=100@1001|14370747643c6d2db0a40ecb4b0bb65</span></center>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
<!--
|
||
|
|
Should you encounter any such publications, we humbly request that you
|
||
|
|
<a href="http://www.icfpcontest.org/submit.shtml">submit them</a> to
|
||
|
|
us via our web site. Our server will track all submitted publications,
|
||
|
|
ensuring that every participant is given appropriate credit for
|
||
|
|
advancing our understanding of the codex.
|
||
|
|
-->
|
||
|
|
Publications are of varying
|
||
|
|
value; some will represent a greater contribution than others. Given our
|
||
|
|
understanding of the Cult's publication process, we believe there is a
|
||
|
|
mechanism within the codex that will verify a set of publications and compute their total
|
||
|
|
value.
|
||
|
|
<!--
|
||
|
|
, and we
|
||
|
|
will take this into account when assigning credit.
|
||
|
|
-->
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
On a personal note, being inspired by the scholarship of the
|
||
|
|
Cult, I have decided to dedicate the remainder of my days to a solitary
|
||
|
|
study of computation and programming languages. However, before
|
||
|
|
embarking on my monastic transformation, I wish to see that the
|
||
|
|
world is well on its way to uncovering the secrets of the Codex.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
Therefore, I ask that you submit as many publications as you can by
|
||
|
|
noon EDT on July 24, 2006, at which time I will be taking my orders.
|
||
|
|
My colleagues in the CMU POP group assure me that at that time, the
|
||
|
|
teams that have made the greatest contribution to the effort shall be
|
||
|
|
identified for special recognition.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>
|
||
|
|
Good luck and thank you for your assistance.
|
||
|
|
</p>
|
||
|
|
|
||
|
|
|
||
|
|
<p>
|
||
|
|
Sincerely,<br/>
|
||
|
|
<br/>
|
||
|
|
Professor Emeritus Harry Q. Bovik<br/>
|
||
|
|
Computational Archaeolinguistics Institute<br/>
|
||
|
|
Carnegie Mellon University<br/>
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<br/><br/>
|
||
|
|
|
||
|
|
<h1>Contest Materials</h1> <a name="materials"></a>
|
||
|
|
|
||
|
|
<h2>UM Specification</h2>
|
||
|
|
|
||
|
|
<div style="margin-left: auto; margin-right : auto; border : 1px dashed #123456 ; background : #345678 ; padding : 4px ; width : 400px ">
|
||
|
|
<table border=0><tr><td valign=center><a href="um-spec.txt"><img src="file_txt.gif" border="0" style="margin-top : 6px ; margin-right : 6px"></a></td><td valign=center><a class="filelink" href="um-spec.txt">um-spec.txt</a></td></tr></table>
|
||
|
|
<table width="100%">
|
||
|
|
<tr><td>Specification for the Universal Machine. Text format.</td></tr>
|
||
|
|
</table>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
|
||
|
|
<h2>Codex</h2>
|
||
|
|
|
||
|
|
<div style="margin-left: auto; margin-right : auto; border : 1px dashed #123456 ; background : #345678 ; padding : 4px ; width : 400px ">
|
||
|
|
<table border=0>
|
||
|
|
<tr><td valign=center><a href="codex.umz"><img src="file_umz.gif" border="0" style="margin-top : 6px ; margin-right : 6px"></a></td><td valign=center>
|
||
|
|
<a class="filelink" href="codex.umz">codex.umz</a> (VOLUME ID 9)</td></tr></table>
|
||
|
|
<table width="100%">
|
||
|
|
<tr><td>MD5 hash</td><td class="hexstring"> e328209bd65ade420371d7bd87b88e4f </td></tr>
|
||
|
|
<tr><td>SHA-1 hash</td><td class="hexstring"> 088ac79d311db02d9823def598e48f2f8723e98a </td></tr>
|
||
|
|
<tr><td>Decryption key</td><td class="hexstring"> (\b.bb)(\v.vv)06FHPVboundvarHRAk </td></tr>
|
||
|
|
</table>
|
||
|
|
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<h2>SANDmark</h2>
|
||
|
|
|
||
|
|
<div style="margin-left: auto; margin-right : auto; border : 1px dashed #123456 ; background : #345678 ; padding : 4px ; width : 400px ">
|
||
|
|
<table border=0>
|
||
|
|
<tr><td valign=center><a href="sandmark.umz"><img src="file_umz.gif" border="0" style="margin-top : 6px ; margin-right : 6px"></a></td><td valign=center>
|
||
|
|
<a class="filelink" href="sandmark.umz">sandmark.umz</a></td></tr>
|
||
|
|
</table>
|
||
|
|
<table width="100%">
|
||
|
|
<tr><td>Benchmark for the Universal Machine. <a href="sandmark-output.txt">Expected output.</a></td></tr>
|
||
|
|
</table>
|
||
|
|
<table width="100%">
|
||
|
|
<tr><td>MD5 hash</td><td class="hexstring">1c604d454de05d04afdabd2c63fb27fb</td></tr>
|
||
|
|
<tr><td>SHA-1 hash</td><td class="hexstring">c2ee087aa661e81407fbcf0d9d7e503aff9b268e</td></tr>
|
||
|
|
</table>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<h2>Reference Implementation</h2>
|
||
|
|
|
||
|
|
<div style="margin-left: auto; margin-right : auto; border : 1px dashed #123456 ; background : #345678 ; padding : 4px ; width : 400px ">
|
||
|
|
<table border=0>
|
||
|
|
<tr><td valign=center><a href="um.um"><img src="file_umz.gif" border="0" style="margin-top : 6px ; margin-right : 6px"></a></td><td valign=center>
|
||
|
|
<a class="filelink" href="um.um">um.um</a> (1024 bytes)</td></tr>
|
||
|
|
</table>
|
||
|
|
<table width="100%">
|
||
|
|
<tr><td>CMU Reference implementation of the Universal Machine.</td></tr>
|
||
|
|
</table>
|
||
|
|
<table width="100%">
|
||
|
|
<p>This implementation supports all UM programs, including uncompressed
|
||
|
|
.um files and self-decompressing .umz files. To use this
|
||
|
|
implementation to run a UM binary called c.um, simply concatenate the
|
||
|
|
two files together:</p>
|
||
|
|
|
||
|
|
<p><span class="balance">cat um.um c.um > cmu.um</span></p>
|
||
|
|
|
||
|
|
<p>The resulting binary can be run in any compliant universal machine
|
||
|
|
implementation, including itself.</p>
|
||
|
|
</table>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
<p> </p>
|
||
|
|
|
||
|
|
</div>
|
||
|
|
</td>
|
||
|
|
</tr></table>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
</body>
|
||
|
|
</html>
|