[SOLUTION] Ruby Quiz #15 Animal Quiz

ruby-talk
1

Just got a chance to solve it today ...
Here is my solution; many @todo exist, however, it responds to the Quiz.

# Program : Ruby Quiz #15 Animal Quiz
# Author : David Tran
# Date : 2005-01-17

=begin

···

+------+

     >
     V
   [init (load learned data?)]
     ><-------------------+
     V |
   [leaf ?] ----> [question and move to next node]
     >y n
     V
   [quest animal] ----> [learn]
     >y n |
     V |
   [show win text] |
     > >
     V |

+--- [ask play again] <-----+
  y |n
       V
      exit (persistence learned data ?)

* use array of array to simulate binary research tree
* @todo: maybe implement binary data structure
* many @todo for future version

=end

class AnimalQuest
  
  def initialize
    @qtree = [['an elephant']] # @todo: maybe load saved data
    @state = :INIT
  end

  def play
    while (@state != :EXIT) do
      case @state
        when :INIT : init
        when :CHECK_TREE : check_tree
        when :QUEST_ANIMAL : quest_animal
        when :LEARN : learn
        when :PLAY_AGAIN : play_again
      end
    end
  end
  
  private

  def get_answer
    # $stdout.flush
    gets.chomp.upcase == 'Y'
  end
    
  def init
    @node = @qtree[0]
    puts "Think of an animal..."
    @state = :CHECK_TREE
  end
  
  def check_tree
    if @node.size == 1 # leaf node ?
      @state = :QUEST_ANIMAL
    else
      # @state = :CHECK_TREE # (state unchange)
      puts( @node[0] + " (y or n)" )
      @node = @node[get_answer ? 1 : 2]
    end
  end

  def quest_animal
    puts("Is it " + @node[0] + " (y or n)")
    if (get_answer)
      puts("I win. Pretty smart, aren't I?")
      @state = :PLAY_AGAIN
    else
      @state = :LEARN
    end
  end

  def learn
    puts "You win. Help me learn from my mistake before you go..."
    puts "What animal were you thinking of?"
    animal = gets.chomp
    # @todo: check if animal already exist on the database
    # then the player is cheating!! => show cheating message
    puts "Give me a question to distinquish " + animal + " from " +
@node[0] + "."
    question = gets.chomp
    # @todo: check conflict of question,
    # for example, question already asked before.
    puts "For " + animal + ", what is the answer to your question? (y or n)"
    if get_answer
      @node[0,1] = [question, [animal], @node.dup]
    else
      @node[0,1] = [question, @node.dup, [animal]]
    end
    puts "Thanks."
    @state = :PLAY_AGAIN
  end

  def play_again
    puts("Play again? (y or n)")
    @state = get_answer ? :INIT : :EXIT
    # @todo: save learned data before exit
  end

end

AnimalQuest.new.play

--

David Tran
http://www.doublegifts.com

2

Quick review, find a performance and memory issue ...

The code:
    if get_answer
      @node[0,1] = [question, [animal], @node.dup]
    else
      @node[0,1] = [question, @node.dup, [animal]]
    end

is better replace by:
    temp = @node
    if get_answer
      @node[0,1] = [question, [animal], temp]
    else
      @node[0,1] = [question, temp, [animal]]
    end

···

--

David Tran
http://www.doublegifts.com

3

=begin
My second solution.

Most solutions do a tree walk.
Kids will get boring soon,
because it always ask the questions in the same order.
No fun at all...

Here I try to do "ask question in random order".
( ==> Not good to quick find the answer. )

Random select "possible" question.
If we try to count the "weight" of the possible questions,
and select the "heaviest" one, we end up like tree walk order.
Except, if there are equal-heavy, example:
      Q1 Q2
     / \ ==> / \
   Q2 Q2 Q1 Q1

Note: You could change the program to take
the average weigth question instead of
random select.
   
Since we random ask "possible" questions,
that may help to get more information about
existing knowledge animal, example:
     Q1 ==> Q1
    / \ / \
   Q2 c Q2 Q2
  / \ / \ \
a b a b Q3
                        / \
                       c d
           
==> this may happend ask Q2 first,
and finally distinct c,d by Q3.

A little explanation about my data structure:
* db_questions: array to store questions. (index 0 no use)
* db_animals: hash; key == animals,
  value == array of questions, the absolute value map
  to db_questions's index; and positive for 'Yes' answer
  and negative for 'No' answer.
  
=end

require 'yaml'

ANIMALS_FILE = 'animals.yaml'
QUESTIONS_FILE = 'questions.yaml'

# reuse Jim Weirich ConsoleUi class and modified
class ConsoleUi
  def ask(prompt)
    print prompt + "\n"
    answer = gets
    answer ? answer.chomp : nil
  end

  def ask_if(prompt)
    answer = ask(prompt + " (y or n)")
    answer =~ /^\s*[Yy]/
  end
  
  def say(*msg)
    puts msg
  end
end

def ui
  $ui ||= ConsoleUi.new
end

def get_possible_questions(animals, asked_questions)
  questions = []
  animals.each_value do |qs|
    qs.each do |q|
      q = q.abs;
  if !questions.include?(q) &&
     !asked_questions.include?(q) &&
     !asked_questions.include?(-q)
        questions << q
  end
    end
  end
  questions
end

def filter_animals(animals, question)
  animals.each do |animal, questions|
    animals.delete(animal) if questions.include? question
  end
end

db_animals = File.exist?(ANIMALS_FILE) ?
             YAML.load_file(ANIMALS_FILE) :
       { 'an elephant' => [] }
       
db_questions = File.exist?(QUESTIONS_FILE) ?
               YAML.load_file(QUESTIONS_FILE) :
         [ '' ]

loop do
  asked_questions = []
  animals = db_animals.dup

  ui.say "Think of an animal..."

  while animals.size > 1
    qs = get_possible_questions(animals, asked_questions)
    q = qs[rand(qs.size)]
    q = -q unless ui.ask_if db_questions[q]
    asked_questions << q
    filter_animals(animals, -q)
  end

  animal = animals.keys[0]
  if ui.ask_if "Is it #{animal}?"
    ui.say "I win!"
    # update knowledge, we may have more infomation
    # about the animal, since we random asked questions
    animals[animal] = asked_questions.dup
  else
    ui.say "You win. 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 " +
               "#{animal} from #{new_animal}."
    response = ui.ask_if "For #{new_animal}, " +
               "what is the answer to your question?"
    ui.say "Thanks."
    
    if db_animals.key?(new_animal)
      ui.say "Hey! You are cheating, accroding asked questions," +
             "it cannot be #{new_animal}."
      # ...
    end
    
    q = db_questions.index(question)
    if q
      if asked_questions.include?(q) || asked_questions.include?(-q)
        ui.say "Hey! That question already asked! You try to confuse me."
  # ...
      end
    else
      db_questions << question
      q = db_questions.size - 1
    end
    db_animals[animal] = asked_questions.dup
    db_animals[animal] << (response ? -q : q)
    db_animals[new_animal] = asked_questions.dup
    db_animals[new_animal] << (response ? q : -q)
  end

  break unless ui.ask_if "Play again?"
  ui.say "\n\n"
end

open(ANIMALS_FILE, 'w') { |f| f.puts db_animals.to_yaml }
open(QUESTIONS_FILE, 'w') { |f| f.puts db_questions.to_yaml }

···

--

David Tran
http://www.doublegifts.com

4

David Tran wrote:

Quick review, find a performance and memory issue ...

The code:
if get_answer
@node[0,1] = [question, [animal], @node.dup]
else
@node[0,1] = [question, @node.dup, [animal]]
end

is better replace by:
temp = @node
if get_answer
@node[0,1] = [question, [animal], temp]
else
@node[0,1] = [question, temp, [animal]]
end

I'm very new to Ruby performance: why? In other languages this really isn't
a performance neither a memory issue, what is the problem here?

Always keen to learn...

···

--
"May the source be with you"

5

Hi --

Quick review, find a performance and memory issue ...

The code:
   if get_answer
     @node[0,1] = [question, [animal], @node.dup]
   else
     @node[0,1] = [question, @node.dup, [animal]]
   end

is better replace by:
   temp = @node
   if get_answer
     @node[0,1] = [question, [animal], temp]
   else
     @node[0,1] = [question, temp, [animal]]
   end

I believe that the second one is equivalent to:

   if get_answer
     @node[0,1] = [question, [animal], @node]
   else
     @node[0,1] = [question, @node, [animal]]
   end

since temp is just another reference to the object that @node is a
reference to, not to a copy of that object. So you end up with a
recursive data structure.

David

···

On Tue, 18 Jan 2005, David Tran wrote:

--
David A. Black
dblack@wobblini.net

6

I try to avoid "dup" (and reuse the "pointer"), but the way I did is
not good, it creates recursive array.
So the changed code below is not good. Sorry for the confuse.

BTW: My english is really poor; in my code, all the word "quest"
should read as "guess" instead.

···

On Mon, 17 Jan 2005 11:36:59 -0500, David Tran <email55555@gmail.com> wrote:

Quick review, find a performance and memory issue ...

The code:
    if get_answer
      @node[0,1] = [question, [animal], @node.dup]
    else
      @node[0,1] = [question, @node.dup, [animal]]
    end

is better replace by:
    temp = @node
    if get_answer
      @node[0,1] = [question, [animal], temp]
    else
      @node[0,1] = [question, temp, [animal]]
    end

--

David Tran
http://www.doublegifts.com

--

David Tran
http://www.doublegifts.com

7

Something need to be updated for better solution ...

ui.say "I win!"
animals[animal] = asked_question.dup

is better replace by

ui.say "I win!"
animals[animal] += asked_question
animals[animal].uniq!

(if not, it may lose some old knowledge about the animal ... )

Some as:
db_animals[animal] = asked_questions.dup
db_animals[animal] << (response ? -q : q)

is better replace by

db_animals[animal] += asked_questions
db_animals[animal] << (response ? -q : q)
db_animals[animal].uniq!

···

--
David Tran
http://www.doublegifts.com

8

There are no performance and memory issue,
If you look at origin source code,
the "dup" is only to duplicate array of 1 element.

so either :
@node[0,1] = [question, [animal], @node.dup]
or
@node[0,1] = [question, [animal], [@node[0]]]
works, but not
@node[0,1] = [question, [animal], @node]

I try to make it better but it is unnecessary.
Sorry again for my mistake.
I am newbie on Ruby too. :wink:

···

On Mon, 17 Jan 2005 18:22:14 -0500, David Tran <email55555@gmail.com> wrote:

I try to avoid "dup" (and reuse the "pointer"), but the way I did is
not good, it creates recursive array.
So the changed code below is not good. Sorry for the confuse.

BTW: My english is really poor; in my code, all the word "quest"
should read as "guess" instead.

On Mon, 17 Jan 2005 11:36:59 -0500, David Tran <email55555@gmail.com> wrote:
> Quick review, find a performance and memory issue ...
>
> The code:
> if get_answer
> @node[0,1] = [question, [animal], @node.dup]
> else
> @node[0,1] = [question, @node.dup, [animal]]
> end
>
> is better replace by:
> temp = @node
> if get_answer
> @node[0,1] = [question, [animal], temp]
> else
> @node[0,1] = [question, temp, [animal]]
> end
>

--

David Tran
http://www.doublegifts.com

9

Just found a bug, animals[animal] += asked_question
should be db_animals[animal] += asked_question ... etc

Resend the correct one:

=begin
My second solution.

Most solutions do a tree walk.
Kids will get boring soon,
because it always ask the questions in the same order.
No fun at all...

Here I try to do "ask question in random order".
( ==> Not good to quick find the answer. )

Random select "possible" question.
If we try to count the "weight" of the possible questions,
and select the "heaviest" one, we end up like tree walk order.
Except, if there are equal-heavy, example:
      Q1 Q2
     / \ ==> / \
   Q2 Q2 Q1 Q1

Note: You could change the program to take
the average weigth question instead of
random select.
   
Since we random ask "possible" questions,
that may help to get more information about
existing knowledge animal, example:
     Q1 ==> Q1
    / \ / \
   Q2 c Q2 Q2
  / \ / \ \
a b a b Q3
                        / \
                       c d
           
==> this may happend ask Q2 first,
and finally distinct c,d by Q3.

A little explanation about my data structure:
* db_questions: array to store questions. (index 0 no use)
* db_animals: hash; key == animals,
  value == array of questions, the absolute value map
  to db_questions's index; and positive for 'Yes' answer
  and negative for 'No' answer.
  
=end

require 'yaml'

ANIMALS_FILE = 'animals.yaml'
QUESTIONS_FILE = 'questions.yaml'

# reuse Jim Weirich ConsoleUi class and modified
class ConsoleUi
  def ask(prompt)
    print prompt + "\n"
    answer = gets
    answer ? answer.chomp : nil
  end

  def ask_if(prompt)
    answer = ask(prompt + " (y or n)")
    answer =~ /^\s*[Yy]/
  end
  
  def say(*msg)
    puts msg
  end
end

def ui
  $ui ||= ConsoleUi.new
end

def get_possible_questions(animals, asked_questions)
  questions = []
  animals.each_value do |qs|
    qs.each do |q|
      q = q.abs;
  if !questions.include?(q) &&
     !asked_questions.include?(q) &&
     !asked_questions.include?(-q)
        questions << q
  end
    end
  end
  questions
end

def filter_animals(animals, question)
  animals.each do |animal, questions|
    animals.delete(animal) if questions.include? question
  end
end

db_animals = File.exist?(ANIMALS_FILE) ?
             YAML.load_file(ANIMALS_FILE) :
       { 'an elephant' => [] }
       
db_questions = File.exist?(QUESTIONS_FILE) ?
               YAML.load_file(QUESTIONS_FILE) :
         [ '' ]

loop do
  asked_questions = []
  animals = db_animals.dup

  ui.say "Think of an animal..."

  while animals.size > 1
    qs = get_possible_questions(animals, asked_questions)
    q = qs[rand(qs.size)]
    q = -q unless ui.ask_if db_questions[q]
    asked_questions << q
    filter_animals(animals, -q)
  end

  animal = animals.keys[0]
  if ui.ask_if "Is it #{animal}?"
    ui.say "I win!"
    # update knowledge, we may have more infomation
    # about the animal, since we random asked questions
    db_animals[animal] += asked_questions
    db_animals[animal].uniq!
  else
    ui.say "You win. 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 " +
               "#{animal} from #{new_animal}."
    response = ui.ask_if "For #{new_animal}, " +
               "what is the answer to your question?"
    ui.say "Thanks."
    
    if db_animals.key?(new_animal)
      ui.say "Hey! You are cheating, accroding asked questions," +
             "it cannot be #{new_animal}."
      # ...
    end
    
    q = db_questions.index(question)
    if q
      if asked_questions.include?(q) || asked_questions.include?(-q)
        ui.say "Hey! That question already asked! You try to confuse me."
  # ...
      end
    else
      db_questions << question
      q = db_questions.size - 1
    end
    db_animals[animal] += asked_questions
    db_animals[animal] << (response ? -q : q)
    db_animals[animal].uniq!
    db_animals[new_animal] = asked_questions.dup
    db_animals[new_animal] << (response ? q : -q)
  end

  break unless ui.ask_if "Play again?"
  ui.say "\n\n"
end

open(ANIMALS_FILE, 'w') { |f| f.puts db_animals.to_yaml }
open(QUESTIONS_FILE, 'w') { |f| f.puts db_questions.to_yaml }

···

--
David Tran
http://www.doublegifts.com

10

Previous exists logic error
Correct again...

=begin
My second solution.

Most solutions do a tree walk.
Kids will get boring soon,
because it always ask the questions in the same order.
No fun at all...

Here I try to do "ask question in random order".
( ==> Not good to quick find the answer. )

Random select "possible" question.
If we try to count the "weight" of the possible questions,
and select the "heaviest" one, we end up like tree walk order.
Except, if there are equal-heavy, example:
      Q1 Q2
     / \ ==> / \
   Q2 Q2 Q1 Q1

Note: You could change the program to take
the average weigth question instead of
random select.
   
Since we random ask "possible" questions,
that may help to get more information about
existing knowledge animal, example:
     Q1 ==> Q1
    / \ / \
   Q2 c Q2 Q3
  / \ / \ / \
a b a b Q2 c
                        \
                         d
           
==> this may happend ask Q2 first, then Q1,
and finally distinct c,d by Q3.

A little explanation about my data structure:
* db_questions: array to store questions. (index 0 no use)
* db_animals: hash; key == animals,
  value == array of questions, the absolute value map
  to db_questions's index; and positive for 'Yes' answer
  and negative for 'No' answer.
  
=end

require 'yaml'

ANIMALS_FILE = 'animals.yaml'
QUESTIONS_FILE = 'questions.yaml'

# reuse Jim Weirich ConsoleUi class and modified
class ConsoleUi
  def ask(prompt)
    print prompt + "\n"
    answer = gets
    answer ? answer.chomp : nil
  end

  def ask_if(prompt)
    answer = ask(prompt + " (y or n)")
    answer =~ /^\s*[Yy]/
  end
  
  def say(*msg)
    puts msg
  end
end

def ui
  $ui ||= ConsoleUi.new
end

def get_possible_questions(animals, asked_questions)
  questions = []
  animals.each_value do |qs|
    qs.each do |q|
      q = q.abs;
  if !questions.include?(q) &&
     !asked_questions.include?(q) &&
     !asked_questions.include?(-q)
        questions << q
  end
    end
  end
  questions
end

def filter_animals(animals, question)
  animals.each do |animal, questions|
    animals.delete(animal) if questions.include? question
  end
end

db_animals = File.exist?(ANIMALS_FILE) ?
             YAML.load_file(ANIMALS_FILE) :
       { 'an elephant' => [] }
       
db_questions = File.exist?(QUESTIONS_FILE) ?
               YAML.load_file(QUESTIONS_FILE) :
         [ '' ]

loop do
  asked_questions = []
  animals = db_animals.dup

  ui.say "Think of an animal..."

  while animals.size > 1
    qs = get_possible_questions(animals, asked_questions)
    q = qs[rand(qs.size)]
    q = -q unless ui.ask_if db_questions[q]
    asked_questions << q
    filter_animals(animals, -q)
  end

  animal = animals.keys[0]
  if ui.ask_if "Is it #{animal}?"
    ui.say "I win!"
    # update knowledge, we may have more infomation
    # about the animal, since we random asked questions
    db_animals[animal] += asked_questions
    db_animals[animal].uniq!
  else
    ui.say "You win. 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 " +
               "#{animal} from #{new_animal}."
    response = ui.ask_if "For #{new_animal}, " +
               "what is the answer to your question?"
    ui.say "Thanks."
    
    if db_animals.key?(new_animal)
      ui.say "Hey! You are cheating, accroding asked questions," +
             "it cannot be #{new_animal}."
      # ...
    end
    
    q = db_questions.index(question)
    if q
      if asked_questions.include?(q) || asked_questions.include?(-q)
        ui.say "Hey! That question already asked! You try to confuse me."
  # ...
      end
    else
      db_questions << question
      q = db_questions.size - 1
    end
    db_animals[animal] << (response ? -q : q)
    db_animals[animal].uniq!
    db_animals[new_animal] = asked_questions
    db_animals[new_animal] << (response ? q : -q)
  end

  break unless ui.ask_if "Play again?"
  ui.say "\n\n"
end

open(ANIMALS_FILE, 'w') { |f| f.puts db_animals.to_yaml }
open(QUESTIONS_FILE, 'w') { |f| f.puts db_questions.to_yaml }

···

--

David Tran
http://www.doublegifts.com