Roger Burton West wrote:
>
> On Wed, May 26, 2004 at 02:58:40PM -0400, Ron Isaacson wrote:
>
> >3. Filter the list of possibilities to those which could be the
> > target, based on the letters you already know (i.e. if your guess
> > is currently "he__o", remove all possibilities that don't match
> > /^he..o$/)
>
> Y'know, you can be a lot more aggressive than that in pruning the list
> of possible words.
>
> Say you've guessed h, e, o and also t, a, n incorrectly. Your target
> word matches not just /^he..o$/ but /^he[^heotan][^heotan]o$/ .
Of course... the results are interesting though. My version, without
your optimization:
Guessed 19983 words in 879.14s.
The average word took 7.69 guesses.
The easiest word took 1 (electroencephalography).
The hardest word took 23 (jinx).
The average word had 2.85 incorrect guesses.
The easiest word had 0 (yesteryear).
The hardest word had 19 (jinx).
and with your optimization:
Guessed 19983 words in 818.77s.
The average word took 6.70 guesses.
The easiest word took 1 (electroencephalography).
The hardest word took 24 (jazz).
The average word had 2.47 incorrect guesses.
The easiest word had 0 (yesteryear).
The hardest word had 21 (jazz).
It's faster, and the averages are all lower, but the worst case is
worse. Take "jazz", in my original version:
The word is: jazz
Start: ....
Guess 'e': .... (1 bad)
Guess 'a': .a.. (1 bad)
Guess 'l': .a.. (2 bad)
Guess 't': .a.. (3 bad)
Guess 'r': .a.. (4 bad)
Guess 'n': .a.. (5 bad)
Guess 's': .a.. (6 bad)
Guess 'm': .a.. (7 bad)
Guess 'p': .a.. (8 bad)
Guess 'k': .a.. (9 bad)
Guess 'd': .a.. (10 bad)
Guess 'h': .a.. (11 bad)
Guess 'c': .a.. (12 bad)
Guess 'b': .a.. (13 bad)
Guess 'w': .a.. (14 bad)
Guess 'g': .a.. (15 bad)
Guess 'i': .a.. (16 bad)
Guess 'f': .a.. (17 bad)
Guess 'y': .a.. (18 bad)
Guess 'v': .a.. (19 bad)
Guess 'z': .azz (19 bad)
Must be: jazz
Got it in 22 guesses, with 19 bad
but with your optimization:
The word is: jazz
Start: ....
Guess 'e': .... (1 bad)
Guess 'a': .a.. (1 bad)
Guess 'l': .a.. (2 bad)
Guess 't': .a.. (3 bad)
Guess 'r': .a.. (4 bad)
Guess 'n': .a.. (5 bad)
Guess 's': .a.. (6 bad)
Guess 'h': .a.. (7 bad)
Guess 'i': .a.. (8 bad)
Guess 'k': .a.. (9 bad)
Guess 'd': .a.. (10 bad)
Guess 'm': .a.. (11 bad)
Guess 'p': .a.. (12 bad)
Guess 'w': .a.. (13 bad)
Guess 'b': .a.. (14 bad)
Guess 'c': .a.. (15 bad)
Guess 'g': .a.. (16 bad)
Guess 'y': .a.. (17 bad)
Guess 'f': .a.. (18 bad)
Guess 'u': .a.. (19 bad)
Guess 'o': .a.. (20 bad)
Guess 'v': .a.. (21 bad)
Guess 'z': .azz (21 bad)
Must be: jazz
Got it in 24 guesses, with 21 bad
Apparently the distribution of letters in the words that match /.a../
leads to "jazz" faster than that in the words matching /XaXX/ where X
is [^ealtrns]. I chalk this up to a freaky edge case though, rather
than a weakness in the algorithm.
It really seems like there should be a fundamentally more interesting
way to do this...
--
Ron Isaacson
Morgan Stanley
ron.isaacson-/PgpppG8B+R7qynMiXIxWgC/G2K4zDHf@xxxxxxxxxxxxxxxx / (718) 754-2345
NOTICE: If received in error, please destroy and notify sender. Sender
does not waive confidentiality or privilege, and use is prohibited.
|
