## Guess a Number 1..500

 ```/*** Guess a Secret Number ************************************* Luke is making a game for his little sister, to keep her busy. The program chooses a number between 1 and 500, and the user must try to guess the number. They are permitted to guess 10 times. ****************************************************************/ public class GuessNumber { public GuessNumber() { int secret = (int)(Math.random()*500+1); for(int c = 1; c <= 10; c=c+1) { int guess = Integer.parseInt( input("Your guess?") ); if(guess < secret) { output("too small"); } if(guess > secret) { output("too big"); } if(guess == secret) { output("RIGHT! That took " + c + " guesses."); System.exit(0); } } } public static void main(String[] args) { new GuessNumber(); } public String input(String prompt) { return javax.swing.JOptionPane.showInputDialog(null,prompt); } public void output(String message) { javax.swing.JOptionPane.showMessageDialog(null,message); } } ```

### Divide and Conquer

It seems like 10 guesses would not be enough to guess a number chosen from 500 choices.  But the divide-and-conquer
strategy, it is possible to win this game every time.  You must guess 250 as the first guess.  Then the program tells you
whether the secret number is higher or lower.  This cuts the number of possibilities in half.  Then you need to guess the
middle number of the ones that are left.

 Guess:  250  too small  Guess:  375  too big  Guess:  315  too small  Guess:  345  too small  Guess:  360  too big  Guess:  352  too small  Guess:  356  too small  Guess:  358  too big  Guess:  357  RIGHT! That took 9 guesses

At every guess, it cuts the number of remaining possibilities in half, like this:

500
250
125
63
32
16
8
4
2
1

We see this takes 10 steps, so 10 guesses should be enough if we use the divide-and-conquer strategy.

### Algorithm Efficiency

If we use a divide and conquer algorithm that cuts the problem in half over and over again, it is much faster than
an exhaustive algorithm that simply counts through all the possibilities - e.g. guess 1, then 2, then 3, etc..
If we can divide the problem in half over and over again, then the number
of steps is not N (the number of items), but rather log2N , where log2N is
defined as "the number of times you must divide a number by 2 until the result is 1 or smaller."

A typical example of divide-and-conquer as a binary search, which is exactly what we are doing
when we try to guess the number by guessing in the middle each time.

### Practice

• Download the program and run it
• Practice the guessing game until you can solve it in 10 tries each time
• Change the game to choose a number between 1 and 1 million, and change the loop
to allow an appropriate number of guesses.
• Change the program so that it asks the user whether they want to guess between 1 and 100,
or between 1 and 1000, or between 1 and 1000000.  The program must then automatically
choose the appropriate maximum number of guesses.
Use if... commands to decide the maximum number of guesses to allow.

### Artificial Intelligence = AI

After practicing the guessing game, you should see that you follow a simple algorithm:
• at the beginning, the HIGHEST possibility is 500, and LOWEST is 0
• calculate the MIDDLE value between LOWEST and HIGHEST - guess this
• if the response is "Right", then you can quit
• if the response is "too small", then change LOWEST to equal your GUESS+1
• if the response is  "too big", then change HIGHEST to be your GUESS-1
• repeat - e.g. go back to calculate MIDDLE and guess again
This is an algorithm - a clear and specific set of steps to follow,
guaranteed to eventually find an answer.
Since there is a clear algorithm, we can program the COMPUTER to do the guessing automatically.
That means we can think of a secret number, and then let the COMPUTER try to guess
our number.

### More Practice

• Write a program that makes the computer try to guess our secret number