# DS Blank, Data Structures, Fall 2010
# Solution to 20 Questions

class Animal:
    def __init__(self, name):
        self.name = name

class Tree:
    def __init__(self, other):
        animal = raw_input("New Animal: ")
        self.question = raw_input("Question that separates '%s' from '%s': " % 
                                  (animal, other.name))
        if raw_input("What is the answer for a '%s' [y/n]? " % animal) == "y":
            self.yes = Animal(animal)
            self.no = other
        else:
            self.yes = other
            self.no = Animal(animal)

tree = Tree(Animal("cat")) # Add a question that separates new animal from cat
# Let's Play!
print "Welcome to 20 Questions!"
while raw_input("Play again [y/n]? ") == "y":
    current = tree # always start at top
    print "Think of an animal."
    while current:
        yesno = raw_input(current.question + " [y/n] ")
        if yesno == "y":
            if isinstance(current.yes, Animal):
                guess = raw_input("Is your animal a '%s' [n/y]? " % current.yes.name)
                if guess == "y":
                    print "I guessed it!"
                else: # I don't know it
                    current.yes = Tree(current.yes)
                current = None
            else:
                current = current.yes
        elif yesno == "n":
            if isinstance(current.no, Animal):
                guess = raw_input("Is your animal a '%s' [y/n]? " % current.no.name)
                if guess == "y":
                    print "I guessed it!"
                else: # I don't know it
                    current.no = Tree(current.no)
                current = None
            else:
                current = current.no

### Recursive Play version:

def play(current):
    if current is None: return
    yesno = raw_input(current.question + " [y/n] ")
    if yesno == "y":
        if isinstance(current.yes, Animal):
            guess = raw_input("Is your animal a '%s' [n/y]? " % current.yes.name)
            if guess == "y":
                print "I guessed it!"
            else: # I don't know it
                current.yes = Tree(current.yes)
            current = None
        else:
            current = current.yes
    elif yesno == "n":
        if isinstance(current.no, Animal):
            guess = raw_input("Is your animal a '%s' [y/n]? " % current.no.name)
            if guess == "y":
                print "I guessed it!"
            else: # I don't know it
                current.no = Tree(current.no)
            current = None
        else:
            current = current.no
    play(current)

print "Welcome to 20 Questions!"
while raw_input("Play again [y/n]? ") == "y":
    play(tree)