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:
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]};
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.
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
In reply to Re: Updates to a guessing number script
by davido
in thread Updates to a guessing number script
by Anonymous Monk
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |