Note that the hour of the deadline is not the same as for homework assignments.
This project must be completed individually. Seeking or giving aid on this assignment is prohibited; doing so constitutes academic misconduct which can have serious consequences. The only resources you are allowed to consult are the ones listed below. If you are unsure about whether something is allowed, ask. The course syllabus contains more information about the course and university policies regarding academic honesty.
This project focuses on solving problems using recursion. You'll write a number of recursive functions that all involve a common theme, exploring variations on a single idea more deeply than you get to do in worksheets and homework.
Ask if you are unsure whether a resource falls under one of these categories, or if you think I missed an essential resource.
Contact the instructor or your TA by email, in office hours, or on discord.
The starter pack is available here:
This time, the starter pack only contains a demonstration program splitdemo.py and a text file showing what its output should be splitdemo_expected_output.txt. The demo program won't work until you've completed your part of the project.
Write a module intsplit, in a file called intsplit.py, and submit it to Gradescope. That is the only file you should submit.
The module must contain the functions documented in the section Specification of the module intsplit below. Before describing those functions, let's discuss the core mathematical ideas they involve.
Suppose you start with a positive integer, like 17. For this assignment we'll say that a splitting of an positive integer is a way to write that integer as a sum of other positive integers. For example, these are some splittings of 17:
Things to notice:
For another example, here are all of the splittings of 5:
We'll consider several restricted types of splittings.
To fix terminology, in a splitting like 8+2+7, the individual summands 8, 2, and 7 will be called the parts.
A splitting of an integer is said to have distinct parts if no two of the parts appearing in the splitting are equal. For example, these are the splittings of 6 that have distinct parts:
Every other splitting of 6 has some duplicated part. Notice we consider the splitting into one part (6 by itself) to have "distinct parts".
In general, a splitting of $n$ can use any positive integer between 1 and $n$. But we could also decide on a smaller list of available summands. For example, here are all the splittings of 6 where the only allowable summands are 2, 3, and 4:
Notice we're allowed to use a summand more than once in this case. Also note that 6 by itself is not allowed this time, because 6 was not on the list of allowable parts.
Combining the two ideas above, we could start with a list of distinct, allowable parts like 2,3,4,5,6 and ask for splittings of an integer into distinct parts from that list. For example, the splittings of 6 into distinct parts from the list 2,3,4,5,6 are:
Notice that some of the allowed parts were never actually used; for example, the only way to write 6 as a sum of parts from the list 2,3,4,5,6 that includes 3 is the splitting 3+3, but that uses 3 twice, so it is not a splitting into distinct parts.
Finally, we can ask for splittings where the total number of parts is less than or equal to a specified number. For example, here are the splittings of 6 into at most 2 parts:
intsplit¶The module must contain functions
splittingssplittings_iterativesplittings_memoizedsplittings_distinctsplittings_intosplittings_distinct_intosplittings_limited_sizedescribed below. In short, they compute splittings with any or all of the constraints descibed above.
The module must not do anything other than define functions and one global variable when imported. No output is allowed (no calls to print(), no file IO, etc.) at any time---not even inside the functions described below.
splittings¶n, a positive integern is less than or equal to zero, raises ValueErrorn. Each splitting is represented as a list of its parts (i.e. the splitting "8+2+3" would be represented as the list of integers [8,2,3]. Thus, the return value of this function is a list of lists. The splittings can be returned in any order, but keep in mind that the order of the parts within a splitting is significant.splittings(3) returns [[3], [1, 2], [1, 1, 1], [2, 1]] or some other list containining the same elements but in a different order.
splittings(1) returns [[1]] (the list with one element, where that element is the list [1])
splittings with n greater than 22 unless your computer has a lot of memory and you have a lot of time.splittings_iterative¶Exactly the same specifications as splittings, except that this one should be implemented using only iteration, no recursion.
Hint: There's a rather clean solution that you might guess by looking at the total number of splittings as a function of n and noticing a pattern. You don't need to use that particular method, but I wanted to give you a push in a potentially helpful direction.
splittings_memoized¶Exactly the same specifications as the recursive function splittings, but memoized. That is, it should store the return value of each calculation, and use the stored value if available and recursion if not. The store of previous values should be a global dictionary in the intsplit module.
Note: The fact that it is memoized won't be checked by the autograder so I recommend you test this carefully yourself. It should be much faster than splittings for larger values of n. For example, on my home computer I found that splittings(22) takes about 9 seconds while splittings_memoized(22) takes about 2.5 seconds.
splittings_distinct¶n, a positive integern is less than or equal to zero, raises ValueErrorn with distinct parts.splittings_distinct(3) returns [[3], [1, 2], [2, 1]] or some other list containining the same elements but in a different order.
splittings_distinct(2) returns [[2]]
splittings_into¶n, a positive integerparts, a list of distinct integersn is less than or equal to zero, raises ValueErrorn into parts that belong to the list parts. An element of the list parts can be used more than once in a splitting.splittings_into(6,[2,4,3]) returns [[2, 2, 2], [2, 4], [3, 3], [4, 2]] or some other list containining the same elements but in a different order.
splittings_into(6,[4,5]) returns [] (an empty list, because no splittings of 6 satisfy that condition!)
splittings_into(6,[3,28,599]) returns [[3,3]] (notice that there are elements in parts that cannot ever be used, because they are too large)
splittings_into(6,[3,5]) returns [[3,3]] (notice that there are elements in parts that end up going unused, i.e. 5)
splittings_distinct_into¶n, a positive integerparts, a list of distinct integers that are allowed as partsn is less than or equal to zero, raises ValueErrorn into distinct parts that also belong to the list parts. splittings_distinct_into(6,[2,4,3]) returns [[2, 4], [4, 2]] or [[4, 2], [2, 4]]
splittings_distinct_into(6,[2,3]) returns [] (an empty list, because no splittings of 6 satisfy that condition!)
splittings_limited_size¶n, a positive integermaxparts, an integer specifying the maximum number of parts allowedn is less than or equal to zero, raises ValueErrorn that have at most maxparts parts in them.splittings_limited_size(7,3) returns the list shown below, or some or some other list containining the same elements but in a different order
[[7], [1, 6], [1, 1, 5], [1, 2, 4], [1, 3, 3], [1, 4, 2], [1, 5, 1], [2, 5], [2, 1, 4], [2, 2, 3], [2, 3, 2], [2, 4, 1], [3, 4], [3, 1, 3], [3, 2, 2], [3, 3, 1], [4, 3], [4, 1, 2], [4, 2, 1], [5, 2], [5, 1, 1], [6, 1]]splittings_limited_size(2752022,1) returns [[2752022]] and should do so very quickly. (If it sits there computing for a while, it probably means you are generating all splittings and then filtering out the short ones, which is explicitly forbidden by the specifications above.)
The starter pack contains splitdemo.py, a script that you can use to test your intsplit module. I suggest trying to run it as soon as you've writen splittings, and trying again ever time you add another one of the required functions.
When some required functions are missing, the output from splitdemo.py will end with an exception, but the output before the exception can still be helpful.
I also recommend trying out the functions in your own test scripts or notebooks. I'm including splitdemo.py to give you a head start on that.
Your project must follow the 7 rules in the MCS 275 coding standards document. In addition:
The autograder tests your program and grades it based on its behavior. The following tests will be run:
intsplit.py submitted? (5 points)intsplit.py as valid Python code? (5 points)intsplit.py contain docstrings for all classes, functions, and methods? (5 points)intsplit.py be imported without raising an exception? (5 points)Plan your project work so that you can submit to the autograder as much before the deadline as possible. The first submission often has easily-fixed problems, and you want to allow yourself time to make those fixes.