So when I get the chance I am working through Bruce Tate’s Seven Languages in Seven Weeks (it might end up being seven years in my case) and commenting on it when the mood strikes. I am currently working through the exercises for Io Day 2 and today I was contemplating the final exercise.
In this task, Tate asks us to write a program that will generate a random number between 1 and 100 and then prompt the user to guess it within ten guesses. The user is given feedback in the form of hotter or colder. The task itself was relatively straightforward after discovering how to read input from the console:
GuessMe := Object clone do(
min ::= 1
max ::= 100
guessLimit ::= 10
value ::= nil
lastGuess ::= nil
guessesLeft ::= 0
start := method(
reset
value = Random value(min, max+1) floor
guessesLeft = guessLimit
)
reset := method(
value = nil
lastGuess = nil
guessesLeft = 0
)
guess := method(guess,
guessesLeft = guessesLeft - 1
oldGuess := lastGuess
lastGuess = guess
if (guess == value) then (return "Done")
if (oldGuess == nil) then (return "Guess again")
lastDelta := (value-oldGuess) abs
delta := (value-guess) abs
if (delta == lastDelta) then (
return "Same temperature"
) elseif (delta < lastDelta) then (
return "Hotter"
) else (
return "Colder"
)
)
interactive := method(
if (value == nil) then (start)
stdin := File standardInput
while (guessesLeft > 0,
in := stdin readLine asNumber
result := guess(in)
result println
if (result == "Done") then (break)
)
if (guessesLeft <= 0) then (
("No more guesses, the value was " .. value) println
)
reset
)
) |
If you want to try it, save the above in GuessMe.io and then run the interpreter in the same directory and use the command GuessMe clone interactive.
So what really intrigued me about this assignment was not the exercise itself but the resulting game. It gets obvious pretty fast that the standard binary search solution for guessing games would not work; we need to tweak it somehow. (This is probably an elementary exercise in an algorithms course but it has been a while so it was a fun exercise for me.)
The solution comes from literally thinking outside the box. That is, you need to realize that you can guess numbers outside the range of possible values. So, let’s say that you start by guessing 1 and that’s not it. What should your next guess be? At this point you know the value is between 2 and 100 inclusive, i.e. [2,100]. You’d like to cut your range in half, that is, determine if the value is in the range [2,51] or the range [52,100]. What’s the proper guess?
We want to make our next guess further away from 51 than 1 is. At the same time, it should be closer to 52 than 1 is. In this case the guess is 102, since 51 - 1 = 50 = 102 - 52. Now if the result is hotter, the new range is [52,100]. If the result of the guess is colder, the new range is [2,51].
Now that we’ve seen how we can cut our options in half on every guess (following the first), we can start to create an algorithm. Suppose the range is [x,y] and the last guess is L. First, we find the bifurcation point a = floor((x+y)/2). So we will end up with either [x,a] or [a+1,y].
What should the guess g be? If L is less than a then g will be greater than a and we want g - (a+1) = a - L. This becomes g = 2a - L + 1. If L was greater than a then we want a - g = L - (a+1) which also reduces to g = 2a - L + 1.
Now we have enough to write a prototype to solve our game:
Guesser := Object clone do(
min ::= 0
max ::= 0
guess ::= 0
result ::= nil
report := method(
"Guessed #{guess}: #{result}; [#{min},#{max}]" interpolate println
)
guessIt := method(guessMe,
guessMe start
min = guessMe min
max = guessMe max
// Get through the first guess, it is special
guess = min
result = guessMe guess(guess)
// Assume min wasn't it, no harm if it was
last := min
min = min + 1
report
while (result != "Done",
if (guessMe guessesLeft <= 0) then (
"No guesses left, the value was #{guessMe value}" interpolate println
break
)
avg := ((min+max)/2) floor
guess = if(min==max, min, 2*avg - last + 1)
result = guessMe guess(guess)
if (result == "Colder") then (
if (guess < last) then (
min = avg + 1
) else ( // last < guess
max = avg
)
) elseif (result == "Hotter") then (
if (guess < last) then (
max = avg
) else ( // last < guess
min = avg + 1
)
) elseif (result != "Done") then (
"Did not understand result" println
report
break
)
report
last = guess
)
)
) |
Here’s the Guesser in action:
Io> gm := GuessMe clone ==> GuessMe_0xa18e3b8: Io> guesser := Guesser clone ==> Guesser_0xa1756d8: Io> guesser guessIt(gm) Guessed 1: Guess again; [2,100] Guessed 102: Colder; [2,51] Guessed -49: Hotter; [2,26] Guessed 78: Hotter; [15,26] Guessed -37: Colder; [21,26] Guessed 84: Hotter; [24,26] Guessed -33: Hotter; [24,25] Guessed 82: Colder; [24,24] Guessed 24: Done; [24,24] ==> 24 |
If you enjoyed this post, here are some exercises you may want to think about:
- What happens if we start our algorithm with 50 instead of 1?
- Will the algorithm always be able to find the value within 10 guesses (when the range is [1,100]? What’s the largest range it can guarantee finding the answer over given 10 guesses? Given n guesses?
- Can the algorithm be improved upon?
- What if the game told you if you were hotter or colder than all of your previous guesses? How would you change the algorithm to use less guesses?
