Lecture 2 : Application

November, 2021 - François HU

Master of Science in Artificial Intelligence Systems - EPITA

This lecture is available here: https://curiousml.github.io/

Table of contents

Lecture 1: correction and remarks

Graded project

Correction and feedback

You will find bellow the correction of the exercices of the first lecture.

Exercice 1.

Create the following list with loops:

[['car', 0, 1, 4, 9, 16],
 ['bus', 1, 4, 9, 16, 25],
 ['train', 4, 9, 16, 25, 36],
 ['boat', 9, 16, 25, 36, 49]]

Create a script that prints this list in the following manner:

car      0    1    4    9   16
bus      1    4    9   16   25
train    4    9   16   25   36
boat     9    16  25   36   49

Common mistake 1

Instead of generating the list with for loops, many of you gave me the answer:

# No: need at least a loop instead of manually putting the numbers
L = [['car', 0, 1, 4, 9, 16],
 ['bus', 1, 4, 9, 16, 25],
 ['train', 4, 9, 16, 25, 36],
 ['boat', 9, 16, 25, 36, 49]]

L

[['car', 0, 1, 4, 9, 16],
 ['bus', 1, 4, 9, 16, 25],
 ['train', 4, 9, 16, 25, 36],
 ['boat', 9, 16, 25, 36, 49]]

Common mistake 2

some of you gave me four independant lists instead of a single list (of lists)

# No: create a list including these independant lists
l1 = ["car"] + [i**2 for i in range(5)]
l2 = ["bus"] + [i**2 for i in range(1, 6)]
l3 = ["train"] + [i**2 for i in range(2, 7)]
l4 = ["boat"] + [i**2 for i in range(3, 8)]

print(l1)
print(l2)
print(l3)
print(l4)

# one should add for example the line: L = [l1, l2, l3, l4]

['car', 0, 1, 4, 9, 16]
['bus', 1, 4, 9, 16, 25]
['train', 4, 9, 16, 25, 36]
['boat', 9, 16, 25, 36, 49]

Common mistake 3

first_index = ['car','bus','train','boat']
list=[]

#Populating list
for i in first_index:
    row_first_number = len(list)
    list.append([i])
    for j in range(row_first_number,(row_first_number+5)):
        if j==0:  
            list[row_first_number].append(0) 
        else:
            list[row_first_number].append(j**2)

#Printing list
for i in list:
    for j in i:
        print(j,'\t',end=" ")
    print("\n")

car 	 0 	 1 	 4 	 9 	 16 	 

bus 	 1 	 4 	 9 	 16 	 25 	 

train 	 4 	 9 	 16 	 25 	 36 	 

boat 	 9 	 16 	 25 	 36 	 49 	 

• Be carfeful of your variable names. list is already a python-object, therefore you may encounter some conflict. Suggested: write other name for instantiating your list (like lst)

l = list()
print(l)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
/var/folders/55/c2kg8h2d2wnfzx5wnypmt8kr0000gn/T/ipykernel_2143/2873245483.py in <module>
----> 1 l = list()
      2 print(l)

TypeError: 'list' object is not callable

del list
l = list()
print(l)

Solution proposed by a student 1

x = ['car','bus','train','boat']
odd = [i**2 for i in range(15)]

num = []
lign = 0 # not needed
index = 0 # not needed
temp = [] # not needed
for lign in range(4):
    temp = []
    temp.append(x[lign])
    for index in range(5):
        temp.append( odd[index+lign] )
    num.append(temp)
    
num

[['car', 0, 1, 4, 9, 16],
 ['bus', 1, 4, 9, 16, 25],
 ['train', 4, 9, 16, 25, 36],
 ['boat', 9, 16, 25, 36, 49]]

• It works !
• pros: we compute $i^2$ one time for all lists so we gain in time and space complexity
• cons: there are some unnecessary lines here

Solution proposed by a student 2

trans = ["car", "bus", "train", "boat"]
total = []

for a in range(4):
    temp = []
    temp.append(trans[a])
    for b in range(1,6):
        temp.append(a**2)
        a = a + 1 # it works but dangerous
    total.append(temp)

total

[['car', 0, 1, 4, 9, 16],
 ['bus', 1, 4, 9, 16, 25],
 ['train', 4, 9, 16, 25, 36],
 ['boat', 9, 16, 25, 36, 49]]

• It works !
• pros: very intuitive
• cons: when one uses a for loop, it is often advised to not reassign the items of the iterator

Suggested correction

# There are many ways to do it.
transports = ["car", "bus", "train", "boat"]

L = [] # my final list (of lists)
for index, transport in enumerate(transports):
    line = [transport] + [i**2 for i in range(index, 5+index)]
    L.append(line)
    
L

[['car', 0, 1, 4, 9, 16],
 ['bus', 1, 4, 9, 16, 25],
 ['train', 4, 9, 16, 25, 36],
 ['boat', 9, 16, 25, 36, 49]]

for line in L:
    for item in line:
        print(item, end="\t")
    print()

car	0	1	4	9	16	
bus	1	4	9	16	25	
train	4	9	16	25	36	
boat	9	16	25	36	49	

Another way to print

str_to_print = ""
for line in L:
    for item in line:
        str_to_print += "\t"
        str_to_print += str(item)
    str_to_print += "\n"
        
print(str_to_print)

	car	0	1	4	9	16
	bus	1	4	9	16	25
	train	4	9	16	25	36
	boat	9	16	25	36	49

for line in L:
    print( * line, sep = '\t')

car	0	1	4	9	16
bus	1	4	9	16	25
train	4	9	16	25	36
boat	9	16	25	36	49

Exercice 2.

For the following list of dictionaries, write a script that add a field registrations which is twice the number of accepted papers.

confs = [{"Name": "NeurIPS", "Date": 2016, "Location": "Barcelona", "acc_papers": 300},
             {"Name": "ICML", "Date": 2016, "Location": "New York City", "acc_papers": 450},
             {"Name": "ICML", "Date": 2015, "Location": "Lille", "acc_papers": 250},
             {"Name": "AISTATS", "Date": 2016, "Location": "Cadiz", "acc_papers": 100}]

Common mistake 1

confs needs some clarification . This is a list of dictionaries. More precisely it is one list containing four dictionaries and each dictionary contains four fields (or keys) : "Name", "Date", "Location" and "acc_papers" -> Here in each dictionary of the list we want to add fifth field named registration which the value is twice the number of accepted paper.

Suggested correction

for conf in confs:
    conf["registrations"] = conf["acc_papers"] * 2
    
confs

[{'Name': 'NeurIPS',
  'Date': 2016,
  'Location': 'Barcelona',
  'acc_papers': 300,
  'registrations': 600},
 {'Name': 'ICML',
  'Date': 2016,
  'Location': 'New York City',
  'acc_papers': 450,
  'registrations': 900},
 {'Name': 'ICML',
  'Date': 2015,
  'Location': 'Lille',
  'acc_papers': 250,
  'registrations': 500},
 {'Name': 'AISTATS',
  'Date': 2016,
  'Location': 'Cadiz',
  'acc_papers': 100,
  'registrations': 200}]

Exercice 3.

Write a function include, that produces the following results:

>>> l = [0]
>>> include(l, 2)
>>> print(l)
[0, 2]
>>> include(l, "-1")
>>> print(l)
[0, 2, '-1']
>>> include(l)
>>> print(l)
[]

Let us clarify this exercice: Our objective is to create a function that:

• appends item to the list (in an inline manner)
• clears the list if we don't give a second argument (in an inline manner)

Common mistake 1

def include(l, item):
    l.append(item)
    return l

l = [0]
include(l, 2)
print(l)
include(l, "-1")
print(l)
include(l)
print(l)

[0, 2]
[0, 2, '-1']

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
/var/folders/55/c2kg8h2d2wnfzx5wnypmt8kr0000gn/T/ipykernel_2143/2280774624.py in <module>
      4 include(l, "-1")
      5 print(l)
----> 6 include(l)
      7 print(l)

TypeError: include() missing 1 required positional argument: 'item'

Common mistake 2

def include(l, item = None):
    if item == None: # recommended to use `is None`
        l = []
        return l
    else:
        l.append(item) # or `l += [item]`
        return l

l = [0]
include(l, 2)
print(l)
include(l, "-1")
print(l)
include(l)
print(l)

[0, 2]
[0, 2, '-1']
[0, 2, '-1']

• No need to return a value here
• Error with l = []

Common mistake 3

def include(l, item=None):
    if item:
        l.append(item)
        return l
    else:
        l.clear()
        return []

l = [0]
include(l, 2)
print(l)
include(l, "-1")
print(l)
include(l)
print(l)

[0, 2]
[0, 2, '-1']
[]

• include(l, 0) will return [].

include(l, 0)
print(l)

[]

Suggested correction

def include(l, item = None):
    if item is None:
        del l[:]
    else:
        l.append(item)

l = [0]
include(l, 2)
print(l)
include(l, "-1")
print(l)
include(l)
print(l)

[0, 2]
[0, 2, '-1']
[]

Or alternatively

def include(l, item = None):
    if item is None:
        l.clear()
    else:
        l.append(item)

l = [0]
include(l, 2)
print(l)
include(l, "-1")
print(l)
include(l)
print(l)

[0, 2]
[0, 2, '-1']
[]

Exercice 4.

Create a module, that contains a function fibonacci(n) computing the $n^{th}$ Fibonacci number. Then create a script using this function.

Common mistake 1

Functions of a module should be in a python file (extension .py) not in a ipython notebook file (extension .ipynb)

Common mistake 2

def fibo(n):
    """
    mistake 1 : print instead of return
    mistake 2 : do not use a and b in the statements
    """
    a,b=0,1
    if n<a:
        print('negative')
    elif n==a:
        print(a) # here: problem
    elif n==b:
        print(b) # here: problem
    else:
        while a<n:
            print(a, end=' ')
            a, b=b, a+b # here: problem

fibo(10) # should be 55

0 1 1 2 3 5 8 

Common mistake 3

def fibonacci_ite(n): # iterative approach
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    F = [0, 1]
    for i in range(1, n):
        F.append(F[i] + F[i-1])
    return F[n]

def fibonacci(n):
    b = 0
    if n == 1:
        b = 1
    elif n > 1:
        a = 0
        sum = 1
        for i in range(n-1):
            b = sum + a
            a = sum
            sum = b
    return b

fibonacci(10)

55

• don't take account negative numbers
• sum is a built-in function name
• we can swap values with a, b = b, a

a = 1
b = 2
print(a,b)

a, b = b, a
print(a,b)

1 2
2 1

Suggested correction

• fibonacci_rec: recursive approach
• fibonacci_ite: iterative approach

def fibonacci_rec(n): # recursive approach
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_rec(n-1) + fibonacci_rec(n-2)

fibonacci_rec(10)

55

fibonacci_rec(-1)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
/var/folders/55/c2kg8h2d2wnfzx5wnypmt8kr0000gn/T/ipykernel_2143/4136678502.py in <module>
----> 1 fibonacci_rec(-1)

/var/folders/55/c2kg8h2d2wnfzx5wnypmt8kr0000gn/T/ipykernel_2143/3168884607.py in fibonacci_rec(n)
      1 def fibonacci_rec(n): # recursive approach
      2     if n < 0:
----> 3         raise ValueError("Negative arguments not implemented")
      4     elif n == 0:
      5         return 0

ValueError: Negative arguments not implemented

def fibonacci_ite(n): # iterative approach
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    F = [0, 1]
    for i in range(1, n):
        F.append(F[i] + F[i-1])
    return F[n]

fibonacci_ite(10)

55

fibonacci_ite(-1)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
/var/folders/55/c2kg8h2d2wnfzx5wnypmt8kr0000gn/T/ipykernel_2143/3775388262.py in <module>
----> 1 fibonacci_ite(-1)

/var/folders/55/c2kg8h2d2wnfzx5wnypmt8kr0000gn/T/ipykernel_2143/3172447240.py in fibonacci_ite(n)
      1 def fibonacci_ite(n): # iterative approach
      2     if n < 0:
----> 3         raise ValueError("Negative arguments not implemented")
      4     F = [0, 1]
      5     for i in range(1, n):

ValueError: Negative arguments not implemented

Exercice 5.

Change the class Point (the toy example bellow) in order to take account a 3rd coordinate z.

class Point:
    def __init__(self, x, y):          
        self.x = x                     
        self.y = y                     
        self.norm = self.compute_norm()

    def compute_norm(self):
        norm = (self.x**2 + self.y**2)**(0.5) 
        return norm

    def __add__(self, another_point) :
         return Point(self.x + another_point.x, self.y + another_point.y)

Then execute the following script.

p1 = Point(1, -1, 1)
p2 = Point(1, 1, 3)
p3 = p1 + p2

print(f"p1 = ({p1.x}, {p1.y}, {p1.z})")
print(f"p2 = ({p2.x}, {p2.y}, {p2.z})")
print(f"p3 = ({p3.x}, {p3.y}, {p3.z})")

Suggested correction

class Point:
    def __init__(self, x, y, z):           # add a new argument: z
        self.x = x
        self.y = y
        self.z = z                         # initialize the attribute z
        self.norm = self.compute_norm()

    def compute_norm(self):
        norm = (self.x**2 + self.y**2 + self.z**2)**(0.5) # for the norm computation, take z into account
        return norm

    def __add__(self, another_point):      # dont forget to add the 3rd coordinate
         return Point(self.x + another_point.x, self.y + another_point.y, self.z + another_point.z)

p1 = Point(1, -1, 1)
p2 = Point(1, 1, 3)
p3 = p1 + p2

print(f"p1 = ({p1.x}, {p1.y}, {p1.z})")
print(f"p2 = ({p2.x}, {p2.y}, {p2.z})")
print(f"p3 = ({p3.x}, {p3.y}, {p3.z})")

p1 = (1, -1, 1)
p2 = (1, 1, 3)
p3 = (2, 0, 4)

Project: sudoku

Objective : solve a problem with nested functions. The project this year is a sudoku game. Citation wikipedia about the sudoku game

the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (a.k.a. "boxes", "blocks", or "regions") contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Your 9x9 sudoku will have the following form (0 corresponds to an empty cell)

grid_wiki =   [[5, 3, 0, 0, 7, 0, 0, 0, 0],
               [6, 0, 0, 1, 9, 5, 0, 0, 0],
               [0, 9, 8, 0, 0, 0, 0, 6, 0],
               [8, 0, 0, 0, 6, 0, 0, 0, 3],
               [4, 0, 0, 8, 0, 3, 0, 0, 1],
               [7, 0, 0, 0, 2, 0, 0, 0, 6],
               [0, 6, 0, 0, 0, 0, 2, 8, 0],
               [0, 0, 0, 4, 1, 9, 0, 0, 5],
               [0, 0, 0, 0, 8, 0, 0, 7, 9]]

step 1.

Define a function row_unused_digit(grid, valid_digit, i) that updates the list valid_digit so that the function checks for each column k in row i of the sudoku grid whether the digit grid[i][k] is not zero. valid_digit[k] == 0 means that k+1 is already taken in row i.

def row_unused_digit(grid, valid_digit, i):
    """
    Input:
    - grid:           the sudoku
    - valid_digit:    ``valid_digit[k] == 0`` means number *k+1* is already taken on this line
    - i:              row index (0 based: the index is between 0 and 8)
    """
    for k in range(9):
        if grid[i][k] > 0:
            valid_digit[grid[i][k] - 1] = 0

step 2.

Define a function column_unused_digit(grid, valid_digit, j) that updates the list valid_digit so that the function checks for each row k in column j of the sudoku grid whether the digit grid[k][j] is not zero. valid_digit[k] == 0 means that k+1 is already taken in column j.

step 3.

Define a function block_unused_digit(grid, valid_digit, i, j) that updates the list valid_digit so that the function checks whether for each digit in the block including row i and column j is not zero. valid_digit[k] == 0 means that k+1 is already taken in the block containing (i, j).

step 4.

Define a function possible_number(grid, i, j) that returns, for a certain position grid[i][j], the list of possible numbers

step 5.

Define a function best_cell(grid) that looks at all the empty cells of the sudoku grid and chooses the cell with the least number of options. You should have the following results:

>>> best_cell(grid_wiki)
(4, 4, [0, 0, 0, 0, 1, 0, 0, 0, 0])

step 6.

define a function solve_sudoku(grid) which solves the sudoku. This function returns 0 if the sudoku is impossible to solve (1 otherwise). it should do the following steps:

• Find the position of a zero element (no number yet) with the smallest number of options;
• If there is at least one possible option, try the first one;
• If not, the Sudoku cannot be solved, go back to last list of multiple options and try the next one.

step 7.

Define a function sudoku2str(grid) that converts a sudoku grid into a string. Desired result for the sudoku grid_wiki:

>>> print(sudoku2str(grid_wiki))
>>>
------------------------------
 | _ _ _  | 3 _ _  | 8 _ _  |
 | _ _ 7  | 9 _ 8  | _ _ 5  |
 | _ _ _  | 2 _ 4  | 1 _ _  |
------------------------------
 | _ 9 _  | 8 1 _  | _ 4 7  |
 | _ 4 _  | _ _ _  | _ _ 6  |
 | _ _ _  | _ _ _  | _ _ _  |
------------------------------
 | _ 1 _  | _ _ 5  | _ 2 _  |
 | 5 3 4  | _ _ _  | _ _ _  |
 | _ _ _  | 7 _ _  | _ _ _  |
------------------------------

step 8.

Solve the soduku grid_wiki and print the solution grid. You should have th following results

>>> solve_sudoku(grid_wiki)
>>> print(sudoku2str(grid_wiki))
------------------------------
 | 5 3 4  | 6 7 8  | 9 1 2  |
 | 6 7 2  | 1 9 5  | 3 4 8  |
 | 1 9 8  | 3 4 2  | 5 6 7  |
------------------------------
 | 8 5 9  | 7 6 1  | 4 2 3  |
 | 4 2 6  | 8 5 3  | 7 9 1  |
 | 7 1 3  | 9 2 4  | 8 5 6  |
------------------------------
 | 9 6 1  | 5 3 7  | 2 8 4  |
 | 2 8 7  | 4 1 9  | 6 3 5  |
 | 3 4 5  | 2 8 6  | 1 7 9  |
------------------------------