CMU 15-112 Spring 2018: Fundamentals of Programming and Computer Science
Colab 3 (Due Thursday 01-Feb, at 10pm)

  1. testIsEquidigital() [25pts]
    We say that a number is equidigital if it is positive and has the same number of digits as the number of digits in all of its unique prime factors combined. For example, 10 is equidigital because it has two digits and its prime factors, 2 and 5, have two digits combined. 3 is also equidigital because it has the same number of digits as its only prime factor, which is itself. 66 is not equidigital because its prime factors (2, 3, and 11) have four combined digits and 66 only has two. We want to write the function isEquidigital(n) which returns True if the number n if equidigital and False otherwise.

    We've made several attempts to solve this problem, each included in the starter file. We've given each a number (isEquidigital1, isEquidigital2, isEquidigital3...) to distinguish them. Only one of these implementations is correct according to the specification we've given above. Your task is to write a test function, testIsEquidigital(isEquidigital), which only passes when called on the correct function. On all other functions, it should raise an assertion error. The argument isEquidigital is actually a function; our own test function, testTestIsEquidigital (meta!), provides the different versions of isEquidigital for you to test. You can call the argument isEquidigital as you would a normal function name (we'll go over how this actually works closer to the end of the semester). For example, we would implement our example from before as:

    def testIsEquidigital(isEquidigital): assert(isEquidigital(10) == True)

  2. Debug the Programs [25pts]
    Each of the following three programs has one error (or bug) in it somewhere. Your task is to find and fix that bug without substantially rewriting the program. Specifically, each bug can be fixed by modifying only one of the program lines (which will result in full credit); if you modify more than one line, you'll only get partial credit. We define 'modify' to mean either changing one line, adding one line, or deleting one line.

    Note: for each of these problems, you'll need to remove the triple-string quotes before debugging the program.

    1. countEvenDigits(n) [5pts]
      This program is supposed to count the number of even digits that appear in the parameter n.
      """def countEvenDigits(n): if n < 0: return countEvenDigits(-n) elif n == 0: return 1 count = 0 while n > 0: digit = n % 10 if digit % 2 == 0 count += 1 n = n // 10 return count"""

    2. hasDoubleLetters(s) [10pts]
      This program is supposed to return True if the given string has two letters in a row that are the same, and False otherwise.
      """def hasDoubleLetters(s): for i in range(len(s)): if s[i] == s[i+1]: return True return False"""

    3. largestNumber(s) [10pts]
      This program is supposed to take a string of text and return the largest int value that occurs within that text, or None if no such value occurs. The only numbers in the text are non-negative integers, and numbers are always composed of consecutive digits (without commas, for example). So "test 1234 test" contains one number (1234), but "test 1234a test" contains no numbers.
      """import string def largestNumber(s): biggest = None for word in s.split(): allNumbers = True for i in range(len(word)): if word[i] not in string.digits: allNumbers = False if allNumbers: n = int(word) if biggest == None or n > biggest: n = biggest return biggest"""

  3. Fix the Style [25pts]
    We've written a program, areAnagrams(s1, s2), which returns True if two strings are anagrams (that is, if they contain the same letters in possibly-different orders). The program is functionally correct, but we've written this program with terrible style.

    Fix this program so that it meets the 112 style guidelines without rewriting the main logic. Then, in a comment above the fixed program, write out a list of the changes you made to fix the style. You must make valid changes that cover at least five different style rules to get full credit. This problem is not autograded; we will hand-grade it instead.
    def areAnagrams(s1, s2): if len(s1) != len(s2): return False print("bad case") if len(s1) == len(s2): for str in s1: one = 1 count_matches_1 = 0 count_matches_2 = 0 for i in range(len(s1)): if s1[i] == str: count_matches_1 += one for i in range(len(s2)): if s2[i] == str: count_matches_2 += one if count_matches_1 != count_matches_2: return False return True

  4. nthKaprekarNumber [10pts]
    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 nthKaprekarNumber(n) that takes a non-negative int n and returns the nth Kaprekar number. For example, nthKaprekarNumber(0) == 1.

  5. mostFrequentLetters [15pts]
    Write the function mostFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the letters of s in most frequently used order. (In the event of a tie between two letters, follow alphabetic order, aka normal string comparison.) For example, mostFrequentLetters("We Attack at Dawn") returns "atwcdekn". Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered lists, sets, maps, or efficiency, you are not expected to write the most efficient solution. (And you should not use lists, sets, or maps in your solution.) Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").

    Note that in this problem and in many other future problems, we will not give you much guidance on how to approach solving the problem. You should use the notes on algorithmic thinking to come up with an algorithm yourself.