Question
You may have seen online games that purport to be psychic, with the ability to correctly guess any item or character that you may be
You may have seen online games that purport to be psychic, with the ability to correctly guess any item or character that you may be thinking of by asking yes/no questions of the player. Your goal is to write a program that can play this game, in part by learning about a universe of your choice as it plays by asking yes/no questions. For example, your program might learn about animals by having the following dialogue with its user. (For readability, user responses are shown here in red. The responses also use capital letters, which is not a requirement for this assignment.) Think of an animal, and I will guess it. Does it have legs? YES Is it a cat? YES I win! Continue? YES Think of an animal, and I will guess it. Does it have legs? NO Is it a snake? YES I win! Continue? YES Think of an animal, and I will guess it. Does it have legs? NO Is it a snake? NO I give up. What is it? EARTHWORM Please type a question whose answer is yes for earthworm and no for snake: DOES IT LIVE UNDERGROUND? Continue? YES Think of an animal, and I will guess it. Does it have legs? NO Does it live underground? NO Is it a snake? NO I give up. What is it? FISH Please type a question whose answer is yes for fish and no for snake: DOES IT LIVE IN WATER? Continue? NO Good-bye. The program begins with minimal knowledge about animals: It knows that cats have legs and snakes do not. When the program incorrectly guesses snake the next time, it asks for the answer and also asks for a way to distinguish between snakes and earthworms. The program builds a binary tree of questions and animals. A YES response to a question is stored in the questions left child; a NO response to a question is stored in the questions right child. Task Extend the LinkedBinaryTree class to create a data structure that supports this game. Make use of the protected methods in LinkedBinaryTree to modify the tree structure. You may name your class anything you wish, though your module must be named twenty.py. Additionally, you must have a play_game() function in the module (not your class) that allows the user to play when it is called. When the game ends, you should offer the player the opportunity to save the data in the tree so that they do not have to re-train your program from scratch every time. When starting the game, you should give an option to load a saved game. Make use of the save_tree() and load_tree() methods in BinaryTree to save and load the game from a file. You should not modify these methods, just call them.
tree.py code
class Tree:
"""Abstract base class representing a tree structure"""
#-------------------- nested Position class ---------------------
class Position:
"""An abstraction representing the location of a single element"""
def element(self):
raise NotImplementedError('Must be implemented by subclass')
def __eq__(self, other):
"""Return True if other Position represents the same location"""
raise NotImplementedError('Must be implemented by subclass')
def __ne__(self, other):
"""Return True if other does not represent the same location"""
return not(self == other)
#--- abstract methods that concrete subclass must support -----------
def root(self):
"""Return Position representing the tree's root (or None if empty)"""
raise NotImplementedError('Must be implemented by subclass')
def parent(self, p):
"""Return Position representing p's parent (or None if p is root)"""
raise NotImplementedError('Must be implemented by subclass')
def num_children(self, p):
"""Return the number of children that p has"""
raise NotImplementedError('Must be implemented by subclass')
def children(self, p):
"""Generate an iteration of Positions representing p's children"""
raise NotImplementedError('Must be implemented by subclass')
def __len__(self):
"""Return the total number of elements in the tree"""
raise NotImplementedError('Must be implemented by subclass')
#--- concrete methods implemented in this class --------------------
def is_root(self, p):
"""Return True if Position p represents the root of the tree"""
return self.root() == p
def is_leaf(self, p):
"""Return True if Position p does not have any children"""
return self.num_children(p) == 0
def is_empty(self):
"""Return True if the tree is empty"""
return len(self) == 0
# -------------- traversal methods ---------------------------------
def preorder(self):
"""Generate a preorder iteration of positions in the tree"""
if not self.is_empty():
for p in self._subtree_preorder(self.root()): # Start recursion
yield p
def _subtree_preorder(self, p):
yield p # Visit p before its subtrees
for c in self.children(p): # For each child c
for other in self._subtree_preorder(c): # Do preorder of c's subtree
yield other # Yielding each
def postorder(self):
if not self.is_empty():
for p in self._subtree_postorder(self.root()):
yield p
def _subtree_postorder(self, p):
for c in self.children(p): # For each child c
for other in self._subtree_postorder(c): # Do postorder of c's subtree
yield other # Yielding each
yield p # Visit p after its subtrees
binary_tree.py code
from tree import Tree
import pickle # Special, used for saving and loading the tree from a file
class BinaryTree(Tree):
"""Abstract base class representing a binary tree structure"""
#---------- additional abstract methods ---------------
def left(self, p):
"""Return a Position representing p's left child.
Return None if p does not have a left child.
"""
raise NotImplementedError('Must be implemented by subclass')
def right(self, p):
"""Return a Position representing p's right child.
Return None if p does not have a right child.
"""
raise NotImplementedError('Must be implemented by subclass')
# ---------- concrete methods implemented by this class
def sibling(self, p):
"""Return a position representing p's sibling (or None if no sibling)"""
parent = self.parent(p)
if parent is None:
return None
else:
if p == self.left(parent):
return self.right(parent)
else:
return self.left(parent)
def children(self, p):
"""Generate an iteration of Positions representing p's children"""
if self.left(p) is not None:
yield self.left(p)
if self.right(p) is not None:
yield self.right(p)
# -------------- traversal methods --------------------------------
def inorder(self):
"""Generate an inorder iteration of positions in the tree"""
if not self.is_empty():
for p in self._subtree_inorder(self.root()):
yield p
def _subtree_inorder(self, p):
if self.left(p) is not None: # If left child exists, traverse its subtree
for other in self._subtree_inorder(self.left(p)):
yield other
yield p
if self.right(p) is not None: # If right child exists, traverse its subtree
for other in self._subtree_inorder(self.right(p)):
yield other
# ------------ methods for saving to files ----------------------
def save_tree(self, filename):
"""Saves this tree to the specified filename in binary format.
Returns True if saved successfully, False if an error caused failure.
"""
try:
file = open(filename, 'wb')
pickle.dump(self, file)
file.close()
return True
except Exception:
return False
@staticmethod
def load_tree(filename):
"""Loads and returns a tree from the specified binary file."""
file = open(filename, 'rb')
data = pickle.load(file)
file.close()
return data
linked_binary_tree.py code
from binary_tree import BinaryTree
class Node:
__slots__ = '_element', '_parent', '_left', '_right'
def __init__(self, element, parent=None, left=None, right=None):
self._element = element
self._parent = parent
self._left = left
self._right = right
class Position(BinaryTree.Position):
"""An abstraction repreesnting the location of a single element."""
def __init__(self, container, node):
"""Constructor should not be invoked by user."""
self._container = container
self._node = node
def element(self):
"""Return the element stored at this position"""
return self._node._element
def __eq__(self, other):
"""Return True if other is a Position representing the same location"""
return type(other) is type(self) and other._node is self._node
class LinkedBinaryTree(BinaryTree):
"""Linked representation of a binary tree structure"""
def _validate(self, p):
"""Return associated node, if position is valid"""
if not isinstance(p, Position):
raise TypeError('p must be proper Position type')
if p._container is not self:
raise ValueError('p does not belong to this container')
if p._node._parent is p._node:
raise ValueError('p is no longer valid')
return p._node
def _make_position(self, node):
"""Return Position instance for given node (or None if no node)"""
if node is not None:
return Position(self, node)
return None
#----------------------constructor------------------------
def __init__(self):
"""Create an initially empty binary tree"""
self._root = None
self._size = 0
#------------------public accessors ------------------------
def __len__(self):
"""Return the total number of elements in the tree"""
return self._size
def root(self):
"""Return the root Position of the tree (or None if tree is empty)"""
return self._make_position(self._root)
def parent(self, p):
"""Return the Position of p's parent (or None if p is root)"""
node = self._validate(p)
return self._make_position(node._parent)
def left(self, p):
"""Return the Position of p's left child (or None if p has no left child)"""
node = self._validate(p)
return self._make_position(node._left)
def right(self, p):
"""Return the Position of p's right child (or None if p has no right child)"""
node = self._validate(p)
return self._make_position(node._right)
def num_children(self, p):
"""Return the number of children of Position p"""
node = self._validate(p)
count = 0
if node._left is not None:
count += 1
if node._right is not None:
count += 1
return count
# ------------------ non-public methods -----------------------
def _add_root(self, e):
"""Place element e at the root of an empty tree and return new Position.
Raise ValueError if tree nonempty.
"""
if self._root is not None:
raise ValueError('Root already exists')
self._size = 1
self._root = Node(e)
return self._make_position(self._root)
def _add_left(self, p, e):
"""Create a new left child for Position p, storing element e.
Return the Position of new node.
Raise ValueError if Position p is invalid or p already has a left child.
"""
node = self._validate(p)
if node._left is not None:
raise ValueError('Left child already exists')
self._size += 1
node._left = Node(e, node)
return self._make_position(node._left)
def _add_right(self, p, e):
"""Create a new right child for Position p, storing element e.
Return the Position of new node.
Raise ValueError if Position p is invalid or p already has a right child.
"""
node = self._validate(p)
if node._right is not None:
raise ValueError('Right child already exists')
self._size += 1
node._right = Node(e, node)
return self._make_position(node._right)
def _replace(self, p, e):
"""Replace the element at position p with e, and return old element"""
node = self._validate(p)
old = node._element
node._element = e
return old
def _delete(self, p):
"""Delete the node at Position p, and replace it with its child, if any.
Return the element that had been stored at Position p.
Raise ValueError if Position p is invalid or p has two children.
"""
node = self._validate(p)
if self.num_children(p) == 2:
raise ValueError('p has two children')
child = node._left if node._left else node._right
if child is not None:
child._parent = node._parent
if node is self._root:
self._root = child
else:
parent = node._parent
if node is parent._left:
parent._left = child
else:
parent._right = child
self._size -= 1
node._parent = node # Convention for deprecated node
return node._element
def _attach(self, p, t1, t2):
"""Attach trees t1 and t2 as left and right subtrees of external p"""
node = self._validate(p)
if not self.is_leaf(p):
raise ValueError('Position must be leaf')
if not type(self) is type(t1) is type(t2):
raise TypeError('Tree types must match')
self._size += len(t1) + len(t2)
if not t1.is_empty():
t1._root._parent = node
node._left = t1._root
t1._root = None
t1._size = 0
if not t2.is_empty():
t2._root._parent = node
node._right = t2._root
t2._root = None
t2._size = 0
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started