{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 260 Fall 2021 Project 3\n",
"\n",
"* Course instructor: Emily Dumas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Instructions\n",
"\n",
"### Deadline is 6pm CDT on Friday November 5, 2021\n",
"\n",
"### Detailed schedule:\n",
"\n",
"* Oct 18: Last lecture whose material is needed for this project ([Lecture 24](https://www.dumas.io/teaching/2021/fall/mcs260/slides/lecture24.html#/))\n",
"* Oct 22: Project description released\n",
"* Nov 1: Autograder opens\n",
"* Nov 3: Date by which you should make your first autograder submission (if you're following the schedule I suggest)\n",
"* Nov 5, 11:00-11:50am: My last office hours before the deadline\n",
"* Nov 5, 1:30pm: Latest time you can count on reaching me by email\n",
"* Nov 5, 6:00pm: Deadline for final submission\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",
"### 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",
"* Instructor or TA\n",
"\n",
"**Ask** if you are unsure whether a resource falls under one of these categories."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## What to submit\n",
"\n",
"The rest of this document describes a module `dynam` that you need to write. It should be contained in a single file called `dynam.py`. That's the only thing you need to submit to gradescope."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Intro: Iterating a function\n",
"\n",
"This project is about taking a function of one variable, say $f(x)$, and applying it repeatedly to some starting value $x_0$. When you do that, you get an infinite sequence of values\n",
"$$x_0, f(x_0), f(f(x_0)), f(f(f(x_0))), ...$$\n",
"which is called the **orbit of $x_0$ under $f$**.\n",
"\n",
"For this project, the functions we'll consider are ones that take an integer as input and produce an integer as output. So, for example, if $f(x) = x^2$ then the orbit of $3$ is the sequence\n",
"\n",
"$$ 3, 9, 81, 6561, 43046721, 1853020188851841, 3433683820292512484657849089281, ... $$\n",
"\n",
"These numbers keep getting bigger, never repeating. But here's another example. Consider the function $mwdp(x)$ that was defined in [Project 1](https://www.dumas.io/teaching/2021/fall/mcs260/nbview/projects/project1.html). If you apply that function repeatedly to the starting value $x_0 = 50$, then you get this sequence (which is the orbit of $50$ under $mwdp$):\n",
"\n",
"$$ 50, 37, 43, 29, 55, 40, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, ... $$\n",
"\n",
"Notice that this sequence wanders around for a while but eventually settles into a pattern where $46, 41, 28$ just repeats forever. We could therefore split the orbit up into two parts:\n",
"* The **initial part**, before anything repeats: $ 50, 37, 43, 29, 55, 40 $\n",
"* The **periodic cycle**, a finite list of values that repeat forever, and which begins immediately after the initial part: $ 28, 46, 41 $\n",
"\n",
"Let's consider one more example. Define a function\n",
"$$ g(x) = \\begin{cases}\n",
"x/2 & \\text{if $x$ is even} \\\\\n",
"3x+1 & \\text{ if $x$ is odd}\n",
"\\end{cases}\n",
"$$\n",
"Then the orbit of $17$ under $g$ looks like this:\n",
"\n",
"$$\n",
"17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, ...\n",
"$$\n",
"\n",
"In this case, the initial part is $17, 52, 26, 13, 40, 20, 10, 5, 16, 8$ followed by the periodic cycle $4,2,1$.\n",
"\n",
"It's possible for a cycle to have just one element, as well. That's called a **fixed point**. For example, if the orbit under some function was\n",
"\n",
"$$\n",
"5, 11, 29, 25, 25, 25, 25, 25, 25, 25, 25, 25, ...\n",
"$$\n",
"\n",
"then we'd say the orbit has initial part $5, 11, 29$ and then a periodic cycle of length one, $25$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Your task: A module for studying orbits and cycles\n",
"\n",
"**This project is not about iterating any particular function, like $f(x) = x^2$ or $mwdp(x)$ or $g(x)$.** Instead, it's about writing a module of functions that you can use to study the iteration of whatever function you are interested in. For example, the module `dynam` you need to write is going to contain a function `orbit(f,x0,n)` that computes the first `n` terms of the orbit of `x0` under function `f`. It could be used like this to study the orbits of the squaring function:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 9, 81, 6561, 43046721, 1853020188851841, 3433683820292512484657849089281, 11790184577738583171520872861412518665678211592275841109096961]\n"
]
}
],
"source": [
"import dynam\n",
"\n",
"def f(x):\n",
" \"\"\"square x\"\"\"\n",
" return x*x\n",
" \n",
"# First 8 terms in the orbit of 3 under f\n",
"print(dynam.orbit(f,3,8))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Or, the very same function `orbit` from module `dynam` could be used to study orbits of the `mwdp` function like this:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[50, 37, 43, 29, 55, 40, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41]\n"
]
}
],
"source": [
"import dynam\n",
"\n",
"def mwdp(x):\n",
" \"\"\"mean with digit power\"\"\"\n",
" digits = [int(c) for c in str(x)]\n",
" maxdigit = max(digits)\n",
" numdigits = len(digits)\n",
" return (x + maxdigit ** numdigits) // 2\n",
" \n",
"# First 30 terms in the orbit of 50 under mwdp\n",
"print(dynam.orbit(mwdp,50,30))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So `dynam.orbit` is an example of a *higher-order function*: One of its arguments is a function, and it uses that function to do its work. A program using `dynam.orbit` can specify any function it likes.\n",
"\n",
"Below you'll find the **skeleton** for the module `dynam`. It contains function definitions and docstrings, but the functions lack bodies. You are expected to fill in the bodies of the functions so that they work exactly as the docstrings say they do."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## One more thing about cycles\n",
"\n",
"Two orbits of a function might end up in the same repeating cycle but enter the cycle at different places. For example, considering the function $mwdp(x)$, the orbit of $39$ is:\n",
"\n",
"$$39, 60, 48, 56, \\mathbf{46}, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, ...$$\n",
"\n",
"while we saw earlier that the orbit of $50$ is:\n",
"\n",
"$$50, 37, 43, 29, 55, 40, \\mathbf{28}, 46, 41, 28, 46, 41, 28, 46, 41, 28, ...$$\n",
"\n",
"These are obviously very similar, because they enter the same repeating pattern. But the orbit of $39$ first hits the cycle at the number $46$, while the orbit of $50$ first hits the cycle at $28$. (In both cases the first number from the periodic cycle that appears in the orbit is shown in bold.)\n",
"\n",
"The reason you need to care about this is that the skeleton for the module `dynam` contains some functions that deal with splitting an orbit into an initial part and repeating cycle; those functions need to notice the place where the repeating pattern begins. However, it also contains some functions that search many starting points to see what cycles are seen. Those functions would not consider the cycle `[46,41,28]` to be different from `[28,46,41]`, because they represent the same repeating pattern (just starting at a different spot)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The skeleton of module `dynam`\n",
"\n",
"Copy the code below into your `dynam.py` file. Don't change the function names or docstrings, but fill in the bodies of the functions so they do what the docstrings explain.\n",
"\n",
"Don't add any new functions ot the module, either. You are encouraged to write some test code that checks whether the module's functions work, and that test code will need to define some functions (to have something to pass as `f`), but you should keep those tests separate from the module itself."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def orbit(f,x0,n):\n",
" \"\"\"\n",
" Compute the first `n` terms of the orbit of `x0` under\n",
" the function `f`.\n",
" Arguments:\n",
" `f` - a function (should take one integer argument and return an integer)\n",
" `x0` - a value of the type that `f` accepts as its argument\n",
" `n` - the number of points to compute (a positive integer)\n",
" Returns:\n",
" A list of length `n` containing the values [ x0, f(x0), f(f(x0)), f(f(f(x0))), ... ]\n",
" \"\"\"\n",
" # PUT THE BODY OF orbit HERE AND DELETE THIS LINE\n",
"\n",
"\n",
"def orbit_data(f,x0):\n",
" \"\"\"\n",
" Repeatedly apply function `f` to initial value `x0` until some\n",
" value is seen twice. Return dictionary of data about the observed\n",
" behavior.\n",
"\n",
" Arguments:\n",
" `f` - a function (should take one integer argument and return an integer)\n",
" `x0` - a value of the type that `f` accepts as its argument\n",
"\n",
" Returns:\n",
" Dictionary with the following keys (after each key is a description of\n",
" the associated value):\n",
" \"initial\": The part of the orbit up to, but not including, the first\n",
" value that is ever repeated.\n",
" \"cycle\": The part of the orbit between the first and second instances of\n",
" the first value that appears twice, including the first but not the\n",
" second. In other words, the entire orbit consits of the \"initial\"\n",
" part followed by the \"cycle\" repeating over and over again.\n",
"\n",
" Example: Suppose that applying f repeatedly to start value 11 gives this sequence:\n",
" 11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...\n",
"\n",
" Then the return value would be:\n",
" {\n",
" \"initial\":[11, 31, 12, 5, 6, 2],\n",
" \"cycle\": [8,19,17]\n",
" }\n",
" \n",
" (If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever\n",
" trying to find one.)\n",
" \"\"\"\n",
" # PUT THE BODY OF orbit_data HERE AND DELETE THIS LINE\n",
" \n",
"\n",
"def eventual_period(f,x0):\n",
" \"\"\"\n",
" Determine the length of the periodic cycle that `x0` ends up in.\n",
" \n",
" Arguments:\n",
" `f` - a function (should take one integer argument and return an integer)\n",
" `x0` - a value of the type that `f` accepts as its argument\n",
"\n",
" Returns:\n",
" The length of the periodic cycle that the orbit of `x0` ends up in.\n",
"\n",
" Example: Suppose that applying f repeatedly to start value 11 gives this sequence:\n",
" 11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...\n",
" \n",
" Then the return value of eventual_period(f,11) would be 3, since the periodic\n",
" cycle contains the 3 values 8,19,17.\n",
" \n",
" (If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever\n",
" trying to find one.)\n",
" \"\"\"\n",
" # PUT THE BODY OF eventual_period HERE AND DELETE THIS LINE\n",
"\n",
" \n",
"def steps_to_enter_cycle(f,x0):\n",
" \"\"\"\n",
" Determine the length of the intial part of the orbit of `x0` under `f` before\n",
" it enters a periodic cycle.\n",
" \n",
" Arguments:\n",
" `f` - a function (should take one integer argument and return an integer)\n",
" `x0` - a value of the type that `f` accepts as its argument\n",
"\n",
" Returns:\n",
" The number of elements of the orbit of `f` before the first value that \n",
" repeats.\n",
" \n",
" Example: Suppose that applying f repeatedly to start value 11 gives this sequence:\n",
" 11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...\n",
" \n",
" Then the return value of steps_to_enter_cycle(f,11) would be 6, because there are 6\n",
" values in the intial segment of the orbit (i.e. 11, 31, 12, 5, 6, 2) which are followed by\n",
" a periodic cycle.\n",
" \n",
" (If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever\n",
" trying to find one.)\n",
" \"\"\"\n",
" # PUT THE BODY OF steps_to_enter_cycle HERE AND DELETE THIS LINE\n",
"\n",
"\n",
"def eventual_cycle(f,x0):\n",
" \"\"\"\n",
" Return the periodic cycle that the orbit of x0 ends up in as a list.\n",
" \n",
" Arguments:\n",
" `f` - a function (should take one integer argument and return an integer)\n",
" `x0` - a value of the type that `f` accepts as its argument\n",
"\n",
" Returns:\n",
" The earliest segment from the orbit of `x0` under `f` that repeats\n",
" indefinitely thereafter, as a list.\n",
" \n",
" Example: Suppose that applying f repeatedly to start value 11 gives this sequence:\n",
" 11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...\n",
" \n",
" Then eventual_cycle(f,x0) would return [8, 19, 17].\n",
" \n",
" (If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever\n",
" trying to find one.)\n",
" \"\"\"\n",
" # PUT THE BODY OF eventual_cycle HERE AND DELETE THIS LINE\n",
" \n",
" \n",
"def smallest_first(L):\n",
" \"\"\"\n",
" Rotates a list so that its smallest element appears first.\n",
" \n",
" Arguments:\n",
" `L`: A list of integers, no two of them equal\n",
" \n",
" Returns:\n",
" A list that is the result of moving the first element of `L` to the end,\n",
" repeatedly, until the first element of `L` is the smallest element of the list.\n",
" \n",
" Example: smallest_first([46,41,28]) returns [28,46,41]\n",
" Example: smallest_first([4,2,1]) returns [1,4,2]\n",
" Example: smallest_first([9,8,7,6,5,4,3,2,1]) returns [1,9,8,7,6,5,4,3,2]\n",
" \"\"\"\n",
" # PUT THE BODY OF smallest_first HERE AND DELETE THIS LINE\n",
"\n",
"\n",
"def find_cycles(f,start_vals):\n",
" \"\"\"\n",
" Find all the periodic cycles of the function `f` that appear when you consider\n",
" orbits of the elements of `start_vals`.\n",
" \n",
" Arguments:\n",
" `f` - a function (should take one integer argument and return an integer)\n",
" `start_vals` - a list of integers to use as starting values\n",
"\n",
" Returns:\n",
" A list of lists, consisting of all the periodic cycles that are seen\n",
" in the orbits of the start values from `start_vals`. Each cycle is \n",
" given with its smallest entry appearing first, and any given cycle\n",
" appears only once in the list.\n",
" \n",
" e.g. If `mwdp` is the mean with digit power function, then find_cycles(mwdp,[65,66,67])\n",
" would return [ [28,46,41], [38,51] ] because both 65 and 67 end up in the [28,46,41]\n",
" cycle and 66 ends up in the [38,51] cycle.\n",
" \"\"\"\n",
" # PUT THE BODY OF find_cycles HERE AND DELETE THIS LINE"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Advice\n",
"\n",
"\n",
"### Work in order\n",
"I suggest you write the functions in the order shown in the skeleton, i.e. work from top to bottom.\n",
"\n",
"The function `orbit_data` is probably the hardest to write, with `find_cycles` second hardest.\n",
"\n",
"\n",
"### Functions can call each other\n",
"You can, and should, have some of the functions in your module call other functions! Specifically:\n",
"\n",
"* I suggest you use the function `orbit_data` inside these functions:\n",
" * `eventual_period`\n",
" * `steps_to_enter_cycle`\n",
" * `eventual_cycle`\n",
" \n",
"* I suggest you use both `eventual_cycle` and `smallest_first` inside `find_cycles`\n",
"\n",
"### Make some tests\n",
"The functions in your module `dynam` probably won't work perfectly the first time. Testing in the REPL is possible, but tedious. You'd need to open the Python interpreter, import the module, define a function of an integer argument, and then apply one of the functions from `dynam` to the function you defined.\n",
"\n",
"Using the autograder as your only way of testing has its own problems: It isn't available until Nov 1, it's slow, and if your program has unexpected types of errors (like syntax problems), it can be hard to understand where the problem is based on the autograder's report.\n",
"\n",
"For all these reasons, you should test your work locally, on whatever computer you use to write code. Submit to the autograder when things appear to be working locally.\n",
"\n",
"For local testing, I recommend you make a script called `test_dynam.py` that imports `dynam`, defines some functions of an integer argument to use with it, and then calls various functions from `dynam`. It should probably print the results. That way, each time you finish a function in `dynam`, you can save it, run `python3 test_dynam.py` in the terminal, and see if the results match your expectations.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## IMPORTANT: Code structure and style requirements\n",
"\n",
"\n",
"### Required header\n",
"The first three lines of your Python program must be comments in the following format:\n",
"\n",
"```\n",
"# MCS 260 Fall 2021 Project 3\n",
"# Full Name\n",
"# REPLACE THIS WITH YOUR INDIVIDUAL WORK DECLARATION\n",
"```\n",
"\n",
"In the second line, replace `Full Name` with your full name.\n",
"\n",
"In the third line, replace the all-caps comment with a single full sentence, written in your own words, explaining that makes an accurate statement about whether or not you completed the project individually and followed the rules in the syllabus and project description.\n",
"\n",
"These comments should be immediately followed by a file-level docstring (as explained below).\n",
"\n",
"### Use of docstrings\n",
"\n",
"The file `dynam.py` must have a docstring at the file level (i.e. first statement must be a string literal describing what it does).\n",
"\n",
"The functions must have the same docstrings shown in the skeleton above.\n",
"\n",
"\n",
"### Clean import\n",
"\n",
"Importing the module `dynam` shouldn't do anything other than define functions. It's a really good idea for you to write code to test the functions, but that should either be in another file or protected by the `if __name__==\"__main__\":` idiom so it only runs when `dynam.py` is the main script.\n",
"\n",
"### Use good variable names\n",
"\n",
"You are expected to choose variable names that communicate a variable's purpose in a concise way, but without being too terse. Uninformative low-effort names like `intvar` or `mystring` are not acceptable. Single-letter variable names can be used, but sparingly, and should usually be avoided for lists or other complex data structures. Most of the time, a good variable name will be a single word or compound word, like `cycles` or `iterates`, but descriptive multiword names are also acceptable.\n",
"\n",
"### Use comments to explain, not to disable code\n",
"\n",
"You are encouraged, but not required, to include comments that contain explanatory text.\n",
"\n",
"Do not use comments to disable code that you don't want to run. Instead, remove such code before submitting."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## How your project will be graded\n",
"\n",
"### Autograder: 60 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 `dynam.py` submitted? (**5 points**)\n",
"2. Does the Python interpreter accept the contents of `dynam.py` as valid Python code? (**5 points**)\n",
"3. Does `dynam.py` have a docstring for the file, and a docstring in every function? (**5 points**)\n",
"4. Is it possible to import `dynam.py` as a module, without it exiting with an error? (**5 points**)\n",
"5. Operational tests (at least two tests for each function, **40 points total**): The autograder will call functions from your module on sample inputs and test they they produce the expected output.\n",
"\n",
"\n",
"### Manual review: 5 points\n",
"\n",
"I will review your code and look for adherence to the style guidelines given above, and examine your method for accomplishing the requested task in each function. If I see a function does not do what was requested in this document, but the error was not detected in the automated testing, a deduction may be given at this point. The scores assigned by the autograder will not be changed during manual review unless I discover some kind of intentional wrongdoing (such as an attempt to circumvent or reverse-engineer the autograder's operation)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Revision history\n",
"\n",
"* 2021-10-22 Initial publication\n",
"* 2021-10-24 Add note that no new functions should be added to the skeleton and more advice about local testing"
]
}
],
"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
}