Lab Notes

Things I want to remember how to do.

An Io Guessing Game

September 30, 2012
7languages7weeks algorithms Io

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?