15-112
Spring 19

Home

Syllabus

Schedule

Staff

Gallery

Piazza

Autolab

OH Queue

CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 5 (Due Sunday 17-Feb, at 5pm)

    Collaborative problems
  1. COLLABORATIVE: Tetris [50 pts] [manually graded]
    Write Tetris according to the design given in this step-by-step tutorial. You may not use a different design, even if you think there's a better way to do it (there probably is, but you still have to do it this way). This may seem limiting, but sometimes you have to write code according to a specific algorithm, rather than writing code to solve a specific problem.

    To get full credit, you'll need to complete the basic implementation according to the design spec. Please write this basic version (WITHOUT extra features) in hw5-tetris.py. If you'd like to add extra features to your game for extra credit (up to 3 points, at graders' discretion), create a second version of your Tetris file called hw5-tetris-bonus.py and add your bonus features in this file. Have fun!

    IMPORTANT NOTE: We are not providing a starter file this week!
    • While you may submit to Autolab as often as you like for this assignment, there is no autograded portion for hw5-tetris.py, so you will be responsible for testing your code and making sure it meets the problem requirements. As stated in the style guide, you do not have to write test cases for interactive, random, graphics, data initialization or event functions. Instead, you should test by visually inspecting your code's behavior as you complete steps of each problem, where reasonably possible. This will make debugging your code much easier!

  2. COLLABORATIVE: isKnightsTour(board) [15pts]
    Background:  A "knight's tour in chess is a sequence of legal knight moves such that the knight visits every square exactly once. We can represent a (supposed) knight's tour as an NxN list of the integers from 1 to N2 listing the positions in order that the knight occupied on the tour.  If it is a legal knight's tour, then all the numbers from 1 to N2 will be included and each move from k to (k+1) will be a legal knight's move. With this in mind, write the function isKnightsTour(board) that takes such a 2d list of integers and returns True if it represents a legal knight's tour and False otherwise. Code for this problem should go in hw5.py and will be autograded!

    To help you undertand how a knight's tour is represented, and so you can write your own test cases, here is one example of a successful knight's tour:
    board = [ [ 1, 60, 39, 34, 31, 18, 9, 64 ], [ 38, 35, 32, 61, 10, 63, 30, 17 ], [ 59, 2, 37, 40, 33, 28, 19, 8 ], [ 36, 49, 42, 27, 62, 11, 16, 29 ], [ 43, 58, 3, 50, 41, 24, 7, 20 ], [ 48, 51, 46, 55, 26, 21, 12, 15 ], [ 57, 44, 53, 4, 23, 14, 25, 6 ], [ 52, 47, 56, 45, 54, 5, 22, 13 ], ] assert(isKnightsTour(board)==True)

    Here is an image from Wikipedia's article on knights in chess which demonstrates the possible moves for two knights.


    If you are unfamiliar with how a knight moves in chess, you can envision the possible moves as a 3-by-2 L-shape, where the start and destination are are at opposite ends of the letter.

    3. SOLO problems

  3. removeRowAndCol [10pts]
    Write removeRowAndCol first with a non-destructive approach, then with a destructive approach. Code for this problem should go in hw5.py and will be autograded!

    Both functions take a rectangular list lst and two ints, row and col. They then both create a version of the list that has the given row and given column removed. You may assume that row and col are both legal values (that is, they are non-negative integers that are smaller than the largest row and column, respectively). For example, the list shown to the left would lead to the result shown on the right when called with the row 1 and the column 2.

    listresult
    [ [ 2, 3, 4, 5],
  [ 8, 7, 6, 5],
  [ 0, 1, 2, 3] ]

    [ [ 2, 3, 5],
  [ 0, 1, 3] ]

    nondestructiveRemoveRowAndCol(lst, row, col): the non-destructive version should return a new list, and should not modify the provided list at all.

    destructiveRemoveRowAndCol(lst, row, col): the destructive version should modify the original list, and should not return anything (aka, None).

    Hint: writing test functions for non-destructive and destructive functions is a little different from writing ordinary test functions. Here is an example of a test case for a non-destructive function:

    # This is a test case for a non-destructive function. # The input list and output list lst = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3] ] result = [ [ 2, 3, 5], [ 0, 1, 3] ] # Copy the input list so we can check it later import copy lstCopy = copy.deepcopy(lst) # The first assert is an ordinary test; the second is a non-destructive test assert(nondestructiveRemoveRowAndCol(lst, 1, 2) == result) assert(lst == lstCopy), "input list should not be changed"

    And here is an example of a test case for a destructive function:

    # This is a test case for a destructive function. # The input list and output list lst = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3] ] result = [ [ 2, 3, 5], [ 0, 1, 3] ] # The first test is an ordinary test; the second is a destructive test assert(destructiveRemoveRowAndCol(lst, 1, 2) == None) assert(lst == result), "input list should be changed"


  4. Scrolling ball game [25pts]
    Watch this video first!



    Now let's make an animation with 2D scrolling! Start by copying this week's run function into your hw5-ball.py file, and modify the window size to be square (for example, 400 by 400 pixels). Draw a filled rectangle (with no visible outline) to make the background a nice color! Then put some text up in the top left corner that shows your "score," which starts at 0. Your animation should look something like this... sort of boring.



    Remember that with MVC sidescrolling, objects exist in model coordinates, and we draw them in the view by subtracting scrollX and scrollY from those coordinates. Now create a big rectangle that will act as a sort of fence for a moving ball. This rectangle should be 1.5 times the size of the view (for example, if our view is 400 by 400 pixels, this new rectangle should be 600 by 600 pixels). Implement sidescrolling in both the x and y directions so that when the keyboard up arrow is pressed, the rectangle appears to travel down relative to the view (and vice versa), and when the keyboard right arrow is pressed, the rectangle appears to move left relative to the view. Watch the video again if you're confused! Make sure sidescrolling with this rectangle is working before you proceed. While you can't see which keys are being pressed in this gif, you should be able to move the rectangle around like this:


    Now draw a ball (of any color and sized similarly to the one in the video) which also exists in model coordinates, like the previous rectangle. The ball should appear at a random location completely inside the rectangle, and it should move in a straight line with a random direction. Remember, it exists in model coordinates! That means it should be drawn in the view by subtracting scrollX and scrollY from its model coordinates.

    The next step is to make the ball bounce off the inside "walls" of the rectangle. That means you'll want to detect collisions and reverse the model velocity of the ball in either the x or y direction. The ball should bounce before it overlaps the rectangle edge, so you'll want to take its radius into account! (A few pixels of overlap due to the thickness of the rectangle outline is acceptable.) Follow the ball with the arrow keys and make sure it bounces off of all four walls appropriately.



    Hint: Make the ball move smoothly by decreasing data.timerDelay to something like 10 or 20! Make sure the ball doesn't move so fast that it's difficult to find though. Use the video for guidance (the gifs have a low framerate), but it doesn't have to be exact!

    Let's add another feature: The score in the top corner should increase whenever any part of the ball is visible in the view! It doesn't matter how fast the score increases; just make it go up whenever you can see all or part of the ball. Note: We don't want the score to be obscured by the ball, so you probably want to draw it last in redrawAll.



    Finally, let's add one last feature that didn't make it into the video: When the user clicks the ball, the animation (i.e. the ball and score) should pause. When the user clicks the ball again, the ball and score should un-pause. Clicking anywhere that isn't the ball doesn't do anything. You shouldn't try to stop timerFired from running! Just change whether timerFired actually does anything when the animation is paused.
    Double-check that your animation behaves similarly to the one in the video, and then you're done!