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');
my $answer = hex($digest_hex);
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;
$diff = $guess - $answer;
print "entering at guess number $num_guesses, current range:\n mi
+n: $min\n max: $max\n answer: $answer\n guess: $guess\n diff: $di
+ff\n";
if( $guess < $answer ){
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 {
# graduitously ripped off from Ben Aveling's answer in
# 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
answer: 216530321997656745029789011476757518019484653552
guess: 216530321997656745029789011476757518019484653552
diff: 0
bingo in XXX guesses! the answer was: 25ed8e31b995bb927966616df2a42b97
+9a2717f0 and your guess was 25ed8e31b995bb927966616df2a42b979a2717f0
+(216530321997656745029789011476757518019484653552).
EDIT: this is interesting reading
bw, bliako
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.