# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Chapter 12 - Lists

# -------------------------------

# Lists are ordered collections of data items, just like tuples. The major difference with tuples is that lists are mutable. This makes them a highly flexible data structure, that you will find many uses for.

# ---

# ## List basics

# A list is a collection of elements.
#
# The elements of a list are *ordered*. Because they are ordered, you can access each of the elements of a list using an index, just like you can access the characters of a string, and just like you can access the elements of a tuple.
#
# In Python, lists are recognizable from the fact that they enclose their elements in square brackets (`[]`). You can get the number of elements in a list by using the `len()` function. You can use a `for` loop to traverse the elements of a list. You can mix data types in a list. You can apply the `max()`, `min()` and `sum()` functions to a list. You can test for the existence of an element in a list using the `in` operator (or for the non-existence by using `not in`).

# +
fruitlist = ["apple", "banana", "cherry", 27, 3.14]
print( len( fruitlist ) )
for element in fruitlist:
    print( element )
print( fruitlist[2] )

numlist = [314, 315, 642, 246, 129, 999]
print( max( numlist ) )
print( min( numlist ) )
print( sum( numlist ) )
print( 100 in numlist )
print( 999 in numlist )
# -

# **Exercise**: Write a `while` loop to print the elements of a list.

# Traversing a list using while.
fruitlist = ["apple", "banana", "cherry ", "durian", "orange"]


# Apart from the square brackets, lists seem to be a lot like tuples. Yet there is a big difference...

# ---

# ## Lists are mutable

# Because lists are mutable, you can change the contents of a list.
#
# To overwrite an element of a list, you can assign a new value to it.

fruitlist = ["apple", "banana", "cherry", "durian", "orange"]
print( fruitlist )
fruitlist[2] = "strawberry"
print( fruitlist )

# You can also overwrite list slices by assigning a new list to the slice. The slice you remove need not be of equal length to the new list you insert.

fruitlist = ["apple", "banana", "cherry", "durian", "orange"]
print( fruitlist )
fruitlist[1:3] = ["raspberry", "elderberry", "strawberry", "blueberry"]
print( fruitlist )

# You can insert new elements into a list by assigning them to an empty slice.

fruitlist = ["apple", "banana", "cherry", "durian", "orange"]
print( fruitlist )
fruitlist[1:1] = ["raspberry", "elderberry", "strawberry", "blueberry"]
print( fruitlist )

# You can delete elements from a list by assigning an empty list to a slice.

fruitlist = ["apple", "banana", "cherry", "durian", "orange"]
print( fruitlist )
fruitlist[1:3] = []
print( fruitlist )

# Using slices and assignments, you can adapt a list in any way that you like. However, it is easier to change lists using methods. There are many helpful methods available, which I am going to discuss below.
#
# **Exercise**: Change the list in the code block below by turning every word in the list into a word consisting of only capitals. At this point in the notebook, the way to do that is by using a while loop that uses a variable i that starts at 0 and runs up to `len(fruitlist)-1`. This is an index for all the elements of `fruitlist`, which you can change by simply assigning a new value to them. 

# Making capital fruits.
fruitlist = ["apple", "banana", "cherry", "durian", "orange"]


# ---

# ## Lists and operators

# Lists support the use of the operators `+` and `*`. These operators work similar as to how they work for strings. 
#
# You can add two lists together with the `+` operator, the result of which is a list which contains the elements of both lists involved. Of course, you have to assign the result to a variable to store it.
#
# You can multiply a list by a number to create a list that contains the elements of the original list, repeated as often as the number indicates. This can be a fast approach to create a list with all equal elements.

fruitlist = ["apple", "banana"] + ["cherry", "durian"]
print( fruitlist )
numlist = 10 * [0]
print( numlist )

# Note: With the `+` you can add a list to another list, but you cannot add a new element to a list, unless you turn that new element into a list with a single element by putting two square brackets around it. If you try to add something to a list that is not a list, Python will try to interpret it as a list -- if it can do that (which it can, for instance, for a string, which it can consider a list of letters); it will then still do the addition but the result will not be what you want. For instance, the code below tries to add a "cherry" to a list, but only the second addition actually does what is intended.

# +
fruitlist = ["apple", "banana"]
fruitlist += "cherry"
print( fruitlist )

fruitlist = ["apple", "banana"]
fruitlist += ["cherry"]
print( fruitlist )
# -

# ---

# ## List methods

# Python supports many methods to change lists or get information from them. You do not need to import a module to use them. Since they are methods, you call them using the syntax `<list>.<method>()`.
#
# **Important!** Lists are mutable and these methods actually *change* the list! It is not as you are used to with string methods, where the methods create a new string, and return it, while the original string remains. Most list methods have an irrevocable effect on the list they work on. Usually they have no return value, and you do not need one either, as the purpose of the methods is to change the list.

# ### `append()`

# `append()` attaches an item at the end of a list. You call the method with the item you wish to add as argument.

fruitlist = ["apple", "banana", "cherry", "durian"]
print( fruitlist )
fruitlist.append( "orange" )
print( fruitlist )

# An alternative for using the `append()` method is to add a list with one new element to the existing list with a `+`, and assign the resulting list to the original list variable. However, the `append()` method is preferable as it is more readable. `<list>.append(<element>)` is equivalent to `<list>[len(<list>):] = [<element>]`, or simply `<list> += [<element>]`.

# ### `extend()`

# `extend()` makes a list longer by appending the elements of another list at the end. You call the method with the list of which you want to add the elements as argument.

fruitlist = ["apple", "banana", "cherry", "durian"]
print( fruitlist )
fruitlist.extend( ["raspberry", "elderberry", "strawberry", "blueberry"] )
print( fruitlist )

# Just as with the `append()` method, you can extend an existing list with a new list by simply using the `+` operator, and assigning the result to the original list variable. And just as with the `append()` method, using the `extend()` method is preferable. `<list>.extend(<addlist>)` is equivalent to `<list>[len(<list>):] = <addlist>`.

# ### `insert()`

# `insert()` allows you to insert an element at a specific position in a list. It is called with two arguments, the first being the index of the location where you wish to insert the new element, and the second the new element itself. To insert an element at the front of the list, you can use index 0.

fruitlist = ["apple", "banana", "cherry", "durian"]
print( fruitlist )
fruitlist.insert( 2, "orange" )
print( fruitlist )

# `<list>.insert(<index>,<element>)` is equivalent to `<list>[<index>:<index>] = [<element>]`.

# ### `remove()`

# `remove()` allows you to remove an element from a list. The element you wish to remove is given as argument. If the element occurs in the list multiple times, only the first occurrence will be removed. If you try to remove an element that is not on the list, a runtime error is generated. 

fruitlist = ["apple", "banana", "cherry", "banana", "durian"]
print( fruitlist )
fruitlist.remove( "banana" )
print( fruitlist )

# ### `pop()`

# Like `remove()`, `pop()` removes an element from the list, but does so by index. It has one optional argument, which is the index of the element that you wish to remove. If you do not provide that argument, `pop()` removes the last element from the list. If the index is beyond the boundaries of the list, `pop()` generates a runtime error.
#
# A major difference with `remove()` is that `pop()` actually has a return value, namely the element that gets removed. This allows you to quickly process all the elements of a list, while emptying the list at the same time.

fruitlist = ["apple", "banana", "cherry", "durian"]
print( fruitlist )
print( fruitlist.pop() )
print( fruitlist )
print( fruitlist.pop( 0 ) )
print( fruitlist )

# ### `del`

# `del` is neither a method nor a function, but since it is often metioned in one breath with `remove()` and `pop()`, I place it here. `del` is a keyword that allows you to delete a list element, or list slice, by index. It is similar to `pop()` in functionality, but does not have a return value. Also, `pop()` cannot be used on slices. To use `del`, use the statement `del <list>[<index>]` or `del <list>[<index1>:<index2>]`.

fruitlist = ["apple", "banana", "cherry", "banana", "durian"]
del fruitlist[3]
print( fruitlist )

# ### `index()`

# `index()` returns the index of the first occurrence on the list of the element that is given to `index()` as argument. A runtime error is generated if the element is not found on the list.

fruitlist = ["apple", "banana", "cherry", "banana", "durian"]
print( fruitlist.index( "banana" ) )

# ### `count()`

# `count()` returns an integer that indicates how often the element that is passed to it as an argument occurs in the list.

fruitlist = ["apple", "banana", "cherry", "banana", "durian"]
print( fruitlist.count( "banana" ) )

# ### ``sort()``

# `sort()` sorts the elements of the list, from low to high. If the elements of the list are strings, it does an alphabetical sort. If the elements are numbers, it does a numeric sort. If the elements are mixed, it generates a runtime error, unless certain arguments are given.

# +
fruitlist = ["apple", "strawberry", "banana", "raspberry", "cherry", "banana", "durian", "blueberry"]
fruitlist.sort()
print( fruitlist )

numlist = [314, 315, 642, 246, 129, 999]
numlist.sort()
print( numlist )
# -

# To do a reverse sort, you can add an argument `reverse=<boolean>`.

fruitlist = ["apple", "strawberry", "banana", "raspberry", "cherry", "banana", "durian", "blueberry"]
fruitlist.sort( reverse=True )
print( fruitlist )

# Another argument that you can give `sort()` is a key. You have to provide this argument as `<list>.sort( key=<key> )`, whereby `<key>` is a function that takes one argument (the element that is to be sorted) and returns a value that is used as key. A typical use for the `key` argument is if you want to sort a list of strings, but want to do the sorting case-insensitively. So as key you want to use the elements, but in lower case, i.e., you want to apply the function `str.lower()` to the element. You call the sort as in the following example:

fruitlist = ["apple", "Strawberry", "banana", "raspberry", "CHERRY", "banana", "durian", "blueberry"]
fruitlist.sort() 
print( fruitlist )
fruitlist.sort( key=str.lower ) # case-insensitive sort
print( fruitlist )


# Note that for the key argument, you do not place parentheses after the function name. This is not a function call, it is an argument that tells Python which function to use to generate the key.
#
# You can write your own function to be used as key. For example, in the code below, `numlist` is sorted with the last digit of each number as the most important digit, followed by the middle digit:

# +
def revertdigits( element ):
    return (element%10)*100 + (int( element/10 )%10)*10 + int( element/100 )

numlist = [314, 315, 642, 246, 129, 999]
numlist.sort( key=revertdigits )
print( numlist )


# -

# Here is another example, that sorts a list of strings by string length, followed by alphabetical order:

# +
def len_alphabetical( element ):
    return len( element ), element 

fruitlist = ["apple", "strawberry", "banana", "raspberry", "cherry", "banana", "durian", "blueberry"]
fruitlist.sort( key=len_alphabetical )
print( fruitlist )


# -

# Note that the `len_alphabetical()` function returns a tuple. When two tuples are compared, first the first elements of both tuples are compared, and if they are equal, the second elements are compared. You can use this knowledge to create a `key` function which sorts a mixed list, e.g., a list which consists of both strings and numbers. Just let the `key` function return a tuple of which the first item indicates the type of the element represented by a number, and the second the element itself.

# +
def mixed_key( element ):
    if isinstance( element, str ):
        return 1, element
    return 0, element

mixedlist = ["apple", 0, "strawberry", 5, "banana", 2, "raspberry", 9, "cherry", "banana", 7, 7, 6, "blueberry"]
mixedlist.sort( key=mixed_key )
print( mixedlist )
# -

# At this point I can give a typical example of the use of "anonymous functions", which I introduced in the chapter on functions. Using an anonymous function to specify the key for the `sort()` method keeps the code for the key next to where you call the `sort()`, instead of elsewhere in the program. This may improve readability. Here is once more the example of the sorting of a list of strings by length, followed by alphabetical order, now using an anonymous function:

fruitlist = ["apple", "strawberry", "banana", "raspberry", "cherry", "banana", "durian", "blueberry"]
fruitlist.sort( key=lambda x: (len(x),x) )
print( fruitlist )

# ### `reverse()`

# `reverse()` simply reverses the elements of the list.

fruitlist = ["apple", "strawberry", "banana", "raspberry", "cherry", "banana", "durian", "blueberry"]
fruitlist.reverse()
print( fruitlist )

# ### Practice

# **Exercise**: Write a program that asks the user to enter some data, for instance the names of their friends. When the user wants to stop providing inputs, he just presses *Enter*. The program then displays an alphabetically sorted list of the data items entered. Do not just print the list, but print each item separately, on a different line.

# Present a sorted list.


# **Exercise**: Sort a list of numbers using their absolute values.

# Sorting with absolute values.
numlist = [-10, -7, -3, -2, 0, 1, 2, 5, 7, 8, 10]


# **Exercise**: Count how often each letter occurs in a string (case-insensitively). You can ignore every character that is not a letter. Of course, you should not introduce 26 variables to do this; instead, use a list of 26 items that all start at zero. Print the resulting counts. As index for the list you can use `ord(letter) - ord("a")`, where letter is a lower case letter (the `ord()` function is explained in the strings chapter). If you have troubles with this exercise, see the hints below the code block.

# Letter counting.
text = """Now, it's quite simple to defend yourself against a man armed
with a banana. First of all you force him to drop the banana; then, 
second, you eat the banana, thus disarming him. You have now rendered 
him helpless."""


# Hints: If I ask you to count how many times the letter "a" occurs in the string, you use one variable `count_a`, which you start at zero. Then you process the letters in the string using `for letter in text`, and every time you note that `letter` is "a", you add 1 to `count_a`. If I ask you to do the same for the letter "b", you may decide to track a `count_b` variable next to `count_a`. If I ask you to do that for all the letters of the alphabet (which I do indeed), a solution using 26 separate variables and 26 conditions would be very inelegant. However, a list of length 26 is actually equal to 26 variables. Call this list `countlist` and fill it with 26 times the value 0. The first element of this list, with index 0, you use to track the number of "a"s. The second, with index 1, you use to track the number of "b"s. Etcetera. But how do you know which of the elements of the list you have to increase when you have a variable `letter` which contains one of the letters of the alphabet? If you take `ord(letter)`, you get a number. If `letter` is "a", this number is 97, if `letter` is "b", the number is 98, etcetera. This means that if I calculate `ord(letter)-97`, and `letter` is indeed a (lower-case) letter of the alphabet, I get a number between 0 and 25, which I can use as the index for the list. Instead of 97, I prefer that you use `ord("a")`, as 97 is a "magic number". This means that if `letter` is in the alphabet, then you can add 1 to the variable that tracks the number of times the letter occurs using the command `countlist[ord(letter)-ord("a")] += 1`.

# ---

# ## Aliasing

# If you assign variable that contains a list to another variable, you might expect that you create a copy of the list in the second variable. But you are not doing that. You are actually creating an *alias* for the list, i.e., a new variable that is referring to the same list. This means that the new variable can be treated as a list, but any change that you make to the list it refers to, is visible in the original list variable, and vice versa. They are not different lists.

fruitlist = ["apple", "banana", "cherry", "durian"]
newfruitlist = fruitlist
print( fruitlist )
print( newfruitlist )
newfruitlist[2] = "orange"
print( fruitlist )
print( newfruitlist )

# Every variable in Python has an identification number. You can see it with the `id()` function. The ID number indicates which memory spot the variable refers to. For an alias of a list, the ID is the same as for the original list.

fruitlist = ["apple", "banana", "cherry", "durian"]
newfruitlist = fruitlist
print( id( fruitlist ) )
print( id( newfruitlist ) )

# If you want to create a copy of a list, you can do so using a little trick. Instead of using `<newlist> = <oldlist>`, you use the command `<newlist> = <oldlist>[:]`.

# +
fruitlist = ["apple", "banana", "cherry", "durian"]
newfruitlist = fruitlist
verynewfruitlist = fruitlist[:]

print( id( fruitlist ) )
print( id( newfruitlist ) )
print( id( verynewfruitlist ) )

fruitlist[2] = "orange"
print( fruitlist )
print( newfruitlist )
print( verynewfruitlist )
# -

# ### `is`

# The keyword `is` is introduced to compare the identities of two variables.

# +
fruitlist = ["apple", "banana", "cherry", "durian"]
newfruitlist = fruitlist
verynewfruitlist = fruitlist[:]

print( fruitlist is newfruitlist )
print( fruitlist is verynewfruitlist )
print( newfruitlist is verynewfruitlist )
# -

# As you can see, the keyword `is` manages to determine that `fruitlist` and `newfruitlist` are aliases, but that `verynewfruitlist` is not the same list. If you compare them with the `==` operator, the results are not the same as comparing them with `is`:

# +
fruitlist = ["apple", "banana", "cherry", "durian"]
newfruitlist = fruitlist
verynewfruitlist = fruitlist[:]

print( fruitlist == newfruitlist )
print( fruitlist == verynewfruitlist )
print( newfruitlist == verynewfruitlist )
# -

# The `==` operator actually compares the contents of the lists, so it returns `True` for all comparisons. For data types for which `==` is not defined, it executes an identity comparison, but for lists it has been defined as a comparison of the contents. I will return to this topic when discussing "operator overloading", much later in the course.

# ### Shallow vs. deep copies

# If (some of) the items of your list are lists themselves (or other mutable data structures which are introduced in the next chapters), copying the list using the `<newlist> = <oldlist>[:]` syntax may give problems. The reason is that such a copy is a "shallow copy", which means that it copies each of the elements of the list with a regular assignment, which entails that the items in the list that are lists themselves become aliases of the items on the original list.

# +
numlist = [ 1, 2, [3, 4] ]
copylist = numlist[:]

numlist[0] = 5
numlist[2][0] = 6
print( numlist )
print( copylist )
# -

# In the code above, you can see that the assignment `numlist[0] = 5` only has an effect on `numlist`, as `copylist` contains a copy of numlist. However, since this is a shallow copy, the assignment to `numlist[2][0]` has an effect on both lists, as the sublist `[3, 4]` is stored in `copylist` as an alias.
#
# If you want to create a "deep copy" of a list (i.e., a copy that also contains true copies of all mutable substructures of the list, which in turn contain true copies of all their mutable substructures, etcetera), then you can use the `copy` module for that. The `deepcopy()` function from the copy module allows you to create deep copies of any mutable data structure.

# +
from copy import deepcopy

numlist = [ 1, 2, [3, 4] ]
copylist = deepcopy( numlist )

numlist[0] = 5
numlist[2][0] = 6
print( numlist )
print( copylist )


# -

# Note that the `copy` module also contains a function `copy()` that makes shallow copies. If you wonder why that function is included as you can easily create shallow copies of lists with the `<newlist> = <oldlist>[:]` command: the `copy` module not only works for lists, but for any mutable data structure. Not for all such data structures there exist shortcuts to create shallow copies. 

# ### Passing lists as arguments

# When you pass a list as an argument to a function, this is a "pass by reference". The parameter that the function has access to will be an alias for the list that you pass. This means that a function that you pass a list to, can actually change the contents of the list.
#
# This is important, so I repeat it: when you pass a mutable data structure to a function, this is a "pass by reference", meaning that the data structure is passed as an alias and the function can change the contents of the data structure.
#
# You have to know whether a function that you pass a list to will or will not change the list. If you do not want the function to change the list, and you do not know if it will, you best pass a deep copy of the list to the function.

# +
def changelist( x ):
    if len( x ) > 0:
        x[0] = "CHANGE!"
        
fruitlist = ["apple", "banana", "cherry", "durian"]
changelist( fruitlist )
print( fruitlist )
# -

# The reason that a list is "passed by reference" and not "by value" is that technically, every argument that is passed to a function must be stored in the computer in a specific block of memory that is part of the processor. This is called the "stack", and it is pretty limited in size. Since lists can be really long, allowing a program to place a list on the stack would cause all kinds of annoying runtime errors. In Python, as in most other programming languages, for the most part only basic data types (such as integers, floats, and strings) are passed by value.

# ---

# ## Nested lists

# The elements of a list may be lists themselves (which also may contains lists, etcetera). This is a good way to create a matrix in a program. For instance, you can create a Tic-Tac-Toe board, where a dash (`-`) represents an empty cell, as follows:

board = [ ["-", "-", "-"], ["-", "-", "-"], ["-", "-", "-"] ]


# The first row of the board is represented by `board[0]`, the second row by `board[1]`, and the third row by `board[2]`. If you want to access the first cell of the first row, that is `board[0][0]`, the second cell is `board[0][1]` and the third cell is `board[0][2]`.
#
# For example, the following code places an "X" in the middle of the board, and an "O" in the upper right corner. It also displays the board in a nice way (with markers for rows and columns around it).

# +
def display_board( b ):
    print( "  1 2 3" )
    for row in range( 3 ):
        print( row+1, end=" ")
        for col in range( 3 ):
            print( b[row][col], end=" " )
        print()
           
board = [ ["-", "-", "-"], ["-", "-", "-"], ["-", "-", "-"] ]
board[1][1] = "X"
board[0][2] = "O"
display_board( board )
# -

# ---

# ## List casting

# You can type cast a sequence of elements to a list using the `list()` function.

t1 = ( "apple", "banana", "cherry" )
print( t1 )
print( type( t1 ) )
fruitlist = list( t1 )
print( fruitlist )
print( type( fruitlist ) )

# This is sometimes necessary, in particular when you have an "iterator" available and you want to use the elements in a list format. An iterator is a function that generates a sequence. An example of an iterator that I already discussed is the `range()` function. The `range()` function generates a sequence of numbers. If you want to use these numbers as a list, you can use list casting.

numlist = range( 1, 11 )
print( numlist )
numlist = list( range( 1, 11 ) )
print( numlist )


# You can turn a string into a list of its characters by using a list casting on the string.

# ---

# ## List comprehensions

# List comprehensions are a concise way to create lists. They are typical for Python, but you do not find them in many other programming languages. They are not actually needed, as you can use functions to achieve the same effect, but as they are often used in examples (especially by people who want to show off their Python abilities to create short statements that have extensive effects), I thought it prudent to discuss them.
#
# Suppose that you want to create a list consisting of the squares of the numbers 1 to 25. A function that creates such a list is:

# +
def squareslist():
    squares = []
    for i in range( 1, 26 ):
        squares.append( i*i )
    return squares

sl = squareslist()
print( sl )
# -

# In Python, you can create that list with one single statement, namely as follows:

sl = [ x*x for x in range( 1, 26 )]
print( sl )

# Now suppose that you want to create this list, but want to leave out (for some reason) the squares of any numbers that end in 5. That would add at least two lines to the function above, but with list comprehensions you can still do it with that single line:

sl = [ x*x for x in range( 1, 26 ) if x%10 != 5]
print( sl )

# A list comprehension consists of an expression in square brackets, followed by a `for` clause, followed by zero or more `for` and/or `if` clauses. The result is a list that contains the elements that result from evaluating the expression for the combination of the `for` and `if` clauses.
#
# The results can become quite complex. For instance, here is a list comprehension that creates a list of tuples with three integers between 1 and 4, whereby the three integers are all different:

triplelist = [ (x,y,z) for x in range( 1, 5 ) for y in range( 1, 5 ) for z in range( 1, 5 ) 
              if x != y if x != z if y != z]
print( triplelist )

# If you find list comprehensions hard to use, remember that there is absolutely no reason to use them except for keeping code concise, and that keeping code readable and understandable is far more important than keeping it concise.

# ---

# ## What you learned

# In this chapter, you learned about:
#
# - Lists
# - Mutability of lists
# - Using `+` and `*` with lists
# - List methods `append()`, `extend()`, `insert()`, `remove()`, `pop()`, `index()`, `count()`, `sort()`, and `reverse()`
# - `del` with lists
# - Aliasing
# - The keyword `is`
# - Creating list copies
# - Creating deep copies of lists using `deepcopy()`
# - Using lists as arguments
# - Nested lists
# - List casting
# - List comprehensions

# -------------

# ## Exercises

# ### Exercise 12.1

# A magic 8-ball, when asked a question, provides a random answer from a list. The code below contains a list of possible answers. Create a magic 8-ball program that asks a question, then gives a random answer.

# Magic 8-ball
answers = [ "It is certain", "It is decidedly so", "Without a doubt",
    "Yes, definitely", "You may rely on it", "As I see it, yes",
    "Most likely", "Outlook good", "Yes", "Signs point to yes",
    "Reply hazy try again", "Ask again later", "Better not tell you now",
    "Cannot predict now", "Concentrate and ask again", "Don't count on it",
    "My reply is no", "My sources say no", "Outlook not so good",
    "Very doubtful" ]


# ### Exercise 12.2

# A playing card consists of a suit ("Hearts", "Spades", "Clubs", or "Diamonds") and a value ("Ace", 2, 3, 4, 5, 6, 7, 8, 9, 10, "Jack", "Queen", "King"). Create a list of all possible playing cards, which is a deck. Then create a function that shuffles the deck, producing a random order.

# Shuffling a deck.


# ### Exercise 12.3

# A first-in-first-out (FIFO) structure, also called a "queue", is a list that gets new elements added at the end, while elements from the front are removed and processed. Write a program that processes a queue. In a loop, ask the user for input. If the user just presses the *Enter* key, the program ends. If the user enters anything else, except for a single question mark (`?`), the program considers what the user entered a new element and appends it to the queue. If the user enters a single question mark, the program pops the first element from the queue and displays it. You have to take into account that the user might type a question mark even if the queue is empty.  

# Queue.


# ### Exercise 12.4

# Count how often each letter occurs in a string (case-insensitively). You can ignore every character that is not a letter. Print the letters with their counts, in order from highest count to lowest count.

# Letter counting.


# ### Exercise 12.5

# The sieve of Eratosthenes is a method to find all prime numbers between 1 and a given number using a list. This works as follows: Fill the list with the sequence of numbers from 1 to the highest number. Set the value of 1 to zero, as 1 is not prime. Now loop over the list. Find the next number on the list that is not zero, which, at the start, is the number 2. Now set all multiples of this number to zero. Then find the next number on the list that is not zero, which is 3. Set all multiples of this number to zero. Then the next number, which is 5 (because 4 has already been set to zero), and do the same thing again. Process all the numbers of the list in this way. When you have finished, the only numbers left on the list are primes. Use this method to determine all the primes between 1 and 100.

# Eratosthenes.


# ### Exercise 12.6

# Write a Tic-Tac-Toe program that allows two people to play the game against each other. In turn, ask each player which row and column they want to play. Make sure that the program checks if that row/column combination is empty. When a player has won, end the game. When the whole board is full and there is no winner, announce a draw.

# Tic-Tac-Toe player.


# This is a fairly long program to write (60 lines or so). It will definitely help to use some functions. I recommend that you create a function `display_board()` that gets the board as parameter and displays it, a function `getRowCol()` that asks for a row or a column (depending on a parameter) and checks whether the user entered a legal value, and a function `winner()` that gets the board as argument and checks if there is a winner. Keep track of who the current player is using a global variable `player` that you can pass to a function as an argument if the function needs it. I also use a function `opponent()`, that takes the player as argument and returns the opponent. I use that to switch players after each move.
#
# The main program will be something along the lines of (in pseudo-code):
#
#     display board
#     while True:
#         ask for row
#         ask for column
#         if row/column combination already occupied:
#             display error message
#             continue
#         place player marker on row/column combination
#         display board
#         if there is a winner
#             announce winner
#             break
#         if the board is full
#             announce draw
#             break
#         switch players

# ### Exercise 12.7

# Create a program that is a simplified version of the game "Battleship". The computer creates (in memory) a grid that is 4 cells wide and 3 cells high. The rows of the grid are numbered 1 to 3, and the columns of the grid are labeled `A` to `D`. The computer hides a battleship in three random cells in the grid. Each battleship occupies exactly one cell. Battleships are not allowed to touch each other horizontally or vertically. Make sure that the program places the battleships randomly, so not pre-configured.
#
# The computer asks the player to "shoot" at cells of the grid. The player does so by entering the column letter and row number of the cell which he wants to shoot at (e.g., "D3"). If the cell which the player shoots at contains nothing, the computer responds with "Miss!". If the cell contains a battleship, the computer responds with "You sunk my battleship!", and removes the battleship from the cell (i.e., a second shot at the same cell is a miss). As soon as the player hits the last battleship, the computer responds with displaying how many shots the player needed to shoot down all three battleships, and the program ends.
#
# To help with debugging the game, at the start the computer should display the grid with periods marking empty cells and `X`s marking cells with battleships.
#
# Hint: If you have troubles with this exercise, start by using a board which has the battleships already placed. Once the rest of the code works, add a function that places the battleships at random, at first without checking if they are touching one another. Once that works, add code that disallows battleships touching each other.

# Battleship.


# ### Exercise 12.8

# The "subset sum" problem asks the question whether a list of integers contains a subset of integers that, when summed, gives zero as answer. For instance, for the list `[1, 4, -3, -5, 7]` the answer is "yes", as `1 + 4 - 5 = 0`. However, for the list `[1, 4, -3, 7]` the answer is "no", as there is no subset of integers that adds up to zero. Write a program that solves the "subset sum" problem for a list of integers. If there is a solution, print it; if not, report that there is no solution.
#
# Hint: This problem is tackled best using recursion. If you skipped that chapter, you better skip this exercise too.

# Subset sum problem.


# ---

# ## Python 2

# In Python 2, sorting a mixed list does not give a runtime error. The `sort()` function also supports an argument `cmp=<function>`, that allows you to specify a function that does the comparison between two elements. This function is no longer supported in Python 3, but you can use the `key` parameter for the same purpose. In the Python module `functools` a function `cmp_to_key()` is found that turns the old-style `cmp` specification into the new-style `key` specification.
#
# In Python 2, the `range()` function produces an actual list, and you do not need list casting to turn the result of it into one.

# --------

# End of Chapter 12. Version 1.3.

StarcoderdataJupyterScriptsDedupFiltered