Due Tuesday 5-Sep, at 10:00pm
hw2.py file includes test functions to help you test on your own before
you submit to Gradescope. When you run your file, problems will be tested in order. If
you wish to temporarily bypass specific tests (say, because you have not yet completed
some functions), you can comment out individual test function calls at the bottom
of your file in main(). However, be sure to uncomment and test everything together
before you submit! Ask a CA if you need help with this.containsOddDigits(x) that takes an integer, x, and returns True if it contains any odd digits, and False otherwise.printNumberTriangle that takes one integer, n, and prints out a number triangle based on n. For example, given the number 4, this function would print outhasConsecutiveDigits(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.
isPalindromicNumber(n) that takes a non-negative
int n and returns True if that number is palindromic and
False otherwise. 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.
longestCommonDigitStart(x, y) that takes two
non-negative integers, x and y, and returns the digits that match between the
two integers, starting from the ones digit. For examples, the pair (1234, 2134)
returns 34 because two digits match from right to left, 4 with 4 and 3 with 3.
The pair (2223, 23) also has two matches, and the solution is 23. If
there's no common digit start, the function should return None. For
example, the pair (1234,4321) has no common start, and the result should
be None.
Here are a few more examples:
Note: This is a bonus problem for students who want an extra challenge. Bonus problems are optional, and should only be attempted after the rest of the assignment has been finished.
Write the function bonusCarrylessMultiply(x, y), that works similarly to carrylessAdd(x, y), 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 bonusCarrylessMultiply(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! Carryless multiplication is not like normal multiplication, and if we take + to be carryless addition and * to be carryless multiplication, 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: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:
Why is that interesting? If we take + to be carryless addition and * to be carryless multiplication, (x * y) is the same as (x + x + ... + x + x) if y is a one-digit number. 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.