Almost twenty years ago I was introduced to the game of Jotto by the man who
would later become my father-in-law.
Naturally I recognized the similarity to MasterMind(TM) which I had played a
few times as a kid. At the time I was also teaching myself how to program.
Naturally I decided to write a version of Jotto as an educational exercise.
Back then I had an old XT computer (originally running MS-DOS 3.3 or
so --- this was before MS Windows existed. I had a copy of Borland
TurboPascal.
The first think I needed was a list of five letter words. My favorite
word processor and text editor back then was a bit of shareware called
PC-Write (yes, I registered it). It had a built-in spell check program.
No problem!
I wrote a little program to generate every letter sequence from aaaaa
through zzzzz (it's basically counting in base-26). Saved that out to a
file, then loaded that up into PC-Write and wrote a quick macro to
delete every line that was a mis-spelled word.
Presto! A few thousand five letter words.
Then I wrote a very simple version of my program. Rather than fuss
with a bunch of file handling I just used another editor macro and
turned my word list into a static array declaration which I could
use as an include file. So the whole list was built into my .EXE
(executable) file.
Then I wrote a program around that. It would pick a word, display
a grid showing the answers and clues (with some ASCII art work around
it). It would then give you clues and let you know when you won.
Then I decided it was only fair for me to figure out how to make it
guess against the word chosen by the human. I was curious if I could
make it *always* win (in less than 10 guesses) for any word that it
knew ... and if I could even take reasonable guesses even for words
that weren't in it's list. (I was also curious how fast my guessing algorithm
would perform --- this was only about a 6MHz 16-bit CPU with 640K
(kilobytes, not megabyte ... and megaHertz rather than gigaHertz ---
oh how far we've come!)
SPOILER WARNING!!!(Don't scroll down if you don't want to know how to win *every* time).
I mulled over this for hours trying to figure out a simple way to tell
when a word from my list is consistent with *all* of the clues today.
Try it! Try to imagine something like a mathematical function that
will tell you whether a word ... say the word "guess" might be the
one that could have resulted in the a clue of 0, 1 against hidden
word (say "wrong").
... (Scroll down when you think you've got it) ...
;D
Ready for the answer?
It's a commutative function! If "wrong" scores 0,1 against some unknown
word than any word that does NOT score exactly 0,1 against "wrong" cannot
be the unknown word. So the programming is almost trivial (after you've
alread written the function which scores a guess against the known hidden
word, you can reuse the same function to eliminate every possible word
from our known word list. (Those were, in fact, the names of the functions,
"score()" and "eliminate()"). All I had to do was add a Boolean "possible"
flag to each of the words on my list.
As for performance ... I discovered that my function could score every
known work in less than a blink of the eye --- even on that old system.
(And the little program that generates aaaaa through zzzzz gets turned
into an include function and reused to try finding unknown words if the
human picks one that is not known. But that was a bit slower).
(And to satisfy my curiosity --- my program could consistently isolate a
single known word within 4 or 5 guesses. Any score eliminates over 90%
of the remaining words at each guess. That's actually intuitive if you think
about it thus: there are roughly 14 possible results to any guess (0 through
4 are the right letter in the right place, and 0 through 4 might be elsewhere
but the sum of "right" and "elsewhere" has to be 4 or less except in the
special case where the guess in an anagram of the secret word). It can
exhaust every possible letter sequence in only about 20 to 30 guesses,
and every possible word (any 4 letters with at least one vowel --- 4 ** 26 * 5)
in about a dozen guesses).
So, if you can do that in your head ... you can always win at Jotto
JimD
P.S. ... I never did publish that program ... I thought of putting it out as
shareware but felt that it lacked any sort of professional polish
and also I was worried that someone would pop up and sue me for trademark
infringement or some stupidity like that.