[Neworleans-pm] Fwd: Perl 'Expert' Quiz of the Week #25 (acrostic puzzle generator)

[E. Strade, B.D.]

=====
http://www.brettsbsd.net/~estrabd

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com

----- Original message -----
From: "Mark Jason Dominus" <mjd at plover.com>
To: perl-qotw at plover.com
Date: Wed, 06 Oct 2004 11:22:29 -0400
Subject: Perl 'Expert' Quiz of the Week #25 (acrostic puzzle generator)



IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.
        Thanks.

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.

Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
        Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
        Xie4Lou4 Da2An4 De5 Jian4Yi4.  Xie4Xie4.

UWAGA: Prosimy nie publikowac rozwiazan, dodatkowych  badz pomocniczych
	informacjii przez co najmniej 60 godzin od daty tej wiadomosci.
	Dziekuje.

----------------------------------------------------------------

You will write a program to generate double-acrostic puzzles.

A double-acrostic puzzle is a little like a crossword puzzle, except
that the words don't cross.  The goal of the puzzle is to determine
the contents of a secret quotation.  The solver receives a list of
crossword-style clues.  The solution to each clue is a word or a short
phrase.  Each letter in a clue answer is transferred to corresponding
labeled spaces in a grid.  When all the spaces in the grid are filled
in with the correct letters, the grid will contain the secret
quotation.

At each point in the solution process, the solver can work forwards,
using the clue answers to determine letters in the quotation, or
backwards, completing partial words in the quotation and then
transferring the inferred letters back to the clue answers.  

Here's a very small example:

        __  __  __       __  __  __  __  __  __  __  __       __  __
        1d  2f  3g       4d  5b  6c  7g  8a  9f  10e 11g      12d 13a

        __  __  __  __  __      __  __  __  __  __  __      __  __  __ 
        14f 15a 16e 17c 18b     19b 20a 21e 20f 23a 24e     25g 26c 27d

        __  __  __  __       __  __  __  __      __  __       __  __  __
        28f 29g 30b 31a      32  33b 34L 35e     36f 37e      38a 39d
        40c


        ----------------------------------------------------------------


        a. __ __ __ __ __ __            Unorthodox belief
           15 23 38 8  13 31

        b. __ __ __ __ __ __            Where the sun comes up
           19 18 33 30 5  22

        c. __ __ __ __ __ __ __         A new twist
           40 24 6  26 34 32 17

        d. __ __ __ __ __               Check the records
           39 4  27 12 1

        e. __ __ __ __ __ __            Strive against
           24 35 21 16 10 37

        f. __ __ __ __ __ __            A score and half
           28 2  36  9 14 20

        g. __ __ __ __ __               Followed by a ho?
           29 11 25 7  3


Suppose you guess that the answer to clue c, "A new twist", is
"upgrade".  You would fill in "UPGRADE" into the seven blanks
following clue c, and then transfer the letters to the corresponding
spaces in the quotation grid, "U" into space 40, "P" into space 24,
and so on up to "E" in space 17.

At this point the word at spaces 38-39-40 in the main grid is "__U",
and there are very few three-letter words in English that end in 'U'.
The most common is "YOU", so perhaps you tentatively guess that
38-39-40 is "YOU".  The notation "a" below space 38 means that that
letter is found in the answer to clue a, so you can fill in "Y" in the
third space of "a", and similarly, the first letter of d would be "O".

There's a third source of information in these puzzles: The initial
letters of the clue answers form the name of the author of the
quotation, and sometimes the title of its source.  In this example,
letters 15-19-40-39-24-38-29 spell the last name of the author.

Typical examples are larger than this.  The quotation is usually
between 100 and 200 letters long, and there are typically 20-30 clues.

Write a program, "acrostic2", which generates a double acrostic
puzzle, given a quotation, an author credit, and a dictionary file:

        acrostic2 quotefile dictionary

The quote file will contain the quotation, followed by a blank line,
followed by the author or source credit.  The program should remove
all nonalphabetic characters from the quotation and source credit.
Upper and lowercase letters are considered equivalent.

The dictionary should contain one word per line.  Again upper and
lower case letters are equivalent.

The program should output a list of clue answer values, one per line,
such that:

0. No two clue answers are the same

1. Each clue answer is a dictionary entry,

2. There are exactly as many clue answers as there are alphabetic
   characters in the source credit,

3. Each clue answer begins with the corresponding letter of the source
   credit, and

4. The letters in the output can be rearranged to form the quotation,
   with no letters left over.

The program is not responsible for assigning the letters to the grid
or for formatting the puzzle, because coming up with the answer list
is the hard part.  If you do decide to have your program emit
completed puzzles, please do not make this the default behavior; have
it be enabled by a command-line option.  (Note that there is a
quality-of-implementation issue here: the letters from any one or two
clue answers should be scattered around the grid, and not clustered
together into just a few words.)

[ ADMIN: Dan Sanderson assures me that he is working on writing up
  sample solutions for the RPN calculator quiz from last week.   The
  report will be along when he finished it.  -- MJD ]