Search

September 30, 2012

An Io Guessing Game

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:

  1. What happens if we start our algorithm with 50 instead of 1?
  2. 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?
  3. Can the algorithm be improved upon?
  4. 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?