[Kc] Perl 'Expert' Quiz-of-the-Week #17
Garrett Goebel
garrett at scriptpro.com
Thu Jun 3 08:22:59 CDT 2004
-----Original Message-----
From: Mark Jason Dominus [mailto:mjd at plover.com]
Sent: Wednesday, June 02, 2004 6:21 PM
To: perl-qotw at plover.com
Subject: Perl 'Expert' Quiz-of-the-Week #17 [x-adr]
IMPORTANT: Please do not post solutions, hints, or other spoilers
until at least 60 hours after the date of this message.
Thanks.
IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra
cosa que pueda echar a perder la resolución del problema hasta
que hayan pasado por lo menos 60 horas desde el envío de este
mensaje. Gracias.
IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la
date de ce message avant de poster solutions, indices ou autres
révélations. Merci.
WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für
diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser
Mail. Danke.
BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de
eerste 60 uur na het verzendingstijdstip van dit
bericht. Waarvoor dank.
VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i
voobshe lyubye podskazki v techenie po krajnej mere 60 chasov
ot daty etogo soobshenija. Spasibo.
Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4.
----------------------------------------------------------------
[ ADMINISTRATIVE NOTE: In my report yesterday, I included the wrong
URL for the example programs. The correct URL is
http://perl.plover.com/qotw/misc/r017/
- MJD. ]
----------------------------------------------------------------
[ This isn't the quiz that I planned to send today; there are still
some kinks we have to work out of that one. Once again I would
like to encourage people to contribute quizzes or to volunteer to do
sample solution reports afterwards. Send me mail if you are
interested. Thanks, -MJD. ]
Last year my mother-in-law gave me a delightful little puzzle, called "The
Sphinx". It's seven variously shaped wooden tiles, which you try to arrange
into various configurations.
I did a lot of this kind of puzzle when I was younger; in particular I spent
many many hours playing around with pentominoes, which are a set of 12
different-shaped tiles each made by sticking five squares together. Writing
a program to solve pentomino puzzles is not hard, because the configuration
you're typically trying to achieve has all the pieces aligned with the
points of a square grid. The "Sphinx"
puzzle was a nice change for me, because the tiles aren't square at all.
I've illustrated the seven tiles at
http://perl.plover.com/qotw/misc/e017/sph.jpg
http://perl.plover.com/qotw/misc/e017/sph.ps
Exact descriptions follow:
Tile Description Angles Sides Area
A Equilateral 60 60 60 1 1 1 1
triangle
B Isosceles 30 30 120 1 1 S 1
triangle
C Right triangle 30 60 90 1 S 2 2
D Right triangle 30 60 90 1 S 2 2
E Quadrilateral 60 150 30 120 1 S 2 1 3
F Trapezoid 120 60 60 120 1 1 2 1 3
G Rectangle 90 90 90 90 S 1 S 1 4
An "S" in the "Sides" column represents a side with length
sqrt(3). The areas in the "Area" column are measured in multiples
of tile A, which actually has an area of sqrt(3)/4 square units.
Piece "E" is rather irregular. It is formed by taking a copy of tile
C and gluing a copy of tile A to its short side.
Tiles C and D are identical.
It is permissible to flip the tiles over. And, of course, to rotate them or
slide them around on the table. But it is not permitted to overlap them.
Your job is to write a program which can solve Sphinx puzzles. The program
will be given an input file which describes the configuration that into
which the tiles are to be placed. See
http://perl.plover.com/qotw/misc/e017/conf.jpg
http://perl.plover.com/qotw/misc/e017/conf.ps
for an example. The program should figure out a way to place the tiles into
the specified configuration, if there is one, and report the arrangement
unambiguously on the output; if no arrangement is possible, it should say
so.
It's up to you to determine the format of the input and the output.
The puzzle, by the way, was designed by Nob Yoshigahara, a famous designer
of puzzles. The Sphinx puzzle is a little out of his usual line. He
specializes in puzzles in which you have to fit a bunch of objects into a
container. For example, see
http://www.johnrausch.com/PuzzleWorld/puz/pack_the_asparagus.htm
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/pipermail/kc/attachments/20040603/f878ecad/attachment.htm
More information about the kc
mailing list