CMU 15-112 Summer 2019: Fundamentals of Programming and Computer Science
Homework 4-2 (Due Thu 25-Jul, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. There is no starter file for this assignment! You should create a file, hw4-2.py, to start.
  2. Edit hw4-2.py using Pyzo
  3. When you are ready, submit hw4-2.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
• Do not use sets or dictionaries in this assignment.
• Make sure to put all animation code, including the import to tkinter, underneath the "#ignore_rest" line
• Do not hardcode the test cases in your solutions.
• Remember to write your own test cases, and in general, follow the style guide!

1. flatten(lst) [15 pts] [autograded]
   Write the recursive and non-destructive 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 non-lists, in order, from the original list. This is called flattening the list. For example:

   assert(flatten([1,[2]]) == [1,2])
   assert(flatten([1,2,[3,[4,5],6],7]) == [1,2,3,4,5,6,7])
   assert(flatten(['wow', [2,[[]]], [True]]) == ['wow', 2, True])
   assert(flatten([]) == [])
   assert(flatten([[]]) == [])
   



2. getCourse(courseCatalog, courseNumber) [20 pts] [autograded]
   Background: for this problem, we will use a so-called courseCatalog, which for this problem is a recursively-defined list-of-lists like so (this being just an example, your solution must work for any similarly-defined courseCatalog):
   courseCatalog = ["CMU", ["CIT", [ "ECE", "18-100", "18-202", "18-213" ], [ "BME", "42-101", "42-201" ], ], ["SCS", [ "CS", ["Intro", "15-110", "15-112" ], "15-122", "15-150", "15-213" ], ], "99-307", "99-308" ]
   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 sub-level. So we see that "99-307" is offered by "CMU", and "15-122" is offered by "CS". Also, the fully-qualified name of a course includes the dot-separated names of all the levels that contain it, in top-down order. Thus, the fully-qualified name of "15-112" is "CMU.SCS.CS.Intro.15-112", and the fully-qualified name of "99-307" is just "CMU.99-307". 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 "18-100" or "15-112"), and returns the fully-qualified 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, "18-100") == "CMU.CIT.ECE.18-100") assert(getCourse(courseCatalog, "15-112") == "CMU.SCS.CS.Intro.15-112") assert(getCourse(courseCatalog, "15-213") == "CMU.SCS.CS.15-213") assert(getCourse(courseCatalog, "99-307") == "CMU.99-307") assert(getCourse(courseCatalog, "15-251") == None)


3. solveSudoku(board) [25 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 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 non-recursive 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.



4. Asteroids [40 pts] [manually graded]
   
   
   Using our animation framework and assuming that run() is already written, write init(data), mousePressed(event, data), keyPressed(event, data), and redrawAll(data) for an animation with the following elements:
   • Rocket:
   • Below is an implementation of the Rocket class. You should read this code carefully, since you will need to call the methods from your animation!
   • The rocket is already drawn for you, but it cannot move. When the user presses the right arrow key, the rotate should rotate clockwise. When the user presses the left arrow key, the rocket should rotate counter-clockwise. It can rotate however much you like.
   • When the user presses the space bar, the rocket should create a bullet.
   • Are there methods in the Rocket class that will help with this?
   • Rocket Class
     # Helper function for drawing the Rocket def drawTriangle(canvas, cx, cy, angle, size, fill="black"): angleChange = 2*math.pi/3 p1x, p1y = (cx + size*math.cos(angle), cy - size*math.sin(angle)) p2x, p2y = (cx + size*math.cos(angle + angleChange), cy - size*math.sin(angle + angleChange)) p3x, p3y = (cx, cy) p4x, p4y = (cx + size*math.cos(angle + 2*angleChange), cy - size*math.sin(angle + 2*angleChange)) canvas.create_polygon((p1x, p1y), (p2x, p2y), (p3x, p3y), (p4x, p4y), fill=fill) # Read this class carefully! You'll need to call the methods! class Rocket(object): def __init__(self, cx, cy): self.cx = cx self.cy = cy self.angle = 90 def rotate(self, numDegrees): self.angle += numDegrees def makeBullet(self): offset = 10 dx, dy = (offset*math.cos(math.radians(self.angle)), offset*math.sin(math.radians(self.angle))) speedLow, speedHigh = 20, 40 return Bullet(self.cx+dx, self.cy-dy, self.angle,random.randint(speedLow, speedHigh)) def draw(self, canvas): size = 30 drawTriangle(canvas, self.cx, self.cy, math.radians(self.angle), size, fill="green2")
   • Bullets:
   • Below is an implementation of the Bullet class. You should read this code carefully, since you will need to call the methods from your animation!
   • You should store and draw the bullets.
   • Every timerFired, the bullets move in the appropriate direction. Hint: There is a method written in the bullet class that handles this.
   • Bullet Class
     # Read this class carefully! You'll need to call the methods! class Bullet(object): def __init__(self, cx, cy, angle, speed=20): self.cx = cx self.cy = cy self.r = 5 self.angle = angle self.speed = speed def moveBullet(self): dx = math.cos(math.radians(self.angle))*self.speed dy = math.sin(math.radians(self.angle))*self.speed self.cx, self.cy = self.cx + dx, self.cy - dy def isCollisionWithAsteroid(self, other): # in this case, other must be an asteroid if(not isinstance(other, Asteroid)): return False else: return (math.sqrt((other.cx - self.cx)**2 + (other.cy - self.cy)**2) < self.r + other.r) def draw(self, canvas): cx, cy, r = self.cx, self.cy, self.r canvas.create_oval(cx - r, cy - r, cx + r, cy + r, fill="white", outline=None) def onTimerFired(self, data): self.moveBullet()
   
   
   
   At this point, you should have a Rocket that can rotate and shoot Bullets. Now we can start incorporating the Asteroids into the animation!
   • Asteroids:
   • You should not be writing a lot of new code here. Instead, use the methods you wrote in hw4-1.
   • Every 2 seconds, an asteroid is created with a random cx and cy on the canvas, a random radius between 20 and 40 pixels, a random speed between 5 and 20 pixels per timerFired call, and a random direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]. Hint: Use random.choice here.
   • The asteroid is chosen randomly from the three types: Asteroid, ShrinkingAsteroid, and Splitting Asteroid. Hint: Use random.choice here.
   • Asteroids are purple, ShrinkingAsteroids are pink, and SplittingAsteroids are blue.
   • You should be able to store and draw the asteroids. Hint: Where could you put a draw method?
   • Movement:
   • Asteroids wrap around when they get to an edge of the canvas.
   • Shrinking Asteroids bounce when they get to an edge of the canvas.
   • Splitting Asteroids wrap around when they get to an edge of the canvas.
   • Collisions (reactToBulletHit):
   • You do not need to handle asteroids colliding with each other. You do need to handle when they collide with bullets.
   • Hint: There is a method in the bullet class that will help with collison.
   • Asteroids stop moving when they collide with a bullet. Every 10 seconds, all frozen Asteroids are removed from the canvas.
   • Shrinking Asteroids shrink by shrinkAmount when they get hit by a bullet. You can change shrinkAmount from the default, but we won't test this. When a ShrinkingAsteroid's radius is 15 or less, it is removed from the canvas.
   • Splitting Asteroids split into two when they get hit by a bullet. They are never removed from the canvas.
   • Hint: You should write an onTimerFired method within each asteroid class, just like we did in lecture.
   • Extra Hint: Be careful in the case that 2 bullets hit the same asteroid!
   • Study the code from the dots example in the notes for help!
   
   
5. Bonus/Optional: Towers of Hanoi Animation [3pts]
   Using our animation framework, write an animation that shows a step-by-step walkthrough of how Towers of Hanoi works. To get full credit, each disc movement must be shown, and the user must be able to modify the number of discs at the start state. There must also be some kind of visualization of the recursive function calls.