From: Ruby Quiz <james@...>
Date: 2005-01-20T23:49:35+09:00
Subject: [SUMMARY] Animal Quiz (#15)

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...