[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