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

// 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!
    state = "ask";
    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);
    if (state == "ask") {
        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:

Run Pause setup() draw()

Sketch #18 state: Loading...