Homework 10
Due Monday 01Apr, at 8pm
 Reminder: all problems that are not explicitly marked COLLABORATIVE must be completed individually, as stated in the course syllabus.
 To start:
 Create and go to a folder named ‘week10’
 Create a file named hw10.py. There is no starter file this week.
 Edit hw10.py using Pyzo.
 When you’re done, submit hw10.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
 Important Note: the autograder we use breaks when it tries to import tkinter. Therefore, all of your tkinter code (for fractalSunViewer() ) must be included after a comment that reads #ignore_rest. The autograder will only grade code that appears before #ignore_rest. This means that your solutions to all autograded problems must appear before #ignore_rest!
 Do not hardcode the testcases into your solutions.
 Don’t forget to write test cases! They should follow the model of testcases for previous homeworks. If you don’t have proper testcases, you’ll lose style points.
 Note: you are not required to generate additional test cases for fractalSunViewer() but you should write test cases for each other problem.

Mentor Meeting [0 pts]
This week during your mentor meeting you should further refine term project ideas with your mentor. As always, failure to meet with your mentor will result in 5 on this assignment. 
Collaborative: getCourse(courseCatalog, courseNumber) [15 pts]
Background: for this problem, we will use a socalled courseCatalog, which for this problem is a recursivelydefined listoflists like so (this being just an example, your solution must work for any similarlydefined courseCatalog):courseCatalog = ["CMU", ["CIT", [ "ECE", "18100", "18202", "18213" ], [ "BME", "42101", "42201" ], ], ["SCS", [ "CS", ["Intro", "15110", "15112" ], "15122", "15150", "15213" ], ], "99307", "99308" ]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 sublevel. So we see that "99307" is offered by "CMU", and "15122" is offered by "CS". Also, the fullyqualified name of a course includes the dotseparated names of all the levels that contain it, in topdown order. Thus, the fullyqualified name of "15112" is "CMU.SCS.CS.Intro.15112", and the fullyqualified name of "99307" is just "CMU.99307". 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 "18100" or "15112"), and returns the fullyqualified 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, "18100") == "CMU.CIT.ECE.18100") assert(getCourse(courseCatalog, "15112") == "CMU.SCS.CS.Intro.15112") assert(getCourse(courseCatalog, "15213") == "CMU.SCS.CS.15213") assert(getCourse(courseCatalog, "99307") == "CMU.99307") assert(getCourse(courseCatalog, "15251") == None) 
Collaborative: distList(n) [20 pts]
Write a recursive backtracking function, distList(n), that, given a number n, returns a list of size 2n that contains all the numbers from 1 to n twice such that if x is in the list then the two xs are separated by exactly x other numbers. If such a list cannot be generated, return None.
Consider the following examples:
distList(3) returns [3, 1, 2, 1, 3, 2] distList(2) returns None distList(4) returns [4, 1, 3, 1, 2, 4, 3, 2]
Notes/Hints: To receive credit, you must use backtracking to solve the problem, even if another approach would work.
 If you don't understand the problem, look at the examples again. Notice that the 3s always have three other numbers between them, the 2s always have two other numbers between them, etc.
 While there are multiple valid approaches to the problem, consider starting with a list of size 2n and fill it in as you go.

Collaborative: runFractalSunViewer() [25 pts] [manually graded]
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.
All your code for this problem should be written below the #ignore_rest line. 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.
Also below the #ignore_rest line, write the function runFractalSunViewer() 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 your sun and not Sierpinsky Triangles). The initial depth of recursion for your suns should be 5.
The following picture shows a fractal sun with a maximum recursion depth of 5, with colors fading from yellow to red.
All problems below here are SOLO.

flatten(lst) [15 pts]
Write the recursive, nondestructive, function flatten(lst), 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 nonlists, 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)

solveSudoku(board) [25 pts]
Write the function solveSudoku(board) that takes a partiallycompleted 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 will want to make use of the code you wrote in HW5. 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 will be testing on boards you haven't seen before.
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!')
...and here's a board with lots of empty spaces and no solution! You may want to use this or a similar board to test the efficiency of your code. Autolab doesn't always give good feedback if your code times out. For reference, our code takes about 15 seconds to return None on this board.def testSolveSudoku2(): print('Testing solveSudoku()...', end='') board = [ [ 0, 0, 2, 0, 0, 0, 1, 0, 9 ], [ 0, 0, 0, 3, 0, 0, 2, 8, 0 ], [ 0, 0, 0, 0, 5, 0, 3, 0, 0 ], [ 0, 0, 0, 0, 0, 6, 4, 0, 0 ], [ 8, 7, 6, 5, 4, 3, 0, 2, 1 ], [ 0, 0, 0, 0, 0, 0, 6, 7, 0 ], [ 0, 0, 3, 0, 0, 0, 7, 0, 4 ], [ 0, 2, 0, 0, 1, 0, 8, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 9, 0, 0 ] ] solved = solveSudoku(board) solution = None 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 nonrecursive solution!
 This is a backtracking problem. Study the backtracking template and backtracking examples; they will help.
 Make sure to return None as soon as you determine that a step has no solutions! Otherwise, the code might take a very long time to run.