Functions - Exercises, IPO Charts

Exercises!

1. Designing a Function
2. Factorial
3. David Lynch Movies
4. Greatest Common Divisor
5. Euclidean Rhythms

A Couple of Tools for Designing Functions

1. Pseudocode (we've seen this before)
2. IPO Charts

IPO Charts

Starting Out with Python describes the use of IPO Charts to help design and document functions. The chart has three columns, input, processing, output:

• the input column shows a description of data that is passed in to the function
• the processing column describes the process that the function performs
• finally, the output column shows the data that is returned from the function

IPO Charts Example

An example IPO chart for our version of absolute value:

"""
+-----------------------------------------------------+
| absolute_value                                      |
+-----------------------------------------------------+
| input            | processing        | output       |
+------------------+-------------------+--------------+
| the number to be | calculate the     | a number     |
| processed        | number's distance | representing |
|                  | from 0, e.g. -5   | the absolute |
|                  | is 5 away from 0  | value        |
+------------------+-------------------+--------------+
"""

And … Some Exercises

Factorial

Does anyone remember what the factorial of a number is? For example, what is 4!? →

Factorial Definition

The factorial of a number is the product of all positive integers less than or equal to that number.

• it's denoted by an exclamation point (!)
• the factorial of 0 is 1

The previous example of 4! is:

>>> 4 * 3 * 2 * 1
24

Write a Function That Calculates Factorial

We want a function that takes a number and gives back (not prints out!) the factorial of that number.

Example usage:

>>> result = factorial(4)
>>> print(result)
24
>>> result = factorial(0)
>>> print(result)
1

IPO Chart

How many arguments will the factorial function take, if any? What processing will it do? What will it return, if anything? →

How About Some Pseudocode

In pseudocode, what would the implementation of this function look like? →

define a function that takes one parameter
keep track of the product...
for every number less than or equal to n (up to, but not including 0)
	multiply the product by each number

Possible Solution

Here's a possible iterative solution:

def factorial(n):
	product = 1
	for i in range(n, 0, -1):
		product = product * i
	return product

print(factorial(4))
print(factorial(20))

Using Our New Factorial Function

How would I use this function in a program that asks the user for a number… and then prints out the factorial of that number? →

def factorial(n):
	product = 1
	for i in range(n, 0, -1):
		product = product * i
	return product

user_input = input("Give me a number, I'll give you the factorial\n>")
num = int(user_input)
print(factorial(num))

Is It a David Lynch Movie?

Write a program that determines whether or not a user inputted movie was made by David Lynch.

Who?

• American filmmaker and television director
• surrealist style
• you might know him from:
  • Blue Velvet
  • Eraserhead
  • Dune (yes!)
  • Twin Peaks
  • the voice of the bartender in Family Guy (!?)
  • etc.

Requirements

• define a function that determines if a string given is the title of a David Lynch movie
• the function will return True or False
• use the function in a program that…
  • continually asks the user:
  • "Give me a movie title or q to quit"
• if the user types q, end the program
• if it's a David Lynch movie, print out "(movie) is a David Lynch movie!"
• otherwise, print out "There's a fish in the percolator"

Example Output

Go!→

Give me a movie title
>Blue Velvet
Blue Velvet a David Lynch movie!
Give me a movie title
>Clueless
There's a fish in the percolator
Give me a movie title
>q

Example Usage of the Function

movie = "Blue Velvet"
result = is_a_david_lynch_movie(movie)

IPO Chart

How many arguments will it take, if any? What processing will it do? What will it return, if anything? →

Possible Solution

def is_a_david_lynch_movie(s):
	if s == "Blue Velvet" or s == "Dune" or s == "Lost Highway":
		return True
	else:
		return False

movie = input("Give me a movie title\n>")
while movie != 'q':
	if is_a_david_lynch_movie(movie):
		print("%s a David Lynch movie!" % (movie))
	else:
		print("There's a fish in the percolator")
	movie = input("Give me a movie title\n>")

Greatest Common Divisor?

What's the greatest common divisor (GCD) for 12 and 8?

How Did You Figure That Out?

Maybe This Guy Could Help…

Euclid of Alexandria

Who was that? That was Euclid (obv!).

• AKA "Father of Geometry"
• was writing algorithms two millennia ago! (about 300 BC)
• wrote a series of book called Euclid's Elements
  • one of the most influential works in the history of mathematics
  • was used to teach math up until the 19th or 20th century

Euclidean Algorithm

One method for finding the greatest common divisor is using Euclid's Algorithm:

1. start with a pair of positive integers
2. form a new pair that's made up of the smaller number and the difference between the larger and smaller numbers
3. repeat until the numbers are equal
4. the resulting number is the GCD

The Euclidean Algorithm in Action

By hand, find the GCD of 12 and 8 using Eclid's Algorithm. →

Larger of the pair goes in column A

 A | B | delta
___|___|______
12 | 8 | 4  
 8 | 4 | 4      (4 replaced 12) 
 4 | 4 | 0      (Done!)

Another Example

By hand, find the GCD of 60 and 24 using Eclid's Algorithm. →

Larger of the pair goes in column A

 A | B | delta
___|___|______
60 | 24| 36
36 | 24| 12     (36 replaced 60) 
24 | 12| 12     (12 replaced 36)
12 | 12| 0

Requirements

Create a function that calculates the greatest common divisor of two numbers by using Euclid's algorithm.

Example Usage of the Function

number_1, number_2 = 24, 144
greatest_common_divisor = gcd(number_1, number_2)
print(greatest_common_divisor)

IPO Chart

How many arguments will it take, if any? What processing will it do? What will it return, if anything? →

Pseudocode

create a function that takes two arguments, a and b

while a and b aren't equal...
	let's make sure that we know which variable is the larger one 
	(we'll always assign it to a)
	if a is larger than b, then swap
	otherwise a gets changed to the difference between itself and b

Possible Solution

#  version 1
def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

#  version 2
def gcd(a, b):
    while a != b:
        # let's always make a the larger number
        if a < b:
            # swap the values!
            a, b = b, a
        else:
            a = a - b
    return a
print(gcd(12, 8))
print(gcd(30, 105))

Um. That's cool… but I just wanna dance! (To some algorithmically generated rhythms).

Euclidean Rhythms

Apparently, the Euclidean Algorithm can be used to generate rhythms. A paper by Godfried Toussaint explores the concept of Euclidean Rhythms.

• Euclid's Algorithm can be used to generate traditional music rhythms
• The rhythms generated cover almost all of the most important World Music rhythms

Euclidean Rhythms Continued

The Euclidean Algorithm can be used to distribute a set number of notes as evenly as possible over a set period of time (where time is divided into equal parts).

• for example, 4 notes in 16 units of time (four notes in one measure of 16 sixteenth notes):
  • (X denotes a pulse, . denotes silence)
  • X…X…X…X…
  • Let's take a listen
• …and a less even distribution… 5 notes in 12: * X..X.X..X.X.
  • we'll see how this works next!

General Algorithm

1. Put all of the pulses in the beginning: XXXXX…….
2. Break into two groups of repeating patterns
3. Evenly distribute 2nd group of patterns to each element in the first group
4. Go back to 2.

How It Works

5 notes in 12

1. Put all of the pulses in the beginning: XXXXX…….
2. Move the remaining periods after each X: X.X.X.X.X…
3. (There are 5 pairs of [X.], with two dots remaining)
4. Place the remainder dots after the 1st two pairs of [X.]: X..X..X.X.X.
5. (There are 2 triplets of [X..], with two pairs of [X.] remaining)
6. Place the remainder of [X.] after the 1st two triplets of [X..]: X..X.X..X.X.
7. From here, the replacements become cyclical, so end here

How It Works 2

Sometimes it's easier to visualize in columns:

"""
XXXXX....... 5, 12, delta is 7

XXXXX..      5, 2, delta is 3
.....

XXXXX        2, 3, delta is 1
.....
..

XXX          2, 1, stop
...
..
XX
..
"""

What Does That Actually Sound Like?

Let's take a listen. Some examples of pulses and intervals:

• 3, 8 - tresillo - the fundamental rhythm in cuban and other latin music (also in ragga or djembe drumming, etc.)
• 7, 12 - west african bell pattern
• 5, 9 - Arab rhythm called Agsag-Samai