Homework 10 (Due Sat 12-Nov at 8pm)

Important Notes:

1. Read the "Important Notes" at the top of hw1. The same general rules apply to this hw regarding solo, sample solution videos, etc.
2. This homework is solo. You must not collaborate with anyone (besides current course TAs and faculty) in any way. See the syllabus for more details.
3. The same rules about recursion from hw9 apply to this hw, with one exception: unlike last hw, in this hw you can use for loops or while loops, as long as you also use recursion meaningfully in each problem.
4. You will need these starter files:
   • hw10.py
   • cs112_f22_week10_linter.py
5. For this hw, you may submit to Autolab up to 5 times, but only your last submission counts.
6. Do not hardcode the test cases in your solutions.

---

1. Tree class [20 pts]
2. createFullTree(height, numChildren, valueForAllNodes) [10 pts]
3. GameTree class [10 pts]
4. NimGameTree class [10 pts]
5. knightsTour(rows, cols) # with backtracking [50 pts]

---

Tree class

[20 pts] [autograded]

In this assignment, we will be representing trees (as discussed in recitation last week) using object-oriented programming. We'll start with implementing a Tree class. Each instance of the Tree class will store:
• The value corresponding to top node of the tree and
• A list of Tree objects representing the children of this node (recursive data structure!)

A instance of Tree that has no children (and empty list of children) is called a leaf.


Once we implement this Tree class, we'll be able to build the above example tree. We could do this by either A) starting from the bottom (the leaves) and assembling up or B) starting at the top node and building down. See both examples below.






Implement a Tree class with the following methods:


• Constructor:
  The constructor (__init__) takes a value that will be stored at the top node of this tree. (Note that any Tree object could also be a sub-tree of some other Tree instance.) This constructor will create a tree with a single node and zero child sub-trees. This is not a recursive method.
  
  
• getNodeValue(self):
  Returns the value associated with the top node of this tree. This is not a recursive method.
  
  
• getChildren(self):
  Returns the list of children stored in this tree. Note this only returns the children of the top node of this tree. For example, it does not include the children's children. If there are no children, this returns an empty list. This is not a recursive method.
  
  
• addChild(self, childTree):
  Append childTree to the list of child sub-trees. This method does not check to see if the child already exists. This is not a recursive method.
  
  
• getTotalNumNodes(self):
  Recursively count and return all nodes in the tree. A tree with zero children will return 1.
  
  
• getHeight(self):
  Recursively count and return the maximum height of the tree. A tree with zero children will return 0. The green example tree below A-->[B, C-->E, D] will return 2.
  
• __str__(self):
  Recursively construct and return a string that represents this tree. We recommend using the recursive helper function getStringHelper(self, depth=0) to implement __str__. The value of the top node (depth=0) should be printed first with zero '**' characters in front, followed by a new line character, '\n'. Then, each complete sub-tree should be printed with an added '**' in front, starting with the first sub-tree in the getChildren() list.
  For example:
  • The purple example tree below A-->B-->C-->D should return the multiline string:

    """A
    **B
    ****C
    ******D
    """

  • The green example tree below A-->[B, C-->E, D] should return the multiline string:

    """A
    **B
    **C
    ****E
    **D
    """


        



createFullTree(height, numChildren, valueForAllNodes)

[10 pts] [autograded]

Implement the recursive function createFullTree(height, numChildren, valueForAllNodes) that recursively creates and returns a new Tree instance with height equal to height. Other than the leaf nodes at the bottom of the tree, each sub-tree in this "full" tree will have numChildren children. Every node, from the top node to the leaves, will have the same value, valueForAllNodes. If either height or numChildren equals zero, the function will return a Tree instance with a single node that has no children.

GameTree class

[10 pts] [autograded]

Implement a GameTree class that inherits from the Tree class and adds the following methods:
• Constructor:
  The constructor (__init__) takes a value that will be stored at the top node of this tree. Unlike the Tree superclass, the GameTree constructor also has a boolean argument, myTurn, that represents whose turn it is at the top node in the tree. (Note that any GameTree object could also be a sub-tree of some other GameTree instances.) This constructor will create a game tree with a single node and zero child sub-trees. This is not a recursive method.
  
  
• isMyTurn(self):
  Returns a boolean representing whose turn it is at the top node of this tree. This is not a recursive method.
  
  
• __str__(self):
  Recursively construct and return a string that represents this game tree. This will behave similarly to the Tree.__str__() method but instead of just printing the value at each node, each node will print the value followed by ", myTurn=" followed by True or False depending on the value of myTurn at that node (and then a new line, \n). Calling str() with the single node tree GameTree('A', False) should return the string "A, myTurn=False\n".
  

NimGameTree class

[10 pts] [autograded]

This NimGameTree class represents a game tree containing all of the possible results from playing a simple variant of the game Nim. In our Nim variant, there is a single pile of sticks from which two players take turns taking either one or two sticks. The player that takes the last set of sticks wins.

Implement a NimGameTree class that inherits from the GameTree class and has the following constructor method:
• Constructor:
  The constructor (__init__) takes in parameters for the number of pieces and whose turn it is. Unlike the Tree and GameTree superclasses, the NimGameTree constructor will recursively create the tree to represent all possible paths of two players taking one or two pieces. This tree will be created such that:
  • The remaining number of pieces will be the value at each node. The number of pieces of the children will decrease appropriately based on how many pieces are taken.
  • The list of children for any node will be the NimGameTrees representing the game after taking one piece and after taking two pieces, in that order.
  • If there is only one piece remaining, the node will only have one NimGame Tree child representing the game after taking one piece.
  • If numPieces is zero, the node will have zero children.
  • The tree will continue to grow until each leaf has zero pieces.
  • The superclass GameTree myTurn boolean will alternate between True and False as the NimGameTree grows deeper, i.e., as the players take turns.

For example, given tree = NimGameTree(3, True), calling print(tree) will print:

3, myTurn=True
**2, myTurn=False
****1, myTurn=True
******0, myTurn=False
****0, myTurn=True
**1, myTurn=False
****0, myTurn=True

knightsTour(rows, cols) # with backtracking

[50 pts] [autograded]

First, read about the Knight's Tour problem here. Next, write the function knightsTour(rows, cols) that takes a non-negative int n and returns a 2d list of a knight's tour on a rows-by-cols board, or None if this does not exist. This is a slight generalization since here we will allow non-square rectangular boards.

Following these instructions, knightsTour(4, 5) should return a legal 4x5 knight's tour, such as this one:

[
 [ 1, 14,  5, 18,  7], 
 [10, 19,  8, 13,  4],
 [15,  2, 11,  6, 17],
 [20,  9, 16,  3, 12]
]

Here we see that the tour started at 1, which is at the top-left corner. Then following the sequence 1,2,3,... to follow each move in order.

Note that it is possible for some dimensions that there is a legal knight's tour, only not one starting at the top-left corner. You will have to account for that in your solution.

Also: backtracking can be slow, and your solution will probably not run fast enough after 6-by-6 or so. That's ok. :-)

Hint: if your solution is "correct" but takes a long time to run, you may be able to speed it up by placing the 1st number before calling your backtracker. Most but not all boards we will consider have a solution with 1 in the top-left corner. So you can just use the usual nested for loops to place the 1 in every possible location, but first at (0,0), and then backtracking from there. That may well speed things up a bit.

Optional extra challenge: speed this up even more! There are techniques that can make this work fast enough for somewhat larger boards (though they still bog down eventually). You can do some pondering of your own, or some internet sleuthing, but in any case, try to make this run faster. Or not, since it is optional.

In any case, have fun!

---