A document from MCS 260 Fall 2021, instructor Emily Dumas. You can also get the notebook file.

MCS 260 Fall 2021 Project 3

  • Course instructor: Emily Dumas

Instructions

Deadline is 6pm CDT on Friday November 5, 2021

Detailed schedule:

  • Oct 18: Last lecture whose material is needed for this project (Lecture 24)
  • Oct 22: Project description released
  • Nov 1: Autograder opens
  • Nov 3: Date by which you should make your first autograder submission (if you're following the schedule I suggest)
  • Nov 5, 11:00-11:50am: My last office hours before the deadline
  • Nov 5, 1:30pm: Latest time you can count on reaching me by email
  • Nov 5, 6:00pm: Deadline for final submission

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.

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
  • Instructor or TA

Ask if you are unsure whether a resource falls under one of these categories.

What to submit

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.

Intro: Iterating a function

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:

  • The initial part, before anything repeats: $ 50, 37, 43, 29, 55, 40 $
  • The periodic cycle, a finite list of values that repeat forever, and which begins immediately after the initial part: $ 28, 46, 41 $

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

Your task: A module for studying orbits and cycles

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:

In [3]:
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))
[3, 9, 81, 6561, 43046721, 1853020188851841, 3433683820292512484657849089281, 11790184577738583171520872861412518665678211592275841109096961]

Or, the very same function orbit from module dynam could be used to study orbits of the mwdp function like this:

In [5]:
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))
[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]

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.

One more thing about cycles

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

The skeleton of module 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.

In [7]:
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

Advice

Work in order

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.

Functions can call each other

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_period
    • steps_to_enter_cycle
    • eventual_cycle
  • I suggest you use both eventual_cycle and smallest_first inside find_cycles

Make some tests

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.

IMPORTANT: Code structure and style requirements

Required header

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 DECLARATION

In 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).

Use of docstrings

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.

Clean import

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.

Use good variable names

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.

Use comments to explain, not to disable code

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.

How your project will be graded

Autograder: 60 points

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

  1. Was a file called dynam.py submitted? (5 points)
  2. Does the Python interpreter accept the contents of dynam.py as valid Python code? (5 points)
  3. Does dynam.py have a docstring for the file, and a docstring in every function? (5 points)
  4. Is it possible to import dynam.py as a module, without it exiting with an error? (5 points)
  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.

Manual review: 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).

Revision history

  • 2021-10-22 Initial publication
  • 2021-10-24 Add note that no new functions should be added to the skeleton and more advice about local testing