15-112 Fall 2014 Homework 2
Due Sunday, 7-Sep, at 10pm

• This entire hw is strictly SOLO, in the same way hw1-part2 was, so you may not even discuss the problems with any other students or anyone except the course staff.


• There is no starter file this week. Instead, you should download hw1.py from hw1, and rename it to hw2.py. Then replace the functions above the #ignore_rest line with your autograded functions (and their helper functions, if any), and replace the test functions below the #ignore_rest line with your new test functions.


• Also, be sure to place your solution to playPig, and all its helper functions, below the #ignore_rest line, so the autograder is not confused by it.


• Starting this week, you may use loops and conditionals, but (as usual) you may not use constructs we have not yet covered (strings, lists, sets, maps, recursion, etc), unless explicitly allowed below. Note that in playPig you may make very limited use of strings, strictly to deal with the results of raw_input().


• Seeing as you do not have a starter file this week, we will allow more Autolab submissions than usual. Even so, to help avoid an overreliance on the autograder, this week you may only make up to 10 submissions max to Autolab. As usual, only your last one counts.


• Do not use global variables! Do use test functions!


• You can and should use previous functions on the hw to solve later functions.


• You also can and should use your own helper functions, where appropriate.


• And you also can use anything from the course notes, including isPrime, fasterIsPrime (which you can rename to isPrime), and nthPrime. Just cite it if you use it, and be sure you can also generate the code from first principles!


• While optional this week, you are still strongly encouraged to attend small-group CA sessions. These should be a big help for hw2.


• Each of the autograded problems is worth 10 points, for 70 total points, and playPig is non-autograded (hence, below the #ignore_rest line), and worth 30 points.

1. digitCount(n)
   Write the function digitCount 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, or by simply repeatedly removing the ones digit until you cannot. Note that this function is listed first because it may be useful for some of the functions below (or not, depending on how you implement your solutions).


2. kthDigit(n, k)
   Write the function kthDigit that takes a possibly-negative int n and a non-negative int k, and returns the kth digit of n, starting from 0, counting from the right. So kthDigit(789, 0) returns 9, kthDigit(789, 2) returns 7, kthDigit(789, 3) returns 0, and kthDigit(-789, 0) returns 9. This function may also be helpful later on.


3. nthIsolatedPrime(n)
   Write the function nthIsolatedPrime(n). See here for details. From that writeup, and noting that we start counting at 0, we see that nthIsolatedPrime(0) is 2, and nthIsolatedPrime(1) is 23, and so on.


4. nthLeftTruncatablePrime
   Write the function nthLeftTruncatablePrime(n). See here for details. So nthLeftTruncatablePrime(0) returns 2, and nthLeftTruncatablePrime(10) returns 53.


5. carrylessAdd(x,y)
   First, read the first page (page 44) from here about Carryless Arithmetic. Fun! Then, 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.


6. carrylessMultiply(x,y)
   Similarly, write carrylessMultiply(x,y). The same 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.


7. longestDigitRun(n)
   Write the function longestDigitRun(n) that takes an 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).


8. playPig (Dice Game)
   This is an open-ended exercise, without any test functions, and without an autograder (the CA's will grade it manually). First, read about the dice game of pig here. Then, write the function playPig() that takes no parameters and plays a console-based (that is, no graphics) two-player interactive game of pig. The computer does not actually play a side, but just manages play between two human players. This involves showing the score and whose turn it is, managing the turn sequence by rolling a die, asking the user what their move will be, enacting that choice, switching sides, determining a winner, and displaying suitable messages for all of this. While you may want to do more than this, say using more exotic rules, or using a GUI rather than console input, resist the urge. We will grade you on how closely you abide to this spec. That said, this spec is broad, so you have some leeway on how you design this, both in terms of the user experience as well as how your code is written. Hint: you will almost surely want to use random.randint(1, 6) to randomly roll your die. Look it up to see the details.


9. Bonus/Optional: Fun with generators! (3 pts; 1 pt each)
   Note: if you attempt the optional bonus problems, please be sure to place your solutions above the #ignore_rest line, so the autograder can see them and test them.
   
   First, do your own Google search to read about the "yield" statement and so-called "generators" in Python. 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 xrange(11):
           # Explicitly calling the next() function is a less common
           # way to use a generator, but it still works, of course..
           print g.next(),
       print "Done!"
   
   oddsGeneratorDemo()
   

   
   
   • Bonus/Optional: squaresGenerator()
     Write the function squaresGenerator(), so that it passes the following tests. Your function must not use globals or other explicit non-locals (don't worry if you don't know what those are), and it must use "yield" properly.

     def testSquaresGenerator():
         print "Testing squaresGenerator()...",
         # This time, we'll test twice.  First with next(),
         # then with a "for" loop
         g = squaresGenerator()
         assert(g.next() == 1)
         assert(g.next() == 4)
         assert(g.next() == 9)
         assert(g.next() == 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()
     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. Again, your function must not use globals or other explicit non-locals (don't worry if you don't know what those are), and it must use "yield" properly.

     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()
     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. Again, your function must not use globals or other explicit non-locals (don't worry if you don't know what those are), and it must use "yield" properly.

     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"
                             #"489133282872437279"
               )
         print "Passed!"