CIS 554 Scala 1: The Animals Game
Fall 2014, David Matuszek

Purposes of this assignment

Part 1: Implement binary trees

Define a generic class BinaryTree.

"Generic" means it has a type parameter, in this case, the type of value held in each node. So you could have a binary tree of Strings, or of Integers, or of Persons. Later on in this assignment we will use a binary tree of Strings. See the short example below for how to create and use a generic class.

package generics

/** A class for two things, both of the same type A. */
class Pair[A](one: A, two: A) {
  override def toString = "(" + one + ", " + two + ")"
}

object GenTest {
  def main(args: Array[String]) {
    val p1 = new Pair("King", "Queen")
    val p2 = new Pair(5, 7)
    println(p1)
    println(p2)
  }
}

A binary tree is composed of nodes. Each node contains:

  1. A value, of the type specified by the type parameter (call it T).
  2. A left subtree, of type Option[BinaryTree[T]].
  3. A right subtree, of type Option[BinaryTree[T]].

You should supply a primary constructor for the BinaryTree class, which takes a value of type T and two subtrees of type BinaryTree[T]. Also supply a secondary constructor which takes only a value as a parameter, and calls the primary constructor with None for each of the other two parameters. You can define a secondary constructor with def this(parameters).

Your BinaryTree class should provide methods for navigating, examining, and modifying the binary tree. Keep the class general purpose--that is, it should not have anything in it that is specific to the Animals game. On the other hand, don't implement anything that isn't needed for the Animals game.

Part 2: Write an "Animals" game

Define an object (not a class) called AnimalsGame.

"Animals" is a classic computer game. The user thinks of an animal, and the computer asks a series of binary (yes/no) questions in an attempt to guess the user's animal. A typical interaction with the game goes something like this:

Computer: Think of an animal. Hit "Return" when ready.
User: (Hits the Return key).
Computer: Does it live in the water?
User: Yes.
Computer: Is it green?
User: No.
Computer: OK, I've got it. Is the animal you're thinking of a whale?
User: No.
Computer: What was your animal?
User: A seal.
Computer: What question would you ask to distinguish between a whale and a seal?
User: Is it very large?
Computer: What would the answer be for a seal?
User: No.
Computer: Thanks, I'll remember that. Would you like to play again?

When the program starts, it should read in a text file containing all the previously learned questions and answers. When the program quits, it should replace the input file with the new, expanded tree of questions and answers. So that you never have to deal with an empty decision tree, you should manually create a file containing the first question and two answers (Traditionally, "Does it live in the water?" and "frog"/"cow".)

About the data file

There are a number of ways you could represent a binary tree in text. If you make your input/output methods sufficiently general, it would make sense to put them in the BinaryTree class; but remember, the binary tree may have any type of values in its nodes, not just Strings. Unless you want to tackle the more interesting problem of doing I/O for any type of binary tree, your I/O methods should be in the AnimalsGame object. In this way, you can not only assume that node values are Strings, but you can also assume that every node either has two children, or none.

Due date

Turn your assignment in to Canvas before 6am Monday, December 1.