Algo Toolbox and "Pythoneries"¶

Lists¶

Exercise: Split List¶

Write a function that split a list of length n, with n odd, into 3 parts:

the elements of the first half of the list (without the middle one)
the middle element
the elements of the second half of the list (without the middle one)

def splitlist(L):
    #FIXME

Pythonery¶

This can be simplified with Python list slices:

L[a:b] is the sub list of L with elements from positions a to b (b excluded)
L[:a] is the list L[0:a]
L[a:] is the list L[b:len(n)]
L[-1] is L[len(L)]

def splitlist(L):
        #FIXME

L = [1, 2, 3, 4, 5, 6, 7, 8, 9]
splitlist(L)

Exercise: Binary Search¶

Write two functions to search an element in a sorted (in increasing order) list:

binarysearch(L, x, left, right) returns the position where x is or might be in L[left, right[, with L sorted in increasing order.

def binarysearch(L, x, left, right):
    """Binary Search
    
    Args:
        L: List to search in
        x: Value to search
        left, right: Search intervalle in L [left, right[
        
    Returns:
        The position where x is or might be
    """

    #FIXME

L = [-3, 0, 5, 8, 13, 24, 32, 37, 42]

binarysearch(L, 0, 0, len(L))

listSearch(L, x) returns -1 if x in not in the list L, its position otherwise

def listsearch(L, x):
    #FIXME

Pythonery¶

Use Python "ternary" operator:

[on_true] if [expression] else [on_false]

def listsearch2(x, L):
    #FIXME

Exercise: Build List → Build Matrix

Write the function buildlist(nb, val = None, alea = None) that builds a new list of length nb:

buildlist(nb) returns [None, None, ...]
buildlist(nb, val) returns [val, val, ...]
buildlist(nb, alea = (a, b)) returns a list of nb random values in [a, b[

Note: if a: is False when a is 0, None, [], "" ...

# Reminder on imports, random and seed
import random
help(random.randint)

help(random.seed)
random.seed()    # do it once only!

def buildlist(nb, val = None, alea = None):
    #FIXME

Pythonery¶

Python gives a short way to build list: [val] * nb

def buildlist(nb, val = None, alea = None):
    #FIXME

Test the "short" version ([val] * n) with random numbers...

[random.randint(0, 10)] * 5

Pythonery: "list comprehension"¶

Test the following, then use it to write again buildlist

[i for i in range(10)]

def buildList(nb, val = None, alea = None):
    #FIXME

buildlist(5), buildList(5, 0), buildList(5, alea = (0,10))

WARNING:¶

when you want to build a list of lists

L = buildList(9, [])

L

L[0].append(1)

L

Write again buildlist to avoid the problem

def buildlist(nb, val = None, alea = None):
    #FIXME

Use buildlist to build a (5*5) matrix filled with None, then change a value

M = buildlist(4, buildlist(5, None))

M

M[0][0] = 5

M

Write a function buildmatrix(line, col, val = None) that builds a (line*col) matrix filled with val.

def buildmatrix(line, col, val = None):
     #FIXME

M = buildmatrix(4, 5)
M[0][0] = 3
M