For "latest" (but before the closing date) news on the competition, and an FAQ of sorts, see section 4 below.
For results of the competition, see the judges' report. The entries themselves are also available: please start with the readme file which accompanies them.
The "Last Piece Puzzle" consists of fourteen pieces which have to be fitted into a frame. There are pictures on each piece but these give no help with the solution (each picture is fully contained within a single piece, and the pictures are rotated so that their orientation can't be used as a clue). The pieces interlock with each other and with the frame; if we ignore the slots and tabs then the frame is an 8x8 square and the pieces are polyominos: nine pentominos, four tetrominos, one triomino. For the most part, slots and tabs alternate around both the frame and all the pieces, and all the slots and tabs are the same size and shape. There are two exceptions to this alternation of slots and tabs, and we'll come to these in a moment. If there were no exceptions then we would be able to fit the pieces in like this:
The two exceptions to the slot / tab alternation are coloured in the above diagram. They are:
the frame has a slot where you'd expect a tab (this leaves a gap between the frame and one of the pieces in this example, coloured green here);
the triomino has a tab where you'd expect a slot (this makes two pieces overlap a little in the example, coloured red).
As a result of the exceptions it turns out that we are constrained to place the triomino so that its unexpected tab fits into the frame's unexpected slot, thus:
Can you place the remaining thirteen pieces? Can you do it in lisp?
The aim in this contest is for you to write a program, in Common Lisp, to solve the above puzzle, giving positions and orientations for each piece.
By entering the contest, you are deemed to have accepted all of the following, so please read them carefully.
The deadline for submissions will be noon EDT on Saturday 2003-09-27 (universal time 3273667200).
Entries may be submitted only by email, which should be sent to ILC03-lisp-contest (at) alu (dot) org. The string "ILC03-lisp-contest" should appear in the subject line. If such email would be over 1 megabyte in length, please send instead a short message to this address stating how your entry can be acquired by some other electronic means (http / ftp, etc).
Prizes may be awarded in the following categories:
first working answer to be submitted;
fastest running program -- this is a test of algorithm, not of use of optimizations, therefore (a) no type declarations or the forms will be permitted and (b) the judges reserve the right to run entries on the lisp implementation(s) of their choice;
most elegant algorithm;
most elegant use of lisp;
best use of really obscure lisp features;
contestants under the age of 21 on the first day of the conference;
best "added value".
The judges reserve the rights (a) not to award a prize in any category if they do not believe the standard of entries in that category merits it, (b) to create additional prize categories after the closing date for submissions and (c) to entertain any suggestions, which are received before the deadline for submissions, for other categories.
Names of prize winners will be announced at the conference, and subsequently on this website.
The prizes will be tasteful medals of low scrap-metal value. As if fame wasn't enough.
Entries are to consist of source code, plus sufficient documentation (potentially in the form of comments) to allow the judges to (a) build and run the program and (b) understand the algorithm employed to solve the puzzle.
Please include with each entry a list of any sources (e.g. publications, internet sites, etc) used to generate that entry.
Team entries will be allowed. Please indicate with your entry if this is a team effort, and name the particpants.
All entries will be tested on the same machine: a laptop running Windows XP. If you intend to submit an entry which cannot be run on this machine then you are advised to consult with the judges beforehand. You may be responsible for bringing hardware to the conference on which to demonstrate your entry, and - depending on the speed of that hardware - your entry may not be eligible to win a prize under the "fastest running program" category.
If you intend to submit an entry which is not written portably then you are advised to consult with the judges beforehand. The judges will make reasonable efforts to obtain particular lisp implementations on which to test entries, provided there is sufficient justification for doing so. Use of an implementation-specific UI will be considered to be a "sufficient justification".
Employees of Blue Opal Australia Pty Ltd and of Ravenbrook Limited, the judges, and the immediate families of all of these, are not eligible to enter this contest.
The judges will be Nick Levine and Nicholas Barnes. The judges can be contacted by email via ILC03-lisp-contest (at) alu (dot) org. Include the string "ILC03-lisp-contest" in the subject line. The judges' decision will be final in all matters, including whether or not to enter into any correspondance.
Although each entry will remain the intellectual property of the entrant, the judges may demonstrate and publish winning entries at the conference, and may publish them in conference proceedings and on this website. Entries must be licensed in such a manner as to permit these activities freely..
Sketches of the fourteen pieces and the frame into which they must be fitted are reproduced below. Please note that these are only approximate representations. All pieces are made up of between three and five squares "stuck together"; all these squares are the same size; all tabs and slots are the same size and in the centre of an edge of one of the squares which comprise that piece. Once the triomino has been placed you can think of the frame as a chessboard (i.e. alternate black and white squares); of each piece as a small collection of alternate black and white squares; and of your task as being to place the 13 remaining pieces such that black squares on the pieces are always and only placed onto black squares on the board.
For the purposes of identification, we have given each piece a name which you may or may not care to use. These names are all single characters: upper case alphabetic for the pentominos, lower case for the tetrominos, digit for the triomino.
Last updated: $Date: 2014/04/27 $.
The rules omit to mention that entrants in the "under 21" category will have to tell the judges that they're under 21, otherwise we won't know.
We've been asked whether the pieces can be turned over. The answer is no: the pieces can be rotated only about an axis vertical to the paper / your screen.
We've been asked whether a solution actually exists. The back of the puzzle, which counts as being in the "public domain", says: We guarantee it can be done...
We've been asked whether it's allowed to submit more than one entry. The answer is that you may submit more than one entry, but only your last submission (before the closing date) will be judged.
We've been asked whether any entries have been received to date. The answer is that entries (plusp length) have been received but they have not been examined by the judges, therefore we cannot yet say whether anybody has yet qualified for any of the prizes.
We've been asked to clarify the meaning of "fastest running program". This is to be defined as the total time, as measured by time, taken to read source, expand macros, compile code, load compiled code, and execute it. Plus anything else we forgot to mention here. The judges will take steps to integrate each entry into the implementation used for the timings, in such a way as to ensure a level playing field for each entry.
There was an error in the figure, near the head of section 1, which illustrates an example configuration of the pieces. This configuration is not actually possible because of the two 'exceptions' to the slot / tab alternation rule. The original version of this figure (corrected on 2003-08-14) showed one piece (the triomino) in the wrong place, and as a result replaced the "Q" pentomino with another piece which is not part of the puzzle. This error, while confusing, does not materially affect the contest because the illustration was explicitly labelled as an invalid arrangment of pieces. (Nevertheless we apologise for any anxiety caused by it.) To correct the error, we made the following change, where "?" is used to denote the interloping piece:
JJJJLLLL JJJJLLLL
NNsJL??? NNsJL3QQ
TNss??3j TNss33Qj
TNNst33j -> TNNstQQj
TTWtttjj TTWtttjj
TWWZZZll TWWZZZll
WWSSFZZl WWSSFZZl
SSSFFFFl SSSFFFFl
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 or any of the images herein 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.
