Extra Practice for Week 9 (Due never)

Free Response - Recursive Applications

  1. Recursively solve earlier problems
    Starting from week 2 (loops), revisit extra-practice problems, hw's, collabs, quizzes, and midterms, and redo those problems only using recursion and not using for or while loops. You have a huge sea of practice problems to draw from!

  2. 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))

  3. 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.

  4. 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.

  5. 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):


  6. 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).


  7. 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.

  8. 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  
"""