ICC-P Corrigé 4

x: int = 10
fibo: list[int] = []
fibo.extend([0, 1])
for i in range(2, x):
    fibo.append(fibo[i - 1] + fibo[i - 2])

print(fibo)
for f in fibo:
    print(f)

for i, f in enumerate(fibo):
    print(f"F({i}) = {f}")

from random import randint

def has_duplicates1(l: list[int]) -> bool:
    for i, v in enumerate(l):
        for j, w in enumerate(l):
            if i != j and v == w:
                return True
    return False


def has_duplicates2(l: list[int]) -> bool:
    length = len(l)
    for i in range(length):
        for j in range(i + 1, length):
            if l[i] == l[j]:
                return True
    return False

# Bonus: Solution alternative utilisant sorted():
def has_duplicates3(l: list[int]) -> bool:
    sl = sorted(l)
    for i in range(len(sl)-1):
        if sl[i] == sl[i+1]:
            return True
    return False

# Bonus: Solution alternative utilisant set():
def has_duplicates4(l: list[int]) -> bool:
    # Note: set(l) converti la liste en set (ce qui retire les doublons)
    return len(l) != len(set(l))


has_duplicates = has_duplicates1  # change to has_duplicates2 to test other method

print(has_duplicates([]))  # False
print(has_duplicates([9, 3, 2, 5, 1]))  # False
print(has_duplicates([1, 1]))  # True
print(has_duplicates([1, 2, 2, 3, 1, 5, 1]))  # True


def find_duplicates1(l: list[int]) -> list[int]:
    dupes: list[int] = []
    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[i] == l[j] and l[i] not in dupes:
                dupes.append(l[i])
    return dupes

def find_duplicates2(l: list[int]) -> list[int]:
    dupes: list[int] = []
    for i in range(len(l)):
        if l[i] not in dupes:
            for j in range(i + 1, len(l)):
                if l[i] == l[j]:
                    dupes.append(l[i])
                    break
    return dupes

# Note bonus: il est possible d'utiliser sorted ou des set là aussi...

find_duplicates = find_duplicates1  # change to find_duplicates2 to test other method

print(find_duplicates([]))  # []
print(find_duplicates([1, 2, 3, 5, 9]))  # []
print(find_duplicates([1, 1]))  # [1]
print(find_duplicates([1, 2, 2, 3, 1, 5, 1]))  # [1, 2]


def has_duplicates_alt(l: list[int]) -> bool:
    return len(find_duplicates(l)) > 0

from random import randint

ints: list[int] = []
for _ in range(20):
    ints.append(randint(1, 50))
print(ints)


def find_min_index(l: list[int], start_index: int = 0) -> int:
    min_index = start_index
    for i in range(min_index + 1, len(l)):
        if l[i] < l[min_index]:
            min_index = i
    return min_index


print(find_min_index([3, 1, 4, 1, 18]))  # 1
print(find_min_index([3, 1, 4, 1, 18], 0))  # 1, équivalent
print(find_min_index([3, 1, 4, 1, 18], start_index=2))  # 3
print(find_min_index([3, 1, 4, 1, 18], start_index=4))  # 4


def sort(l: list[int]) -> None:
    for i in range(0, len(l) - 1):
        j = find_min_index(l, i)
        l[i], l[j] = l[j], l[i]


sort(ints)
print(ints)

# Variante 1
def binary_to_decimal(binstr: str) -> int:
    acc = 0
    for i, bit in enumerate(reversed(binstr)):
        acc += int(bit) * 2**i
    return acc


# Variante 2
def binary_to_decimal_alt(binstr: str) -> int:
    acc = 0
    mult = 1
    for bit in reversed(binstr):
        acc += int(bit) * mult
        mult *= 2
    return acc

# Variante 3
def binary_to_decimal_alt3(binstr: str) -> int:
    acc = 0
    for bit in binstr:
        acc *= 2
        acc += int(bit)
    return acc

# Pas mal d'autres variantes possibles!

# Tests
for test_case in "101010", "10010110", "11110111110", "1000000000000000000000000000000":
    print(binary_to_decimal(test_case))
    print(binary_to_decimal_alt(test_case))
    print(int(test_case, 2))  # version native de Python
    print()