[Kc] Perl 'Expert' Quiz of the Week #25 (acrostic puzzle generator)

[Garrett Goebel]

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 plat, attendez au minimum 60 heures aprs la
        date de ce message avant de poster solutions, indices ou autres
        rvlations. 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 ]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/archives/kc/attachments/20041006/85778ea7/attachment.htm