- confirmPolicies() [0 pts] [autograded]
The starter file for hw11.py contains a function confirmPolicies.
Follow the directions there, also included here for your convenience:
def confirmPolicies():
# Replace each 42 with True or False according to the course policies.
# If you are unsure, testConfirmPolicies() below contains the answers.
# This is just to be sure you understand those policies!
# We very much encourage you to collaborate, but we also want
# you to do it right. Be sure both of you are working closely together,
# and both of you are contributing and learning the material well.
# Have fun!!!!!
return {
'I can work solo on hw11': 42,
'I can work with one partner on hw11': 42,
("I must list my hw11 partner's name and andrewId at the top" +
"of my hw11.py file that I submit"): 42,
'I can switch hw11 partners and then work with a new partner': 42,
'My hw11 partner must be in 112 this semester': 42,
'My hw11 partner must be in the same lecture or section as me': 42,
"I can look at my hw11 partner's code": 42,
"I can copy some of hw11 partner's code": 42,
"I can help my hw11 partner debug their code": 42,
"I can electronically transfer some of my code to my hw11 partner": 42,
("I can tell my hw11 partner line-by-line, character-by-character " +
"what to type so their code is nearly-identical to mine."): 42,
}
Note: you must get all the policies correct to receive any points
on hw11.
- findLargestFile(path) [10 pts] [autograded]
Without using os.walk, write the recursive function findLargestFile(path), which takes a string path to a folder and returns the full path to the largest file in the folder (and all its subfolders). You can compute the size of a file using os.path.getsize(path). If there are no files, the empty string ("") is returned. You do not need to handle the case where the supplied path is not valid or is not a folder, and you may handle ties however you wish.
Note that file systems can be very large, so in this problem, efficiency is important! Therefore, you may not use listFiles (or anything similar)
to gather all the files into one place, and you should avoid calling os.path.getsize on a single file more than once.
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") == "")
Hints:
- You will almost certainly want to use a wrapper function to make the problem easier to solve. In our sample solution, our recursive function returned not one but two values in a tuple -- the largest file and its size.
- You also may need to get rid of those pesky .DS_Store files that
Macs like to add to folders that you unzip. To do that,
use
removeTempFiles.
Remember to be careful, since it removes without asking and
it does not move the removed files to the trash (they are
really gone).
- runFreddyFractalViewer() [10 pts] [manually graded]
Below the #ignore_rest line, in the class FreddyFractalViewer
(which is already started for you, if just briefly),
write the method teddyFace(self, canvas, xc, yc, r) that draws a circular-shaped face of a teddy bear (named "Freddy"!), without ears. This method 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 reasonably similar to the one in the image below.
Hint: to draw the mouth, you should use the function create_arc(...) of Tkinter with the optional parameters style and extent. For more information about this function read the documentation here.
Also below the #ignore_rest line, in the class FreddyFractalViewer,
and exploiting your previous method teddyFace, write the method fractalTeddy(self, 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 method 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 Teddy with maximum recursion level (depth) of 6.
Also below the #ignore_rest line, in the class FreddyFractalViewer,
add the code required so that it 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 Teddy Bears and not Sierpinsky Triangles).
We have provided you with a simple top-level function
runFreddyFractalViewer that just creates an instance of your FreddyFractalViewer
class. You can modify that function, say to change the window size,
if you prefer.
- evalPrefixNotation(L) [15 pts] [autograded]
Background: in so-called 'prefix notation', an arithmetic expression
is listed with the operator first. So instead of writing '2 + 3'
we would write '+ 2 3'. Actually, for this problem, we'll represent
the expression in a list, so we'd write ['+', 2, 3]. Each value can
itself be another full expression, so for example we could have:
['+', 2, '*', 3, 4]
This would be the same as (2 + (3 * 4)), or 14. Again, we could have:
['+', '*', 2, 3, '*', 4, 5]
This would be the same as ((2 * 3) + (4 * 5)), or 26. Look at the test
function in the code for a few more examples.
With this in mind, write the recursive function evalPrefixNotation(L) that
takes a list L that contains a legal arithmetic expression in
prefix notation, as just described, and returns the value that
the expression evaluates to.
Your function only needs to work for '+', '-', and '*'. If you see
any other operators, raise an exception as such:
raise Exception('Unknown operator: ' + operator)
Hints:
- After removing the first element, if it is an operator,
you should use evalPrefixNotation to recursively evaluate the
operands for that operator.
- This is not a backtracking problem!
Take the time to really think about that hint!
Also, for what it is worth, our sample solution used L.pop(0) to destructively remove the first element. We could then test if it was a string (and so an operator, like '+', or '-', etc) and do one thing, or if it is an int, and do something else.
- solveABC(constraints, aLocation) [40 pts] [autograded]
Note: when solving this problem, you must use appropriate
subclasses of BacktrackingPuzzleSolver and State.
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!
Hints:
- This is a backtracking problem. Study nQueens. This is most like that problem.
- Reminder: when solving this problem, you must use appropriate
subclasses of BacktrackingPuzzleSolver and State.
- We strongly suggest that you add the letters
in alphabetical order, not in the order of the constraints.
This made our sample solution run much faster,
since we could then enforce constraints earlier, specifically
we could check that each letter we placed immediately satisfies the constraint
that it is next to the previous letter alphabetically.
- We found it very helpful to first create what we called
a movesMap -- a dictionary that maps each letter to the
(row, col) positions on the board where it could possibly be placed
based on where that letter is positioned in the initial constraints.
That is,
we set the movesMap to a dictionary mapping each constraint letter to a set of the 5 (row, col) positions in the row, column, or diagonal that are labeled by that constraint letter. So, in the example, we have:
movesMap['B'] == set([(0, 3), (1, 3), (2, 3), (3, 3), (4, 3)])
movesMap['C'] == set([(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)])
- Our sample solution required about 90 lines of code (not counting
the superclasses we copy-pasted into our file, as you should, too). If you are ranging well past that, perhaps you should pause and rethink your approach. Probably in the vicinity of some blue-hoodied TA's!!!
- Don't store the board as a 2d list! Only construct the board at the end, after you have solved the puzzle.
- To construct the board, we added a method getBoard to our state subclass and called that in solveABC.
- We suggest that the state be a dictionary or a list that maps each letter to its (row, col) position, similar to how we solved nQueens using queenPositions.
- Bonus/Optional: flatten(L) [1.5 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)
- Bonus/Optional: Rectangula [3.5 pts]
In the game Rectangula, the goal of the player is to place numbers in boxes in order to fill the grid with rectangles. Watch here for a demonstration:
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.
Note 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.
To test your function, download and use the file hw11_rectangula_tester.py. You should place that code in the same folder as your hw11.py file. Do not include any code from the tester file in your hw11.py file! Instead, include these lines in your hw11.py file, below the #ignore_rest line:
###############################################
# ignore_rest
###############################################
# Place these imports in hw11.py below the ignore_rest line!
from hw11_rectangula_tester import testSolveRectangula
from hw11_rectangula_tester import playRectangula
def testRectangula():
testSolveRectangula(solveRectangula)
playRectangula(solveRectangula)
# Then, call testRectangula from your testAll function.
Then, when you run your hw11.py file, you'll run the testSolveRectangula function and the playRectangula function in rectangula-tester.py. Have fun!