Perl-Sensitive Sunglasses PerlMonks

by bliako (Monsignor)
 on Aug 30, 2021 at 18:27 UTC Need Help??

There's the 20-questions game of: client trying to guess a server-chosen integer. The server responds with one of higher, lower or yes to any guess from the client. The best strategy for such a game is to always guess halfway between the current possible range. This is because you are essentially doing a binary search and want to eliminate the biggest possible range with your every question, slowly zooming-in to the correct answer.

The output of a hashing algorithm can be labelled as a unique non-negative integer (or be converted to one). SHA1 has 160 bits of output. Giving the possible guesses to be in the range 0 to 2^160 = 0 to 1461501637330902918203684832716283019655932542976. The best guess would be 2^160/2. If the server answers with try lower, then your next guess should be 2^160/4.

Bonus points for how many guesses guessing a SHA1 hash needs, given that the server is ever so helpful in giving us 2 bits of information each time. But from what I gather from this post's little 20-questions game, the server does give hints (e.g. Then the server answers yes/no, or gives some hint.)

Here is something to play with, if indeed your problem falls in this category (it certainly did keep me entertained for a while):

```# by bliako on 30/08/2021
# for https://perlmonks.org/?node_id=11136212

use bigint qw/hex/;
use Digest::SHA1 qw/sha1 sha1_hex/;

my \$digest_hex = sha1_hex('blah blah blah');
print "\$0 : starting with this number: \$answer.\n";

my \$min = 0;
my \$max = 2**160;

my \$num_guesses = 0;
my (\$guess, \$diff);
while( ++\$num_guesses ){
\$guess = \$min + (\$max - \$min) / 2.0;
print "entering at guess number \$num_guesses, current range:\n  mi
+ff\n";

print "your guess (\$guess) needs to go higher ...\n";
\$min = int(\$guess);
} elsif( \$guess > \$answer ){
print "your guess (\$guess) needs to go lower ...\n";
\$max = int(\$guess);
} else {
print "bingo in \$num_guesses guesses! the answer was: \$digest_
+hex and your guess was ".bigint_to_hex(\$guess)." (\$guess).\n";
last;
}
}

sub bigint_to_hex {
# https://stackoverflow.com/questions/828462/how-can-i-sprintf
+-a-big-number-in-perl
# because sprintf("%x", bigint) does not work sadly...
my \$inp = shift;
my \$out = "";
while(\$inp){
my \$chunk=\$inp & 0xf;
\$inp >>= 4;
\$out = sprintf("%x",\$chunk).\$out;
}
return \$out;
}
```entering at guess number XXX, current range:
min: 216530321997656745029789011476757518019484653536
max: 216530321997656745029789011476757518019484653568
guess: 216530321997656745029789011476757518019484653552
diff: 0
bingo in XXX guesses! the answer was: 25ed8e31b995bb927966616df2a42b97
+9a2717f0 and your guess was 25ed8e31b995bb927966616df2a42b979a2717f0
+(216530321997656745029789011476757518019484653552).

bw, bliako

Replies are listed 'Best First'.
by tomasz (Acolyte) on Aug 30, 2021 at 19:07 UTC
Thanks a lot for your positive reply. I will give you feedback later on. I need to analyse your thoughts. It may take a while... It's not exactly what I asked about, but closely related. Thanks again!
A reply falls below the community's threshold of quality. You may see it by logging in.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11136238]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2022-11-26 23:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite new Perl feature (in 2022) ...

Results (40 votes). Check out past polls.

Notices?