um/provided/task.html

258 lines
10 KiB
HTML
Raw Permalink Normal View History

2018-06-29 02:08:11 +00:00
<!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&nbsp;Programming&nbsp;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&nbsp;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&nbsp;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&mdash;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>&nbsp;</p>
</div>
</td>
</tr></table>
</div>
</body>
</html>