Re: [FWP] Jotto jot-matcher

["Bernie Cosell" <bernie@rev.net>]

On 7 Aug 99, at 9:17, Matthew Wickline wrote:

> bernie@fantasyfarm.com wrote:
> > boolean subroutine to determine whether a word matches 
> > a probe/jots result; _fast_ is more important than small.
> 
> 
> So.... if I understand correctly, you're looking for a sub
> which
> 1) takes in a $guess, a $probe, and $jotts for that $probe
> 2) returns a boolean value: true if $guess is a possible
> match with target in light of $probe and $jots (with no
> information about the actual target word), false if not.

That's exactly correct...

> What I'd do:
> Assume that $guess *is* the target word. Then, you can
> derive how many jotts $probe *should* have received. Return
> true if and only if the number of jotts derived is the same
> as the actual number of $jotts for $probe.

In fact, that's what I've done so far.  I only provided the additional info 
[about needing the boolean] in case there was some really sexy algorithm that 
might be able to figure out the true/false without actually counting jots 
[e.g., it could special case '0' and return false as soon as it found a single 
match, instead of plowing through the rest of the letter-matches].

> So now the problem is reduced to finding the number of jotts
> a probe should get for a given target word. I don't know
> that this is the fastest way to do it, but this seems good
> to me:
> 
> sub get_jotts {
>     my($probe, $target) = @_;
>     my %letters;
>     for ( split('',$target) )
>         { $letters{$_}++ };
>     my $jotts = 0;
>     for ( split('',$probe)  )
>         {$jotts++ if $letters{$_}-- > 0};
>     $jotts;
> }

I wasn't sure about how efficient having a hash in the inner loop would be.  
One thing I see is instead of a hash, you could just use an array and directly-
index it with the charactercode.  Just for the record, here's what I'm using 
now:

sub count_jots
{
    my ($wd1, $wd2) = @_ ;
    my @lets = split(//, $wd1) ;
    my $jots = 0 ;
    foreach my $let (split(//,$wd2))
    {
        foreach (@lets)
        {
            next if $_ ne $let ;
            $jots += 1;
            $_ = "" ;
            last ;
        }
    }
    return $jots ;
}

I see that your loop uses just 2*N steps, while mine is order N^2, so yours is 
clealy going to be better... I shied away from something like that because I 
have this probably-irrational fear of using hashes instead of arrays [probably 
dates back to my days as an assembly-lang programmer], but even that could be 
quelled by doing the 'ord($_) - ord('a')' hack to convert a letter to a numeric 
index.

> > 'jotto player' that uses that -very- nasty algorithm
> 
> 
> I'd be interested in seeing that :)
> If it's of any use, help yourself to jotto-related code at
>     http://wickline.org/saog/index.cgi/spew_source

Thanks!  Your code includes a bunch of nice things that I never bothered with 
in my old program...  I suspect I'll steal a bit of it..:o).  [BTW: for the 
record, my old jotto player, the unbeatable one, was written in BASIC with a 
hand-coded-inassembler subroutine to do the list pruning [the 'jot matches' guy 
I mentioned here].  Waht I did was assembled the little program, got a hex dump 
of the subroutine, and then defined a binary string in the BASIC program with 
the subroutine's "hex" as its value.  Then there was some hack, which I don't 
remember now, by which you could convinced Basic to "call a string" or 
soemthing like that..

Another possibility for this jotting part would be to code up the jot-part in C 
and then use XS [is that the right thing? it is a part of Perl I've never had 
occasion to mess with] to incorporate it into the Perl prog...

> 
> I tried playing someone using that very nasty algorithm
> (human/human play... no FWP). The first time, I got the
> target in only five guesses! I figured that this was *the*
> strategy and I should use it in every jotto game henceforth.

If we're talking about the same strategy, yes: the one I used, all those years 
ago [sigh] was simple but very un-jotto-like [because it involved no deduction, 
no sets of five-words-using-25-letters or anyhting like that]: at each step, 
pick a word that is consistent with all of the previous clues.  It sounds so 
simple, but it is VERY effective.  It is also not fun [as you'll see if/when I 
get my jotto/CGI hack up: with a human opponent, you can see your opponent 
"closing in" even as you do the same.  With the evil-strategy you see no such 
thing: you see the computer guessing apparently-random words and then before 
you know it it has guessed yours.

> Unfortunately, it turns out that I had just been incredibly
> lucky. Every time after that, whenever I tried to use the
> strategy, my lack of brute force access to a giant
> dictionary really got in the way: I couldn't keep comming up
> with good guesses in any reasonable amount of time. That
> sort of processing just isn't the strongest suit for human
> grey matter :)

What's interesting is that for the computer using this strategy, the compute 
time is just *backwards* from the way it is with people [making it yet MORE 
annoying to play against! :o)]  With human players, typically the first few 
guesses are pretty quick and the human-player begins to slow down as the 
deductive info begins to mount and it is harder to figure out where to go next 
or what conclusion about a letter to decided on next.  With the computer 
strategy, the SECOND guess is the killer: first guess is easy [just ask any 
word in the wordlist at random], but with the second guess, you have to go over 
the *ENTIRE* word list [5000+ 5-letter words in /usr/dict/words on my Linux box 
here] to prune out the dead words, but with each subsequent guess the list of 
still-possible words gets smaller and smaller, and so the program goes faster 
and faster...

  /Bernie\
-- 
Bernie Cosell                   Roanoke Electronic Village
mailto:bernie@rev.net           Roanoke, VA


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