R
Ruby Quiz
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:
#!/usr/bin/env ruby
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:
#!/usr/bin/env ruby
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...
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:
#!/usr/bin/env ruby
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:
#!/usr/bin/env ruby
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...