{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 275 Spring 2022 Project 2\n",
"\n",
"* Course instructor: David Dumas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Instructions\n",
"\n",
"### Deadline is 6pm central time on Friday 25 February 2022.\n",
"\n",
"Note that the hour of the deadline is *not* the same as for homework assignments.\n",
"\n",
"### Collaboration policy and academic honesty\n",
"\n",
"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.\n",
"\n",
"### Topic\n",
"\n",
"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.\n",
"\n",
"### Resources you are allowed to consult\n",
"\n",
"* Documents and videos posted to the course web page\n",
"* Any of the optional textbooks listed on the course web page\n",
"\n",
"**Ask** if you are unsure whether a resource falls under one of these categories, or if you think I missed an essential resource.\n",
"\n",
"### What to do if you are stuck\n",
"\n",
"Contact the instructor or your TA by email, in office hours, or on discord."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Get the starter pack\n",
"\n",
"The starter pack is available here:\n",
"\n",
"* [MCS 275 Spring 2022 Project 2 Starter Pack](https://www.dumas.io/teaching/2022/spring/mcs275/project2/mcs275proj2starterpack.zip)\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## What to submit\n",
"\n",
"Write a module `intsplit`, in a file called `intsplit.py`, and submit it to Gradescope. That is the only file you should submit.\n",
"\n",
"The module must contain the functions documented in the section [Specification of the module `intsplit`](#Specification-of-the-module-intsplit) below. Before describing those functions, let's discuss the core mathematical ideas they involve."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Integer splittings\n",
"\n",
"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:\n",
"* 8 + 2 + 7\n",
"* 3 + 11 + 3\n",
"* 11 + 3 + 3\n",
"* 17\n",
"* 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1\n",
"\n",
"\n",
"Things to notice:\n",
"* Order matters, i.e. we consider 3+11+3 and 11+3+3 to be different splittings\n",
"* It's allowable to have just one summand (the number itself)\n",
"\n",
"For another example, here are *all* of the splittings of 5:\n",
"* 5\n",
"* 4 + 1\n",
"* 3 + 2\n",
"* 2 + 3\n",
"* 1 + 4\n",
"* 3 + 1 + 1\n",
"* 2 + 2 + 1\n",
"* 2 + 1 + 2\n",
"* 1 + 3 + 1\n",
"* 1 + 2 + 2\n",
"* 1 + 1 + 3\n",
"* 2 + 1 + 1 + 1\n",
"* 1 + 2 + 1 + 1\n",
"* 1 + 1 + 2 + 1\n",
"* 1 + 1 + 1 + 2\n",
"* 1 + 1 + 1 + 1 + 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Constrained splittings\n",
"\n",
"We'll consider several restricted types of splittings.\n",
"\n",
"To fix terminology, in a splitting like 8+2+7, the individual summands 8, 2, and 7 will be called the **parts**.\n",
"\n",
"### Splittings into distinct parts\n",
"\n",
"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:\n",
"* 6\n",
"* 5 + 1\n",
"* 4 + 2\n",
"* 2 + 4\n",
"* 1 + 5\n",
"* 3 + 2 + 1\n",
"* 3 + 1 + 2\n",
"* 2 + 3 + 1\n",
"* 2 + 1 + 3\n",
"* 1 + 3 + 2\n",
"* 1 + 2 + 3\n",
"\n",
"Every other splitting of 6 has some duplicated part. Notice we consider the splitting into one part (6 by itself) to have \"distinct parts\".\n",
"\n",
"### Splittings with a limited set of parts\n",
"\n",
"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:\n",
"* 2 + 4\n",
"* 4 + 2\n",
"* 3 + 3\n",
"* 2 + 2 + 2\n",
"\n",
"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.\n",
"\n",
"### Splittings with a limited set of parts that are also distinct\n",
"\n",
"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:\n",
"* 6\n",
"* 2 + 4\n",
"* 4 + 2\n",
"\n",
"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.\n",
"\n",
"### Splittings with a limited number of parts\n",
"\n",
"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:\n",
"* 6\n",
"* 1 + 5\n",
"* 2 + 4\n",
"* 3 + 3\n",
"* 4 + 2\n",
"* 5 + 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Specification of the module `intsplit`\n",
"\n",
"The module must contain functions\n",
"* `splittings`\n",
"* `splittings_iterative`\n",
"* `splittings_memoized`\n",
"* `splittings_distinct`\n",
"* `splittings_into`\n",
"* `splittings_distinct_into`\n",
"* `splittings_limited_size`\n",
"\n",
"described below. In short, they compute splittings with any or all of the constraints descibed above.\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings`\n",
"\n",
"#### Arguments\n",
"\n",
"* `n`, a positive integer\n",
"\n",
"#### Behavior\n",
"\n",
"* If `n` is less than or equal to zero, raises `ValueError`\n",
"* 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.\n",
"* **Must use recursion.**\n",
"\n",
"#### Sample output\n",
"\n",
"* `splittings(3)` returns `[[3], [1, 2], [1, 1, 1], [2, 1]]` or some other list containining the same elements but in a different order.\n",
"\n",
"* `splittings(1)` returns `[[1]]` (the list with one element, where that element is the list `[1]`)\n",
"\n",
"#### Warning\n",
"* 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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings_iterative`\n",
"\n",
"Exactly the same specifications as `splittings`, except that this one should be implemented using only iteration, no recursion.\n",
"\n",
"**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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings_memoized`\n",
"\n",
"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.\n",
"\n",
"**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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings_distinct`\n",
"\n",
"#### Arguments\n",
"\n",
"* `n`, a positive integer\n",
"\n",
"#### Behavior\n",
"\n",
"* If `n` is less than or equal to zero, raises `ValueError`\n",
"* Otherwise, returns a list of all splittings of `n` with distinct parts.\n",
"* **Must use recursion.**\n",
"* **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.*\n",
"\n",
"#### Sample output\n",
"\n",
"* `splittings_distinct(3)` returns `[[3], [1, 2], [2, 1]]` or some other list containining the same elements but in a different order.\n",
"\n",
"* `splittings_distinct(2)` returns `[[2]]`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings_into`\n",
"\n",
"#### Arguments\n",
"\n",
"* `n`, a positive integer\n",
"* `parts`, a list of distinct integers\n",
"\n",
"#### Behavior\n",
"\n",
"* If `n` is less than or equal to zero, raises `ValueError`\n",
"* 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.\n",
"* **Must use recursion.**\n",
"* **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.*\n",
"\n",
"#### Sample output\n",
"\n",
"* `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.\n",
"\n",
"* `splittings_into(6,[4,5])` returns `[]` (an empty list, because no splittings of 6 satisfy that condition!)\n",
"\n",
"* `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)\n",
"\n",
"* `splittings_into(6,[3,5])` returns `[[3,3]]` (notice that there are elements in `parts` that end up going unused, i.e. 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings_distinct_into`\n",
"\n",
"#### Arguments\n",
"\n",
"* `n`, a positive integer\n",
"* `parts`, a list of distinct integers that are allowed as parts\n",
"* **Must use recursion.**\n",
"* **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.*\n",
"\n",
"#### Behavior\n",
"\n",
"* If `n` is less than or equal to zero, raises `ValueError`\n",
"* Otherwise, returns a list of all splittings of `n` into **distinct** parts that also belong to the list `parts`. \n",
"* **Must use recursion.**\n",
"\n",
"#### Sample output\n",
"\n",
"* `splittings_distinct_into(6,[2,4,3])` returns `[[2, 4], [4, 2]]` or `[[4, 2], [2, 4]]`\n",
"\n",
"* `splittings_distinct_into(6,[2,3])` returns `[]` (an empty list, because no splittings of 6 satisfy that condition!)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Function `splittings_limited_size`\n",
"\n",
"#### Arguments\n",
"\n",
"* `n`, a positive integer\n",
"* `maxparts`, an integer specifying the maximum number of parts allowed\n",
"\n",
"#### Behavior\n",
"\n",
"* If `n` is less than or equal to zero, raises `ValueError`\n",
"* Otherwise, returns a list of all splittings of `n` that have at most `maxparts` parts in them.\n",
"* **Must use recursion.**\n",
"* **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.*\n",
"\n",
"#### Sample output\n",
"\n",
"* `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\n",
"```\n",
"[[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]]\n",
"```\n",
"\n",
"* `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.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The demonstration script\n",
"\n",
"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.\n",
"\n",
"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.\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## IMPORTANT RULES YOUR CODE MUST FOLLOW\n",
"\n",
"Your project must follow the 7 rules in the [MCS 275 coding standards](https://www.dumas.io/teaching/2022/spring/mcs275/doc/codestd.pdf) document. In addition:\n",
"\n",
"* **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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## How your project will be graded\n",
"\n",
"### Autograder: 55 points\n",
"\n",
"The autograder tests your program and grades it based on its **behavior**. The following tests will be run:\n",
"\n",
"1. Was a file called `intsplit.py` submitted? (**5 points**)\n",
"1. Does the Python interpreter accept the contents of `intsplit.py` as valid Python code? (**5 points**)\n",
"1. Does `intsplit.py` contain docstrings for all classes, functions, and methods? (**5 points**)\n",
"1. Can `intsplit.py` be imported without raising an exception? (**5 points**)\n",
"1. Functional tests of the seven required functions (**35 points** total, several tests of each function)\n",
"\n",
"### Manual review: 20 points\n",
"\n",
"1. **10 points** based on checking that you followed important specifications that can't be easily tested by the autograder:\n",
" * using recursion or iteration or memoization as specified\n",
" * never generating a larger list of splittings and filtering it to a smaller list to return\n",
"1. **10 points** The usual manual review of code standards adherance, docstring accuracy, formatting, correctness issues possibly missed by the autograder"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Final word: Submit before deadline\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Revision history\n",
"\n",
"* 2022-02-12 Initial publication"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}