CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 10 (Due Thursday 2-Nov, at 10pm)
- This lab is Collaborative. No solo work allowed!. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details. Be sure to list your collaboration partners (name and andrew id) in a comment on the first line of your submitted file.
- Even though this is collaborative, you may not directly copy any code from anyone, and you may not electronically share your code with anyone.
- Be a good lab partner! Help everyone in your lab group, and accept their help if you need it. Don't be in a hurry to finish the problems. Instead, take your time and be sure that everyone in the lab group is following and understanding. The goal is to learn, not just to finish.
- No starter code this week!
- You should make use of this week's linter: cs112_f17_week10_linter.py
- This week you may use up to 5 submissions. Only your last submission counts.
- Do not hardcode the test cases in your solutions.
- As usual, there are no late days for this lab.
- Do not use os.walk()
- Group Form [5 pts]:
Fill out one form found here. This is due Thursday by 11:59pm. Even if you work on the lab alone (which you shouldn't do), you should still fill out the form, and simply enter your name without any partner scores.
If you need a new group, fill out this form to be assigned to one. - findLargestFile(path) [25 pts] [autograded]
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. - runTeddyFractalViewer() [30 pts] [manually graded]
Below the #ignore_rest line, write a function teddyFace(canvas, xc, yc, r) that draws a circular-shaped face of a teddy bear, 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 teddyFace, write a function fractalTeddy(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 Teddy with maximum recursion level (depth) of 6.
Also below the #ignore_rest line, write the function runTeddyFractalViewer() 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 Teddy Bears and not Sierpinsky Triangles). - solveSudoku(board) [40 pts] [autograded]
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. You may want to make use of the code you wrote in lab5. If you never completed that code, you should meet with a TA as soon as possible to help you get that code working.
Here is a very simple testing function to help get you started. You will need to test more than this. We certainly will...def testSolveSudoku(): print('Testing solveSudoku()...', end='') board = [ [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ], [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ], [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ], [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ], [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ], [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ], [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ], [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ], [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ] ] solved = solveSudoku(board) solution = [ [5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9] ] assert(solved == solution) print('Passed!')Notes/Hints:- To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
- This is a backtracking problem. Study nQueens. This is most like that problem.