Homework 3

Due Tuesday 14-Sep, at 10:00pm

To start

Create a folder named ‘hw3’
Download hw3.py to that folder
Edit hw3.py and modify the functions as required
When you have completed and fully tested hw3, submit hw3.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

Some important notes

This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
Do not hardcode the test cases in your solutions.
The starter 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.
Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

Limitations

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.

A Note About Style Grading

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!

A Note About Testing

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.)

Problems

nthCircularPrime [15 pts]
A circular prime is a number with the property that any rotation of that number's digits is prime. In this case, rotation refers to cycling the digits of a number; for example, the rotations of 1234 are 1234, 2341, 3412, and 4123. You can read more about this on the Wikipedia page. Single-digit primes are all circular, of course. To find the nth circular prime, you'll need to write isPrime and three other functions:
1. rotateNumber
  This function takes a number, x, and rotates that number's digits by one place. This would turn the number 1234 to 4123.
2. isCircularPrime
  This function takes a number, x, and determines whether that number is a circular prime. To do this, you'll need to check whether every rotation of the number is prime.
3. nthCircularPrime
  This function takes a number, n, and returns the nth circular prime.
Hint: You may want to write the sizeof function from question 4 before starting this problem. It might be helpful...

longestDigitRun [10 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).

findExit [10 pts]

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

Helper Functions [30 pts]

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.
1. Write the function concatNumbers(x,y) which, given two non-negative integers x and y, returns a concatenation (sequential combination) of these two numbers as an integer. Following are some examples of calling this function and expected output:
  - 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
2. Write a function called sizeof(n) which, given an integer n, returns the number of digits in this integer. For example, calling this function with n = 5, should return 1. Calling the function with n = 3421, should return 4.
3. Write a function called getLeftkDigits(n, k) that takes some number of digits from the left part of an integer and returns that value. This function should take two arguments, n and k, where n is the integer value and k is the number of digits to extract from the left. You can assume that n will always be a non-negative integer. For example:
  - getLeftkDigits(1234,2) should return 12
  - getLeftkDigits(1234,3) should return 123
  - getLeftkDigits(1234,5) should return 1234
  - getLeftkDigits(0,1) should return 0
4. Write a function called removeLeftkDigits(n, k) that removes some digits from the left part of an integer and returns the remaining digits as an integer. This function should take two arguments, n and k, where n is the integer value and k is the number of digits to remove from the left. You can assume that n will always be a non-negative integer. For example:
  - removeLeftkDigits(1234,2) should return 34
  - removeLeftkDigits(1234,3) should return 4
  - removeLeftkDigits(1234,5) should return 0
  - removeLeftkDigits(0,1) should return 0

List as Integers [35 pts]

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.
1. Write the function encode(n) that takes a possibly-negative Python integer and returns the encoded integer as described above. For example:
  - 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
2. Now write the decode(n) function that performs the inverse operation of the encode function. Given an encoded integer, this function will return the original integer back. The function returns two values as a list, the first element in the list is the decoded value starting from the left side. The second element is any remaining portion that were not decoded.
  - 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.
3. We will use the encoding functionality to encode a whole list of integers as one list. Write a function called encodeList(L), where L is a List of integers. The values should be encoded such that value at index 0 is to the left most side of the final integer. This function should return all elements in the list encoded within a single integer. for example:
  - encodeList([789,-789,1234512345]) should return 11378921378912101234512345
4. The last part of this task does the inverse of the previous task. In this task, you write a function called decodeList(n) that takes an encoded list as a parameter and passes back a list of all the integers. for example:
  - decodeList(11378921378912101234512345) should return [789,-789,1234512345]