# CMU 15-112 Spring 2018: Fundamentals of Programming and Computer Science Colab 2 (Due Thursday 25-Jan, at 10pm)

• This assignment is collaborative. That means you may work with other students enrolled in the course, and you may even help each other write code and debug. However, you must still type all of your own work, and you must fully understand the code that you submit. Even though this is collaborative, you may not directly copy any code from anyone, and you may not electronically share your code with anyone. See the syllabus for more details.
• List your collaboration partners (name and andrew id) in a comment on the first line of this file. If you collaborate with another student and do not include their name in a comment, it will be considered cheating. You may work alone if you want to, but we recommend working with others, as it generally leads to better learning.
• Be a good collaborator! Help everyone in your group, and accept their help if you need it. Don't be in a hurry to finish the problems. Instead, take your time and be sure that everyone in the group is following and understanding. The goal is to learn, not just to finish.

• To start:
1. Go to your folder named 'week2'
2. Download colab2.py, cs112_s18_week2_linter.py, and colab2_sampleFiles.zip to that folder. Unzip sampleFiles.zip in that folder.
3. Edit colab2.py using Pyzo
4. When you are ready, submit colab2.py to Autolab. For this colab, you may submit up to 10 times, but only your last submission counts.
• Do not use lists or recursion this week.
• Do not hardcode the test cases in your solutions.

1. nthCircularPrime [25 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 [10 pts]
This function takes a number, x, and rotates that number's digits by one place. This would turn the number 1234 to 4123. You should work with the number input directly instead of casting it to a string.

2. isCircularPrime [10 pts]
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 [5 pts]
This function takes a number, n, and returns the nth circular prime.

2. countLowercaseUpToPercent [25 pts]
Write the function countLowercaseUpToPercent(s) that takes a possibly-empty string and returns the number of lowercase letters that occur in the string before the first percent sign (%). If no percent signs occur, the function should return the total number of lowercase characters in the string.

3. longestCommonSubstring [25 pts]
Write the function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example:
```     longestCommonSubstring("abcdef", "abqrcdest") returns "cde"
longestCommonSubstring("abcdef", "ghi") returns "" (the empty string)
```
If there are two or more longest common substrings, return the lexicographically smaller one (ie, just use "<" to compare the strings). So, for example:
```    longestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab"
```

Hint: Start by solving a simpler problem: how would you find and return the longest-matching substring starting from the beginning of each of the strings? Under this restriction:
```     longestCommonSubstring*("abcdef", "abqrcdest") returns "ab"
```
Now imagine you have a helper function that implements that simpler version of longestCommonSubstring. With that helper function, you can solve longestCommonSubstring by generating all possible combinations of the starting places of s1 and s2, and calling the helper function with each. This can help you identify which sequence of matching characters is the longest.

```# the following string is the content of the file gradebook1.txt