15-112 Recursion Practice

  1. 5 Reasoning About (Recursive) Code problems
    In just a few words of plain English, state what each of the following functions does in general. You will receive no credit for describing the line-by-line low-level behavior of the code.

    Here is a non-recursive example just to help you understand the idea:
    def mystery(list): count = 0 for value in list: if (value == 0): count += 1 return count
    Correct answer: "This function returns the number of 0's in the given list." Or, if you prefer to be succinct, just: "number of 0's".

    Incorrect answer (no points): "This function sets count to 0, then sets value to each element in list in turn, and for each value, if it is 0, it adds one to count, and then returns count". This is all true, but completely misses the high-level behavior of the function, and so would receive zero points.

    1. def f(n): # assume n is a non-negative integer if (n < 10): return 1 else: return 1 + f(n//10)

    2. def f(a): # assume a is a list of strings if (len(a) == 0): return "" else: x = f(a[1:]) if (len(x) > len(a[0])): return x else: return a[0]

    3. def f(a): # assume a is a list of integers if (len(a) == 0): return 0 elif (len(a) == 1): return (a[0] % 2) else: i = len(a)//2 return f(a[:i]) + f(a[i:])

    4. def f(n): # assume n is a non-negative integer if (n == 0): return 1 else: return 2*f(n-1)

    5. def f(n): # assume n is a non-negative integer if (n == 0): return 0 else: return f(n-1) + 2*n - 1 # Hint: you may want to try this function with a few sample values. # The answer should quickly become apparent, though you may wish to # think about why the answer is in fact what it is.

  2. permutations
    Write the recursive function permutations(a, k), which modifies the recursive permutations function from the course notes so that it returns all the permutations of length k from the elements in the list a, or the empty list [] if no such permutations exist. For example, permutations([1,2,3,4], 2) would return some ordering of this list:
    [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
    We say "some ordering" because your list must include the correct permutations, but in any order. And, once again, your solution must be recursive, and in fact it must be an obvious adaptation of the code in the course notes.

    For your testing purposes, it might be helpful to use Pythons built-in permutations function. For example, this might be helpful (it generates the solution above):
    import itertools a = [1,2,3,4] print [list(x) for x in itertools.permutations(a, 2)]
    Hint: do not worry about the case where the original list contains duplicate values.

    Note: regarding efficiency, your code should compute the 870-item result to permutations(range(30), 2) almost instantly, and the 117,600-item result to permutations(range(50),3) with at most a couple of seconds delay.

    Most solutions that are not efficient enough will run much too long on these examples. The reason: generally, one way or another, they will create lots of "extra" permutations and then slice, pop, or remove their way down to the required size. For example, this modification of the permutation code is not acceptable:
    def permutations(a, k): # inefficient version that uses permutations code from class, unmodified, # and then, assuming len(a)>=k, uses only first k elements of each permutation, # ignoring the rest (which is not ok). This also produces some duplicates, # so either have to remove all the duplicates at the end (which is also not ok), # or add an expensive O(n) check inside our loop to check if a permutation # is already in our list (which is also not ok). result = [ ] allPerms = allPermutations(a) for fullLengthPerm in allPerms: perm = fullLengthPerm[0:k] # not ok: essentially "removes" (n-k) elements if perm not in result: # also not ok result += [perm] print "len(allPerms) = ", len(allPerms) print "len(result) = ", len(result) return result def allPermutations(a): # renamed permutations code from class notes # returns a list of all permutations of the list a if (len(a) == 0): return [[]] else: allPerms = [ ] for subPermutation in allPermutations(a[1:]): for i in xrange(len(subPermutation)+1): allPerms += [subPermutation[:i] + [a[0]] + subPermutation[i:]] return allPerms
    Why is this unacceptable? Well, say we are finding permutations(range(9), 2). The answer contains 72 permutations of two numbers each. However, the code above will generate all 362,880 permutations of length 9 to find these 72 permutations. This huge amount of extra work makes it intractable to use this code to compute permutations(range(30),2), let alone permutations(range(50),3). Try it, if you want to wait a very, very long time!

    Big Hint: one way to solve this is to modify the permutations code from class to take a second parameter, k, and to return all the permutations of a that are no larger than length k. This still requires a non-recursive wrapper function (like above) that drops all the permutations that are not of length k, but since we never produce any permutations larger than length k, this is much, much faster than the code above.

  3. twoStackHanoi
    Background: Here, we will consider a modified form of the Towers of Hanoi problem. Given an input n>0, there are 2n discs of increasing size (instead of just n discs of increasing size). There are 3 poles as in the original problem (Pole 0, Pole 1, and Pole 2). We label the discs with numbers {1, 2, 3, ..., 2n}, where the label of a disc corresponds to its size. Initially, the odd-numbered discs (i.e. the discs {1, 3, 5, ..., 2n-1}) are on Pole 0, and the even-numbered discs (i.e. the discs {2, 4, 6, ..., 2n}) are on Pole 2. The goal is to get all the discs on Pole 1 (the middle pole).

    With this in mind, write the function twoStackHanoi(n) that takes a positive int n and returns a list of the moves in order required to solve a 2-stack Hanoi problem as described above (so, to ultimately move the n discs from Pole 0 and the n other discs from Pole 2 all to Pole 1, while also maintaining the Hanoi rule that no disc can be placed on a smaller disc). A "move" will be represented as a tuple (x,y), where x and y are both in the set {0,1,2}, and means to move one disc from Pole x to Pole y.

  4. pegSolitaire
    First, read up on peg solitaire here, and then read this entire writeup carefully. Then, write a peg solitaire solver using backtracking. The boards will be given to the function as a string of periods, O's, and spaces, which represent holes, pegs, and invalid spaces respectively (see examples below). The result should be returned as a list of moves to be made in the form (fromRow, fromCol, toRow, toCol), which indicates which piece to pick up (the from piece) and where it goes (the to piece). Your function must give the answer in a reasonable amount of time, which is defined as 10 seconds.

    Note that this problem is actually pretty difficult to do. This is because there are a lot of possible moves one can make at some stages in the puzzle (whereas in nQueens for example there are always only n possible moves). As such, we would grade on a rolling scale as such (examples of each case below).

    1pt boards with 10 pegs
    1pt boards with 14 pegs
    1pt boards with 16 pegs
    2pts boards with 32 pegs

    Your basic backtracking will eventually get the correct answer for all situations, but it'd probably take many many years to get the solution to the 32 peg board. As such, you will have to be a bit smarter to solve the higher peg boards, and maybe even need more advanced AI techniques to get the 32 peg board.

    Here are some boards to play with.
    board10 = """\ ... .O. ..OO.O. .O...O. ..O.O.. O.O ... """ board14 = """\ ... OO. ..O.OO. OO..OO. .OOO..O .O. ... """ board16 = """\ ... OO. ..OO... ..OO.OO OOO..OO OO. .O. """ board32 = """\ OOO OOO OOOOOOO OOO.OOO OOOOOOO OOO OOO """