in reply to Updates to a guessing number script

The fewest guesses possible in the general case (excluding a "lucky guess") is going to be ceil(log2(n)), and that is possible by implementing a binary search.

A stable binary search will require ceil(log2(n))+1, and a simple binary search will require a worst case of ceil(log2(n)) which is 4. That's the lower limit for the worst case.

Here's how a binary search works. Let's extend your game to any number between 1 and 100. You select a secret number, which in this case is 73:

  1. Is it 50? No, higher. (Mid-point between 1 .. 100 )
  2. Is it 75? No, lower. (Mid-point between 51 .. 100 )
  3. Is it 63? No, higher. (Mid-point between 51 .. 74 )
  4. Is it 69? No, higher. (Mid-point between 64 .. 74 )
  5. Is it 72? No, higher. (Mid-point between 70 .. 74 )
  6. Is it 74? No, lower. (Mid-point between 73 .. 74 )
  7. Is it 73? Yes, it is. (Mid-point between 73 .. 73 )

At each step, I take the remaining range, and select the mid-point. So at step one, I'm bisecting the range of 1..100. On step two, I'm bisecting 51..100, and so on until, on step seven, I guess it (and the range happens to also have narrowed to only one possibility anyway).

The Wikipedia article on Binary Search demonstrates the algorithm in code. You could adapt it to work for your needs.

There is no general algorithm for beating log2(n). There will be the occasional lucky guess though. But consider how effective this is. You are guaranteed of finding the correct number between 1..10 in 4 or fewer guesses. Between 1..100 in 7 or fewer guesses. Between 1 and 1,000,000 is guaranteed to be 20 or fewer guesses. Between 1..1,000,000,000 will be 30 or fewer guesses. Between 1 and a trillion, 40 or fewer guesses. If you had to check each number between 1 and a trillion, one by one, your worse case would be a trillion guesses, and average would be 500 billion, but with the binary search's divide and conquer approach, that problem domain a trillion members big is reduced to 40 guesses.

The CPAN module List::BinarySearch implements a stable binary search, which is almost (but not quite) what you need, and it's not really designed to be used for a number guessing game. Nevertheless, it can be coerced to do what you are after:

use List::BinarySearch 'binsearch';
use IO::Prompt::Hooked 'prompt';

print "Please think of a number between 1 and 10...\n";
print "DON'T tell me, just let me guess it!\n\n";

my $tries = 0;

binsearch {

  ++$tries;

  my $response = prompt(
    message => "Is the number $b? (higher, lower, or yes):",
    validate => qr/higher|lower|yes/i,
    error    => sub { "I don't understand $_[0]. Try again.\n" },
  );

  return 1 if $response =~ /higher/i;
  return -1 if $response =~ /lower/i;

  print "Found $b in $tries guesses.\n";
  exit(0);

} undef, @{[1 .. 10]};

[download]

Here's a sample run:

Please think of a number between 1 and 10...
DON'T tell me, just let me guess it!

Is the number 5? (higher, lower, or yes):  higher
Is the number 8? (higher, lower, or yes):  lower
Is the number 7? (higher, lower, or yes):  yes
Found 7 in 3 guesses.

[download]

You won't be able to turn this in to your professor, because certainly he wants you to implement the algorithm yourself. However, with this and a little research you should be able to work out your own solution without too much difficulty. There's also an article about the Binary Search in Mastering Algorithms with Perl (O'Reilly).

(Disclaimer: I'm the author of List::BinarySearch.)


Dave

Replies are listed 'Best First'.
Re^2: Updates to a guessing number script
by quinkan (Monk) on Mar 01, 2014 at 00:55 UTC
    For a start, if you're dealing with humans, forget the idea of starting in any random or binary manner. For numbers between 1 and 10, make 7 your first guess. Weird as it may seem, at least in some cultures, given the 1 to 10 choice, as many as 60% or more will choose 7! In other words, your most efficient algorithm is not a random one. It probably does you no great harm, if you then follow various binary search techniques from that point onward, although this (http://groups.csail.mit.edu/uid/deneme/?p=628) would suggest you have better strategies to continue with past your hard-coded first choice. This is not a "pure maths" solution -- it's about real life, so you'd better prepare your groundwork if your professor wants you to play with abstract theory rather than the Real World. Cite the above as a reference or google for more examples ?
[reply]
Re^2: Updates to a guessing number script
by Laurent_R (Canon) on Mar 02, 2014 at 01:35 UTC

    If you had to check each number between 1 and a trillion, one by one, your worse case would be a trillion guesses, and average would be 500 billion, but with the binary search's divide and conquer approach, that problem domain a trillion members big is reduced to 40 guesses.

    Although I perfectly understand what you really mean (and agree with everything else that you said), the statement above about the average search is technically not true if you play according to the rules of the game, i.e. if you select a number within the range previously determined by the previous tries: the average would be much much smaller than what you said. As an example, let me take the trillion (1e12) case.

    The following program is just selecting a wild guess within the admitted range and adjusting the range in accordance with the results of the previous try. 

    use strict;
use warnings;

my ($low, $high) = qw /0 1e12/;
my $search_number = int rand $high;
my $guess;
my $count = 0;

while (1) {
    $guess = $low + int rand ($high - $low);
    last if $guess == $search_number;
    if ($search_number > $guess) {
        $low = $guess;
    } else {
        $high = $guess;
    }
        printf "%12d", $guess;
        print " - Range is $low - $high \n";
    $count++;
}
print "Searched value is : $guess, found in $count tries \n";

    [download]
    Now running the program a few times:
    Read more... (7 kB)
    In brief, 45, 37 and 50 tries. This is far from being bad. Compared with the optimal 40 guesses, the random approach is actually fairly good.
[reply]
[d/l]
[select]

      Without re-reading my post, I believe I was talking about the Binary Search in general -- that it can reduce a trillion-item problem to 40 "guesses", where guess really should have been written as 40 well-chosen queries.

      But you are correct, and your post is well thought-out. If the person trying to guess the number picks a number at random, then another number at random within the newly discovered valid range, and so on, he would be able to narrow the problem area much faster than doing a linear search.

      And it seems we agree that the optimal solution (excluding approaches involving human frailty or psychology), will still be a binary search. The "random guess" method for dividing and conquering is not totally dissimilar from a binary search; it's just not as well disciplined in perfectly bisecting the remaining problem area. Nevertheless, it still manages to divide and conquer, like Binary Search does.

      Your post is good; it adds real-world practicality to the discussion.


      Dave

[reply]
        And it seems we agree that the optimal solution (excluding approaches involving human frailty or psychology), will still be a binary search.
        Yes, of course, I definitely agree with you that the optimal solution is binary search. And your initial post was very good, I was only picking up on a very minor detail, sorry about it, but I thought it was interesting to make the "educated random guess" experiment.
[reply]

In Section Seekers of Perl Wisdom