[FWP] Jotto puzzle: first five guesses

[Matthew Wickline <listbox@wickline.org>]

Date: Thu, 22 Jul 1999 11:17:13 -0500
Message-id: <01JDV30DEXZ690NS8D@kids.wustl.edu>
X-Mailer: Mailsmith 1.1.3 (Bluto)
X-WARNING: Any unsolicited commercial email sent to wickline.org will be
 charged a processing fee of $500 as per government legislation Section
 227(b)(3)(C).
X-Face:
 (%|6"jJk#UjS^E:{o\\TT5y.>iR|HO\FG>cj;?E&V2j'qvzWTslsiu4f_5k?y
8t7t]]%{15Pw=CD]aqvj-PMeW{[mRI=]]hES3tONV^1Ch}&cjV6{FpTXn#+[,#!(DNz_
 -W$nqyQZ(HpuLTCDJ
X-Munition-Export: print pack"C*",split/\D+/,`echo
 "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*
lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
X-Munitions-Info: http://dcs.ex.ac.uk/~aba/rsa/
X-ModemHUP: +++ATH
X-ModemFIX: +++ATS2=27

a month or so ago, someone showed me how to play jotto. It's
sort of a word-game version of Mastermind (for those of you
familiar with Mastermind).

One person chooses a five letter word to be the "target"
word, and does not reveal the target to the other person
(the "guesser"). The guesser guesses a five letter word. The
first person tells them how many letters in their guess are
found in the target. If the guess has multiples of the same
letter, only so many multiples as are also present in the
target count as "hits". Unlike Mastermind, no information is
given regarding the [un]correctness of the location of any
of the letters.

It's fun to play as above, but the more competive folks out
there might enjoy playing "head-to-head" where each player
chooses a target, and players alternate guessing at each
other's target, trying to win in fewer guesses than their
opponent.

It's a real pain to play without paper and pen handy.


What's that got to do with perl?

Well, in thinking about the game, there are all sorts of
neat things you can do to explore it with perl.

As a first example, I wanted to share the game with someone
in another state, and it wasn't very fun over phone or
e-mail, so I put up a cgi version so he could see how fun it
is.

If you're interested, (it ain't pretty, or well-documented)
    http://wickline.org/saog/
This is only the one-way version. One day when I've ammased
a whole pile of juicy tuits, I'll go for a head-to-head
version. Initially, it had a too-small dictionary of five
letter words (about 3,000). The few folks playing complained
that too many of their guesses were not found in the
dictionary. So, (more fun with perl) I ramped it up to over
10,000. Now, folks complain that too many of the target
words are things they've never heard of. I've gotton some
stats on how common each of the words are according to
altavista (more fun with perl) and will one day be
incorporating a user-config to allow folks to say that words
which are of such-and-such rarity should not be allowable as
the target word.

If you play a bit of jotto, you may see that one decent
initial strategy is to guess a series of words which don't
share any words in common. This brings us to the subject of
this message. Given a dictionary of about 10,000 five letter
words, how can one efficiently determine all sets (if any
exist) of five words which use up twenty five unique letters
of the alphabet.

Let's assume that you've first pre-processed that dictionary
to reduce any anagrams and to remove any words which contain
more than one vowel (a, e, i, o, or u... not counting y as a
vowel here) to get shorter file of just under 1600
non-anagramatic words which don't use up multiple vowels. We
can't remove words which use up a 'u' without a 'q' because
there was one word with a 'q' but no 'u' in the dictionary.

How can you efficiently find all sets of five words from
that list which use up 25 unique letters of the alphabet.

What's the fastest code with unlimited RAM?

What's the fastest code with minimal RAM use (probably lots
of disk use)?

Any takers?

My approach was very brute force and ran in the background
for quite a while (many hours). First build a list of all
pairs of words which don't duplicate any letters. Call this
the "pairs list", with each entry being one such pair. Now,
find all pairs of pairs which don't duplicate letters. Call
this the "quads list". Finally, find all combinations of a
quad with an entry from the inial list of 1600 words which
don't duplicate any letters.

-matt

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe