A document from MCS 275 Spring 2022, instructor Emily Dumas. You can also get the notebook file.

MCS 275 Spring 2022 Project 2

  • Course instructor: Emily Dumas

Instructions

Deadline is 6pm central time on Friday 25 February 2022.

Note that the hour of the deadline is not the same as for homework assignments.

Collaboration policy and academic honesty

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.

Topic

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.

Resources you are allowed to consult

  • Documents and videos posted to the course web page
  • Any of the optional textbooks listed on the course web page

Ask if you are unsure whether a resource falls under one of these categories, or if you think I missed an essential resource.

What to do if you are stuck

Contact the instructor or your TA by email, in office hours, or on discord.

Get the starter pack

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.

What to submit

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.

Integer splittings

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:

  • 8 + 2 + 7
  • 3 + 11 + 3
  • 11 + 3 + 3
  • 17
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Things to notice:

  • Order matters, i.e. we consider 3+11+3 and 11+3+3 to be different splittings
  • It's allowable to have just one summand (the number itself)

For another example, here are all of the splittings of 5:

  • 5
  • 4 + 1
  • 3 + 2
  • 2 + 3
  • 1 + 4
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 2
  • 1 + 3 + 1
  • 1 + 2 + 2
  • 1 + 1 + 3
  • 2 + 1 + 1 + 1
  • 1 + 2 + 1 + 1
  • 1 + 1 + 2 + 1
  • 1 + 1 + 1 + 2
  • 1 + 1 + 1 + 1 + 1

Constrained splittings

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.

Splittings into distinct 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:

  • 6
  • 5 + 1
  • 4 + 2
  • 2 + 4
  • 1 + 5
  • 3 + 2 + 1
  • 3 + 1 + 2
  • 2 + 3 + 1
  • 2 + 1 + 3
  • 1 + 3 + 2
  • 1 + 2 + 3

Every other splitting of 6 has some duplicated part. Notice we consider the splitting into one part (6 by itself) to have "distinct parts".

Splittings with a limited set of 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:

  • 2 + 4
  • 4 + 2
  • 3 + 3
  • 2 + 2 + 2

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.

Splittings with a limited set of parts that are also distinct

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:

  • 6
  • 2 + 4
  • 4 + 2

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.

Splittings with a limited number of 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:

  • 6
  • 1 + 5
  • 2 + 4
  • 3 + 3
  • 4 + 2
  • 5 + 1

Specification of the module intsplit

The module must contain functions

  • splittings
  • splittings_iterative
  • splittings_memoized
  • splittings_distinct
  • splittings_into
  • splittings_distinct_into
  • splittings_limited_size

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

Function splittings

Arguments

  • n, a positive integer

Behavior

  • If n is less than or equal to zero, raises ValueError
  • Otherwise, returns a list of all splittings of n. 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.
  • Must use recursion.

Sample output

  • 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])

Warning

  • I wouldn't recommend that you call splittings with n greater than 22 unless your computer has a lot of memory and you have a lot of time.

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

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

Function splittings_distinct

Arguments

  • n, a positive integer

Behavior

  • If n is less than or equal to zero, raises ValueError
  • Otherwise, returns a list of all splittings of n with distinct parts.
  • Must use recursion.
  • Must not generate a list larger than the final return value. One way to write this function is to generate a list of all splittings (which might be huge) and then filter it down to just the ones that meet the additional conditions given here (potentially much smaller). This is not allowed. You must find a way to only ever generate splittings that meet the given conditions, never considering any others. Note: The autograder doesn't test whether this rule is broken. It is enforced in manual review.

Sample output

  • 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]]

Function splittings_into

Arguments

  • n, a positive integer
  • parts, a list of distinct integers

Behavior

  • If n is less than or equal to zero, raises ValueError
  • Otherwise, returns a list of all splittings of n into parts that belong to the list parts. An element of the list parts can be used more than once in a splitting.
  • Must use recursion.
  • Must not generate a list larger than the final return value. One way to write this function is to generate a list of all splittings (which might be huge) and then filter it down to just the ones that meet the additional conditions given here (potentially much smaller). This is not allowed. You must find a way to only ever generate splittings that meet the given conditions, never considering any others. Note: The autograder doesn't test whether this rule is broken. It is enforced in manual review.

Sample output

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

Function splittings_distinct_into

Arguments

  • n, a positive integer
  • parts, a list of distinct integers that are allowed as parts
  • Must use recursion.
  • Must not generate a list larger than the final return value. One way to write this function is to generate a list of all splittings (which might be huge) and then filter it down to just the ones that meet the additional conditions given here (potentially much smaller). This is not allowed. You must find a way to only ever generate splittings that meet the given conditions, never considering any others. Note: The autograder doesn't test whether this rule is broken. It is enforced in manual review.

Behavior

  • If n is less than or equal to zero, raises ValueError
  • Otherwise, returns a list of all splittings of n into distinct parts that also belong to the list parts.
  • Must use recursion.

Sample output

  • 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!)

Function splittings_limited_size

Arguments

  • n, a positive integer
  • maxparts, an integer specifying the maximum number of parts allowed

Behavior

  • If n is less than or equal to zero, raises ValueError
  • Otherwise, returns a list of all splittings of n that have at most maxparts parts in them.
  • Must use recursion.
  • Must not generate a list larger than the final return value. One way to write this function is to generate a list of all splittings (which might be huge) and then filter it down to just the ones that meet the additional conditions given here (potentially much smaller). This is not allowed. You must find a way to only ever generate splittings that meet the given conditions, never considering any others. Note: The autograder doesn't test whether this rule is broken. It is enforced in manual review.

Sample output

  • 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 demonstration script

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.

IMPORTANT RULES YOUR CODE MUST FOLLOW

Your project must follow the 7 rules in the MCS 275 coding standards document. In addition:

  • Your functions must be reasonably efficient in space and time. The autograder will run each test with a memory budget of 512MiB and a time budget of 3 seconds. This is very generous. The tests will involve return values containing up to 20,000 items, and straightforward solutions to the project using methods from the course can usually complete each test in less than 0.05 seconds while using less than 5MiB of memory. But in case you find some way to write a function that works but is exceptionally slow or uses enourmous amounts of memory, be aware that it won't receive credit in the automated tests.

How your project will be graded

Autograder: 55 points

The autograder tests your program and grades it based on its behavior. The following tests will be run:

  1. Was a file called intsplit.py submitted? (5 points)
  2. Does the Python interpreter accept the contents of intsplit.py as valid Python code? (5 points)
  3. Does intsplit.py contain docstrings for all classes, functions, and methods? (5 points)
  4. Can intsplit.py be imported without raising an exception? (5 points)
  5. Functional tests of the seven required functions (35 points total, several tests of each function)

Manual review: 20 points

  1. 10 points based on checking that you followed important specifications that can't be easily tested by the autograder:
    • using recursion or iteration or memoization as specified
    • never generating a larger list of splittings and filtering it to a smaller list to return
  2. 10 points The usual manual review of code standards adherance, docstring accuracy, formatting, correctness issues possibly missed by the autograder

Final word: Submit before deadline

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.

Revision history

  • 2022-02-12 Initial publication