Due Tuesday 14-Sep, at 10:00pm
hw3.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.Do not convert numbers to strings, use string indexing or recursion this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.
Starting with this assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading starts this week, so please use good style from now on!
You will notice that the skeleton file only includes testcases for some of the functions you are writing. You should write testcases for the others. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)
Write a function called findExit, that takes list of integers as input parameters. Each number in this list represents the number of hops you need to make. You start from index 0 and make as many hops as the number at index 0. Each time you land on an index, make the number of hops at that index. Determine whether you can reach the last index or not. Return True if you reach the last index, and False otherwise. In an empty list, there is no last index, so you can never reach it. For example:
findExit([2,0,1,0]) returns True
findExit([1,1,0,1]) returns False
findExit([1,2,0,3,1]) returns False
findExit([-1,1,1,0]) returns False
In this section, we ask you to write functions that can be useful in solving parts of later tasks. We hope that you will take advange of these functions for the solution to those tasks. For these problems, you CANNOT use string functions or convert integers to strings.
concatNumbers(5,8) should return 58
concatNumbers(200,12) should return 20012
concatNumbers(25,8) should return 258
concatNumbers(8,25) should return 825
concatNumbers(12,200) should return 12200
getLeftkDigits(1234,2) should return 12
getLeftkDigits(1234,3) should return 123
getLeftkDigits(1234,5) should return 1234
getLeftkDigits(0,1) should return 0
removeLeftkDigits(1234,2) should return 34
removeLeftkDigits(1234,3) should return 4
removeLeftkDigits(1234,5) should return 0
removeLeftkDigits(0,1) should return 0
In this problem we will use normal Python integers to represent lists of integers. Since we plan to include multiple integers in a single integer, we will start by encoding integers with a prefix of the number of digits in that integer. For example, we might encode 25 as 225, where the first 2 says there are 2 digits. But then we’d have to encode 1234567890 with a count of 10. But then we’d have to know how many digits our count itself has! And we are now recursing. Oh no!
Our solution, which is not fully general but which is good enough for our purposes, is to first have a count-count of the number of digits in the count. That first count-count will always be exactly one digit, so the count itself can be between 1 and 9 digits. So the largest digit count is 999,999,999. So this approach does not allow numbers with one billion or more digits. We can live with that restriction.
We also have to deal with the sign (+/-) of the number. Normally this might be 0 for positive and 1 for negative, but leading 0’s can cause confusion, so we’ll use 1 for positive and 2 for negative.
Thus, we will encode numbers as such: [sign-digit] [count-count] [count] [number]. So, for example, to encode 789, the sign-digit is 1 (positive). The count is 3, so the count-count is 1. Thus, the entire encoding of 789 is 113789.
For another example, to encode -1234512345, the sign-digit is 2 (negative). The count is 10, so the count-count is 2. Thus, the entire encoding of -1234512345 is 22101234512345.
Hint: Don't forget to use the helper functions you wrote for part 4.
encode(789) should return 113789
encode(-789) should return 213789
encode(1234512345) should return 12101234512345
encode(-1234512345) should return 22101234512345
encode(0) should return 1110
decode(113789) should return [789,0]
decode(213789) should return [-789,0]
decode(12101234512345) should return [1234512345,0]
decode(22101234512345) should return [-1234512345,0]
decode(1110) should return [0,0]
decode(113789113789) should return [789,113789] since after decoding 789 from the left, we are have 113789 remining.
encodeList([789,-789,1234512345]) should return 11378921378912101234512345
decodeList(11378921378912101234512345) should return [789,-789,1234512345]