We wrote several bits of code use the Python programming language. It is fairly easy to set up Python on your own computer for free. The primary resource for Python is at http://www.python.org. From that web page you can download Python to your computer. If you run the Windows installer, it will install the Python programming environment along with an editor known as Idle that provides a convenient environment for writing Python programs.
If you want to learn how to program in Python, there is an excellent online book by Alan Downey called Think Python: How to Think Like a Computer Scientist. It is available at http://www.greenteapress.com/thinkpython/html/. I have produced a summary of the major Python constructs presented in the book.
We found that we often had to say this either in the shell or at the beginning of our Python files:
from math import *
This is a request to load all of the definitions from the math library into
Python. You can say:
help("math")
in the Python shell to get a list of all of the definitions included in this
module.I also added these lines to our file:
import sys
sys.setrecursionlimit(10000)
By default, you can only go 1000 levels deep in recursion. By setting it to
10 thousand, I gave us a little more room to play with.
if (bowl is empty):
we're done (the bowl already has the right number of M&M's--zero)
else:
remove one M&M
double what's left
add back two M&M's
We were able to turn this into the following Python code:
def double(n):
if n == 0:
return 0
else:
return double(n - 1) + 2
This function doubles the number passed to it:
>>> double(3)
6
>>> double(5)
10
It was easier to see the recursive calls when we added a print command:
def double(n):
print "I'm doubling", n
if n == 0:
return 0
else:
return double(n - 1) + 2
This variation produced the following output:
>>> double(3)
I'm doubling 3
I'm doubling 2
I'm doubling 1
I'm doubling 0
6
>>> double(5)
I'm doubling 5
I'm doubling 4
I'm doubling 3
I'm doubling 2
I'm doubling 1
I'm doubling 0
10
n! = 1 ⋅ 2 ⋅ 3 ... ⋅ nIt may seem odd, but by definition, 0! is considered to be 1. This became our base case. In the recursive case, we multiplied n by (n-1)!:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...There are lots of great sites about the Fibonacci numbers including http://pass.maths.org.uk/issue3/fibonacci/ and http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/.
This has an obvious recursive definition where the base case involves the first two values of 1 and the recursive case involves adding the two previous numbers from the sequence:
def fib(n):
if n <= 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
We saw that this took a long time to execute even for relatively small values
like fib(40). The execution time for this version of the function grows
exponentially. In fact, it grows at almost the same rate as the Fibonacci
sequence itself.This was more obvious when we added a depth parameter and printed some output on each call:
def fib(n, depth):
print 4 * depth * "-" + "fib(", n, ")"
if n <= 2:
return 1
else:
return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)
This allowed us to see in detail what was happening:
>>> fib(7, 0)
fib( 7 )
----fib( 6 )
--------fib( 5 )
------------fib( 4 )
----------------fib( 3 )
--------------------fib( 2 )
--------------------fib( 1 )
----------------fib( 2 )
------------fib( 3 )
----------------fib( 2 )
----------------fib( 1 )
--------fib( 4 )
------------fib( 3 )
----------------fib( 2 )
----------------fib( 1 )
------------fib( 2 )
----fib( 5 )
--------fib( 4 )
------------fib( 3 )
----------------fib( 2 )
----------------fib( 1 )
------------fib( 2 )
--------fib( 3 )
------------fib( 2 )
------------fib( 1 )
13
We were able to make this run much faster by introducing a helper function that
had extra parameters to keep track of the previous two values in the
sequence:
def fib2(n):
if n <= 2:
return 1
else:
return helper(n - 2, 1, 1)
def helper(times, prev, prevPrev):
sum = prev + prevPrev
if times == 1:
return sum
else:
return helper(times - 1, sum, prev)
In the recursive solution, we recognize that if there are zero disks to move, then there is nothing to do. And in the case of moving n disks, we can move n-1 from the source to the temporary, using the destination as a temporary. Then we move the large disk from the source to the destination. And then we again move n-1 disks from the temporary to the destination using the source as a temporary.
We came up with the following code to solve this problem:
def towers(n, source, dest, temp):
if (n > 0):
towers(n - 1, source, temp, dest)
print "move disk from", source, "to", dest
towers(n - 1, temp, dest, source)
It was surprising to find that such a short bit of code works. It is evidence
of the power of recursive definitions. Below is a sample execution for moving
4 disks:
>>> towers(4, "A", "B", "C")
move disk from A to C
move disk from A to B
move disk from C to B
move disk from A to C
move disk from B to A
move disk from B to C
move disk from A to C
move disk from A to B
move disk from C to B
move disk from C to A
move disk from B to A
move disk from C to B
move disk from A to C
move disk from A to B
move disk from C to B
We found that the number of moves involved for moving a tower of size n is
always 2n-1.
In going to the next level, we replace the three corners of this triangle with a level 1 triangle, which gives us a level 2 triangle:
This process continues indefinitely. Here is a level 8 triangle:
The level 1 triangle becomes our base case and in the recursive case, we locate the midpoints of the triangle and draw three new triangles of level 1 lower. Here is the crucial recursive code:
def draw_helper(canvas, level, p1, p2, p3):
if level == 1:
canvas.create_polygon(p1, p2, p3)
else:
p4 = midpoint(p1, p2);
p5 = midpoint(p2, p3);
p6 = midpoint(p1, p3);
draw_helper(canvas, level - 1, p1, p4, p6);
draw_helper(canvas, level - 1, p4, p2, p5);
draw_helper(canvas, level - 1, p6, p5, p3);
We then looked at how to build up more complex functions from simple x and y values. For example, you can take the produce of two of these values and you'll get another value in the range of -1 to +1. Or you can take the sine of pi times one of these values and you'll get a value in the range of -1 to +1.
Here is the crucial recursive code that makes this work:
def generate(n):
if n == 0:
if random() < 0.5:
return "x"
else:
return "y"
else:
num = random()
if num < 0.25:
return "sin(pi * " + generate(n - 1) + ")"
elif num < 0.5:
return "cos(pi * " + generate(n - 1) + ")"
elif num < 0.75:
return "(" + generate(n - 1) + " + " + generate(n - 1) + ") / 2"
else:
return generate(n - 1) + " * " + generate(n - 1)
Below is a sample produce with a depth of 9:
This is what the program printed out as the functions that were being used to compute red/green/blue components of the picture:
depth = 9 red = cos(pi * cos(pi * ((sin(pi * (cos(pi * x) * y * x + cos(pi * cos(pi * y))) / 2) + cos(pi * sin(pi * (y + y) / 2)) * (((x + x) / 2 + (y + y) / 2) / 2 + cos(pi * x) * x * x) / 2) / 2 * cos(pi * (cos(pi * x) * cos(pi * x) * sin(pi * sin(pi * y)) + sin(pi * sin(pi * y)) * (x * x + cos(pi * y)) / 2) / 2) + (cos(pi * sin(pi * sin(pi * y * x))) + (cos(pi * (y + x) / 2) * (sin(pi * x) + sin(pi * x)) / 2 + ((x * x + (x + y) / 2) / 2 + sin(pi * x * y)) / 2) / 2) / 2 * (cos(pi * (y + x) / 2 * x * y) * cos(pi * x * x) * cos(pi * (x + x) / 2) + (cos(pi * y) + (x + x) / 2) / 2 * sin(pi * x * x) * sin(pi * x * y) * sin(pi * x) * x * x) / 2) / 2)) blue = (sin(pi * sin(pi * sin(pi * sin(pi * sin(pi * (cos(pi * y * x) + (sin(pi * x) + (x + y) / 2) / 2) / 2))))) + sin(pi * sin(pi * cos(pi * x) * sin(pi * x) * cos(pi * x * y)) * sin(pi * sin(pi * cos(pi * y)) * sin(pi * y * x)) * cos(pi * (sin(pi * (y + x) / 2) + ((x + y) / 2 + sin(pi * y)) / 2) / 2) * sin(pi * sin(pi * sin(pi * cos(pi * y)))) * cos(pi * (((y + x) / 2 * cos(pi * y) + cos(pi * (y + y) / 2)) / 2 + (((y + x) / 2 + sin(pi * y)) / 2 + sin(pi * sin(pi * x))) / 2) / 2 * cos(pi * sin(pi * cos(pi * y) * cos(pi * y)))))) / 2 green = cos(pi * sin(pi * (cos(pi * cos(pi * cos(pi * (x + y) / 2) * x * y * cos(pi * x))) + sin(pi * sin(pi * sin(pi * y) * y * x)) * (sin(pi * y) + sin(pi * y)) / 2 * cos(pi * x) * x * x * sin(pi * sin(pi * x)) * sin(pi * sin(pi * x))) / 2) * sin(pi * cos(pi * (cos(pi * sin(pi * x) * (y + y) / 2) + sin(pi * cos(pi * sin(pi * y)))) / 2 * sin(pi * cos(pi * y) * sin(pi * y) * sin(pi * cos(pi * x))))))
# This program draws the Sierpinski Triangle
from Tkinter import *
from math import *
def midpoint(p1, p2):
return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
def draw_helper(canvas, level, p1, p2, p3):
if level == 1:
canvas.create_polygon(p1, p2, p3)
else:
p4 = midpoint(p1, p2);
p5 = midpoint(p2, p3);
p6 = midpoint(p1, p3);
draw_helper(canvas, level - 1, p1, p4, p6);
draw_helper(canvas, level - 1, p4, p2, p5);
draw_helper(canvas, level - 1, p6, p5, p3);
class App:
def __init__(self, master):
master.title("Sierpinski Triangle Fractal")
frame = Frame(master)
frame.pack()
self.size = 512
self.canvas = Canvas(frame, width=self.size, height=self.size,
bg="cyan")
self.canvas.pack(side=TOP)
self.drawb = Button(frame, text="Draw", command=self.draw)
self.drawb.pack(side=LEFT)
w = Label(frame, text="Level")
w.pack(side=LEFT)
self.level = Entry(frame, width=3, justify=CENTER)
self.level.insert(INSERT, "1")
self.level.pack(side=LEFT)
def draw(self):
level = int(self.level.get())
self.canvas.create_rectangle(0, 0, self.size + 5, self.size + 5, fill="cyan")
triangle_height = int(round(self.size * sqrt(3.0) / 2.0))
p1 = (2, triangle_height + 3)
p2 = (2 + self.size / 2, 3)
p3 = (2 + self.size, triangle_height + 3)
draw_helper(self.canvas, level, p1, p2, p3)
root = Tk()
app = App(root)
root.mainloop()
# This program generates random art
from Tkinter import *
from random import *
from math import *
def generate(n):
if n == 0:
if random() < 0.5:
return "x"
else:
return "y"
else:
num = random()
if num < 0.25:
return "sin(pi * " + generate(n - 1) + ")"
elif num < 0.5:
return "cos(pi * " + generate(n - 1) + ")"
elif num < 0.75:
return "(" + generate(n - 1) + " + " + generate(n - 1) + ") / 2"
else:
return generate(n - 1) + " * " + generate(n - 1)
def to_f(s):
return eval("lambda (x, y): " + s)
def to_intensity(n):
return int(round(n * 127.5 + 127.5))
def rgb2hex(r,g,b):
return '#%02X%02X%02X'%(r,g,b)
class App:
def __init__(self, master, width, height, depth):
master.title("Random Art")
frame = Frame(master)
frame.pack()
self.width = width
self.height = height
self.depth = depth
self.canvas = Canvas(frame, width=width, height=height, bg="gray")
self.canvas.pack(side=TOP)
self.drawb = Button(frame, text="Draw", command=self.draw)
self.drawb.pack(side=LEFT)
w = Label(frame, text="Depth")
w.pack(side=LEFT)
self.depth = Entry(frame, width=3, justify=CENTER)
self.depth.insert(INSERT, "9")
self.depth.pack(side=LEFT)
def draw(self):
depth = int(self.depth.get())
print 70*"-"
print "depth =", depth
red = generate(depth)
blue = generate(depth)
green = generate(depth)
print "red =", red, "\n"
print "blue =", blue, "\n"
print "green =", green, "\n"
redf = to_f(red)
bluef = to_f(blue)
greenf = to_f(green)
for y in range(self.height):
for x in range(self.width):
x2 = (2.0 * x) / self.width - 1
y2 = (-2.0 * y) / self.height + 1
r = to_intensity(redf((x2, y2)))
g = to_intensity(bluef((x2, y2)))
b = to_intensity(greenf((x2, y2)))
self.canvas.create_rectangle(x, y, x, y,
outline=rgb2hex(r, g, b))
root = Tk()
app = App(root, 300, 300, 9)
root.mainloop()