- flatten(L) [25 pts] [autograded]
Write the recursive, non-destructive, 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)
- @noError decorator [15 pts] [autograded]
Write the @noError function decorator so that the following test function
works properly:
def testNoErrorDecorator():
print("Testing @noError decorator...", end="")
@noError
def f(x, y): return x/y
assert(f(1, 5) == 1/5)
assert(f(1, 0) == None)
@noError
def g(): return 1/0
assert(g() == None)
@noError
def h(n):
if (n == 0): return 1
else: return h(n+1)
assert(h(0) == 1)
assert(h(-1) == 1)
assert(h(1) == None)
print("Passed!")
You may notice that a function decorated with @noError behaves
the same, except if the original function would crash (technically, raise an
exception), the decorated function instead just returns None.
Be sure not to hardcode the number of parameters, so that
your decorator works for a function no matter how many parameters it takes.
- hFractal() [25 pts] [manually graded]
Background: First, read about the H-Fractal
here.
Also, be sure to study the Sierpinksy Triangle example from the notes, particularly how it allows the user to use the arrow keys to move up and down to different recursive levels of the fractal.
With this in mind, below the #ignore_rest line, write the function hFractal() that takes no parameters and uses our animation framework (so calls the run() function) to implement an "H-Fractal viewer", that starts by viewing a "level 0 H-Fractal", and allows the user to use the arrow keys to move up and down to view different recursive levels of the H-Fractal.
Consider the following image showing the transition between levels 1, 2, and 3:
Hint: The H that is drawn right in the middle should always have the same size (the width and height should be half the window width and height). At each level, we draw new H's with half the dimensions of the previous level. This is why the window size never has to change (since 1 + 1/2 + 1/4 + 1/8 + ... = 2).
- solveABC(constraints, aLocation) [35 pts] [autograded]
This problem is inspired by the "ABC Path" problems at BrainBashers.com. For more (optional) info,
check this out.
Background: In what we will call an "ABC Puzzle", you are given a 5x5 board like this:
It is an empty board except that it contains a single "A" in an arbitrary cell. Also, the letters from "B" to "Y" are arranged around the outside of the board in an arbitrary order, along with arrows that constrain those letters to a certain row, column, or diagonal. For example, in the image, we see the "H" and "T" are constrained to column 0, "L" and "I" are constrained to row 0, and "C" and "G" are constrained to the column running from (0,0) to (4,4). The goal of this puzzle is to place every letter from "B" to "Y" on the board such that: (1) each letter from "B" to "Y" is placed in the row, column, or diagonal in which it is constrained; and (2) each letter from "B" to "Y" is placed adjacent (including diagonally) to the previous letter (so "B" is adjacent to "A", and "C" is adjacent to "B", and so on).
A solution to the puzzle is here:
Be sure you understand why this solves the puzzle! If you are unsure, go to the link at BrainBashers.com and read more about this kind of puzzle, including
this help page, and maybe try to solve a few more of them (the puzzles include a button you can press to get the solutions!).
Now, for us to represent one of these puzzles in Python, we have to represent the constraints. We'll do that by reading them clockwise starting from the top-left corner. Thus, in the given example, the constraints are:
constraints = "CHJXBOVLFNURGPEKWTSQDYMI"
And we also need to specify the position of the "A", which we will do as a (row,col) tuple, as such:
aLocation = (0,4)
With this in mind, write the function solveABC(constraints, aLocation), that takes constraints and the location of the "A", which together define an ABC Puzzle, and returns a completed board which solves the puzzle, or None if no such board exists. Here is a test function that is based on the puzzle used in the example above (notice how the constraints and aLocation match the unsolved puzzle, and the resulting board matches the solved puzzle):
def testSolveABC():
print('Testing solveABC()...', end='')
constraints = "CHJXBOVLFNURGPEKWTSQDYMI"
aLocation = (0,4)
board = solveABC(constraints, aLocation)
solution = [['I', 'J', 'K', 'L', 'A'],
['H', 'G', 'F', 'B', 'M'],
['T', 'Y', 'C', 'E', 'N'],
['U', 'S', 'X', 'D', 'O'],
['V', 'W', 'R', 'Q', 'P']
]
assert(board == solution)
print('Passed!')
Note: To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
Hint #1: This is a backtracking problem. Study nQueens. This is most like that problem.
Hint #2: Our sample solutions require 50-100 lines of code. If you are ranging well past that, perhaps you should pause and rethink your approach. Probably in the vicinity of some blue hoodies!