## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS110 Intro to Computing / 2015-Fall / Notes

# 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 [3]:
// 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 = 1000000;
guess = int((min_range + max_range) / 2); // CHANGED!
count = 0;
}

int guess_lower() {
// last guess was too high
max_range = guess - 1;
return int((min_range + max_range) / 2);      // CHANGE this!
}

int guess_higher() {
// last guess was too low
min_range = guess + 1;
return int((min_range + max_range) / 2);     // 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 #3: