[SUMMARY] Animal Quiz (#15)

Discussion in 'Ruby' started by Ruby Quiz, Jan 20, 2005.

  1. Ruby Quiz

    Ruby Quiz Guest

    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...
    Ruby Quiz, Jan 20, 2005
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Steve Green

    is there such an animal

    Steve Green, Mar 24, 2005, in forum: Java
    Replies:
    8
    Views:
    375
    Joona I Palaste
    Mar 25, 2005
  2. cyber science
    Replies:
    0
    Views:
    277
    cyber science
    Sep 1, 2009
  3. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    341
    James Edward Gray II
    Jan 18, 2005
  4. David Tran
    Replies:
    9
    Views:
    166
    David Tran
    Jan 21, 2005
  5. Ruby Quiz

    [QUIZ] 1-800-THE-QUIZ (#20)

    Ruby Quiz, Feb 18, 2005, in forum: Ruby
    Replies:
    15
    Views:
    305
    gabriele renzi
    Feb 24, 2005
Loading...

Share This Page