Ravenbrook / ILC 2003

ILC 2003 Programming Contest

Nick Levine, Ravenbrook Limited, 2003-05-28

The closing date for this contest was Saturday 2003-09-27. Many thanks to all those who entered.

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.

1. Introduction

Can you solve the "Last Piece Puzzle"? Can you solve it in lisp?

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:

example configuration of pieces, not actually possible because of the 'exceptions'

The two exceptions to the slot / tab alternation are coloured in the above diagram. They are:

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:

place the triomino in only posible position

Can you place the remaining thirteen pieces? Can you do it in lisp?

2. Contest

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.

  1. The deadline for submissions will be noon EDT on Saturday 2003-09-27 (universal time 3273667200).

  2. 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).

  3. Prizes may be awarded in the following categories:

    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.

  4. Names of prize winners will be announced at the conference, and subsequently on this website.

  5. The prizes will be tasteful medals of low scrap-metal value. As if fame wasn't enough.

  6. 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.

  7. Please include with each entry a list of any sources (e.g. publications, internet sites, etc) used to generate that entry.

  8. Team entries will be allowed. Please indicate with your entry if this is a team effort, and name the particpants.

  9. 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.

  10. 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".

  11. 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.

  12. 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.

  13. 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..

3. Pieces and frame

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.

3.1. The pieces

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.

piece F piece J piece L piece N piece Q piece S piece T piece W piece Z piece j piece l piece s piece t piece 3

3.2. The frame

the frame

4. Material added to this page since it was first posted

Last updated: $Date: 2003/10/21 $.

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.

$Id: //info.ravenbrook.com/user/ndl/lisp/contest/index.html#21 $

Ravenbrook / ILC 2003

Valid XHTML 1.0!