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.
Ask if you are unsure whether a resource falls under one of these categories.
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.
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 $$x_0, f(x_0), f(f(x_0)), f(f(f(x_0))), ...$$ which is called the orbit of $x_0$ under $f$.
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
$$ 3, 9, 81, 6561, 43046721, 1853020188851841, 3433683820292512484657849089281, ... $$These numbers keep getting bigger, never repeating. But here's another example. Consider the function $mwdp(x)$ that was defined in Project 1. 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$):
$$ 50, 37, 43, 29, 55, 40, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, ... $$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:
Let's consider one more example. Define a function $$ g(x) = \begin{cases} x/2 & \text{if $x$ is even} \\ 3x+1 & \text{ if $x$ is odd} \end{cases} $$ Then the orbit of $17$ under $g$ looks like this:
$$ 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, ... $$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$.
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
$$ 5, 11, 29, 25, 25, 25, 25, 25, 25, 25, 25, 25, ... $$then we'd say the orbit has initial part $5, 11, 29$ and then a periodic cycle of length one, $25$.
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:
import dynam
def f(x):
"""square x"""
return x*x
# First 8 terms in the orbit of 3 under f
print(dynam.orbit(f,3,8))
Or, the very same function orbit from module dynam could be used to study orbits of the mwdp function like this:
import dynam
def mwdp(x):
"""mean with digit power"""
digits = [int(c) for c in str(x)]
maxdigit = max(digits)
numdigits = len(digits)
return (x + maxdigit ** numdigits) // 2
# First 30 terms in the orbit of 50 under mwdp
print(dynam.orbit(mwdp,50,30))
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.
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.
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:
$$39, 60, 48, 56, \mathbf{46}, 41, 28, 46, 41, 28, 46, 41, 28, 46, 41, 28, ...$$while we saw earlier that the orbit of $50$ is:
$$50, 37, 43, 29, 55, 40, \mathbf{28}, 46, 41, 28, 46, 41, 28, 46, 41, 28, ...$$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.)
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).
dynam¶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.
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.
def orbit(f,x0,n):
"""
Compute the first `n` terms of the orbit of `x0` under
the function `f`.
Arguments:
`f` - a function (should take one integer argument and return an integer)
`x0` - a value of the type that `f` accepts as its argument
`n` - the number of points to compute (a positive integer)
Returns:
A list of length `n` containing the values [ x0, f(x0), f(f(x0)), f(f(f(x0))), ... ]
"""
# PUT THE BODY OF orbit HERE AND DELETE THIS LINE
def orbit_data(f,x0):
"""
Repeatedly apply function `f` to initial value `x0` until some
value is seen twice. Return dictionary of data about the observed
behavior.
Arguments:
`f` - a function (should take one integer argument and return an integer)
`x0` - a value of the type that `f` accepts as its argument
Returns:
Dictionary with the following keys (after each key is a description of
the associated value):
"initial": The part of the orbit up to, but not including, the first
value that is ever repeated.
"cycle": The part of the orbit between the first and second instances of
the first value that appears twice, including the first but not the
second. In other words, the entire orbit consits of the "initial"
part followed by the "cycle" repeating over and over again.
Example: Suppose that applying f repeatedly to start value 11 gives this sequence:
11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...
Then the return value would be:
{
"initial":[11, 31, 12, 5, 6, 2],
"cycle": [8,19,17]
}
(If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever
trying to find one.)
"""
# PUT THE BODY OF orbit_data HERE AND DELETE THIS LINE
def eventual_period(f,x0):
"""
Determine the length of the periodic cycle that `x0` ends up in.
Arguments:
`f` - a function (should take one integer argument and return an integer)
`x0` - a value of the type that `f` accepts as its argument
Returns:
The length of the periodic cycle that the orbit of `x0` ends up in.
Example: Suppose that applying f repeatedly to start value 11 gives this sequence:
11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...
Then the return value of eventual_period(f,11) would be 3, since the periodic
cycle contains the 3 values 8,19,17.
(If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever
trying to find one.)
"""
# PUT THE BODY OF eventual_period HERE AND DELETE THIS LINE
def steps_to_enter_cycle(f,x0):
"""
Determine the length of the intial part of the orbit of `x0` under `f` before
it enters a periodic cycle.
Arguments:
`f` - a function (should take one integer argument and return an integer)
`x0` - a value of the type that `f` accepts as its argument
Returns:
The number of elements of the orbit of `f` before the first value that
repeats.
Example: Suppose that applying f repeatedly to start value 11 gives this sequence:
11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...
Then the return value of steps_to_enter_cycle(f,11) would be 6, because there are 6
values in the intial segment of the orbit (i.e. 11, 31, 12, 5, 6, 2) which are followed by
a periodic cycle.
(If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever
trying to find one.)
"""
# PUT THE BODY OF steps_to_enter_cycle HERE AND DELETE THIS LINE
def eventual_cycle(f,x0):
"""
Return the periodic cycle that the orbit of x0 ends up in as a list.
Arguments:
`f` - a function (should take one integer argument and return an integer)
`x0` - a value of the type that `f` accepts as its argument
Returns:
The earliest segment from the orbit of `x0` under `f` that repeats
indefinitely thereafter, as a list.
Example: Suppose that applying f repeatedly to start value 11 gives this sequence:
11, 31, 12, 5, 6, 2, 8, 19, 17, 8, 19, 17, 8, 19, 17, 8, ...
Then eventual_cycle(f,x0) would return [8, 19, 17].
(If the orbit of `x0` doesn't end up in a cycle, it's ok for this function to run forever
trying to find one.)
"""
# PUT THE BODY OF eventual_cycle HERE AND DELETE THIS LINE
def smallest_first(L):
"""
Rotates a list so that its smallest element appears first.
Arguments:
`L`: A list of integers, no two of them equal
Returns:
A list that is the result of moving the first element of `L` to the end,
repeatedly, until the first element of `L` is the smallest element of the list.
Example: smallest_first([46,41,28]) returns [28,46,41]
Example: smallest_first([4,2,1]) returns [1,4,2]
Example: smallest_first([9,8,7,6,5,4,3,2,1]) returns [1,9,8,7,6,5,4,3,2]
"""
# PUT THE BODY OF smallest_first HERE AND DELETE THIS LINE
def find_cycles(f,start_vals):
"""
Find all the periodic cycles of the function `f` that appear when you consider
orbits of the elements of `start_vals`.
Arguments:
`f` - a function (should take one integer argument and return an integer)
`start_vals` - a list of integers to use as starting values
Returns:
A list of lists, consisting of all the periodic cycles that are seen
in the orbits of the start values from `start_vals`. Each cycle is
given with its smallest entry appearing first, and any given cycle
appears only once in the list.
e.g. If `mwdp` is the mean with digit power function, then find_cycles(mwdp,[65,66,67])
would return [ [28,46,41], [38,51] ] because both 65 and 67 end up in the [28,46,41]
cycle and 66 ends up in the [38,51] cycle.
"""
# PUT THE BODY OF find_cycles HERE AND DELETE THIS LINE
I suggest you write the functions in the order shown in the skeleton, i.e. work from top to bottom.
The function orbit_data is probably the hardest to write, with find_cycles second hardest.
You can, and should, have some of the functions in your module call other functions! Specifically:
I suggest you use the function orbit_data inside these functions:
eventual_periodsteps_to_enter_cycleeventual_cycleI suggest you use both eventual_cycle and smallest_first inside find_cycles
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.
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.
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.
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.
The first three lines of your Python program must be comments in the following format:
# MCS 260 Fall 2021 Project 3
# Full Name
# REPLACE THIS WITH YOUR INDIVIDUAL WORK DECLARATIONIn the second line, replace Full Name with your full name.
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.
These comments should be immediately followed by a file-level docstring (as explained below).
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).
The functions must have the same docstrings shown in the skeleton above.
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.
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.
You are encouraged, but not required, to include comments that contain explanatory text.
Do not use comments to disable code that you don't want to run. Instead, remove such code before submitting.
The autograder tests your program and grades it based on its behavior. The following tests will be run:
dynam.py submitted? (5 points)dynam.py as valid Python code? (5 points)dynam.py have a docstring for the file, and a docstring in every function? (5 points)dynam.py as a module, without it exiting with an error? (5 points)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).