To begin, go here and fork the project. (Alternatively, grab the unit test at GitHub.) Note that there are two files in the project: main.py and listLib.py. (The second is short for "list library". More about that in a moment.)
Write each of the functions described below. Use the function names and parameters given.
You'll place each function in one of two files: either main.py or listLib.py. Each function title below tells you into which file the function should be placed.
listLib will contain a number of functions that are quite useful to have. For instance, it contains a count_elem function that tells us how many times a given list contains a given value; and often when we work with lists, that's something we need to know. Many of the listLib functions are ones that already implemented (perhaps with a different name) in Python. However, I don't wish you to simply call a function that's built in to Python. Instead you should write it yourself.
Note that main.py begins with the command from listLib import *. This will import every function in listLib and allow you to use those functions by the name given in listLib. I do expect that many functions in main will use one or more functions in listLib.
Some functions you'll write only mutate an input list, some only return a value and some do both. (Recall that a function which returns a value is fruitful and one that does not is fruitless.) In every function description, I say whether it is fruitful or fruitless and whether it is a mutator or a non-mutator.
A few of the descriptions tell you that in certain cases you should raise a value error. This will stop program execution and print an error message in the console. This can be done with the command raise ValueError. If you like, you can place parentheses after ValueError and in them place a message that will be displayed in the console when the program ceases execution. (See here for more about exceptions.)
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.
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 the min and max. Write the code 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 in parentheses, 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
Write a function named sum_elems that takes a list of numbers 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
Write a function named count_elem that takes a list of values L and a particular value v and returns the number of times that v is found in L. This is a fruitful non-mutator.
Don't use Python's built-in count method.
Test Cases:
>>> count_elem([1, 2, 3], 1)
1
>>> count_elem([1, 2, 3, 1], 1)
2
>>> count_elem([1, 2, 3], 4)
0
>>> count_elem([], 1)
0
Write a function named remove_val that takes a list L and a particular value v and removes the first occurrence of v from L. If v is not found in L, L should be remain unchanged. This is a fruitless mutator.
Note that, in the test cases below, I first assign a list to a variable and then use that variable in a call to remove_val. I do this so that I can demonstrate after that the list was indeed mutated.
Requirement Added on 1.8.2025 Your function will of course have to make use of built-in mutator. I want you to use pop only.
Test Cases:
>>> L = [1, 2, 3]
>>> remove_val(L, 1)
>>> L
[2, 3]
>>> L = [1, 2, 3, 1]
>>> remove_val(L, 1)
>>> L
[2, 3, 1]
>>> L = [1, 2, 3]
>>> remove_val(L, 4)
>>> L
[1, 2, 3]
Write a function named insert_at that takes a list L, a value v and an index i and insert v at index i in L. The item originally at i, and all others to its right, should be moved one position to the right. Thus the length of L will increase by 1.
Note that insert_at can be used to append a value to the end of a list, as seen in the Test Cases below. To do that, the value of the index sent should equal the length of the list.
This is a fruitless mutator.
Raise a value error if i is an index at which no value can be inserted. For instance, we cannot insert a value at index 12 in a list of length 3.
Requirement Added on 1.8.2025 You should use only the index operator to mutate the input list and/or append. (Recall that this is when in the index operator occurs on the left of an assignment statement, as in L[i] = val.)
Test Cases:
>>> L = [2, 3, 5, 7, 11]
>>> insert_at(L, 1, 0)
>>> L
[1, 2, 3, 5, 7, 11]
>>> insert_at(L, 13, 6)
>>> L
[1, 2, 3, 5, 7, 11, 13]
>>> insert_at(L, 4, 3)
>>> L
[1, 2, 3, 4, 5, 7, 11, 13]
>>> insert_at(L, 14, 9)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 7, in insert_at
IndexError: list assignment index out of range
Name: elim_dups
Parameter: a list of values
Mutator? Yes. Eliminate duplicate elements from the list.
Return: no value will be returned
Requirement Added on 1.8.2025 Your function will of course have to make use of built-in mutator. I want you to use pop only.
Test Cases:
>>> L = [1, 2, 2, 3, 3, 3, 3, 4]
>>> elim_dups(L)
>>> L
[1, 2, 3, 4]
Note that when you remove duplicates of an element, the first occurrence of that object should remain.
>>> L = [1, 2, 3, 2]
>>> elim_dups(L)
>>> L
[1, 2, 3]
Name: exchange_elems
Parameters: a list and pair of indices
Mutator? Yes indeed. The list will be mutated so that the elements at the indices given are exchanged.
Return: none (or rather None since you won't have a return)
An IndexError should be raised if no element exists at either of the indices.
Note that in the test cases below, I first define a list named L, and then I call exchange on L. This means that L will be mutated. It begins as [1, 2, 3, 4, 5, 6] and ends as [4, 2, 3, 1, 5, 6].
Requirement Added on 1.8.2025 You should use only the index operator to mutate the input list. (Recall that this is when in the index operator occurs on the left of an assignment statement, as in L[i] = val.)
Test Cases:
>>> L = [1, 2, 3, 4, 5, 6]
>>> exchange_elems(ints, 0, 3)
>>> L
[4, 2, 3, 1, 5, 6]
>>> exchange_elems(L, 1, 1)
>>> L
[4, 2, 3, 1, 5, 6]
>>> exchange_elems(L, 3, 12)
IndexError: list index out of range
In the chapter I showed you how to reverse a list. I did it like this:
reverse_of_L = L[::-1]
This is a slice, and like all slices, it does not mutate a list but instead creates a new list. Let me prove this to you with a little console work. In the console snippet below, I make use of Python's is operator. It asks whether an object and an object are the same object (which, from a hardware point of view, means to ask whether the object and the object are stored in the same memory location or locations).
>>> L = [1, 2, 3]
>>> L[::-1]
[3, 2, 1]
>>> reverse_of_L = L[::-1]
>>> L is reverse_of_L
False
Notice first that the line L[::-1] did produce an output - [3, 2, 1]. This means that the slice operator is fruitful. Notice second that, when asked whether L and reverse_of_L were names of the same object (that's the line L is reverse_of_L), Python replied False. This means that [::-1] did not mutate L.
Now, here's what I want you to do: write me a function named reverse that takes a list L and mutates L so that it has the same elements as before but in reverse order. This will be a fruitless mutator. (We say that, when we mutate an input list instead of create and return a new list, we have acted on that input list in place.) Note that, in the test cases below, I define a list named L, send L to reverse, and then have Python show us the contents of L. This proves that L has indeed been mutated.
Requirement Added on 1.8.2025 You should use only the index operator to mutate the input list. (Recall that this is when in the index operator occurs on the left of an assignment statement, as in L[i] = val.)
Test Cases:
>>> L = [1, 2, 3]
>>> reverse(L)
>>> L
[3, 2, 1]
>>> L = [1]
>>> reverse(L)
>>> L
[1]
>>> L = []
>>> reverse(L)
>>> L
[]
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 listLib. 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
To form the dot product of two lists of numbers, we multiply the numbers at index 0 in each, then multiply the numbers at index 1 in each, 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
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 non-mutator.
Test Cases:
>>> mean([1, 2, 3, 4, 5])
3.0
>>> mean([1])
1.0
>>> mean([])
ZeroDivisionError: division by zero
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. 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.
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. 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 it 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
Name: prime_list
Parameters: two positive integers m and n.
Mutator? No.
Return: a list of all primes in the range m to n (inclusive) ordered from least to greatest
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 prime in a particular list 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 functions above are straightforward. This one, and most of those that remain, are not. Let the fun begin!
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 of its multiples that are greater than it. That number is 2, and the multiples greater than it 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 of its multiples that are greater than it. That number is 3, and so the multiples we'll cross out 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
Name: prime_factorization
Parameter: a positive integer n
Mutator? Nope.
Return: the prime factorization of that integer in the form of a sorted list
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]
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]
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. The insert_at method from listLib 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
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, the third student 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
Let us say that a monotonic sequence is a sequence of more than one numbers that either never becomes smaller or never becomes 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 return 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.
This is hard.
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]]
Write a function named sublist_sum that takes a list of integers L and some integer n and returns True if the elements of some sublist of L sum to n, False otherwise. (The sublists of list L are all lists derived by the deletion of some number of elements of L. Do note that the number of elements deleted could be zero; that is, a list is a sublist of itself.)
If you brute-force it (as I did), you should expect potentially long runtimes for even smallish lists. Let's think about why. For each element in the list, we can either choose to add it into the current sublist, or we can choose not to; that's two choices per element. Thus the total number of sublists of a list of length n is 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ ... ⋅ 2, where the number of 2's is n. This is of course just 2 to the n. For even small n, that's big. If n is 24, for instance, that gives us almost 17 million possible sublists. If n is 36, that grows to almost 69 billion.
This is hard.
Test Cases:
>>> L = [66, 34, 99, 67, 23, 74, 32, 28, 30, 53, 21, 40]
>>> sublist_sum(L, 50)
False
>>> sublist_sum(L, 51)
True
>>> sublist_sum(L, 52)
False
>>> sublist_sum(L, 53)
True
>>> sublist_sum(L, 100)
True
>>> sublist_sum(L, 101)
True
>>> sublist_sum(L, 102)
True
>>> sublist_sum(L, 103)
False
>>> sublist_sum(L, 104)
True
>>> sublist_sum(L, 105)
False
I'll begin with a description of m, n, k type games:
The number of players is two.
The game is played on a grid of dimensions m-by-n.
Each player has pieces to play. We'll assume that one player plays 1's and the other player plays 2's. (I'll refer to the player that plays 1's as Player 1 and the player that plays 2's as Player 2.)
The players take turns. Player 1 begins play.
On her turn, a player plays one of her pieces in an open position on the m-by-n grid.
A player wins when, as the result of her play, she now has k of her pieces in a row either horizontally, vertically or diagonally.
Write a function named mnkWon that takes a value for k and a two-dimensional list that represents the state of the game at a moment in time and returns 1 if Player 1 had won, 2 if Player 2 has won and 0 if neither player as won. (We don't need to send the values of m and n to the function. They can be inferred from the list that is sent.)
The 2D list that represents the state of the game at a moment in time will be given in row-major form; that is, the sublists within the list will represent rows of the grid on which the game is played.
Below is an example of a 2D list that represent a moment in a 3, 3, 3 game. Notice that I have placed a 0 in positions where neither player has played.
[[0, 2, 1], [0, 1, 0], [0, 0, 0]]
This represents the grid:
0 | 2 | 1
-----------
0 | 1 | 0
-----------
0 | 0 | 0
Note that neither Player 1 nor Player 2 has won the game.
Below is a grid for a 5, 5, 4 game that has been won by Player 1.
0 | 0 | 1 | 0 | 0
-------------------
0 | 0 | 1 | 2 | 0
-------------------
2 | 1 | 1 | 1 | 2
-------------------
0 | 0 | 1 | 0 | 0
-------------------
0 | 0 | 2 | 2 | 0
The list form of this state of the game is:
[[0, 0, 1, 0, 0], [0, 0, 1, 2, 0], [2, 1, 1, 1, 2], [0, 0, 1, 0, 0], [0, 0, 2, 2, 0]]
You may assume that the list that gives the state of the game involves no violation of the game rules.
Among the most important operations that can be performed on a list is to sort it elements, either from least to greatest or greatest to least. I'll have you implement two sort algorithms - Bubble Sort and Selection Sort. The study of sort algorithms is of great importance in computer science. If you're curious, poke around the Wikipedia article.
So, we begin with Bubble Sort. The variable S is assigned a list of sortable objects. (That could be numbers, but it needn't be. Strings are also sortable.)
Compare the 1st and 2nd elements of S. If out of order, exchange them.
Compare the 2nd and 3rd elements of S. If out of order, exchange them.
Continue on until all pairs of successive elements have been compared.
If no exchanges were made, the list is in order and the algorithm is complete. If at least one exchange was made, return to step 1 and run the algorithm again.
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.
[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.
[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.
[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 is our second algorithm that sorts lists of sortable objects. Here's the idea. (The variable S names a list of sortable objects.)
Find the smallest object in S. Move it to index 0.
Search S from index 1 on. Find the smallest element in that part. Move it to index 1.
Search S from index 2 on. Find the smallest element in that part. Move it to index 2.
Continue until the end of the list is reached.
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.
First find the smallest element from index 0 on. This is 1. Move 1 to the start of the list. The result is [1, 5, 4, 2, 8].
Find the smallest element from index 1 on. This is 2. Move 2 index 1. The result is [1, 2, 5, 4, 8].
Find the smallest element from index 2 on. This is 4. Move 4 to index 2. The result is [1, 2, 4, 5, 8].
Find the smallest element from index 3 on. This is 5. No move is needed.
We are now at the end of the list and so the list is sorted.
Name the function selection_sort. This is a non-fruitful function that mutates its input list.
It's often much easier to perform an operation on a sorted list than it is on an unsorted one. Determination of the median is an example.
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