Marco seems to have disappeared, and I have a little time before work
this morning, so I thought I'd write up a report.

It was pointed out that the original quiz specification contained an
error: it said "The program should take the following arguments
... the maximum number of guesses to give the player. "  It should
have said "... the maximum number of *incorect* guesses to allow the
player.".  This is how hangman is usually played.  Otherwise, if the
player is allowed only six guesses, and the word contains seven
letters, it is impossible for the player to win.  I think all the
solutions that appeared on the -discuss list corrected this.

(People also pointed out that, as posed, the program will not reveal
the mystery word to a losing player at the end of the game; this is
frustrating and unsportsmanlike.  Most (all?) of the solutions posted
on the -discuss list repaired this defect.)

At least ten hangman games were sent to the -discuss list, from the
following programmers:

        Roger Burton West
        Mark Jason Dominus
        Christian Duehl
        Shlomi Fish
        Tor Fuglerud
        James Edward Gray II
        David Jones
        Fred P.
        Kevin Pfeiffer
        Mike South

Each of these programs seemed at least a little bit odd to me, in
different ways.  I decided to use Pr. Jones's program as this week's
sample solution, partly because it was quite short, and mostly because
it was quite straightforward.  (Pr. Gray's was about the same length,
and was beautifully straightforward, except for one line in the middle
that gave me the willies.  But it's worth looking at.)
        use strict;
        use warnings;

        die "Usage: $0 dictionary_name number_of_guesses\n"
           if @ARGV < 2 or $ARGV[1] !~ /^\d+$/;

        my ( $dictionary, $countdown ) = @ARGV;
        my $word = get_word ( $dictionary );
        my $tried = ' ';

        while ( $countdown ) {
           ( my $grid = $word ) =~ s/[^$tried]/_/g;
           print "LIFE!\n" and exit if $grid eq $word;
           print "$grid\n";
           # print "Used so far:", sort split //, $tried;
           # print "\nGuesses left: $countdown\n";
           chomp ( my $guess = lc <STDIN> );
           next if $guess !~ /^[a-z]$/ or $tried =~ /$guess/;
           $tried .= $guess;
           $countdown-- unless $word =~/$guess/;
        }
        print "DEATH!\n";
        # print "($word)\n";

        sub get_word {
           open my $fh, '<', $_[0] or die "Can't open dictionary file: $!";
           my $choice;
           rand $. < 1 and chomp ( $choice = $_ ) while <$fh>;
           return $choice;
        }


1. The 'get_word' function is worth study if you haven't seen
   something like it before.  It chooses each word from the dictionary
   with equal probability, without knowing in advance how big the
   dictionary is and without ever having more than two words in memory
   at once.  

   Note that something like this will not work properly:

        sub get_word {
           open my $fh, '<', $_[0] or die "Can't open dictionary file: $!";
           my $choice;
           while (<$fh>) {
             chomp;
             $choice = $_ if rand() < 0.5;
           }
           return $choice;
        }

   This has a serious problem: it very strongly favors the words at
   the end of the dictionary file. More than 90% of the time, it emits
   one of the last four words from the file.  

   It's easy to select each word with equal probability if you are
   allowed to read the entire dictionary into memory first:

        chomp(@words = <$fh>);
        return $words[int rand @words];

   but the quiz said "The size of the dictionary may be very large,",
   which most people took to mean that it might not be feasible to
   read the entire dictionary into memory at once.  

   It's also easy to select each word with equal probability if you
   are allowed to make two passes over the dictionary:

        my $n = 0;
        $n++ while <$fh>;
        my $i = int(rand $n);
        seek $fh, 0, 0;
        <$fh> while $i--;
        return scalar(<$fh>);

   but Pr. Jones's code only reads the dictionary once.

   If you have not seen this technique before, you might like to try
   to come up with it yourself before looking at the solution.  It's
   one of those things that can seem impossible at first until someone
   tells you that it is possible, and then it is not so hard to find
   the answer.

   The technique is explained on page 281 of "Perl Cookbook", if you
   are stumped; I am pretty sure it also appears in Volume II of "The
   Art of Computer Programming".

2. The example program tracks a string, '$tried', which contains all
   the letters that the player has guessed so far; it is initialized
   to contain a space, to avoid an abberant edge case.  The program's
   main loop generates '$grid', which is the display shown to the
   player, by copying it from '$word', the mystery word, and then
   replacing all the letters that are not in '$tried' with
   underscores.  When the player makes a guess, the guess is appended
   to $tried, and the number of guesses remaining is decremented if
   the guess is not present in the secret word.

3. Pr. Burton West's program has an interesting innovation that I
   don't remember having seen before. %mask initially maps every
   letter of the alphabet to '_', and $mask{$letter} is set to $letter
   if the player guesses $letter.  

   @letters is the letters of the mystery word, one letter per
   element.  The program generates the displayed partially-guessed
   word with

        join('',@mask{@letters});

   The hash slice is what interested me here.  The mapping expressed
   by @mask is actually a function of the letter itself, not of the
   letter's position in the word; otherwise this wouldn't work.

4. Pr. Pfeiffer's program is in a rather different, more verbose style
   than the ones I mentioned above, but it is transparently clear.

5. The real fun in hangman, at least for me, is actually drawing in
   the little guy on the scaffold.  I wanted to supply a version of
   the program that would do this, but I did something else instead.
   Fortunately for me, Mike South came to the rescue with a
   "Hangman::Victim" package and a subclass with an alternative
   graphic, inappropriately named "Hangwoman::Victim".  (Inappropriate
   only because "hangman" refers to the person performing the
   execution, not to the victim.  Plover Systems Co. is an
   equal-opportunity employer of both executioners and condemned
   persons.)

6. Pr. Duehl's and Pr. Fugelrud's programs appeared to have been
   designed to be difficult to read, so I didn't bother to read them.

7. A few people decided that the hangman program itself was not
   interesting enough, and instead wrote programs that would play the
   other side, supplying guesses and trying to guess someone else's
   secret word.  I mentioned that I had done something similar many a
   while back, but found that the problem of adopting an optimal
   strategy is much more complex than it appears at first.  There is
   an interesting tradeoff that may occur between making a guess that
   is likely to yield the most information and a guess that is likely
   to be correct.

   Pr. Isaacson did not post his code, but did post some tantalizing
   results:

        http://perl.plover.com/~alias/list.cgi?1:mss:1653

   Both of the posted hangman players use the strategy of eliminating
   all the impossible words from the dictionary on each turn, and then
   guessing the letter that appears most often in the remaining
   words.  It occurs to me that a slightly better strategy might be to
   guess the letter that appears in the greatest number of remaining
   words, instead.  (That is, if the pattern is "ki__", and the
   remaining legal words are

         kill kell kind kine king kiss kite kiva kivu

   then you should prefer 'n' to 'l', even though there are four 'l's
   and only three 'n's.

8. To assist these people, Randy Sims posted a program to analyze
   patterns in a dictionary and generate a database:

        http://perl.plover.com/~alias/list.cgi?1:mss:1682

9. My own contribution was a little different.  It is within the spec
   that was posted, but may be rather more difficult to beat than some
   of the other programs that were supplied.  That is because it
   cheats.   (Undetectably, of course.  It's easy to cheat by making
   your secret word "kwyjibo" or "pyrzqxgl" or some such. but such
   cheating is beneath even me.)

   Determining a good cheating strategy turns out to be quite
   difficult, for the same reasons that a good hangman-playing
   strategy is difficult.  There is an interesting tradeoff between
   letting the hangman player guess right, and keeping the pool of
   possible words as large as possible.  I don't think I found a good
   quilibrium for this tradeoff, and I'd welcome discussion about this.

Thanks to everyone who posted to the discussion list, and particularly
to the folks who wrote programs and *didn't* post to the discussion
list.   

A new quiz will be along tomorrow, and I am particularly excited about it.