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 2 (Due Sunday 27-Jan, at 5pm)

    Resource-use problems
    The following two problems are intended to show you some of the resources offered as part of the course. You are also encouraged to attend office hours, which can be very helpful too!

  1. Group sessions [7pts] [manually-graded]
    Attend and participate in at least one small group or large group session before Tuesday January 29th. One of the TAs will record your participation by hand. If you already attended a large or small group session this semester, that counts too.

  2. Piazza Post [3pts] [manually-graded]
    Ask a question on Piazza about the homework or coding in general by Tuesday January 29th 10:30am. This has to be a real question! We will check for this on Tuesday and will add points on Autolab manually at that point. If you have already asked a question on Piazza, that counts too.
    3. Lab collaborative problems [20pts]
    The lab problems will be released on Friday, and must be completed collaboratively with your classmates.
    Collaborative problems
  3. COLLABORATIVE Debugging: isMultiPowerfulNumber(n) [10pts] [manually-graded]
    You're given the function isMultiPowerfulNumber(n) (shown below), which has exactly three bugs. Your task is to debug this program and make it work properly. You should not rewrite the program yourself beyond fixing the bugs- the point is to practice testing and debugging, not writing code. In fact, you should not add or remove any lines; you should only change the lines that already exist.

    Copy the code below into your homework file under its collaborators function, and fix it there. Note that testIsMultiPowerfulNumber is empty- you'll need to write test cases for the function yourself. Above the program, write in the comments the three bugs you fix, and how you fixed them. The function will be autograded for 5 points on Autolab for correctness; the remaining 5 points will be graded by TAs after reading your comments.

    Problem statement: This program takes a positive integer, n, and determines whether that number is 'multi-powerful', a made-up term. A multi-powerful number is one which is powerful (for every prime factor p which divides n, p**2 must also divide n) and also has more than one prime factor (not including 1, which is not prime). The first multi-powerful numbers are 36, 72, 100, and 108.

    def isMultiPowerfulNumber(n): factorCount = 0 for factor in range(n): if n % factor = 0 and isPrime(factor): if n % (factor**2) != 0: return False factorCount += 1 return factorCount > 1

  4. COLLABORATIVE Code Writing: drawThreadPattern(canvas, size, numSpokes, startSpoke, numSkips) [15pts] [manually-graded]
    In this problem, you'll be creating a thread pattern with tkinter. A thread pattern (also known as a string art pattern) is made by creating a circle with several spokes placed around the perimeter, then running a thread around different spokes to create a desired pattern.

    We'll create thread patterns algorithmically by specifying a number of spokes to go around the circle, which spoke to start at, and how many spokes should be skipped each time the thread is moved to the next spoke. The thread will continue going between spokes until it reaches the spoke it originally started on. We'll number the spokes starting with 0 at the bottom, then increasing going clockwise. So a circle with eight spokes would have spoke 2 where 9 would be on a clock.

    Write the function drawThreadPattern, which takes five parameters: the canvas, the canvas size (width and height must be equal so that the canvas is a square), the number of spokes in the circle, the starting spoke number, and the number of spokes to skip each time. This function should draw the thread pattern with the given parameters, using lines to represent the threads and a circle that fills the given screen (with a small pixel margin on each side). The starting spoke should be colored green, and the rest of the spokes should be red. Here are a few examples:

    drawThreadPattern(canvas, 400, 12, 0, 5)


    drawThreadPattern(canvas, 200, 10, 3, 4)


    drawThreadPattern(canvas, 500, 19, 8, 15)


    To provide further clarification, here is a gif of a pattern with ten spokes that shows what each spoke's number would be. The gif shows how the thread pattern would be created in real time, starting from the start spoke (2) and skipping 3 spokes each time. You do not need to create this image or animation- this is just here to help you understand the problem!

    Don't make this- it's just for clarification!


    Note: for this problem and other graphics problems, anything we do not specify is a design decision. For example, you can decide the size of the margin, as long as it is reasonably close to the examples shown above.

    Another Note: as a reminder, your graphics solutions do not need to be pixel-perfect identical to our example images! They should just be reasonably close.
    Solo problems
  5. Code Writing: drawSteelersLogo(canvas, x, y, r) [10pts] [manually-graded]
    In this function, you'll use tkinter to draw the Steelers logo! Or rather, you'll draw an alternate version of it, as the astroids used by the real image are a little too complicated for us to attempt just now. The logo you should create is a simplified version, shown below:



    Write the function drawSteelersLogo(canvas, x, y, r) that draws the logo shown above on the given canvas centered at the given x,y location, with radius r. The image shown above was drawn by calling drawSteelersLogo(canvas, 150, 150, 100) on a canvas of 300x300. Here are two more examples:

    runDrawSteelersLogo(canvas, 300, 200, 200) on a 500x600 window:


    runDrawSteelersLogo(canvas, 50, 60, 40) on a 150x100 window:


    Hint: use the font "Times" and the colors "gray", "gold", "red", and "blue" to match the images shown above.

    Another Hint: you'll save yourself some typing time if you make a helper function that draws a diamond given specific coordinates. This is also good coding style!

  6. Code Writing: Kaprekar Numbers [20pts]
    The following three problems all involve Kaprekar numbers. A Kaprekar number is a non-negative integer, the representation of whose square can be split into two possibly-different-length parts (where the right part is not zero) that add up to the original number again. For instance, 45 is a Kaprekar number, because 45**2 = 2025 and 20+25 = 45. The first several Kaprekar numbers are: 1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728...

    • isKaprekarNumber(n) [7pts]
      First, write the function isKaprekarNumber(n), which takes a number n and returns True if n is a Kaprekar number, and False otherwise.

    • nthKaprekarNumber(n) [3pts]
      Second, write the function nthKaprekarNumber(n), which takes a non-negative int n and returns the nth Kaprekar number, starting from 0. For example, nthKaprekarNumber(0) == 1.

    • nearestKaprekarNumber(n) [10pts]
      Finally, write the function nearestKaprekarNumber(n) that takes an int or float value n and returns the Kaprekar number closest to n, with ties going to smaller value. For example, nearestKaprekarNumber(49) returns 45, and nearestKaprekarNumber(51) returns 55. And since ties go to the smaller number, nearestKaprekarNumber(50) returns 45.

      Hint: this problem cannot be solved by counting up from 0, as that will not be efficient enough to get past the autograder. Instead, you should write an algorithm that starts at n and grows in each direction until it finds a Kaprekar number. So nearestKaprekarNumber(51) would start at 51, then check 50 and 52, then check 49 and 53, etc. This allows you to return as soon as you've found the closest number.

      Another Hint: returning the closest number with the smaller number in ties can be tricky. The algorithm becomes much simpler if you consider three cases. Consider the order that you should check numbers in if:
      • n is an integer
      • n is a float with decimal between (0, 0.5)
      • n is a float with decimal between [0.5, 1)

  7. Code Writing: drawButtonPattern(canvas, size, n) [15pts] [manually-graded]
    Write the function drawButtonPattern(canvas, size, n), which is given the canvas, the size of the window (width and height must be the same), and a number n. It then draws an nxn grid of buttons in the window on a purple background. Each button is drawn as several circles drawn on top of each other, where each inner circle has a radius 2/3rds as large as the next-larger circle. This continues until the radius is less than 1. The color of each circle is chosen based on the following set of rules:

    1. Rule 1: Starting from the left-top corner, every 4th diagonal is entirely red.
    2. Rule 2: For the non-red buttons, starting from the top row, every 3rd row is entirely green.
    3. Rule 3: For the non-red and non-green buttons, starting from the second-to-leftmost column, every 2nd column is entirely yellow.
    4. Rule 4: Any non-red, non-green, and non-yellow button is blue.

    drawButtonPattern(canvas, 400, 10):


    drawButtonPattern(canvas, 300, 5):


    drawButtonPattern(canvas, 250, 25):
    8. Bonus problems (optional, and solo)
  8. Bonus Code Writing: drawNiceRobot(canvas, width, height) [1pt] [manually-graded]
    Write a function drawNiceRobot(canvas, width, height) that (you guessed it!) draws a nice robot! This is not meant to be very difficult. We just want to see some really cool robots while grading your homework. To get this bonus point, your function must make a drawing using Tkinter that meets the following criteria:
    1. Easily identifiable as a robot
    2. Includes at least 10 shapes total, including at least one oval, one rectangle, one non-rectangular polygon, and one line
    3. Uses at least 4 colors
    4. Resizes with the canvas. (You may assume that the canvas will always resize proportionally, and you may change the starting proportions in the test case if you want to)
    Do not use anything we haven't learned in class or in the notes through Week 2! No extra files, no importing anything other than Tkinter. Have fun!

  9. Bonus Code Writing: Fun with generators! [3 pts]
    Note: if you attempt this problem, please be sure to place your solutions above the #ignore_rest line, so the autograder can see and test it.

    First, do your own Google search to read about the "yield" statement and so-called "generators" in Python. (You are allowed to read code on external websites for this purpose). Then, carefully look at this code, play around with it, and understand it:

    def oddsGenerator(): odd = 1 while True: yield odd odd += 2 def oddsGeneratorDemo(): print("Demonstrating use of oddsGenerator()...") print(" looping over oddGenerator():") for odd in oddsGenerator(): # This is how generators are typically used print(odd) if (odd > 20): break print("Done!") print(" This time, using the next() function:") g = oddsGenerator() for i in range(11): # Explicitly calling the next() function is a less common # way to use a generator, but it still works, of course. print(next(g)) print("Done!") oddsGeneratorDemo()

    For all three of the following functions, your solution must not use globals or other explicit non-locals (don't worry if you don't know what those are). Your solutions must also use "yield" properly.

    • Bonus/Optional: squaresGenerator() [1pt]
      Write the function squaresGenerator() so that it passes the following tests.

      def testSquaresGenerator(): print("Testing squaresGenerator()...") # This time, we'll test twice. First with next(), # then with a "for" loop g = squaresGenerator() assert(next(g) == 1) assert(next(g) == 4) assert(next(g) == 9) assert(next(g) == 16) # ok, now with a for loop. squares = "" for square in squaresGenerator(): # we'll check the concatenation of the str's, # since we cannot use lists on this hw! if (squares != ""): squares += ", " squares += str(square) if (square >= 100): break assert(squares == "1, 4, 9, 16, 25, 36, 49, 64, 81, 100") print("Passed!")

    • Bonus/Optional: nswGenerator() [1pt]
      First, read about Newman-Shanks-Williams primes here. (Hint: the recurrence relation is probably the most important part for this task.) We will build a generator for these! Before generating the NSW (Newman-Shanks-Williams) primes, we'll just generate all the values, prime or not, in the NSW series as described in that link. As noted, these values are also listed here. With this in mind, write the function nswGenerator(), so that it passes the following tests.

      def testNswGenerator(): print("Testing nswGenerator()...") nswNumbers = "" for nswNumber in nswGenerator(): # we'll check the concatenation of the str's, # since we cannot use lists on this hw! if (nswNumbers != ""): nswNumbers += ", " nswNumbers += str(nswNumber) if (nswNumber >= 152139002499): break # from: http://oeis.org/A001333 assert(nswNumbers == "1, 1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, " "19601, 47321, 114243, 275807, 665857, 1607521, 3880899, " "9369319, 22619537, 54608393, 131836323, 318281039, " "768398401, 1855077841, 4478554083, 10812186007, " "26102926097, 63018038201, 152139002499" ) print("Passed!")

    • Bonus/Optional: nswPrimesGenerator() [1pt]
      Now we put it all together and make an nsw primes generator. Practically, we will be limited by the inefficiency of our isPrime (well, fasterIsPrime) function. So we will only test this function out to 63018038201, and not 489133282872437279 or beyond. Even so, be sure not to hardcode the answers, but instead solve this generally. With this in mind, write the function nswPrimesGenerator() so that it passes the following tests.

      def testNswPrimesGenerator(): print("Testing nswPrimesGenerator()...") nswPrimes = "" for nswPrime in nswPrimesGenerator(): # again, we'll check the concatenation of the str's, # since we cannot use lists on this hw! if (nswPrimes != ""): nswPrimes += ", " nswPrimes += str(nswPrime) if (nswPrime >= 63018038201): break # from: http://oeis.org/A088165 # print nswPrimes assert(nswPrimes == "7, 41, 239, 9369319, 63018038201") print("Passed!")