15-112
Spring 2020

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

CMU 15-112: Fundamentals of Programming and Computer Science
Homework 1 (Due Saturday 18-Jan at 8pm)

Important note about spiciness levels! Note: this homework has 3 levels: Mild, Medium, and Spicy. Choose problems at the level that you think is most appropriate for you. Since 20 points of hw1 are based on your participation in Friday's lab1, that leaves 80 points to be gained here. So you should attempt at least 80 total points in this section.

Your hw score will take your highest-scoring problems, in order, until the total attempted points is >= 80. So for example if you have a 78/80, scoring 2/10 on another problem generally would not change your score but scoring 10/10 on another problem would.

Points are available as such: However, in all cases, total points earned in this part of hw1 are capped at 80. Even so, we strongly encourage you to do the medium or spicy problems if you can.
Mild Problems

  1. isEvenPositiveInt(x) [10pts]
    Write the function isEvenPositiveInt(x) that takes an arbitrary value x, return True if it is an integer, and it is positive, and it is even (all 3 must be True), or False otherwise. Do not crash if the value is not an integer. So, isEvenPositiveInt("yikes!") returns False (rather than crashing), and isEvenPositiveInt(123456) returns True.

  2. nearestBusStop(street) [10pts]
    Write the function nearestBusStop(street) that takes a non-negative int street number, and returns the nearest bus stop to the given street, where buses stop every 8th street, including street 0, and ties go to the lower street, so the nearest bus stop to 12th street is 8th street, and the nearest bus stop to 13 street is 16th street. The function returns an integer, so for example, nearestBusStop(5) returns 8.

  3. isPerfectSquare(n) [10pts]
    Write the function isPerfectSquare(n) that takes a possibly-non-int value, and returns True if it is an int that is a perfect square (that is, if there exists an integer m such that m**2 == n), and False otherwise. Do not crash on non-ints nor on negative ints.

  4. nthFibonacciNumber(n) [10pts]
    Background: The Fibonacci numbers are defined by F(n) = F(n-1) + F(n-2). There are different conventions on whether 0 is a Fibonacci number, and whether counting starts at n=0 or at n=1. Here, we will assume that 0 is not a Fibonacci number, and that counting starts at n=0, so F(0)=F(1)=1, and F(2)=2. With this in mind, write the function nthFibonacciNumber(n) that takes a non-negative int n and returns the nth Fibonacci number. Some test cases are provided for you. You can use Binet's Fibonacci Number Formula which (amazingly) uses the golden ratio to compute this result, though you may have to make some small change to account for the assumptions noted above. Hint: remember not to use loops!

  5. numberOfPoolBalls(rows) [10pts]
    Pool balls are arranged in rows where the first row contains 1 pool ball and each row contains 1 more pool ball than the previous row. Thus, for example, 3 rows contain 6 total pool balls (1+2+3). With this in mind, write the function numberOfPoolBalls(rows) that takes a non-negative int value, the number of rows, and returns another int value, the number of pool balls in that number of full rows. For example, numberOfPoolBalls(3) returns 6. We will not limit our analysis to a "rack" of 15 balls. Rather, our pool table can contain an unlimited number of rows. Hint: you may want to briefly read about Triangular Numbers. Also, remember not to use loops!

  6. isFactorish(n) [10pts]
    Write the function isFactorish(n) that takes a value n that can be of any type, and returns True if n is a (possibly-negative) integer with exactly 3 unique digits (so no two digits are the same), where each of the digits is a factor of the number n itself. In all other cases, the function returns False (without crashing). For example:
    assert(isFactorish(412) == True) # 4, 1, and 2 are all factors of 412 assert(isFactorish(-412) == True) # Must work for negative numbers! assert(isFactorish(4128) == False) # 4128 has more than 3 digits assert(isFactorish(112) == False) # 112 has duplicate digits (two 1's) assert(isFactorish(420) == False) # 420 has a 0 (no 0's allowed) assert(isFactorish(42) == False) # 42 has a leading 0 (no 0's allowed) assert(isFactorish(412.0) == False) # 412.0 is not an int assert(isFactorish('nope!') == False) # don't crash on strings
  7. nearestOdd(n) [10pts]
    Write the function nearestOdd(n) that takes an int or float n, and returns as an int value the nearest odd number to n. In the case of a tie, return the smaller odd value. Note that the result must be an int, so nearestOdd(13.0) is the int 13, and not the float 13.0.

    Hint: Remember that the built-in round function works in surprising ways. Instead of round(n), you should use roundHalfUp(n) from this week's notes. That said, there are good ways to solve this problem without using rounding at all, if you prefer.
Medium Problems

  1. rectanglesOverlap(left1, top1, width1, height1, left2, top2, width2, height2) [20pts]
    A rectangle can be described by its left, top, width, and height. This function takes two rectangles described this way, and returns True if the rectangles overlap at all (even if just at a point), and False otherwise. Note: here we will represent coordinates the way they are usually represented in computer graphics, where (0,0) is at the left-top corner of the screen, and while the x-coordinate goes up while you head right, the y-coordinate goes up while you head down (so we say that "up is down").

  2. numberOfPoolBallRows(balls) [20pts]
    This problem is the inverse of the previous problem. Write the function numberOfPoolBallRows(balls) that takes a non-negative int number of pool balls, and returns the smallest int number of rows required for the given number of pool balls. Thus, numberOfPoolBallRows(6) returns 3. Note that if any balls must be in a row, then you count that row, and so numberOfPoolBallRows(7) returns 4 (since the 4th row must have a single ball in it). Hint: you may want to briefly read about Triangular Numbers, and also think about how this problem relates to the numberOfPoolBalls problem above.

  3. threeLinesArea(m1, b1, m2, b2, m3, b3) [20pts]
    Write the function threeLinesArea(m1, b1, m2, b2, m3, b3) that takes six int or float values representing the 3 lines:
        y = m1*x + b1
        y = m2*x + b2
        y = m3*x + b3
    First find where each pair of lines intersects, then return the area of the triangle formed by connecting these three points of intersection. If no such triangle exists (if any two of the lines are parallel), return 0. To do this, use three helper functions: one to find where two lines intersect (which you will call three times), a second to find the distance between two points, and a third to find the area of a triangle given its side lengths. Hint: you may want to briefly read about Heron's Formula.
Spicy Problems

  1. colorBlender(rgb1, rgb2, midpoints, n) [30pts]
    This problem implements a color blender, inspired by this tool. In particular, we will use it with integer RGB values (it also does hex values and RGB% values, but we will not use those modes). Note that RGB values contain 3 integers, each between 0 and 255, representing the amount of red, green, and blue respectively in the given color, where 255 is "entirely on" and 0 is "entirely off".

    For example, consider this case. Here, we are combining crimson (rgb(220, 20, 60)) and mint (rgb(189, 252, 201)), using 3 midpoints, to produce this palette (using our own numbering convention for the colors, starting from 0, as the tool does not number them):

    color0: rgb(220, 20, 60) color1: rgb(212, 78, 95) color2: rgb(205, 136, 131) color3: rgb(197, 194, 166) color4: rgb(189, 252, 201)

    There are 5 colors in the palette because the first color is crimson, the last color is mint, and the middle 3 colors are equally spaced between them.

    So we could ask: if we start with crimson and go to mint, with 3 midpoints, what is color #1? The answer then would be rgb(212, 78, 95).

    One last step: we need to represent these RGB values as a single integer. To do that, we'll use the first 3 digits for red, the next 3 for green, the last 3 for blue, all in base 10 (decimal, as you are accustomed to). Hence, we'll represent crimson as the integer 220020060, and mint as the integer 189252201.

    With all that in mind, write the function colorBlender(rgb1, rgb2, midpoints, n), which takes two integers representing colors encoded as just described, a non-negative integer number of midpoints, and a non-negative integer n, and returns the nth color in the palette that the tool creates between those two colors with that many midpoints. If n is out of range (too small or too large), return None.

    For example, following the case above: colorBlender(220020060, 189252201, 3, 1) returns 212078095

    Hints: RGB values must be ints, not floats. Also, remember to use roundHalfUp(n) instead of round(n) when calculating midpoint colors.

  2. playThreeDiceYahtzee(dice) [30pts]
    In this exercise, we will write a simplified form of the dice game Yahtzee. In this version, the goal is to get 3 matching dice, and if you can't do that, then you hope to at least get 2 matching dice. The game is played like so:
    1. Roll 3 dice.
    2. If you do not have 3 matching dice:
      1. If you have 2 matching dice (a pair), keep the pair and roll one die to replace the third die.
      2. Otherwise, if you have no matching dice, keep the highest die and roll two dice to replace the other two dice.
    3. Repeat step 2 one more time.
    4. Finally, compute your score like so:
      1. If you have 3 matching dice, your score is 20 + the sum of the matching dice.
        • So if you have 4-4-4, your score is 20+4+4+4, or 32.
      2. If you only have 2 matching dice, your score is 10 + the sum of the matching dice.
        • So if you have 4-4-3, your score is 10+4+4, or 18.
      3. If you have no matching dice, your score is the highest die.
        • So if you have 4-3-2, your score is just 4.
    Our goal is to write some Python code that plays this game. It's a large task, so we will use top-down design and break it up into smaller, more manageable pieces. So we'll first write some helper functions that do part of the work, and then those helper functions will make our final function much easier to write.

    Also note: we will represent a hand of 3 dice as a single 3-digit integer. So the hand 4-3-2 will be represented by the integer 432. With that, let's start writing some code. Be sure to write your functions in the same order as given here, since later functions will make use of earlier ones!

    1. handToDice(hand)
      Write the (very short) function handToRolls(hand) that takes a hand, which is a 3-digit integer, and returns 3 values, each of the 3 dice in the hand. For example: 
      assert(handToDice(123) == (1,2,3))
assert(handToDice(214) == (2,1,4))
assert(handToDice(422) == (4,2,2))
      Hint: You might find // and % useful here, and also getKthDigit.
      Another hint: This returns a tuple. You cannot use tuple indexing this week, but you can use tuple assignment, like so: 
      def f(m):
    return (m+1,m+2,m+3)
x,y,z = f(4)  # this does tuple assignment!
print(f'After tuple assignment, x={x}, y={y}, z={z}')

    2. diceToOrderedHand(a, b, c)
      Write the function diceToOrderedHand(a, b, c) that takes 3 dice and returns them in a hand, which is a 3-digit integer. However, even if the dice are unordered, the resulting hand must be ordered so that the largest die is on the left and smallest die is on the right. For example: 
      assert(diceToOrderedHand(1,2,3) == 321)
assert(diceToOrderedHand(6,5,4) == 654)
assert(diceToOrderedHand(1,4,2) == 421)
assert(diceToOrderedHand(6,5,6) == 665)
assert(diceToOrderedHand(2,2,2) == 222)
      Hint: You can use max(a,b,c) to find the largest of 3 values, and min(a,b,c) to find the smallest.

    3. playStep2(hand, dice)
      This is the most complicated part. Write the function playStep2(hand, dice) that plays step 2 as explained above. This function takes a hand, which is a 3-digit integer, and it also takes dice, which is an integer containing all the future rolls of the dice. For example, if dice is 5341, then the next roll will be a 1, then the roll after that will be a 4, then a 3, and finally a 5. Note that in a more realistic version of this game, instead of hard-coding the dice in this way, we'd probably use a random-number generator.

      With that, the function plays step2 of the given hand, using the given dice to get the next rolls as needed. At the end, the function returns the new hand, but it has to be ordered, and the function also returns the resulting dice (which no longer contain the rolls that were just used).

      For example: 
      assert(playStep2(413, 2312) == (421, 23))
      Here, the hand is 413, and the future dice rolls are 2312. What happens? Well, there are no matching dice in 413, so we keep the highest die, which is a 4, and we replace the 1 and the 3 with new rolls. Since new rolls come from the right (the one's digit), those are 2 and 1. So the new hand is 421. It has to be sorted, but it already is. Finally, the dice was 2312, but we used 2 digits, so now it's just 23. We return the hand and the dice, so we return (421, 23).

      Here are some more examples. Be sure you carefully understand them: 
      assert(playStep2(413, 2345) == (544, 23))
assert(playStep2(544, 23) == (443, 2))
assert(playStep2(544, 456) == (644, 45))
      Hint: You may wish to use handToDice(hand) at the start to convert the hand into the 3 individual dice.
      Hint: Then, you may wish to use diceToOrderedHand(a, b, c) at the end to convert the 3 dice back into a sorted hand.
      Hint: Also, remember to use % to get the one's digit, and use //= to get rid of the one's digit.

    4. score(hand)
      Almost there... Now write the function score(hand) that takes a 3-digit integer hand, and returns the score for that hand as explained in step4 above. For example: 
      assert(score(432) == 4)
assert(score(532) == 5)
assert(score(443) == 10+4+4)
assert(score(633) == 10+3+3)
assert(score(333) == 20+3+3+3)
assert(score(555) == 20+5+5+5)
      Hint: The structure of this function is actually quite similar to the previous function.

    5. playThreeDiceYahtzee(dice)
      Ok, we've made it to the last function: playThreeDiceYahtzee(dice), the function that actually earns the points! This function takes one value, the dice with all the rolls for a game of 3-Dice Yahtzee. The function plays the game -- it does step1 and gets the first 3 dice (from the right), then it does step2 twice (by calling playStep2, which you already wrote), and then it computes the score (by calling score, which you already wrote). The function should return two values -- the resulting hand and the score for that hand. For example: 
      assert(playThreeDiceYahtzee(2312413) == (432, 4))
assert(playThreeDiceYahtzee(2315413) == (532, 5))
assert(playThreeDiceYahtzee(2345413) == (443, 18))
assert(playThreeDiceYahtzee(2633413) == (633, 16))
assert(playThreeDiceYahtzee(2333413) == (333, 29))
assert(playThreeDiceYahtzee(2333555) == (555, 35))

  3. findIntRootsOfCubic(a,b,c,d) [30pts]
    Write the function findIntRootsOfCubic(a,b,c,d) that takes the int or float coefficients a, b, c, d of a cubic equation of this form:

         y = ax3 + bx2 + cx + d

    You are guaranteed the function has 3 real roots, and in fact that the roots are all integers. Your function should return these 3 roots in increasing order. How does a function return multiple values? Like so:

    return root1, root2, root3
    To get started, you'll want to read about Cardano's cubic formula here. Then, from that page, use this formula:
     
    x   =   {q + [q2 + (r-p2)3]1/2}1/3   +   {q - [q2 + (r-p2)3]1/2}1/3   +   p

    where:

    p = -b/(3a),   q = p3 + (bc-3ad)/(6a2),   r = c/(3a)

    This isn't quite as simple as it seems, because your solution for x will not only be approximate (and not exactly an int, so you'll have to do something about that), but it may not even be real! Though the solution is real, the intermediate steps may include some complex values, and in these cases the solution will include a (possibly-negligibly-small) imaginary value. So you'll have to convert from complex to real (try c.real if c is complex), and then convert from real to int.

    Great, now you have one root. What about the others? Well, we can divide the one root out and that will leave us with a quadratic equation, which of course is easily solved. A brief, clear explanation of this step is provided here. Don't forget to convert these to int values, too!

    So now you have all three int roots. Great job! All that's left is to sort them. Now, if this were later in the course, you could put them in a list and call a built-in function that will sort for you.; But it's not, so you can't. Instead, figure out how to sort these values using the limited built-in functions and arithmetic available this week. Then just return these 3 values and you're done.