by Jim Weirich
Here's a program I've had a lot of fun with and might make a good Ruby Quiz entry. The program is a animal quiz program.
It works like this. The program starts by telling the user to think of an animal. It then begins asking a series of yes/no questions about that animal: does it swim, does it have hair, etc. Eventually, it will narrow down the possibilities to a single animal and guess that (Is it a mouse?).
If the program has guessed correctly, the game is over and may be restarted with a new animal. If the program has guess incorrectly, it asks the user for the kind of animal they were thinking of and then asks for the user to provide a question that can distinguish between its incorrect guess and the correct answer. It then adds the new question and animal to its "database" and will guess that animal in the future (if appropriate).
[ Editor's Note: Here's a sample run of my solution, by way of example:
Think of an animal...
Is it an elephant? (y or n)
n
You win. Help me learn from my mistake before you go...
What animal were you thinking of?
a rabbit
Give me a question to distinguish a rabbit from an elephant.
Is it a small animal?
For a rabbit, what is the answer to your question? (y or n)
y
Thanks.
Play again? (y or n)
y
Think of an animal...
Is it a small animal? (y or n)
y
Is it a rabbit? (y or n)
n
You win. Help me learn from my mistake before you go...
What animal were you thinking of?
a Shih Tzu
Give me a question to distinguish a Shih Tzu from a rabbit.
Is it a kind of dog?
For a Shih Tzu, what is the answer to your question? (y or n)
y
Thanks.
Play again? (y or n)
y
Think of an animal...
Is it a small animal? (y or n)
y
Is it a kind of dog? (y or n)
y
Is it a Shih Tzu? (y or n)
y
I win. Pretty smart, aren't I?
Play again? (y or n)
n
-JEG2 ]
Quiz Summary
Quiz creator Jim Weirich shared this wonderful little tidbit with me:
True and slightly off topic story:
The first time I wrote a version of this program, it was on a simple
single board Z80 computer using a FORTH-like language to program it.
I had seeded the program with a single animal (a mouse) and called my
wife in to try it out. I explained the program and she ran the
program. It printed out the words "Think of an animal ...", and then
paused for a few seconds. Then it asked "Is it a mouse?". My wife
turned to me with a look of absolute astonishment and said "HOW did it
know that?".
Yep, she was thinking of a mouse.
Unfortunately, none of the submitted solutions were quite that all-knowing.
Everybody solved this one using pretty much the same technique. Let's go back to Jim for an explanation of the strategy:
There is an easy solution that represents the database as a binary
tree with questions as interior nodes and possible animals as leaf
nodes. Each interior question node has two children corresponding to
a yes or no answer. The children are either further questions (which
will be asked) or an animal (which will be guessed).
Couldn't have said it better myself. Let's see Jim's own implementation of said tree:
require 'yaml'
require 'ui'
def ui
$ui ||= ConsoleUi.new
end
class Question
def initialize(question, yes, no)
@question = question
@yes = yes
@no = no
@question << "?" unless @question =~ /\?$/
@question.sub!(/^([a-z])/) { $1.upcase }
end
def walk
if ui.ask_if @question
@yes = @yes.walk
else
@no = @no.walk
end
self
end
end
class Animal
attr_reader :name
def initialize(name)
@name = name
end
def walk
if ui.ask_if "Is it #{an name}?"
ui.say "Yea! I win!\n\n"
self
else
ui.say "Rats, I lose"
ui.say "Help me play better next time."
new_animal = ui.ask "What animal were you thinking of?"
question = ui.ask "Give me a question " +
"to distinguish a #{an name} from #{an new_animal}."
response = ui.ask_if "For #{an new_animal}, " +
"the answer to your question would be?"
ui.say "Thank you\n\n"
if response
Question.new(question, Animal.new(new_animal), self)
else
Question.new(question, self, Animal.new(new_animal))
end
end
end
def an(animal)
((animal =~ /^[aeiouy]/) ? "an " : "a ") + animal
end
end
if File.exist? "animals.yaml"
current = open("animals.yaml") { |f| YAML.load(f.read) }
else
current = Animal.new("mouse")
end
loop do
current = current.walk
break unless ui.ask_if "Play again?"
ui.say "\n\n"
end
open("animals.yaml", "w") do |f| f.puts current.to_yaml end
This is a very straight forward solution. At the top, you can see that it brings in YAML for storage (many people did this) and a "ui" library to handle interface. It also defines a helper method for the ui library, making it trivial to change the entire interface just by setting a global variable.
Skip over the class definitions now and have a look at the "main" section. The first third loads an existing animal tree, if one is available. Otherwise, it creates a new tree by magically predicting what Jim's wife would guess.
The middle third walk()s the tree, saving the result in case a new node is added. It then asks if the user would like to play again, using the ui() helper method.
The last third/line, just saves out the tree as it stands at the end of this run. Isn't YAML handy?
To make sense of all this talk about a "tree", you need to go back up and examine the two classes. As described in the strategy quote above, Question objects just hold the question itself, and links to the answer nodes for yes and no. The real method of interest here is Question#walk. walk() asks its question through ui(), then recurses into @yes.walk() or @no.walk(), depending on the answer provided. The trick to note here is that the result of the call is saved back to the node. That allows nodes to update themselves, when the game learns a new animal.
That just leaves Animal, which is even easier to grasp. Again, the method of interest is Animal#walk. walk() guesses the animal over ui() and declares victory if it's right. When it's wrong, it asks the clarifying questions to learn and returns itself and the new animal wrapped in a new Question object. This return ensures that the tree is updated, thanks to the saving behavior of Question#walk.
That leaves only the mystical ui library. Here's a look at it:
class ConsoleUi
def ask(prompt)
print prompt + " "
answer = gets
answer ? answer.chomp : nil
end
def ask_if(prompt)
answer = ask(prompt)
answer =~ /^\s*[Yy]/
end
def say(*msg)
puts msg
end
end
This is just a simple console interface, of course. ask() handles input, say() output and ask_if() is a helper method that returns true if it looks like the user answered with a yes or false otherwise (handy for "if" conditions, thus the name). These methods could be replaced with CGI equivalents, GUI routines, or whatever. Nice abstraction here.
Now, I did say the tree method was easy, but it's not without its faults. Once more, I give you the voice of Jim:
However, the tree solution has some draw backs. It is very sensitive
to the order in which animals are added to the tree and the type of
questions used. The tree solution works best when the early questions
divide the set of possible animals into more or less equal groups.
This keeps the tree nicely balanced and the series of questions
leading up to any guess are all equally short. Unfortunately, in real
life the tree tends to become very unbalanced with individual questions
targetting a rather specific animal in the yes branch and the no
branch becoming a long list of more specific questions.
Another small problem with the tree solution is that some questions
are ambiguous, or the user doesn't have the knowledge to answer the
question properly. For example, a question might be "Does it live in
the water?". Some people might select a beaver as their animal and
think "Oh yes, it loves to swim". Others might say "No, it lives on
land, it just enjoys swimming". In actual practice, these ambiguities
average out and you would get the beaver answer on both yes and no
nodes of a question, each branch using different questions to narrow
down the choice. Although not a fatal flaw, it does put redundant
answers in the tree and essentially waste a question that could be put
to better use.
I actually did a fair amount of thinking about other approaches to this problem. Unfortunately, every time I broke from the tree structure, it became a lot trickier to add new animals. I basically had to badger the user for answers to half of all the questions known about their animal and in doing so it seemed I ran into even more irrelevancy issues. Because of that, I eventually abandoned the approach. If anybody has or creates another strategy for this, be sure and send it in!
My thanks to the submitters and Jim, who didn't realize he had already wrote this summary when he told me I could handle it.
Tomorrow, it's every coder for themselves as we get a little friendly competition going...
