Lab 17: Recursion Reloaded¶
Systems of One-Way Roads¶
In Section 15 of the Math 290 textbook it is shown that any finite set of cities with a system of one-way roads connecting them has a valid path (re-read that section if you don’t remember what these terms mean). We will write a program that finds a valid path through any such system of roads.
First, we need to generate systems of roads.
A system of one-way roads through n cities can be represented as a list of n city names together with an n x n matrix A, where
For example, the system of roads through five cities pictured on p. 108 of the Math 290 textbook would be represented by the list L = ['A', 'B', 'C', 'D', 'E'] together with the matrix
Notice that M is antisymmetric, meaning that transpose(M) = -M.
Task 1¶
Write a function random_system(n) that takes as input a positive integer n and returns a random system of one-way roads through n cities as an n x n matrix as described above.
If you need help generating random integers, read about the function randint online. You will need to import random:
>>> from random import randint
To find a valid path through n cities: let X be the first city in the list L.
For each other city Y say that Y is a red city if there is a road from X to Y (i.e. A[X,Y]=1) and say that Y is a blue city if there is a road from Y to X (i.e. A[X,Y]=-1).
Then form two smaller systems of one way roads, one comprising the red cities, and the other comprising the blue cities (where the order of the labels is preserved).
For example, for the matrix M above, we have X=A and
Now we (recursively) find a valid path through the red cities and a valid path through the blue cities and combine them to make the path
Task 2¶
Write a function valid_path(M,L) that takes as input an n x n matrix M and a list L of length n, and returns a valid path through the cities as a list of length n. The list L contains the names of the cities.
For example, the function should return [B, E, D, A, C] as the path for the example above.
If you want to make a copy of a list of lists, such as the matrix M, it is (unfortunately) not as simple as calling M.copy().
The copy package helps with this:
>>> import copy
>>> Mc = copy.deepcopy(M)
As an extra (ungraded) challenge, write a function that computes all valid paths for the given input.
A problem with recursion¶
Pull up your Fibonacci function fib(n) from Lab 12: Recursion and see how long it takes to compute the 40-th Fibonacci number.
To do this, first run the following code:
>>> from timeit import default_timer as timer
Then you can measure how long it takes (in seconds) to compute fib(40) by running:
start = timer()
fib(40)
end = timer()
print(end-start)
The thing you should learn from this is: recursion makes for beautiful code but often expensive results.
The reason it takes so long to compute fib(40) is that all of the earlier Fibonacci numbers are computed several times in order to compute the 40-th. To test this out, add the following print command in the base case of your fib function:
if n==1 or n==2:
print("I'm calling the base case")
return 1
Unsurprisingly, this prints “I’m calling the base case” every time the base case is called.
Now run fib(10) and watch the flood of output.
In theory, computing the 10 -th Fibonacci number “by hand” should only call the base case once or twice.
Task 3: Fast Fibonacci¶
In order to speed up our Fibonacci function, we’ll use a programming technique called “memoization”.
(The name is awkward, but the technique is great.)
The idea is that to compute fib(41) we shouldn’t have to do much work, because we already computed fib(40) and, while computing fib(40), we computed fib(39).
So it would be nice if Python would just remember that for us.
Luckily, there’s a built-in Python tool just for that:
import functools
@functools.lru_cache(maxsize=256)
def fib(n):
blah blah blah
The line starting with @ needs to come immediately before your function definition. Replace blah blah blah by the code you already wrote for the fib function. Now see how fast your function computes fib(40). And just for fun, see how fast it computes fib(200). It should compute this in less than one second; don’t submit your code to CodeBuddy until you have memoization working properly.
Task 4: Towers of Hanoi¶
There is a legend about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it. At the beginning of time, the leftmost post was surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time, in an effort to move the disks to the rightmost post. The rules are:
Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty post.
No larger disk may be placed on top of a smaller disk.
When the last move of the puzzle is completed, the world will end. Your task is to determine how soon the world will end, given that the priests can move one disk per second.
Start by playing the https://www.webgamesonline.com/towers-of-hanoi/index.php. Play with 3 disks first until you have a solution that takes the minimal number of moves (in this case, 7 moves). Then move on to 4 disks until you have a solution that takes 15 moves. Keep playing with more disks until you see the pattern. Don’t read on until you’re done with this step.
Let’s call the leftmost and rightmost posts the “source” and “target,” respectively. We’ll call the middle post “aux.” How do we solve the puzzle when there are two disks?
move the top disk source --> aux
move the next disk source --> target
move the top disk aux --> target
When there are three disks?
move the top [two disks] source --> aux (use the solution for two disks)
move the third disk source --> target
move the top [two disks] aux --> target (use the solution for two disks)
Write a function hanoi(n, source, aux, target) that takes in an integer n and the names of the source, aux, and target posts as strings.
Do not implement memoization for this function.
Your function should move the top n disks from source to target, using aux for help.
At each move, print “move from post _ to post _”, like this:
>>> hanoi(3,'A','B','C')
'move from post A to post C'
'move from post A to post B'
'move from post C to post B'
'move from post A to post C'
'move from post B to post A'
'move from post B to post C'
'move from post A to post C'
For how many years will the priests be moving disks? Remember that there are 64 disks and the priests can move one disk per second.
Hint: don’t run hanoi(64,...) – instead try to find the pattern. Can you prove by induction that your pattern is correct?