Homework 2 (Due Sat 10-Sep at 8pm)

Important Notes:
  1. Read the "Important Notes" at the top of hw1. The same general rules apply to all homework unless otherwise specified.
  2. This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
  3. You will need these starter files:
    1. hw2.py
    2. cs112_f22_week2_linter.py
  4. For this hw, you may submit up to 7 times, but only your last submission counts.
  5. Do not use strings (except where required in playPig and the bonus problems), string indexing (even in bonus problems), lists, list indexing, or recursion this week.
  6. Do not hardcode the test cases in your solutions.
  1. digitCount(n) [5 pts]  
    Write the function digitCount(n) that takes a possibly-negative int and returns the number of digits in it. So, digitCount(12323) returns 5, digitCount(0) returns 1, and digitCount(-111) returns 3. One way you could do this would be to return len(str(abs(n))), but you cannot do that, since you may not use strings here! This can be solved with logarithms, but seeing as this is "loops week", you should instead simply repeatedly remove the ones digit until you cannot.

  2. hasConsecutiveDigits(n) [5 pts]  
    Write the function hasConsecutiveDigits(n) that takes a possibly-negative int value n and returns True if that number contains two consecutive digits that are the same, and False otherwise.

  3. isPalindromicNumber(n) [5 pts]
    Write the function isPalindromicNumber(n) that takes a non-negative int n and returns True if that number is palindromic and False otherwise, where a palindromic number is the same forwards as backwards. For example, these numbers are palindromic: 0, 1, 99, 12321, 123321, and these numbers are not: 1211, 112, 10010.

  4. nthPalindromicPrime(n) [10 pts]
    Write the function nthPalindromicPrime(n) that takes a non-negative int n and returns the nth palindromic prime, where a palindromic prime is a number that is both prime and a palindrome. The first ten palindromic primes are 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, so nthPalindromicPrime(0) would return 2, nthPalindromicPrime(1) would return 3, and so on.

    Note: It is a good idea to write an isPrime(n) helper function. It's fine if yours is similar (or even identical) to the one in the course notes, but you will likely be required to write it from scratch on quizzes, so it is better to practice now instead of simply copying it. (If you do copy anything from the course notes, you should cite it with a simple comment like "#isPrime copied from https://www.cs.cmu.edu/~112/notes/notes-loops.html" right above the relevant code.)

  5. mostFrequentDigit(n) [10 pts]
    Write the function mostFrequentDigit(n), that takes a possibly-negative integer n and returns the digit from 0 to 9 that occurs most frequently in it, with ties going to the smaller digit.

  6. findZeroWithBisection(f, x0, x1, epsilon) [15 pts]
    As we will cover more carefully later in the course, a function may take another function as an argument. For example, consider this code: 
    def h(n):
    return n+5
def f(g, x):
    return 2*g(x)
print(f(h,3)) # prints 16
    Here, we define a function f whose first argument is another function. On the last line, we call f providing the function h, which is bound in f to the parameter g. Hence, calls to g in f are really calls to h. Play around with the sample code to get the hang of this idea.

    In mathematics, one way to numerically (as opposed to algebraically) find a zero of a function f(x) is to search for the zero in between two points, using smaller steps as we get closer. (This is similar to binary search, which we will learn about in a later week.)
    To start, we need to know two values, x0 and x1, with x0<x1, where f(x0) and f(x1) have different signs (so one is positive and the other is negative). We know there is some value x in the range [x0,x1] such that f(x)=0. (This is described by the Intermediate Value Theorem, if you're curious.)
    Our goal is to find the x where f(x) == 0. First, we evaluate f(xmid), which is the midpoint between x0 and x1. If f(xmid) is exactly 0, we are done! Otherwise, we can divide our range in half as such: if f(xmid) and f(x0) are the same sign, use the range [xmid, x1]. Otherwise, f(xmid) and f(x1) must share the same sign, so use the range [x0, xmid]. We repeat the process of evaluating f at the midpoint of our new range, then choosing a new range, and so forth until x0 and x1 are very close (i.e. within some suitably small epsilon).

    With this in mind, write the function findZeroWithBisection that takes a function f, a float x0, a float x1, and a float epsilon, and returns an approximate value x in [x0,x1] where f(x) is approximately zero. Your function should stop when x0 and x1 are within epsilon, and at that time should return the midpoint of that range. Note that if it is not true that exactly one of f(x0) and f(x1) is negative, your function should return the Python value None, signifying that the bisection method cannot be used on the given range.

    Let's see this in action! First, we'll use it to approximate the square root of 2 without the ** operator: 
    print("Use bisection to approximate sqrt(2):")
def f1(x): return x*x - 2 # root at x=sqrt(2)
x = findZeroWithBisection(f1, 0, 2, 0.000000001)
print(f" x = {x}")                # prints  x = 1.41421356192
print(f" check: x**2 = {x*x}")  # prints  check: x**2 = 1.99999999871 (really close!)

    Next, let's use it to approximate phi (the golden ratio), without using the closed-form solution ((1 + sqrt(5))/2), instead using the interesting property of phi that adding one to it is the same as squaring it. That is, ((phi + 1) == phi**2). How do use that? We convert it into an equation equal to 0: phi**2 - (phi + 1) == 0. Now we're set! (Of course, we could just use the Quadratic Formula here, but it's more interesting to use bisection, now that we have it!).

    print("use bisection to approximate phi (the golden ratio):")
def f2(x): return x**2 - (x + 1) # root at x=phi
x = findZeroWithBisection(f2, 0, 2, 0.000000001)
print(f" x = {x}")                  # prints x = 1.61803398887
phi = (1 + 5**0.5)/2             # the actual value (to within Python's floating point accuracy)
print(f" check: x/phi = {x/phi}") # prints check: check: x/phi = 1.00000000007 (nice!)

    The previous two examples are nice, but simpler techniques than bisection would have worked as well. So let's solve a problem that would be hard to solve without bisection (or some other numeric approximation algorithm). Specifically, find a number x such that x**5 == 2**x:

    print("use bisection to approximate x where x**5 == 2**x")
def f3(x): return x**5 - 2**x # f(1)<0, f(2)>0
x = findZeroWithBisection(f3, 1, 2, 0.000000001)
print(f" x = {x}")                              # prints x = 1.17727855081
print(f" check: x**5 - 2**x = {x**5 - 2**x}") # prints check: x**5 - 2**x = 3.63570817896e-09 (great!)


    Hopefully this bisection excursion helps you appreciate the awesome computational power that about 10 lines of Python can have!
     

  7. carrylessAdd(x, y) [15 pts]
    First, you may wish to read the first page (page 44) from here about Carryless Arithmetic. Or, just understand that carryless addition is what it sounds like -- regular addition, only with the carry from each column ignored. So, for example, if we carryless-ly add 8+7, we get 5 (ignore the carry). And if we add 18+27, we get 35 (still ignore the carry). With this in mind, write the function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

  8. longestDigitRun(n) [15 pts]
    Write the function longestDigitRun(n) that takes a possibly-negative int value n and returns the digit that has the longest consecutive run, or the smallest such digit if there is a tie. So, longestDigitRun(117773732) returns 7 (because there is a run of 3 consecutive 7's), as does longestDigitRun(-677886).

  9. playPig() [20 pts] [manually graded]
    Notes:
    1. For only this problem, you may use strings but only in these ways:
      1. Obtain a string from input().
      2. Check if two strings are equal.
      3. Print a string (including f-strings).

    With that, first, read about the dice game Pig here. Then, write the function playPig(), that allows two players to play the game Pig. You will want to use random.randint(1,6) to randomly choose a number between 1 and 6 inclusive. Grading criteria:
    • Your game must enforce the basic rules of Pig.
    • Your game should not use any graphics. This is a console-based game.
    • Your game should use the input(prompt) function to get user input.
    • Your game should print enough information to make the game reasonably fun and usable.
    Be thoughtful but don't overthink this. Any reasonably fun, playable game of Pig will do fine here. Have fun!

  10. Bonus/Optional: bonusCarrylessMultiply(x, y) [1 pts]
    Write the function bonusCarrylessMultiply(x, y), that works similarly to carrylessAdd(x, y) (which we will cover in the writing session), based on this paper on Carryless Arithmetic. This paper shows that bonusCarrylessMultiply(643, 59) returns 417. Hint: it may help if you do this differently than usual long multiplication. Instead of working by rows in the output, work by columns. So first compute all the ones digit values, and sum those mod 10. Then compute all the tens digit values, and sum those mod 10. And so on. You may assume x and y are non-negative.

    Hint #1: do not solve carrylessMultiply(x, y) by simply calling carrylessAdd(x, result) a total of y times. That is wrong on two levels. First, it is simply too inefficient (what if we are multiplying 20-digit numbers?). Second, it is also wrong algorithmically! CarrylessMultiply is not like normal multiply, and if we take + to be carrylessAdd and * to be carrylessMultiply, then it is not necessarily true that (x * y) is the same as (x + x + ... + x + x) for a total of y x's. Yikes. So: stick with the next hint (see below). It also uses carrylessAdd and is fairly straightforward, but it is reasonable efficient and algorithmically correct. Good luck with it.

    Hint #2: Here's a hint on one way to solve this problem (there are many ways, and this way is not the most efficient, to be sure, but it is efficient enough and it is perhaps among the clearest and easiest ways).

    Consider multiplying 123 * 456. Observe that:

        123 * 456 = 123 * 4 * 100 + 123 * 5 * 10 + 123 * 6

    in this way, we actually only have to multiply 123 times a single digit each time, then multiply that result by the right power of 10. Right?

    Ok, so now, to multiply by a single digit, we can instead just add that many times. That is:

        123 * 6 == 123 + 123 + 123 + 123 + 123 + 123

    Why is that interesting? Because we already have carrylessAdd, so we can just use that to do all this addition.

    Of course, multiplying by simply adding is very inefficient. But since we are only doing it for multiplying by a single digit, there's a max of 9 additions (8 if you think about it), and so it's not so inefficient. It's actually acceptable, if not ideal, and certainly good enough for hw2, though again better approaches do exist.

    Hope this helps. And, again, you can safely ignore all of this and solve this problem any way you wish.

  11. Bonus/Optional: Integer Data Structures [2 pts]
    Note: We will not provide debugging help or hints on this problem! You must rely on your own problem-solving and debugging skills. That being said, we have offered rather detailed guidance here. You should only do this if you find it interesting and fun, because it's really not worth spending many hours on this purely for 2 points. That being said, we hope you enjoy it!
carpe diem