Michael Naunton <···@news.bellatlantic.net> wrote in message news:<··················@micron.bellatlantic.net>...
> http://www.ravenbrook.com/doc/2003/05/28/contest/
>
> I wanna see the elegant and generally spiffy solutions!
>
> -- MMN
The following document was "read" at the ILC 2003 last week. It is
now available on the web, at
http://www.ravenbrook.com/doc/2003/05/28/contest/judges-report.txt.
All entries have been published: see
http://www.ravenbrook.com/doc/2003/05/28/contest/entries/.
My apologies for the delay in publication. (I'd like only to cite
laptop problems...)
Thanks once again to all who took the time to enter the competition.
- nick
--------------------8<--------------------
ILC 2003 Programming Contest
Judges' Report
Nick Levine and Nicholas Barnes, 2003-10-02
The "Last Piece Puzzle" consists of fourteen polyominos which have to
be fitted into a square frame. The position of one of the pieces (the
triomino) is constrained. It turns out that there are five ways in
which the other pieces can be fitted around it. The aim of the
programming contest was for contestants to solve the puzzle, in
Common Lisp.
Details of the contest were posted on June 14th. Two entries were
received late the following day and four more over the following
week. We had a bit of a lull over the summer and then a mad scramble
at the end with 6 entries in the final four days bringing the total
number to 15 by the closing date of September 27th.
Many thanks to everyone who took the time to have a go at this.
The judges have awarded prizes as follows. In some cases we have made
an "honourable mention" of someone who did almost as well.
First working entry received: Carlos Ungil, with an honourable mention
for Pierpaolo Bernardi who was only a couple of hours behind.
The prize for elegance is awarded to Russ Ross, in particular for his
elegant description of the pieces:
("JJJJLLLL"
"NNsJL3QQ"
"TNss33Qj"
"TNNstQQj"
"TTWtttjj"
"TWWZZZll"
"WWSSFZZl"
"SSSFFFFl")
Russ generated this description from a diagram in the contest rules
which showed the pieces in the frame but not satisfying the constraint
on the triomino.
An honourable mention for elegant coding goes to Conrad Barski, for
the following piece description:
(( * )
( * * )
( * )
( * ))
However, Conrad also gets an honourable mention in the Obscure Coding
category, for burying labels statements 6 deep. The winner for
Obscure Coding is Denis Mashkevich, for his cunning though somewhat
inpenetrable (not to mention, apparently non-terminating) use of a
"non deterministic lisp".
We also award Denis an "added value" prize, for taking the trouble to
learn lisp from scratch in order to enter the competition.
The "under 21" is prize shared by Scott Fenton and Vladimir Sedach.
Finally, we come to the speed trials. The contest rules state that
this category means: the shortest total time taken to read source,
expand macros, compile code, load compiled code, and then execute
it. No type declarations were permitted.
Because not all the entrants had found more than one solution, we
levelled the playing field by running timings on code modified to halt
after finding the first solution. However we also ran the fastest two
entries over the complete solution space and this test served to
confirm our earlier results.
Additionally, in the name of fairness, we undid the manual
precomputation in one entry. Finally, we placed the set of pieces in
the same canonical order in all entries. This made several entries run
slower (and one much slower); it also made one entry run much faster.
The test platform was a 566Mhz Celeron with 128MB memory (16k level 1
cache, 128k level 2), running LispWorks 4.2.7 on Windows XP.
We compiled, loaded and ran six shortlisted entries, 100 times
each. The averaged results for one run, with times in milliseconds,
are as follows. Note that for the top three entries, the algorithm is
so efficient that compilation times dominate.
Compile Load Run Total
Russ Ross 366 23 172 561
Nils Goesche 490 95 66 651
Edi Weitz 1296 102 452 1850
Michael Naunton 843 61 1288 2192
Pierpaolo Bernardi 439 35 3605 4079
Gabor Melis 1195 100 4209 5504
We therefore declare that Russ' code ran the fastest and that Nils
came in second. Perhaps these two would like to collaborate to combine
fast compile time with fast runtime.
-------------
The "Last Piece Puzzle" is copyright (c) Blue Opal Australia Pty
Ltd. None of the puzzle designs included in this website may be
reproduced, by any means whatsoever, other than for purposes directly
related to this contest.
This document is copyright (c) Nick Levine 2003. All rights
reserved. It is provided "as is", without any express or implied
warranty. In no event will the author be held liable for any damages
arising from the use of this document. You may make and use verbatim
copies of this document for purposes directly related to this
contest. You may not mirror this document on another website. You may
not charge anyone for the use of this document.
"Windows" is a registered trademark of Microsoft Corporation. Other
brand or product names are the registered trademarks or trademarks of
their respective holders.
$Id: //info.ravenbrook.com/user/ndl/lisp/contest/judges-report.txt#1 $
From: ·············@comcast.net
Subject: Re: ILC2003: Where are the programming contest winners?
Date:
Message-ID: <smlmwqir.fsf@comcast.net>
···@ravenbrook.com (Nick Levine) writes:
>
> We also award Denis an "added value" prize, for taking the trouble to
> learn lisp from scratch in order to enter the competition.
Way to go Denis!
From: ·············@comcast.net
Subject: Re: ILC2003: Where are the programming contest winners?
Date:
Message-ID: <oewawq5y.fsf@comcast.net>
···@ravenbrook.com (Nick Levine) writes:
> However, Conrad also gets an honourable mention in the Obscure Coding
> category, for burying labels statements 6 deep.
I use labels expressions perhaps more than others, but
There are LIMITS, dude!
····@hotmail.com (Oudeis) wrote in message news:<····························@posting.google.com>...
>
> [...]
> (How about the medals?)
Most email relays will barf on actual physical objects, so you'd
better send me your postal address (if you haven't already).
> [...]
> As for "apparently non-terminating":
> These are the results of the run on an AMD system at about 1200Mhz:
The system we ran on was faster than that. I would guess it's an
implementation issue - try getting your hands on a copy of lispworks
(which is what we were using). I had to make a couple of changes to
the "screamer" package, to get it to run at all under lispworks; it's
possible that I did something dumb along the way.
- nick
From: Nils Goesche
Subject: Re: ILC2003: Where are the programming contest winners?
Date:
Message-ID: <871xt62pkr.fsf@darkstar.cartan>
···@ravenbrook.com (Nick Levine) writes:
> Thanks once again to all who took the time to enter the
> competition.
And thanks to you for organizing it. Was great fun!
> Additionally, in the name of fairness, we undid the manual
> precomputation in one entry.
Heh, that was my entry. I thought the lookup tables were fair
because they contained only information that would be immediately
apparent to a /human/ solving the problem. But it is true, they
just made the code uglier and others didn't do any such thing
(and I included the code for generating them just in case you
didn't like them :-)
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID #xD26EF2A0
Cool!
Congratulations to everybody who entered, and especially Scott Fenton,
with whom I shared the "under 21" prize (never thought I'd win
something by being too young :)).
Thanks to Nick Levine for organizing this event (he was even nice
enough to provide the both of us with medals).
> Michael Naunton <···@news.bellatlantic.net> wrote:
> > I wanna see the elegant and generally spiffy solutions!
Sorry to disappoint. :)
···@ravenbrook.com (Nick Levine) writes:
> Finally, we placed the set of pieces in the same canonical order in
> all entries. This made several entries run slower (and one much
> slower)
I take the, umm, credit for that last one (I thought I could get away
with a dumb search to find one solution if I just put the data in good
order).
Vladimir
On Thu, 23 Oct 2003 00:06:34 GMT, Vladimir S wrote:
>
> Cool!
>
> Congratulations to everybody who entered, and especially Scott Fenton,
> with whom I shared the "under 21" prize (never thought I'd win
> something by being too young :)).
>
> Thanks to Nick Levine for organizing this event (he was even nice
> enough to provide the both of us with medals).
>
>> Michael Naunton <···@news.bellatlantic.net> wrote:
>
>> > I wanna see the elegant and generally spiffy solutions!
>
> Sorry to disappoint. :)
No disappointments here. I found all the contest entries to be
fascinating reading.
- MMN