{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 275 Spring 2022 Worksheet 2\n",
"\n",
"* Course instructor: David Dumas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Topics\n",
"\n",
"Like worksheet 1, this worksheet consists of Python programming exercises on topics typically covered in prerequisite courses of MCS 275. Compared to worksheet 1, this one is a bit more complex and the problems are more open-ended.\n",
"\n",
"### Where's the new material?\n",
"\n",
"Each worksheet covers the previous week's lecture material. Last week's lectures were used to review some MCS 260 topics, so we still don't have new material to cover this time."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Resources\n",
"\n",
"These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.\n",
"\n",
"* [MCS 275 Python Tour](https://www.dumas.io/teaching/2022/spring/mcs275/nbview/samplecode/python_tour.html)\n",
"* [Downey's book](https://greenteapress.com/thinkpython2/html/)\n",
"* MCS 260 course materials from Fall 2021:\n",
" * [Slides, homework, worksheets, and projects](https://www.dumas.io/teaching/2021/fall/mcs260/)\n",
" * [Sample programs](https://github.com/daviddumas/mcs260fall2021/tree/main/samplecode)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Increasing run length\n",
"\n",
"Suppose you have a list of integers. Even if the list is not entirely in increasing order, there are sometimes *parts* of the list that are in increasing order.\n",
"\n",
"For example, consider `L = [1,21,4,17,39,35,22,0,6,2,5]`. The list is not in increasing order, but the first two elements (i.e. `L[0:2]` or `[1,21]`) are in increasing order. Also, if you take the slice `L[2:6]`, which is `[4,17,38,39]`, that is in increasing order. \n",
"Let's call a slice of a list that is in increasing order an **increasing run**. In the example given above, the longest increasing run is `L[2:6]`, of length 4.\n",
"\n",
"Write a function `IRL(L)` that takes a list `L` whose elements can be compared to one another (e.g. a mix of integers and floats, or a collection of strings) and returns the length of the longest increasing run within `L`.\n",
"\n",
"Special cases (not necessarily requiring special handling, but explained here to clarify the extremes):\n",
"* If `L` is empty, the function should return 0\n",
"* If `L` is in decreasing order, the function should return 1 because a slice with one element can be considered to be in \"increasing order\", and that would be the longest increasing run.\n",
"\n",
"Here are some sample outputs:"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([40, 1, 63, 20, 53, 9]) # [1,63] and [20,53] are the longest, each has length 2"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([22, 40, 47, 46, 26, 45, 25, 30, 47, 40]) # [22,40,47] and [25, 30, 47] are the longest"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([78, 26, 1, 20, 72, 19, 44, 50, 59, 67]) # [19, 44, 50, 59, 67] is the longest"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([1,2,3,4,5,6,7,8]) # The entire list, of length 8, is increasing!"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([]) # no elements = no increasing runs = max increasing run length 0"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([275]) # [275] is the longest increasing run"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"IRL([10,8,6,4,2]) # [10] and [8] and [6] and [4] and [2] are the longest, each has length 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Hint:** Here is one possible strategy: Use a for loop to scan through the list, keeping track of the current element and the previous one. As you go, make note of how many successive elements have been increasing. Use another variable to hold the largest number of increasing elements seen so far, and update it as needed on each iteration."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Zitterbewegung\n",
"\n",
"*Zitterbewegung is a German word meaning \"jittery motion\".*\n",
"\n",
"This is an exercise in object-oriented programming.\n",
"\n",
"Make a class `ZBPoint` that stores a point `(x,y)` in the plane with integer coordinates.\n",
"\n",
"The constructor should take `(x,y)` as arguments and store them as attributes.\n",
"\n",
"Add a `__str__` method Printing an instance of this class should produce a nice string like\n",
"```\n",
"ZBPoint(17,-2)\n",
"```\n",
"\n",
"Also include a method `.jitter()` that will move the point up, down, left or right by one unit. The direction should be chosen at random (e.g. using `random.choice` or `random.randint` from the random module.)\n",
"\n",
"The code below demonstrates how you would use this class to create a point at `(20,22)` and then let it jitter about for 30 steps, printing the location each time."
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"ZBPoint(20,22)\n",
"ZBPoint(20,21)\n",
"ZBPoint(20,20)\n",
"ZBPoint(19,20)\n",
"ZBPoint(19,19)\n",
"ZBPoint(18,19)\n",
"ZBPoint(18,18)\n",
"ZBPoint(18,19)\n",
"ZBPoint(18,18)\n",
"ZBPoint(19,18)\n",
"ZBPoint(19,19)\n",
"ZBPoint(20,19)\n",
"ZBPoint(19,19)\n",
"ZBPoint(19,20)\n",
"ZBPoint(19,21)\n",
"ZBPoint(18,21)\n",
"ZBPoint(18,22)\n",
"ZBPoint(18,23)\n",
"ZBPoint(17,23)\n",
"ZBPoint(17,22)\n",
"ZBPoint(17,23)\n",
"ZBPoint(18,23)\n",
"ZBPoint(17,23)\n",
"ZBPoint(16,23)\n",
"ZBPoint(17,23)\n",
"ZBPoint(17,22)\n",
"ZBPoint(17,23)\n",
"ZBPoint(17,22)\n",
"ZBPoint(17,23)\n",
"ZBPoint(17,24)\n"
]
}
],
"source": [
"P = ZBPoint(20,22)\n",
"for _ in range(30):\n",
" print(P)\n",
" P.jitter()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Text circles\n",
"\n",
"Write a program `circle.py` that takes one command line argument, `r`, and then prints 40 lines of text, each containing 80 characters. The output should make a picture of a circle, using characters as pixels. When `r=20` the circle should be slightly too big to fit in the block of text, and when `r=1` it should be nearly too small to have any empty space inside.\n",
"\n",
"For example, here is possible output for r=5:\n",
"```\n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" @@@@@@@@@@@ \n",
" @@@@ @@@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@@ @@@@ \n",
" @@@@@@@@@@@ \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
"```\n",
"And here is possible output for r=15:\n",
"```\n",
" \n",
" \n",
" \n",
" \n",
" \n",
" @@@@@@@@@@@@@@@@@ \n",
" @@@@@@@ @@@@@@@ \n",
" @@@@@ @@@@@ \n",
" @@@@ @@@@ \n",
" @@@@ @@@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@ @@ \n",
" @@ @@ \n",
" @@ @@ \n",
" @@@ @@@ \n",
" @@ @@ \n",
" @@ @@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@ @@ \n",
" @@ @@ \n",
" @@@ @@@ \n",
" @@ @@ \n",
" @@ @@ \n",
" @@ @@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@ @@@ \n",
" @@@@ @@@@ \n",
" @@@@ @@@@ \n",
" @@@@@ @@@@@ \n",
" @@@@@@@ @@@@@@@ \n",
" @@@@@@@@@@@@@@@@@ \n",
" \n",
" \n",
" \n",
" \n",
"```\n",
"\n",
"This exercise is deliberately a little vague about how to go about this, but here is a hint: Each character you print corresponds to a certain point (x,y) in the plane, with character 40 on line 20 corresponding to (20,20). Calculating those coordinates inside of the main loop will be useful. Then, how would you decide whether to print a `\" \"` or a `\"@\"`?\n",
"\n",
"Note: The reason for using 40 lines of 80 characters is that a character in the terminal is often approximately twice as tall as it is wide.\n",
"\n",
"**Bonus round:** Skip this part unless you have extra time, or want an extra challenge after lab ends. Modify the program so that it makes circles with softer edges, like this:\n",
"```\n",
" \n",
" \n",
" \n",
" \n",
" ............... \n",
" ..***@@@@@@@@@@@@@@@@@***.. \n",
" ..**@@@@@@@******.******@@@@@@@**.. \n",
" .*@@@@@**... ...**@@@@@*. \n",
" .**@@@@*.. ..*@@@@**. \n",
" .*@@@@*.. ..*@@@@*. \n",
" .*@@@*. .*@@@*. \n",
" .*@@@*. .*@@@*. \n",
" .*@@@*. .*@@@*. \n",
" .*@@*. .*@@*. \n",
" .*@@*. .*@@*. \n",
" .*@@*. .*@@*. \n",
" .@@@*. .*@@@. \n",
" .*@@*. .*@@*. \n",
" .*@@*. .*@@*. \n",
" .@@@* *@@@. \n",
" .@@@. .@@@. \n",
" .@@@* *@@@. \n",
" .*@@*. .*@@*. \n",
" .*@@*. .*@@*. \n",
" .@@@*. .*@@@. \n",
" .*@@*. .*@@*. \n",
" .*@@*. .*@@*. \n",
" .*@@*. .*@@*. \n",
" .*@@@*. .*@@@*. \n",
" .*@@@*. .*@@@*. \n",
" .*@@@*. .*@@@*. \n",
" .*@@@@*.. ..*@@@@*. \n",
" .**@@@@*.. ..*@@@@**. \n",
" .*@@@@@**... ...**@@@@@*. \n",
" ..**@@@@@@@******.******@@@@@@@**.. \n",
" ..***@@@@@@@@@@@@@@@@@***.. \n",
" ............... \n",
" \n",
" \n",
" \n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Recurrence time histogram\n",
"\n",
"This builds on the `ZBPoint` class from problem 2.\n",
"\n",
"Suppose you start a `ZBPoint` at `(0,0)` and then repeatedly call the method `.jitter()` until the first time it returns to `(0,0)`. The number of steps it takes to do this is called the **recurrence time**. It's possible that this may never happen, but that is very unlikely. (It can be shown that the probability it will eventually return to `(0,0)` is 100%.)\n",
"\n",
"Write a program that runs this process 1000 times and records the recurrence times. (It's OK to give up on a point if it's taken 200 steps and hasn't yet returned to `(0,0)`.) The program should then print a table showing how many times each recurrence time was seen (a *histogram*). Here's an example of what it might look like:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ran 1000 random walks starting at (0,0). Of these:\n",
" 235 returned to (0,0) after 2 steps\n",
" 76 returned to (0,0) after 4 steps\n",
" 51 returned to (0,0) after 6 steps\n",
" 31 returned to (0,0) after 8 steps\n",
" 24 returned to (0,0) after 10 steps\n",
" 17 returned to (0,0) after 12 steps\n",
" 18 returned to (0,0) after 14 steps\n",
" 7 returned to (0,0) after 16 steps\n",
" 6 returned to (0,0) after 18 steps\n",
" 13 returned to (0,0) after 20 steps\n",
" 7 returned to (0,0) after 22 steps\n",
" 8 returned to (0,0) after 24 steps\n",
" 9 returned to (0,0) after 26 steps\n",
" 4 returned to (0,0) after 28 steps\n",
" 2 returned to (0,0) after 30 steps\n",
" 5 returned to (0,0) after 32 steps\n",
" 3 returned to (0,0) after 34 steps\n",
" 5 returned to (0,0) after 36 steps\n",
" 2 returned to (0,0) after 38 steps\n",
" 2 returned to (0,0) after 40 steps\n",
" 3 returned to (0,0) after 42 steps\n",
" 2 returned to (0,0) after 44 steps\n",
" 1 returned to (0,0) after 46 steps\n",
" 4 returned to (0,0) after 48 steps\n",
" 2 returned to (0,0) after 50 steps\n",
" 1 returned to (0,0) after 52 steps\n",
" 7 returned to (0,0) after 54 steps\n",
" 1 returned to (0,0) after 58 steps\n",
" 3 returned to (0,0) after 60 steps\n",
" 4 returned to (0,0) after 62 steps\n",
" 4 returned to (0,0) after 64 steps\n",
" 2 returned to (0,0) after 66 steps\n",
" 1 returned to (0,0) after 68 steps\n",
" 2 returned to (0,0) after 70 steps\n",
" 1 returned to (0,0) after 72 steps\n",
" 3 returned to (0,0) after 76 steps\n",
" 2 returned to (0,0) after 78 steps\n",
" 1 returned to (0,0) after 80 steps\n",
" 2 returned to (0,0) after 82 steps\n",
" 1 returned to (0,0) after 84 steps\n",
" 2 returned to (0,0) after 86 steps\n",
" 2 returned to (0,0) after 92 steps\n",
" 2 returned to (0,0) after 94 steps\n",
" 1 returned to (0,0) after 96 steps\n",
" 1 returned to (0,0) after 98 steps\n",
" 2 returned to (0,0) after 106 steps\n",
" 1 returned to (0,0) after 108 steps\n",
" 2 returned to (0,0) after 110 steps\n",
" 4 returned to (0,0) after 116 steps\n",
" 2 returned to (0,0) after 118 steps\n",
" 1 returned to (0,0) after 122 steps\n",
" 1 returned to (0,0) after 124 steps\n",
" 1 returned to (0,0) after 126 steps\n",
" 1 returned to (0,0) after 128 steps\n",
" 3 returned to (0,0) after 130 steps\n",
" 1 returned to (0,0) after 134 steps\n",
" 2 returned to (0,0) after 136 steps\n",
" 2 returned to (0,0) after 138 steps\n",
" 1 returned to (0,0) after 142 steps\n",
" 1 returned to (0,0) after 144 steps\n",
" 2 returned to (0,0) after 146 steps\n",
" 1 returned to (0,0) after 156 steps\n",
" 1 returned to (0,0) after 158 steps\n",
" 1 returned to (0,0) after 160 steps\n",
" 3 returned to (0,0) after 162 steps\n",
" 1 returned to (0,0) after 166 steps\n",
" 1 returned to (0,0) after 174 steps\n",
" 2 returned to (0,0) after 178 steps\n",
" 1 returned to (0,0) after 180 steps\n",
" 3 returned to (0,0) after 184 steps\n",
" 1 returned to (0,0) after 190 steps\n",
" 2 returned to (0,0) after 198 steps\n",
" 376 didn't return to (0,0) after 200 steps"
]
}
],
"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
}