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:
- Go to your folder named 'week2'
- Download colab2.py, cs112_s18_week2_linter.py, and colab2_sampleFiles.zip to that folder. Unzip sampleFiles.zip in that folder.
- Edit colab2.py using Pyzo
- 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.
- 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:
- 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.
- 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.
- nthCircularPrime [5 pts]
This function takes a number, n, and returns the nth circular prime.
- rotateNumber [10 pts]
- 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.
- 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.
- gradebookSummary [25 pts]
For this problem, we'll assume that gradebooks are stored in .txt files. Each row of the gradebook file contains a student's name (one word, all lowercase), followed by one or more comma-separated integer grades. A gradebook always contains at least one student, and each row always contains at least one grade. Gradebooks can also contain blank lines and lines starting with the "#" character, which should be ignored.
With this in mind, write the function gradebookSummary(gradebookFilename) that takes the filename of a gradebook as an argument and returns a summary of the gradebook as a string. This summary string should show each student followed by a tab followed by their average grade (rounded to the hundreth place). The summary string should have the students listed in their original order (separated by newlines, but without a newline at the end), but should get rid of any comments or blank lines.
For example, here is a test case:
# the following string is the content of the file gradebook1.txt """# ignore blank lines and lines starting with #'s wilma,91,93,94 fred,80,85,90,97,100 betty,88""" assert(gradebookSummary("gradebook1.txt") == "wilma\t92.67\nfred\t90.40\nbetty\t88.00"))Hint: you most likely will want to use both s.split(",") and s.splitlines() in your solution.