####
### Exercice 1 : Palindromes
####

ch = "ressasser"

print("Question 1")
print(ch[:1])
print(ch[-1:])
print(ch[1:-1])

print("Question 2")
def est_palindrome(ch):
    if len(ch) <= 1:
        return True
    else:
        return ch[0] == ch[-1] and est_palindrome(ch[1:-1])

print("Question 3")        
assert est_palindrome("")
assert est_palindrome("zz")
assert est_palindrome("bob")
assert not est_palindrome("alice")
assert est_palindrome("ressasser")

# Question 4
# On décide si le mot est un palindrome si les sous mots le sont aussi.
# On a diviser notre mot en sous mot
# On vérifie les extremités de chaque sous-mots
# On combine les résultats, un mot est un palindrome si ses sous mots le sont aussi

# Question 5
# 1) ressasser est le pire cas car le mot est un palindrome et on a effectué toutes les comparaisons possibles
# 2) 4
# 3) n/2
# 4) n/2 veut dire O(n)

# Question 6
# n/2 chaines, une par appel a est_palindrome


print("Question 7")
# Version récurcive
def palindrome_rec(ch, g, d):
    if abs(g-d) <= 1:
        return True
    else:
        return ch[g] == ch[d] and palindrome_rec(ch, g+1, d-1)

assert palindrome_rec("", 0, 0)
assert palindrome_rec("zz", 0, 1)
assert palindrome_rec("bob", 0, 2)
assert not palindrome_rec("alice", 0, 4)
assert palindrome_rec("ressasser", 0, 8)

# Version Itérative
def palindrome_ite(ch, g, d):
    while abs(g-d) > 1:
        if ch[g] != ch[d]:  return False
        g += 1
        d -= 1
    return True

assert palindrome_ite("", 0, 0)
assert palindrome_ite("zz", 0, 1)
assert palindrome_ite("bob", 0, 2)
assert not palindrome_ite("alice", 0, 4)
assert palindrome_ite("ressasser", 0, 8)

#Question 8
mot = "ressasser"
palindrome_ite(mot, 0, len(mot)-1)

#Question 9
def est_palindrome2(ch):
    # à compléter
    return palindrome_ite(ch, 0, len(ch)-1)

####
### Exerice 2 : Mini
####

def mini(L, g, d):
    if g == d: 
        return L[g]
    else : 
        return min(mini(L, g, (g + d) // 2), mini(L, (g + d) // 2 +1, d))

def minimum(L):
    return mini(L, 0, len(L)-1)

assert minimum([5, 2, 4, 3, 5]) == 2


####
### Exerice 3 : Fusion
####

# Question 1
# On divise la liste en liste de taille 2 (récursif)
# On tri ces listes de taille 2
# On fusionne les listes au fur et a mesure

# Question 2
# 

def fusion(l1, l2):
    l = []
    i, j = (0,0)
    while i < len(l1) or j < len(l2):
        if i == len(l1):
            l.append(l2[j])
            j += 1
        elif j == len(l2):
            l.append(l1[i])
            i += 1
        elif l1[i] < l2[j]:
            l.append(l1[i])
            i += 1
        else:
            l.append(l2[j])
            j += 1
    return l

def tri_fusion(lst):
    """Renvoie une nouvelle liste avec les éléments triés (dans l'ordre croissant) de la liste d'entiers lst. """
    # à compléter
    if len(lst) == 1:
        return lst
    else:
        m = len(lst) // 2       # m est la position médiane
        l1 = tri_fusion(lst[:m])   # l1 est la sous-liste de gauche (lst[0...m-1]) triée par fusion
        l2 = tri_fusion(lst[m:])   # l2 est la sous-liste de droite (lst[m..]) triée par fusion
        return fusion(l1, l2)

print(tri_fusion([38, 27, 43, 3, 9, 82, 10]))