https://www.dumas.io/teaching/2021/fall/mcs260/nbview/projects/project3.html

dynam.py
# MCS 260 Fall 2021 Project 3
# Afsah Ahmed
# The code in this file has been written by me and works as per the specifications.
'''
Used to compute the orbit of a given value the function specified by the user.
This module primarily does following tasks:
1. Computing the first n terms of the orbit of a value under the function
2. Determining the initial and cycle for orbit of a value under given function.
3. Determining the length of the perodic cycle.
4. Determining the length of the initial part.
5. Finding all the perodic cycles for a given list of numbers.
'''
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))), ... ]
"""
orbit_values = [x0]
for _ in range(n-1):
temp_val = f(orbit_values[-1])
orbit_values.append(temp_val)
return orbit_values
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.)
"""
#
number_of_points = 100
match_point1 = -1
match_point2 = -1
cycle_items = []
initial_items = []
condition = False
data_dict = dict()
while(not condition):
data = orbit(f, x0, number_of_points)
for i in range(1, number_of_points):
match_point1 = -1
match_point2 = -1
cycle_items = []
for j in range(i):
if(data[i] == data[j]):
match_point1 = i
match_point2 = j
break
if(match_point1 != -1):
point1 = match_point1
point2 = match_point2
while(point1 < number_of_points):
if(point2 == match_point1):
condition = True
break
else:
if(data[point2] == data[point1]):
cycle_items.append(data[point2])
point2 += 1
point1 += 1
else:
break
if(condition):
break
number_of_points *= 10
for i in range(match_point2):
initial_items.append(data[i])
data_dict["initial"] = initial_items
data_dict["cycle"] = cycle_items
return data_dict
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.)
"""
data_dict = orbit_data(f, x0)
return len(data_dict["cycle"])
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.)
"""
data_dict = orbit_data(f, x0)
return len(data_dict["initial"])
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.)
"""
data_dict = orbit_data(f, x0)
return data_dict["cycle"]
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]
"""
smallest_val = min(L)
smallest_index = -1
for i in range(len(L)):
if(L[i] == smallest_val):
smallest_index = i
break
return L[smallest_index:] + L[:smallest_index]
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.
"""
cycles = []
for val in start_vals:
cycle = smallest_first(eventual_cycle(f, val))
if cycle not in cycles:
cycles.append(cycle)
return cycles
project3.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 260 Fall 2021 Project 3\n",
"\n",
"* Course instructor: David 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...