CMU 15-112: Fundamentals of Programming and Computer Science
Homework 2 (Due Saturday 7/10 at 5pm ET (Pittsburgh-time))
- 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.
- To start:
- Create a folder named 'hw2'
- Download both hw2.py and cs112_n21_week1_hw2_linter.py to that folder
- Edit hw2.py using VSCode
- When you have completed and fully tested hw2, submit hw2.py to Autolab. For this hw, you may submit up to 8 times (which is more than you should require), but only your last submission counts.
- Do not use string indexing, lists, list indexing, or recursion for this assignment.
- Do not hardcode the test cases in your solutions.
- Hint: The starter hw2.py file includes test functions.
You may comment out individual test functions in
testAll()to temporarily bypass those tests. The autograder will run all the tests in any case. Ask a TA if you need help with this.
- isPalindromicNumber(n) [10 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. - nthPalindromicPrime(n) [15 pts]
Write the function nthPalindromicPrime(n). See here for details. So nthPalindromicPrime(0) returns 2, and nthPalindromicPrime(10) returns 313. - hasConsecutiveDigits(n) [25 pts]
Write the function hasConsecutiveDigits(n) that takes a possibly-negative int n and returns True if somewhere in n some digit occurs consecutively (so the same digit occurs twice in a row), and False otherwise. For example, these numbers have consecutive digits: 11, -543661, 1200, -1200, and these numbers do not: 1, 123, 12321, -12321. - carrylessAdd(x, y) [25 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. - longestDigitRun(n) [25 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).
Bonus Problems
Bonus problems are entirely optional and worth few points. Do them for the fun and the learning.
- bonus: nthSmithNumber(n) [2 pt]
Please be aware that we usually do not offer extensive help on most bonus problems, but we'll offer some help on this one if you get stuck. It's a good practice problem, so we're hoping you'll try it.
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.
To continue, 27 = 3**3, the sum of the digits is 2+7=9, and the sum of the prime factors is 3+3+3=9, so 27 is a Smith Number. However, 144=2**4 + 3**2, the sum of the digits is 1+4+4=9, and the sum of the prime factors is 2+2+2+2+3+3=14, so 144 is not a Smith Number. - bonus: Integer Data Structures [up to 4 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 4 points. That being said, we hope you enjoy it!