# 1. Twenty Questions¶

I'm thinking of a number between 0 (zero) and 1,000 (inclusive).

How many guesses will it take you to guess my number?

When you make a guess, I'll say "higher" or "lower".

Now how many guesses will it take you to guess my number?

# 2. Divide and Conquer Strategies¶

1. Make a guess; try to start in the middle
• Your guess should try to split the possibilities in half
2. The answer will eliminate one half
3. Take the remaining half, and repeat

Try it!

Question: If it is good to eliminate 1/2 of the possibilities, then it would be even better to eliminate 2/3 of the possibilities. Would it be better to divide the

# 3. Writing a program to do it¶

In :
// 20 Questions
// By Doug Blank
// CS110, Fall 2015
// in Processing

// Global variables:
int max_range;
int min_range;
int guess;
int count;
String state;

void setup() {
textFont(createFont("Arial",20));
size(500, 100);
initialize();
}

void initialize() {
min_range = 0;
max_range = 1000;
guess = int(random(0, 1000)); // CHANGE this!
count = 0;
}

int guess_lower() {
// last guess was too high
return guess - 1;      // CHANGE this!
}

int guess_higher() {
// last guess was too low
return guess + 1;     // CHANGE this!
}

void draw() {
background(100);
text("Think of a number between " +
min_range + " and " + max_range +
".\nPress Enter when ready.", 10, 50);
} else if (state == "guess") {
text("Your number is " + guess +
"?\nY: yes, H: guess higher, L: guess lower", 10, 50);
} else if (state == "win") {
text("I win! Your number is " + guess +
"\nI guessed it in " + count + " tries." +
".\nPress 'A' to play again", 10, 20);
}
}

void keyPressed() {
if (key == 10) { // enter
state = "guess";
} else if (key == 'a' || key == 'A') { // start play
initialize();
} else if (key == 'h' || key == 'H') {
// set guess higher
guess = guess_higher();
count += 1;
} else if (key == 'l' || key == 'L') {
// set guess lower
guess = guess_lower();
count += 1;
} else if (key == 'y' || key == 'Y') {
state = "win";
}
}

Sketch #18: