Chp 6 Functions

Instructions

Write each of the functions described below. Use the function names and parameters given.

As always, I suggest that you write the skeleton of each function to begin. Like this:

def max_num():

    pass


def min_num():

    pass

If you do this, the unit test will run.

Note that some functions only mutate, some only return a value and some do both.  Recall that a function with no return statement returns None by default.

A final word. I expect you'll want to write functions other than the ones you're told to write below. Indeed I expect you'll want to write helper functions; and then you'll call these helper functions inside the required functions. For instance, in the perimeter function, I expect you'll want to call a distance function that you wrote for a previous function set.  Why write helper functions? It keeps your functions short and simple; and short, simple functions are easier to get right than long, complex ones.

Max and Min

Write a function named max_num that takes a list of numbers and returns the greatest number in the list.  Write a function and min_num that takes a list of numbers and returns the smallest number in the list. Don't use the built-in functions that find min and max. Write the algorithm yourself!

Both max_num and min_num are fruitful non-mutators.

Raise a ValueError if the list is empty. (That'll be this line of code: raise ValueError. If you want, you can put an optional message immediately after, like "list empty".)

This function is a little tricky. Presumably you'll have a variable with a name like biggest_so_far (or smallest_so_far). As you iterate through the list, if the current element is greater than the biggest so far, it becomes the new biggest so far. But biggest_so_far must have an initial value before you begin to iterate through the list.  What should it be? That's the tricky part.

Test Cases:

>>> max_num([3, -1, -12, 6, 0])

6

>>> min_num([3, -1, -12, 6, 0])

-12

>>> max_num([-1])

-1

>>> min_num([-1])

-1

>>> max_num([])

ValueError

>>> min_num([])

ValueError

Sum

Write a function named sum_elems that takes a list of integers and returns their sum. Don't use the built-in sum function. This is a fruitful non-mutator.

The sum of the empty list should be 0.

Test Cases:

>>> sum_elems([1, 2, 3])

6

>>> sum_elems([])

0

Greatest Sum

Write a function named greatest_sum that takes a list of lists of integers, finds the sum of each of those sub-lists and then returns the greatest of those sums. This is a fruitful non-mutator. Please do make use of the sum_elems function from above. You might also want to make use of max_num.

Test Cases:

>>> greatest_sum([[1], [3, 2, 1], [7, -2]])

6

>>> greatest_sum([[]])

0

>>> greatest_sum([])

0

Dot Product

To form the dot product of two lists of numbers, we multiply the numbers at index 0, multiply those numbers at index 1, etc.; and then we add those products. For instance, the dot product of [1, 2, 3] and [4, 5, 6] is 1*4 + 2*5 + 3*6 = 32.

Write a function named dot_product that takes two number lists and returns their dot product. This is a fruitful non-mutator.

If the two lists don't have the same length, their product is undefined. So I suggest that to begin you test whether the lists have the same length, and if not raise a value error. Like this:

def dot_product(S, T):

    if len(S) != len(T):

        raise ValueError("lists not of same length")

Test Cases:

>>> dot_product([1, 2, 3], [4, 5, 6])

32

>>> dot_product([1, 2, 3], [4, 5])

ValueError: lists not of same length

Mean

The mean of a list of numbers is their sum divided by the length of the list. Write me a function named mean that takes a list of numbers and returns their mean. This is a fruitful function that does not mutate the input list.

Test Cases:

>>> mean([1, 2, 3, 4, 5])

3.0

>>> mean([1])

1.0

>>> mean([])

ZeroDivisionError: division by zero

Mode

The mode of a list of numbers is the number or numbers that occurs most often in the list. Write a function named mode that takes a list of numbers and return the list of its modes. (Suggestion: Google Python's count method.) This function is a fruitful non-mutator.

Test Cases:

>>> mode([1, 2, 3])

[1, 2, 3]

>>> mode([1, 2, 3, 3])

[3]

>>> mode([1, 1, 2, 3, 3, 4, 5, 5])

[1, 3, 5]

>>> mode([])

[]

For some years, my solution to this was two-loop, with the second not inside but after the first.. The first loop found the greatest number of times any element occurs in the input list, and the second loop built the list of all elements in the input list that occur that greater number of times. But I finally realized that the problem can be solved with a single loop. If you want a challenge, try to find a one-loop solution.

Perimeter

The location of a point in the coordinate plane is naturally represented as a two-member tuple. For instance, the tuple (-12, 18) represents the point whose x-coordinate is -12 and whose y-coordinate is 18.

A polygon in the coordinate plane is naturally represented as a tuple of two-member tuples. For instance, ((-12, 18), (0, 0), (3, 04)) is a triangle whose vertices have the locations given.

Write a function named perimeter that takes a tuple of two-member tuples and returns the perimeter of the polygon that tuple represents. You'll use the distance function of course; and I would make that it's own separate function. Remember that each function you write should carry out just one task, and that if you have a multi-task process, you should break that up into multiple functions.

Here's a juicy hint: the perimeter will be distance from first point to second plus distance from second to third ... plus distance from last to first.  A polygon has to close up, you know!

Test Cases:

>>> tri = ((0, 0), (1, 0), (0, 1))

>>> perimeter(tri)

3.414213562373095

What should you do if the input is the empty tuple? I  think it best to say in that case that the perimeter is 0. Let's also say that the perimeter is 0 if the input tuple contains only one point. Last let's say that when the input is two points, the perimeter function should return the length of the segment those two points define. Test cases for these three possibilities (no points, one point, two points) are below:

>>> empty_tuple = ()

>>> perimeter(empty_tuple)

0

>>> one_point_tuple = ((1, 2), )

>>> perimeter(one_point_tuple)

0

>>> two_point_tuple((1,2), (1,3))

>>> perimeter(two_point_tuple)

1.0

Prime List 

If I were you, I'd write a is_prime helper function that takes just one number and returns True if it's prime and False if it's not; and then I'd have my prime_list function call is_prime inside a for loop. Remember to keep your functions as simple as you can.

Beware a certain common mistake as you write is_prime. We can't say  that a number is prime if it isn't divisible by 2. Or if it isn't divisible by 2 or 3. Or if it isn't divisible by 2, 3 or 5. Indeed we can't say that a number is prime if it isn't divisible by any number of primes. For the number of primes is infinite!

Test Cases:

>>> prime_list(2, 12)

[2, 3, 5, 7, 11]

>>> prime_list(12, 12)

[]

>>> prime_list(12, 10)

[]

The Sieve of Eratosthenes (Extra Credit)

Let me take a moment to describe a really clever and fast way to produce a list of all primes from 2 up to some n.

First begin with the sequence of integers from 2 to n. Here they are:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... ,n

We're about to cross out numbers in the sequence. (Those crossed out will be non-primes.) Which ones? All factors of a number in the list greater than it.

So here we go. Take the first number in the sequence that isn't crossed out, and cross out all its multiples. That number is 2, and it's multiples are 4, 6, 8, etc. Thus we have:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... ,n

Now take the next number in the sequence that isn't crossed out, and cross out all its multiples. That number is 3, and its multiples are 6, 9, 12, 15, etc. Of course if a number was already crossed out, we leave it crossed out. Thus we have:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... , n

We continue on until we get to the halfway point of the list. (After that, the multiples will be all larger than n.)

Let's have an example of the completed list where n = 32.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32

Now the final step: collect all the non-crossed out numbers. These will be primes. If we take the non-crossed out elements from the sequence immediately above, we get:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

These are indeed all primes less than or equal to 32.

You'll write two functions, one named sieve and another named sum_sieve. The first will implement the algorithm described above. The second will return the sum of the elements in the list returned by sieve for some input n. Only the second will be unit tested. (Why unit test only the second? I plan to send the second a big input, and if you cheated and didn't use the sieve algorithm described above, your sieve function likely won't terminate in reasonable time.)

Test cases:

>>> sieve(32)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

>>> sieve(144)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139]

>>> sieve(144)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139]

>>> sum_sieve(1234567)

56381686561

 >>> sum_sieve(12345678)

4819033002832

Prime Factorization

How will you do this? Well, let me prove two little theorems for you.


First Theorem For positive integers a, b and c, if a divides b and b divides c, then a divides c.

Examples 2 divides 6 and 6 divides 12, so 2 must divide 12. Another: 11 divides 33 and 33 divides 99, so 11 must divide 99.

The Proof Since a divides b, a times some integer i equals b; that is, a * i = b. Moreover, since b divides c, b time some integer j equals c; that is, b * j = c. Now take the equation a * i = b and multiply both sides by j to get a * i * j = b * j. But b * j = c, so a * i * j = c. But obviously, since i and j are integers, i * j is also an integer. So we know that a time some integer equals c. But this means that a divides c.


Second Theorem The first positive integer divisor greater than 1 of some positive integer must be prime; that is, if p is greater than 1, p divides n and no number q that is greater than 1 and less than p divides n, then p must be prime.

Examples The first integer divisor greater than 1 of 35 is 5, and so 5 must be prime. Another: the first integer divisor greater than 1 of 13843 is 109, and so 109 must be prime.

Proof  Again, our positive integer is n, and its first positive integer divisor greater than 1 is p. Assume that p isn't prime. It must then have some divisor q that is greater than 1 and less than p. But then by our first theorem, q divides n, for q divides p and p divides n. We now have a contradiction - p both is and is not the first divisor of n greater than 1. Thus our assumption - that p isn't prime - is false, which means of course that p is prime.


So what do you do in prime_factorization? Let's say that the input value is n. Find the first factor greater than 1 of n.  (Call it "p".) That's the first prime factor of n. Next divide n by p (n = n // p) and do it again; that is, find the first factor greater than 1 of the new n. That's the second prime factor of the original n. Continue on until n itself is prime. (You'll know that that n is prime when its first factor greater than 1 is itself.)

Test Cases:

>>> prime_factorization(12)

[2, 2, 3]

>>> prime_factorization(13)

[13]

>>> prime_factorization(54)

[2, 3, 3, 3]

>>> prime_factorization(121)

[11, 11]

Flatten

Write a function that takes a list of lists and returns a list whose elements are all and only the elements in those sublists. Name it flatten. (Why flatten? A list of lists is 2D. A table really. Each sublist is a row. When we remove the inner brackets, we flatten it into a 1D sequence.) This is a fruitful function. It is not a mutator.

Test Cases:

>>> flatten([[2, 3], [5, 7, 11], [13, 15]])

[2, 3, 5, 7, 11, 13, 15]

Exchange

An IndexError should be rasied if no element exists at either of the indices.

Note that in the test cases below, I first define a list named ints, and then I  call exchange on ints. This means that ints will be mutated. It  begins as [1, 2, 3, 4, 5, 6] and ends as [4, 2, 3, 1, 5, 6].

Test Cases:

>>> ints = [1, 2, 3, 4, 5, 6]

>>> exchange(ints, 0, 3)

>>> ints

[4, 2, 3, 1, 5, 6]

>>> exchange(ints, 1, 1)

>>> ints

[4, 2, 3, 1, 5, 6]

>>> exchange(ints, 3, 12)

IndexError: list index out of range

Eliminate Duplicates

I expect I'd use Python's count and remove methods.

Test Cases:

>>> a_list = [1, 2, 2, 3, 3, 3, 3, 4]

>>> elim_dups(a_list)

>>> a_list

[1, 2, 3, 4]

Note that when you remove duplicates of an element, the first occurrence of that object should remain.

>>> b_list = [1, 2, 3, 2]

>>> elim_dups(b_list)

>>> b_list

[1, 2, 3]

Partition

This function will mutate a list of integers so that the list will contain those same integers but (likely) in a different order. How so?

It will partition the original list  into two parts: first those less than or equal to the mean of the list, and then after, those greater than the mean. Moreover, it will make no other changes in the order of elements of the list. Thus, for example, if two elements m and n are less than the mean and m comes before n in the original list, m will still come before n once the partition is complete.

Let's have an example. Say the list is [12, 0, -2, 9, 3]. The mean of its elements is 4.4. So we mutate the list so that its first part is all elements less than or equal to 4.4 and its second part is all elements greater than 4.4; and otherwise we leave the order of elements unchanged. So the list becomes [0, -2, 3, 12, 9].

Call the function partition. As I've said, it's a mutator; indeed it is a fruitless mutator. Python's built-in insert method will be of use.

Test cases:

>>> L = [-16, -21, -21, -24, -12, 22, -36, -32, -4, 29, 3, -10]

>>> partition(L)

>>> L

[-16, -21, -21, -24, -12, -36, -32, 22, -4, 29, 3, -10]

>>> sum(L) / len(L) # the mean; here to help you check that the  mutated L is indeed correct

-10.166666666666666

The Locker Problem

A hallway contains n lockers, all initially closed, numbered 1 through n. n students pass through the hallway, one at a time. The kth student switches the state of lockers numbered k*1, k*2, k*3, etc. (To switch the state means to close an open locker and open a closed locker.) For instance, third students switches the states of lockers 3, 6, 9, etc. Write me a function named open_lockers with parameter n that returns the number of open lockers once all students have passed through.

Test cases:

>>> open_lockers(1)

0

>>> open_lockers(2) 

1

>>> open_lockers(3) 

2

>>> open_lockers(4) 

2

>>> open_lockers(50) 

43

>>> open_lockers(500) 

478

Longest Monotonic Subsequence (Extra Credit)

Let us say that a monotonic sequence is a sequence of more than one elements that either never grows smaller or never grows larger. For instance, both the sequence (given as a Python list) [1, 1, 3, 7] and [12, 11, 11, 0, -1] are monotonic; the first never decreases, the second never increases. However, the sequence [1, 3, 3, 5, -2] is not monotonic, for it both gets larger (from 1 to 3) and also gets smaller (from  5 to -2).

Here's a second, equivalent definition of "monotonic": every monotonic sequence either remains constant or increases or remains constant or decreases.

Note that a monotonic sequence is either sorted from least to greatest or greatest to least.  Note as well that a monotonic sequence must have at least two elements.

Now, some sequences that are not monotonic contain monotonic subsequences. For instance, the non-monotonic sequence [1, 3, 3, 5, -2, 7, 12, -3] contains the monotonic subsequences [1, 3], [1, 3, 3], [1, 3, 3, 5], [3, 3], [3, 3, 5], [3, 5], [5, -2], [-2, 7], [-2, 7, 12], [7, 12] and [12, -3].  Note that the longest monotonic subsequence here is [1, 3, 3, 5].

Of course a sequence can have multiple longest monotonic subsequences; these will be monotonic subsequences all equally long as one another and longer than all others. For instance, in [1, 3, 1, 4], the longest monotonic subsequences (given as a list) are [[1, 3], [3, 1], [1, 4]].

Write me a function named longest_monotonic that takes a list L and return a list of the longest monotonic subsequences of L. (It will thus returns a list of lists.) It is a fruitful non-mutator.

In the test cases below, I make use of a helper rand_ints function.  rand_ints(n, a, b) returns a list of random integers n long where each integer in the list lies between a and b inclusive. You need not write this function.

Test Cases:

>>> longest_monotonic([])

[]

>>> longest_monotonic([1])

[]

>>> longest_monotonic([1, 1])

[[1, 1]]

>>> longest_monotonic([3, 2, 1])

[[3, 2, 1]]

>>> longest_monotonic([3, 2, 1, 3, 2, 1])

[[3, 2, 1], [3, 2, 1]]

>>> longest_monotonic([3, 2, 1, 2, 3, 4]) 

[[1, 2, 3, 4]]

>>> longest_monotonic([1, 4, 1, 3])       

[[1, 4], [4, 1], [1, 3]]

>>> L = rand_ints(24, 1, 24)

>>> L = [11, 8, 6, 4, 8, 11, 2, 15, 9, 8, 10, 8, 4, 21, 7, 9, 11, 5, 9, 20, 23, 3, 7, 15]

>>> longest_monotonic(L)

[[11, 8, 6, 4], [5, 9, 20, 23]]

>>> L = rand_ints(96, 1, 24)

>>> L = [4, 16, 10, 8, 16, 14, 3, 18, 19, 5, 12, 16, 21, 17, 24, 24, 13, 4, 11, 23, 12, 4, 21, 9, 13, 22, 18, 2, 9, 1, 18, 9, 5, 5, 19, 8, 24, 5, 16, 23, 15, 19, 3, 5, 7, 22, 9, 6, 12, 13, 18, 19, 9, 13, 5, 19, 3, 12, 21, 23, 10, 4, 1, 1, 8, 2, 22, 13, 18, 6, 17, 10, 7, 18, 18, 1, 4, 23, 21, 17, 13, 23, 1, 8, 22, 2, 19, 5, 11, 21, 10, 15, 19, 8, 1, 17]

>>> longest_monotonic(L)

[[6, 12, 13, 18, 19], [23, 10, 4, 1, 1]]

Bubble Sort

Bubble Sort is an algorithm that sorts a sequence of objects from least to greatest (or greatest to least). It's described below. The variable S is assigned a list of sortable objects.

Example

Let us take the list of numbers [5, 1, 4, 2, 8 ] and sort it from least to greatest. In each step, elements compared are in bold. Three passes will be required.

First Pass

[5, 1, 4, 2, 8] → [1, 5, 4, 2, 8]   The algorithm compares the first two elements, and swaps since 5 > 1.

[1, 5, 4, 2, 8] → [1, 4, 5, 2, 8]   Swap since 5 > 4.

[1, 4, 5, 2, 8] → [1, 4, 2, 5, 8]   Swap since 5 > 2.

[1, 4, 2, 5, 8] → [1, 4, 2, 5, 8]  Since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass

[1, 4, 2, 5, 8] → [1, 4, 2, 5, 8]

[1, 4, 2, 5, 8] → [1, 2, 4, 5, 8]   Swap since 4 > 2.

[1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]

[1, 2, 4, 5, 8] → [1, 2, 4, 5, 8]

The array is now sorted, but the function doesn't know if it's done. The function needs one complete pass without any swap to know it's the list sorted.

 Third Pass

[1, 2, 4, 5, 8] →  [1, 2, 4, 5, 8]

[1, 2, 4, 5, 8] →  [1, 2, 4, 5, 8]

[1, 2, 4, 5, 8] →  [1, 2, 4, 5, 8]

[1, 2, 4, 5, 8] →  [1, 2, 4, 5, 8]

Name the function bubble_sort. This is a non-fruitful function that mutates its input list.

Selection Sort

Selection sort is a second algorithm that sorts lists of objects. Here's the idea. (The variable S names a list of sortable objects.)

Example

Let us take the list of numbers [5, 1, 4, 2, 8 ] and sort it from least to greatest. In each step, the element moved (if any) is bold.

Name the function selection_sort. This is a non-fruitful function that mutates its input list.

Median

Assume that a list of numbers has been ordered from least to greatest. If the length of that list is odd, the median is that value that occurs in the middle. If the length of that list is even, the median is the average of the middle two elements. For instance, the median of the list

 [1, 2, 2, 5, 7, 9, 11]

 is 5, and the median of the list

 [3, 4, 7, 9, 9, 14]

is (7 + 9) / 2 = 8.

Write a function named median that takes a list of integers and returns its median. 

Make it a fruitful non-mutator.  How will you do that given that you need to sort the list and that the sort functions you wrote above are all mutators? Suggestion: send a copy of the list to the sort function you intend to use.  Like this:

copy_lst = lst[:]

bubble_sort(copy_lst)

After, send copy_lst to median.

Test Cases:

>>> median([1, 2, 3])

2

>>> median([1, 2, 2, 3])

2.0

>>> median([1, 2, 3, 4])

2.5

>>> median([1])

1