- 5 Reasoning About (Recursive) Code problems
In just a few words of plain English (in your hw5.txt file), 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. For example:
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.
def f(n):
# assume n is a non-negative integer
if (n < 10):
return 1
else:
return 1 + f(n//10)
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]
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:])
def f(n):
# assume n is a non-negative integer
if (n == 0):
return 1
else:
return 2*f(n-1)
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.
- flatten(L)
Write the recursive function flatten(L), which takes a list which may contain lists
(which themselves may contain lists, and so on), and returns a single list (which does not contain any other lists) which contains each of the non-lists, in order, from the original list. This is called flattening the list. For example:
flatten([1,[2]]) returns [1,2]
flatten([1,2,[3,[4,5],6],7]) returns [1,2,3,4,5,6,7]
flatten(['wow', [2,[[]]], [True]]) returns ['wow', 2, True]
flatten([]) returns []
flatten([[]]) returns []
flatten(3) returns 3 (not a list)
- countFiles(path)
write the recursive function countFiles(path), which takes a string specifying a path to a folder and returns the total number of files in that folder (and all its subfolders). Do not count folders (or subfolders) as files. Do not worry if the supplied path is not valid or is not a folder.
To help test your code, here are some assertions for use with sampleFiles:
assert(countFiles("sampleFiles/folderB/folderF/folderG") == 0)
assert(countFiles("sampleFiles/folderB/folderF") == 0)
assert(countFiles("sampleFiles/folderB") == 2)
assert(countFiles("sampleFiles/folderA/folderC") == 4)
assert(countFiles("sampleFiles/folderA") == 6)
assert(countFiles("sampleFiles") == 10)
Note: regarding efficiency, it is overtly inefficient to create a list of any kind in your solution to this problem. In particular, you may not do this:
def countFiles(path):
return len(listFiles(path))
- permutations
In the file hw5.py, 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.
,br>
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.
- findLargestFile(path)
Without using os.walk, write the recursive function findLargestFile(path), which takes a string path to a folder, returning the full path to the largest file in the folder (and all its subfolders). If there are no files, the empty string ("") is returned. Do not worry if the supplied path is not valid or is not a folder.
Hint: to solve this, you may need the function os.path.getsize(path), which returns the size of the given file.
Another hint: if it is more convenient, findLargestFile can be non-recursive so long as it calls a recursive helper function.
To help test your code, here are some assertions for use with sampleFiles
(available in
sampleFiles.zip):
assert(findLargestFile("sampleFiles/folderA") ==
"sampleFiles/folderA/folderC/giftwrap.txt")
assert(findLargestFile("sampleFiles/folderB") ==
"sampleFiles/folderB/folderH/driving.txt")
assert(findLargestFile("sampleFiles/folderB/folderF") == "")
Note: regarding efficiency, it is overtly inefficient to call os.path.getsize(path) more than once for any given file. One way to manage this is to use a helper function that not only returns the largest file for a given path, but returns it in a tuple along with other information that may be of use (hint, hint). Then findLargestFile is a non-recursive wrapper function that calls that helper function.
Also note: also regarding efficiency, it is overtly inefficient to create a
list of files, say using listFiles. So you may not use listFiles
here. Instead, you must compute the largestFile
as you go, though perhaps returning it in a tuple to a wrapper function,
as the previous note suggests.
Finally: you may resolve ties as you wish.
- runMickeyFractalViewer()
Below the #ignore_rest line, write a function mickeyFace(canvas, xc, yc, r) that draws a circular-shaped face of a Mickey-like character, without ears. This function takes as input a canvas to draw on, the (xc, yc) coordinates of the center of the face, and the radius r of the face. While you need not be pixel-perfect, try to make the face as close as possible to the one in the image below. Hint: to draw the mouth, you should use the function create_arc(...) of Tkinter. For more information about this function see
http://infohost.nmt.edu/tcc/help/pubs/tkinter/canvas.html.
Also below the #ignore_rest line, and exploiting your previous function mickeyFace, write a function fractalMickeyMouse(canvas, xc, yc, r, level) that recursively draws a character with the face you previously defined, and a recursively downsized version of that same face as ears. Your function will take as parameter a canvas to draw on, the (xc, yc) coordinates of the center of the face, the radius r of the face, and an integer level representing the maximum depth of recursion. The radius of each ear is exactly half the radius of the face. The following figure shows an example of a Fractal Mickey Mouse with maximum recursion level (depth) of 6.
Also below the #ignore_rest line, write the function runMickeyFractalViewer()
that behaves similarly to the Sierpinsky Triangle example in the course notes, where pressing arrows changes the depth of the recursion (though of course here you'll display recursive Mickey Mouses and not Sierpinsky Triangles).
- fractalFlower
First, write the function simpleFlower that takes an integer number representing the size of the flower (and whatever else you need to do turtle graphics -- see
the Koch Snowflake example for details).
Your function will draw the following figure:
The position and orientation of the flower will depend on the initial position and orientation of the turtle. The origin of the flower is the bottom part of the stem, and its length develops straight ahead on the current direction of the turtle. When your function terminates, the turtle should be back to the same position and the same orientation it started.
Next, write the function fractalFlower that takes an integer representing the size of the flower, and an integer representing the maximum level (depth) of recursion, and again whatever else you need to do turtle graphics. Your function will paint a recursive fractal flower with the same basic shape outlined above, but with each petal recursively replaced by a scaled down version of the flower itself. For example, a fractal flower with a maximum recursion level of 4 will result in a picture like this one:
Your program should include some test code that draws three flowers, all of them facing up, on three different positions of the screen: (a) a simple flower of size 200; (b) a fractal flower of depth 3 and size 250; and (c) a fractal flower of depth 4 and size 300. Your three test flowers should not overlap.
- fractalSun
Using Python's Tkinter library, you will paint a majestic fractal sun. The fractal sun is composed of a circle of radius r, and 8 rays of length 2*r originating from the center of the circle and radially equally spaced. The external tip of each ray is also the origin of a recursively downsized fractal sun with radius equal to 1/4 of the radius of the sun at the previous level. Also, the suns originating at the tip of the rays will have different colors, i.e., the color of a sun is a function of the recursion level of the fractal sun itself. You can invent the coloring function you prefer, just make sure that your sun will look good no matter what the maximum level of recursion is going to be. Your fractal sun will be generated by a function fractalSun(canvas, xc, yc, r, level) which you will write. Your function will take as parameter a canvas to draw on, the (xc, yc) coordinates of the center of the sun, the radius r of the sun's circle, and an integer level representing the maximum depth of recursion of your fractal sun.
The following picture shows a fractal sun with a maximum recursion depth of 5, with colors fading from yellow to red.
Your program should include some test code that draws a fractal sun of depth 5 on a canvas of your choice.
- vicsekFractals
Write the function vicsekFractals() that runs an animation that draws Vicsek fractals that fill a 400x400 window, where a Vicsek fractal is like so (where the depth is determined each time the user presses a digit key):
- pythagoreanTree
First, read about the Pythagoras Tree
here.
With this in mind, write the function bonusPythagorasTree() that works like hFractal() only here it makes a Pythagoras Tree. For half-credit, just make the balanced one in the first row of the image. For full-credit, oscillate between sloped trees, as in the second image, but varying the angles back and forth over time so that there is a waving effect, as though blowing in the wind (well, with enough imagination).
- 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.
- getCourse(courseCatalog, courseNumber)
Background: for this problem, we will use a so-called courseCatalog, which for this problem is a recursively-defined list-of-lists like so (this being just an example, your solution must work for any similarly-defined courseCatalog):
courseCatalog = ["CMU",
["CIT",
[ "ECE", "18-100", "18-202", "18-213" ],
[ "BME", "42-101", "42-201" ],
],
["SCS",
[ "CS",
["Intro", "15-110", "15-112" ],
"15-122", "15-150", "15-213"
],
],
"99-307", "99-308"
]
Each level is defined by a list, and the first element of the list is the name of that level ("CMU", "CIT", "ECE", etc). The rest of the elements of a list contain either strings, which are course names offered at that level, or lists, which contain a sub-level. So we see that "99-307" is offered by "CMU", and "15-122" is offered by "CS". Also, the fully-qualified name of a course includes the dot-separated names of all the levels that contain it, in top-down order. Thus, the fully-qualified name of "15-112" is "CMU.SCS.CS.Intro.15-112", and the fully-qualified name of "99-307" is just "CMU.99-307". Finally, you may assume that a course name may not occur more than once in a course catalog.
With this in mind, write the function getCourse(courseCatalog, courseNumber) that takes a courseCatalog, as defined above, and a courseNumber (as a string, such as "18-100" or "15-112"), and returns the fully-qualified name of the given course, or None if it is not in the catalog. For example, given the courseCatalog above, here are some test cases:
assert(getCourse(courseCatalog, "18-100") == "CMU.CIT.ECE.18-100")
assert(getCourse(courseCatalog, "15-112") == "CMU.SCS.CS.Intro.15-112")
assert(getCourse(courseCatalog, "15-213") == "CMU.SCS.CS.15-213")
assert(getCourse(courseCatalog, "99-307") == "CMU.99-307")
assert(getCourse(courseCatalog, "15-251") == None)
- solveRectangula(board)
Background: first, watch this short video on how to play
the game of Rectangula:
Now, your task is to write the function solveRectangula(board).
This function takes a board which is a 2d list of integers
corresponding to the board you see in the video, where blank
cells contain 0's. Your function should return a solution
to that board, which consists of a list of rectangles (in any
order) such that:
- Every rectangle in your solution is on the board.
- No two rectangles in your solution overlap.
- Every non-zero number on the board is inside exactly one rectangle in your solution, and the area of that rectangle matches the number.
- And every rectangle in your solution contains exactly one number on the board.
One oddity is that your rectangles must be of the form (row0, col0, width, height), where (row0, col0) marks the top-left of the
rectangle (remember, rows increase vertically, cols increase horizontally), and
width is the total number of columns, and height is the total number
of rows (so width*height is the area of the rectangle).
If there is no possible solution, your function should return None.
We have provided a lot of code for you. This code is in the file
lab11_rectangula_tester.py.
###############################################
# ignore_rest
###############################################
# Place these imports in lab11.py below the ignore_rest line!
from lab11_rectangula_tester import testSolveRectangula
from lab11_rectangula_tester import playRectangula
testSolveRectangula(solveRectangula)
playRectangula(solveRectangula)
Then, when you run your lab11.py file, you'll run the testSolveRectangula function and the playRectangula function
in rectangula-tester.py.
Remember: Do not include any code from rectangula-tester.py in your lab11.py file!
Now, how should you solve a Rectangula puzzle? You may do this any way you wish, so long as you use backtracking meaningfully. That said, here are some hints about how we did this in our sample solution:
Have fun!!!
- findRTP(digits)
Background: A number n is a right-truncatable prime, or RTP, if every prefix of n (including n itself) are all prime. So, 593 is an RTP because 5, 59, and 593 are all prime. With this in mind, write the function findRTP(digits) that takes a positive int, digits, and returns the smallest RTP with that many digits, or None if no such number exists. To do this, you must use backtracking even if you could do it
in some other way. At each step, try to add one more digit to the right of the number. Also, make sure you are only creating RTP's as you go. Note: even though findRTP(8) returns 23399339, it runs almost instantly because backtracking rules out most numbers without trying them, so it actually calls isPrime very few times.
Hint: you may need to use callWithLargeStack so your isPrime does not stack
overflow.
- solveSudoku(board)
Write the function solveSudoku(board) that takes a partially-completed Sudoku board (a 2d list with 0's representing empty cells), and returns a solved version of the same puzzle, or None if no such solution exists. Note: you must use backtracking here. Also, it will take way too long if you are not clever about the order in which you make your guesses. For that, always find the cell that is the most constrained, that is, the one that has the fewest possible legal choices (resolving ties arbitrarily).
- 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
"""
- Gate class and subclasses
Write the classes required to make the following test function work properly.
import types
def getLocalMethods(clss):
# This is a helper function for the test function below.
# It returns a sorted list of the names of the methods
# defined in a class.
result = [ ]
for var in clss.__dict__:
val = clss.__dict__[var]
if (isinstance(val, types.FunctionType)):
result.append(var)
return sorted(result)
def testGateClasses():
print("Testing Gate Classes... ", end="")
# require methods be written in appropriate classes
assert(getLocalMethods(Gate) == ['__init__', '__str__',
'numberOfInputs', 'setInput'])
assert(getLocalMethods(AndGate) == ['getOutput'])
assert(getLocalMethods(OrGate) == ['getOutput'])
assert(getLocalMethods(NotGate) == ['getOutput', 'numberOfInputs'])
# make a simple And gate
and1 = AndGate()
assert(type(and1) == AndGate)
assert(isinstance(and1, Gate) == True)
assert(and1.numberOfInputs() == 2)
and1.setInput(0, True)
and1.setInput(1, False)
# Hint: to get the name of the class given an object obj,
# you can do this: type(obj).__name__
# You might do this in the Gate.__str__ method...
assert(str(and1) == "And(True,False)")
assert(and1.getOutput() == False)
and1.setInput(1, True) # now both inputs are True
assert(and1.getOutput() == True)
assert(str(and1) == "And(True,True)")
# make a simple Or gate
or1 = OrGate()
assert(type(or1) == OrGate)
assert(isinstance(or1, Gate) == True)
assert(or1.numberOfInputs() == 2)
or1.setInput(0, False)
or1.setInput(1, False)
assert(or1.getOutput() == False)
assert(str(or1) == "Or(False,False)")
or1.setInput(1, True)
assert(or1.getOutput() == True)
assert(str(or1) == "Or(False,True)")
# make a simple Not gate
not1 = NotGate()
assert(type(not1) == NotGate)
assert(isinstance(not1, Gate) == True)
assert(not1.numberOfInputs() == 1)
not1.setInput(0, False)
assert(not1.getOutput() == True)
assert(str(not1) == "Not(False)")
not1.setInput(0, True)
assert(not1.getOutput() == False)
assert(str(not1) == "Not(True)")
print("Passed!")
testGateClasses()