Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) 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'); 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


In reply to Re: Reverse download protocols by bliako
in thread Reverse download protocols [solved] by tomasz

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • 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.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2022-12-06 20:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?