[SOLUTION] Ruby Quiz #15 Animal Quiz

[David Tran]

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 LAY_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 = LAY_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 = LAY_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]

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

 

[Aquila]

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

 

[David A. Black]

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

 

[David Tran]

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.

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]

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

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.

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]

=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]

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]

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]

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 }