import numpy as np


# Trois plus grandes valeurs

# Question 1

def valmax(t):
    """
    Version "parcours par références (= indices)"
    """
    m = t[0]
    for i in range(1, len(t)):
        if t[i] > m:
            m = t[i]
    return m


def valmax_(t):
    """
    Version "parcours par valeurs"
    """
    m = t[0]
    for v in t[1:]:
        if v > m:
            m = v
    return m

t = np.random.randint(0, 100, 100)
assert valmax(t) == max(t)

# Question 2

def val3max(t):
    a = b = c = -1
    for v in t[1:]:
        if v > c:
            a, b, c = b, c, v
        elif b < v < c:
            a, b = b, v
        elif a < v < b:
            a = v
    return (a, b, c)

assert val3max([1, 5, 7, 4, 2, 3, 1, 7]) == (4, 5, 7)
assert val3max([4, 4, 4, 4, 4]) == (-1, -1, 4)

# Tri par partition-fusion

# Question 3

def partition(l):
    l0 = []
    l1 = []  # sinon l0 et l1 pointent vers le même objet
    for i in range(len(l)):
        if i % 2 == 0:
            l0.append(l[i])
        else:
            l1.append(l[i])
    return (l0, l1)


def partition_(l): # variante plus compacte
    r = ([], [])
    for i in range(len(l)):
        r[i % 2].append(l[i])
    return r

assert partition(t) == partition_(t)

# Question 4

def fusion(u0, u1):
    assert est_triée(u0) and est_triée(u1)  # q. 5.4
    u = []
    i0 = i1 = 0
    while i0 < len(u0) and i1 < len(u1):
        if u0[i0] <= u1[i1]:
            u.append(u0[i0])
            i0 += 1
        else:
            u.append(u1[i1])
            i1 += 1
    u.extend(u0[i0:])
    u.extend(u1[i1:])
    assert est_triée(u)  # q. 5.4
    return u


# Question 5

def test():
    assert fusion([1, 2, 3, 5], [4, 7, 10]) == [1, 2, 3, 4, 5, 7, 10]

"""
Terminaison de la fonction fusion : la somme i0 + i1 augmente de 1 à chaque itération, donc elle ne peut rester indéfiniment strictement inférieure à len(u0) + len(u1), donc il existe un rang auquel i0 >= len(u0) ou i1 >= len(u1). 
Plus formellement, on peut introduire le variant de boucle (len(u0) - i0) + (len(u1) - i1).
"""


def est_triée(l):
    """
    En parcourant la liste, 
    - soit on rencontre un problème et on s'arrête en renvoyant False, 
    - soit on n'a jamais rencontré de problème et on renvoie alors True.
    """
    for i in range(len(l)-1):
        if l[i] > l[i+1]:
            return False
    return True


def est_triée_(l):
    return all(l[i] <= l[i+1] for i in range(len(l)-1))


# Question 6

def tri_fusion(l):
    if len(l) <= 1:  # cas de base
        return l
    else:  # appels récursifs
        u0, u1 = partition(l)
        u0 = tri_fusion(u0)
        u1 = tri_fusion(u1)
        return fusion(u0, u1)


l = list(np.random.randint(0, 100, 1000))
assert(tri_fusion(l) == sorted(l))

# Entiers conjugués

# Question 7

def décodage(t):
    s = 0
    for i in range(8):
        s += int(t[i]) * 2**i
        # on part du principe que t contient des entiers, sinon il faudrait en toute rigueur transtyper
    return s


def décodage_(t):
    return sum(t[i] * 2**i for i in range(8))


def codage(n):
    t = np.empty(8, dtype=np.int8)
    for i in range(8):
        t[i] = (n // (2**i)) % 2
    return t

n = 41
t = codage(n)
print(t)
m = décodage(t)
assert n == m

# Question 8

def rotation(t):
    s = t[-1]
    for i in reversed(range(1, len(t))):
        t[i] = t[i-1]
    t[0] = s


def rotation_gauche(t):
    s = t[0]
    for i in range(len(t)-1):
        t[i] = t[i+1]
    t[-1] = s


# Question 9

def sont_conjugues(n1, n2):
    t1, t2 = codage(n1), codage(n2)
    for _ in range(8):
        if t1 == t2:
            return True
        rotation(t1)
    return False


def ensemble_des_conjugues(n):
    s = {n}
    t = codage(n)
    for _ in range(7):
        rotation(t)
        s.add(décodage(t))
    return s

print(ensemble_des_conjugues(n))