CS 61A

Time: Tue 9/26/17 2 pm

Recursions

Verbose Factorial

Here's a good way to visualize factorials--but a little challenging to code. Write a functional verbose_fact(n) that prints out the steps to reduce the recursive cases to a base case. You may utilize the params fact_so_far and prefix to help with building up your solution.

def verbose_fact(n, fact_so_far = 1, prefix = ""):
  """
  >>> verbose_fact(1)
    1!
  = 1
  >>> verbose_fact(2)
    2!
  = 2 x 1!
  = 2 x 1
  = 2
  >>> verbose_fact(3)
    3!
  = 3 x 2!
  = 3 x 2 x 1!
  = 3 x 2 x 1
  = 6
  """

  assert n >= 1, "Use n >= 1"
  "*** YOUR CODE HERE ***"

Solution

def verbose_fact(n, fact_so_far = 1, prefix = ""):
  """
  >>> verbose_fact(1)
    1!
  = 1
  >>> verbose_fact(2)
    2!
  = 2 x 1!
  = 2 x 1
  = 2
  >>> verbose_fact(3)
    3!
  = 3 x 2!
  = 3 x 2 x 1!
  = 3 x 2 x 1
  = 6
  """

  assert n >= 1, "Use n >= 1"

  # Check if it's the first time calling the function
  if not prefix:
    # First time
    print("  " + str(n) + "!")
  else:
    # Not the first time
    print("= " + prefix + str(n) + "!")

  # Check if recursion is finished
  if n == 1:
    # Base case, end of recursion
    if prefix: print("= " + prefix + str(n)) # Print the simplified "1!"
    # Print out the solution
    print("= " + str(fact_so_far * n))
  else:
    # Continue by recursion
    verbose_fact(n - 1, fact_so_far * n, prefix + str(n) + " x ")

Towers of Hanoi (fa16-hw5-3)

A classic puzzle called the Towers of Hanoi is a game that consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with n disks in a neat stack in ascending order of size on a start rod, the smallest at the top, forming a conical shape.

The objective of the puzzle is to move the entire stack to an end rod, obeying the following rules:

Only one disk may be moved at a time.
Each move consists of taking the top (smallest) disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
No disk may be placed on top of a smaller disk.

Complete the definition of move_stack, which prints out the steps required to move n disks from the start rod to the end rod without violating the rules.

def print_move(origin, destination):
  """
  Print instructions to move a disk.
  """

  print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
  """
  Print the moves required to move n disks on the start pole to the end pole without violating the rules of Towers of Hanoi.

  n -- number of disks
  start -- a pole position, either 1, 2, or 3
  end -- a pole position, either 1, 2, or 3

  There are exactly three poles, and start and end must be different. Assume
  that the start pole has at least n disks of increasing size, and the end
  pole is either empty or has a top disk larger than the top n start disks.

  >>> move_stack(1, 1, 3)
  Move the top disk from rod 1 to rod 3
  >>> move_stack(2, 1, 3)
  Move the top disk from rod 1 to rod 2
  Move the top disk from rod 1 to rod 3
  Move the top disk from rod 2 to rod 3
  >>> move_stack(3, 1, 3)
  Move the top disk from rod 1 to rod 3
  Move the top disk from rod 1 to rod 2
  Move the top disk from rod 3 to rod 2
  Move the top disk from rod 1 to rod 3
  Move the top disk from rod 2 to rod 1
  Move the top disk from rod 2 to rod 3
  Move the top disk from rod 1 to rod 3
  """

  assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
  "*** YOUR CODE HERE ***"

Solution

def print_move(origin, destination):
  """
  Print instructions to move a disk.
  """

  print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
  """
  Print the moves required to move n disks on the start pole to the end pole without violating the rules of Towers of Hanoi.

  n -- number of disks
  start -- a pole position, either 1, 2, or 3
  end -- a pole position, either 1, 2, or 3

  There are exactly three poles, and start and end must be different. Assume
  that the start pole has at least n disks of increasing size, and the end
  pole is either empty or has a top disk larger than the top n start disks.

  >>> move_stack(1, 1, 3)
  Move the top disk from rod 1 to rod 3
  >>> move_stack(2, 1, 3)
  Move the top disk from rod 1 to rod 2
  Move the top disk from rod 1 to rod 3
  Move the top disk from rod 2 to rod 3
  >>> move_stack(3, 1, 3)
  Move the top disk from rod 1 to rod 3
  Move the top disk from rod 1 to rod 2
  Move the top disk from rod 3 to rod 2
  Move the top disk from rod 1 to rod 3
  Move the top disk from rod 2 to rod 1
  Move the top disk from rod 2 to rod 3
  Move the top disk from rod 1 to rod 3
  """

  assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
  if n == 1:
    print_move(start, end)
  else:
    other = 6 - start - end
    move_stack(n - 1, start, other)
    print_move(start, end)
    move_stack(n - 1, other, end)

Weekly Misc about Trees

They are naturally sustainable! Oh well, think about how trees are conceptually related to pairs. Define the terminologies around trees--root, node, leaf node (the language we use may vary in different places).

Consider the following implementation:

def tree(label, branches=[]):
  return [label] + branches

def label(tree):
  return tree[0]

def branches(tree):
  return tree[1:]

There are multiple ways to get started on playing with such tree structure! As a few examples:

Given a tree, how can we find a largest/smallest label in the leaves?
Given a tree, how can we find a largest/smallest label in the tree?
Given a tree, how can we find the sum of all labels (assuming all labels are numbers)?
Given a tree, how can we make a copy of it with all the leaves pruned? The function is non-destructive.
Given a tree and a label, how can we check if the label we want is in the tree?
Given a tree, how can we check if there aren't any descendent nodes of a same label for any node in the tree?

And here's sample tree to work with:

sample_tree = \       # the back slash is here to break the line
  tree(5, [
    tree(-5),
    tree(10, [
      tree(2),
      tree(5, [
        tree(3, [
          tree(15, [
            tree(-2)  # Leaf
          ])
        ]),
        tree(4),      # Leaf
        tree(5, [
          tree(99),   # Leaf
          tree(6)
        ])
      ])
    ])
  ])