CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Homework 2 (Due Saturday 10-Sep, at 6pm)

• This hw is SOLO. See the syllabus for details.
• Starter files: hw2.py and cs112_f16_wk2.py
• This week you may use up to 10 submissions (which is still plenty more than you should need). Only your last submission counts.
• Do not use strings, lists, or recursion this week.
• Do not hardcode the test cases in your solutions.

1. Happy Numbers [20 pts; 5 pts each]
   Background: read the first paragraph from the Wikipedia page on happy numbers. After some thought, we see that no matter what number we start with, when we keep replacing the number by the sum of the squares of its digits, we'll always either arrive at 4 (unhappy) or at 1 (happy). With that in mind, we want to write the function nthHappyNumber(n). However, to write that function, we'll first need to write isHappyNumber(n) (right?). And to write that function, we'll first need to write sumOfSquaresOfDigits(n). And that's top-down design! Here we go....
   
   Note: the autograder will grade each of the following functions, so they are required. However, they also are here specifically because they are just the right helper functions to make nthHappyNumber(n) easier to write!
   
   
   1. sumOfSquaresOfDigits(n)
      Write the function sumOfSquaresOfDigits(n) which takes a non-negative integer and returns the sum of the squares of its digits. Here are some test assertions for you (note that in the hw2.py starter file, instead of assert, these use assertEqual):

      assert(sumOfSquaresOfDigits(5) == 25)   # 5**2 = 25
      assert(sumOfSquaresOfDigits(12) == 5)   # 1**2 + 2**2 = 1+4 = 5
      assert(sumOfSquaresOfDigits(234) == 29) # 2**2 + 3**2 + 4**2 = 4 + 9 + 16 = 29
      

   2. isHappyNumber(n)
      Write the function isHappyNumber(n) which takes a possibly-negative integer and returns True if it is happy and False otherwise. Note that all numbers less than 1 are not happy. Here are some test assertions for you:

      assert(isHappyNumber(-7) == False)
      assert(isHappyNumber(1) == True)
      assert(isHappyNumber(2) == False)
      assert(isHappyNumber(97) == True)
      assert(isHappyNumber(98) == False)
      assert(isHappyNumber(404) == True)
      assert(isHappyNumber(405) == False)
      

   3. nthHappyNumber(n)
      Write the function nthHappyNumber(n) which takes a non-negative integer and returns the nth happy number (where the 0th happy number is 1). Here are some test assertions for you:

      assert(nthHappyNumber(0) == 1)
      assert(nthHappyNumber(1) == 7)
      assert(nthHappyNumber(2) == 10)
      assert(nthHappyNumber(3) == 13)
      assert(nthHappyNumber(4) == 19)
      assert(nthHappyNumber(5) == 23)
      assert(nthHappyNumber(6) == 28)
      assert(nthHappyNumber(7) == 31)
      

   4. nthHappyPrime(n)
      A happy prime is a number that is both happy and prime. Write the function nthHappyPrime(n) which takes a non-negative integer and returns the nth happy prime number (where the 0th happy prime number is 7).


2. nearestKaprekarNumber(n) [20 pts]
   Background: 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. You can read more about Kaprekar numbers here. The first several Kaprekar numbers are: 1, 9, 45, 55, 99, 297, 703, 999 , 2223, 2728,...
   
   With this in mind, 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.
   
   Note: as you probably guessed, this also cannot be solved by counting up from 0, as that will not be efficient enough to get past the autograder. Hint: one way to solve this is to start at n and grow in each direction until you find a Kaprekar number.


3. carrylessMultiply(x, y) [30 pts]
   Write the function carrylessMultiply(x, y), that works similarly to carrylessAdd(x, y) (which we will cover in the lab, and please do not do it prior to then, which means that this problem should not be attempted until after you finish lab2), based on this paper on Carryless Arithmetic. This paper shows that carrylessMultiply(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.


4. nthSmithNumber(n) [30 pts]
   Write the function nthSmithNumber that takes a non-negative int n and returns the nth Smith number, where a Smith number is a composite (non-prime) the sum of whose digits are the sum of the digits of its prime factors (excluding 1). Note that if a prime number divides the Smith number multiple times, its digit sum is counted that many times. For example, 4 equals 2**2, so the prime factor 2 is counted twice, thus making 4 a Smith Number.


5. Bonus/Optional nthWeaklyPrime(n) [2 pts]
   As you can read here, a number is weakly prime if it is prime and any change of any digit always results in a composite number. With this in mind, write the function nthWeaklyPrime(n) that takes a non-negative int n and returns the nth weakly prime number. For example, nthWeaklyPrime(0) returns 294001.


6. Bonus/Optional: play112 (The 112 Game) [3 pts]
   Read the writeup for "The 112 Game" here (skip to Part B). Be sure to follow the spec exactly, so the autograder can properly grade your work! As with all bonus, we recommend that you only do this for the joy of learning (which is great), and not for the points (which are modest).