ICC-P Corrigé 5

a = {1, 2, 3, 4, 5}
b = {4, 5, 6, 7, 8}

def my_union(a: set, b: set) -> set:
    result = set()
    for x in a:
        result.add(x)
    for x in b:
        result.add(x)
    return result

def my_intersection(a: set, b: set) -> set:
    result = set()
    for x in a:
        if x in b:
            result.add(x)
    return result

def my_difference(a: set, b: set) -> set:
    result = set()
    for x in a:
        if x not in b:
            result.add(x)
    return result

# verification against built-in operators
print(my_union(a, b) == a | b)  # True
print(my_intersection(a, b) == a & b)  # True
print(my_difference(a, b) == a - b)  # True

text = ["the", "cat", "sat", "on", "the", "mat", "the", "cat", "sat", "on", "a", "mat"]

def unique_words(words: list) -> set:
    return set(words)

print(unique_words(text))  # {'a', 'cat', 'mat', 'on', 'sat', 'the'}

def is_subset(a: set, b: set) -> bool:
    for x in a:
        if x not in b:
            return False
    return True

print(is_subset({1, 2}, {1, 2, 3}))  # True
print(is_subset({1, 6}, {1, 2, 3}))  # False
print(is_subset({1, 2}, {1, 2}))  # True

def my_equals(a: set, b: set) -> bool:
    return is_subset(a, b) and is_subset(b, a)

print(my_equals({1, 2, 3}, {3, 1, 2}))  # True
print(my_equals({1, 2, 3}, {1, 2}))  # False

# on définit le type Matrix comme étant équivalent à une liste de liste de floats
Matrix = list[list[float]]

# on définit une matrice
m1: Matrix = [[1, 2, 3], [9, 8, 7]]
m2: Matrix = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
m3: Matrix = [[0, 2], [2, 0]]
m4: Matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [1, 5, 7]]
m5: Matrix = [[1, 2, 3]]
m6: Matrix = [[1], [2], [3]]

def print_matrix(mat: Matrix) -> None:
    print("[")
    for row in mat:
        print(" ", end="")
        for val in row:
            print(val, end="")
            print(" ", end="")
        print("")
    print("]")

matrices = [m1, m2, m3, m4, m5, m6]
for m in matrices:
    print_matrix(m)

def dim_m(mat: Matrix) -> int:
    return len(mat)

def dim_n(mat: Matrix) -> int:
    m = dim_m(mat)
    if m == 0:
        return 0
    n = len(mat[0])
    for i in range(1, m):
        if len(mat[i]) != n:
            return 0
    return n

for m in matrices:
    print(f"{dim_m(m)}x{dim_n(m)}")

def identity(size: int) -> Matrix:
    mat: Matrix = []
    for i in range(size):
        line: list[float] = []
        for j in range(size):
            if i == j:
                line.append(1)
            else:
                line.append(0)
        mat.append(line)
    return mat

# version raccourcie avec compréhension de liste (avancé)
def identity2(size: int) -> Matrix:
    return [[int(i == j) for i in range(size)] for j in range(size)]

print(f"identity check: {identity(3) == m2}")

def empty(m: int, n: int) -> Matrix:
    mat: Matrix = []
    for _ in range(m):
        line: list[float] = []
        for _ in range(n):
            line.append(0)
        mat.append(line)
    return mat

# version raccourcie avec compréhension de liste (avancé)
def empty2(m: int, n: int) -> Matrix:
    return [[0 for _ in range(n)] for _ in range(m)]

def mult(mat1: Matrix, mat2: Matrix) -> Matrix:
    mat1_m, mat1_n = dim_m(mat1), dim_n(mat1)
    mat2_m, mat2_n = dim_m(mat2), dim_n(mat2)
    if mat1_m == 0 or mat2_m == 0 or mat1_n != mat2_m:
        return []
    mat3 = empty(mat1_m, mat2_n)
    for i in range(mat1_m):
        for j in range(mat2_n):
            sum = 0.0
            for k in range(mat2_m):
                sum += mat1[i][k] * mat2[k][j]
            mat3[i][j] = sum
    return mat3

print_matrix(mult(m1, m2))
print_matrix(mult(m5, identity(dim_n(m5))))
print_matrix(mult(identity(dim_m(m4)), m4))

numbers = sorted([1, 5, 6, 2, 8, 12, 5])
print(numbers)

def binary_search(values: list[int], item: int) -> int:
    from_index = 0
    to_index = len(values)
    while True:
        print(f"Searching {item} in {values[from_index:to_index]}")
        if to_index - from_index <= 0:
            return -1
        middle_index = (from_index + to_index) // 2
        if values[middle_index] == item:
            return middle_index
        else:
            if item < values[middle_index]:
                to_index = middle_index
            else:
                from_index = middle_index + 1

def binary_search_recursive(values: list[int], item: int, from_index: int = 0, to_index: int = -1) -> int:
    if to_index == -1:
        to_index = len(values)
    print(f"Searching {item} in {values[from_index:to_index]}")
    if to_index - from_index <= 0:
        return -1
    middle_index = (from_index + to_index) // 2
    if values[middle_index] == item:
        return middle_index
    elif item < values[middle_index]:
        return binary_search_recursive(values, item, from_index, middle_index)
    else:
        return binary_search_recursive(values, item, middle_index + 1, to_index)

for v in numbers:
    print(binary_search(numbers, v))
print(binary_search(numbers, 3))
print(binary_search(numbers, 7))
print(binary_search(numbers, 42))