####
### 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
# Pour savoir si on mot est un palindrome, on commence par comparer ses extremités
# Si elles sont égales, alors on se retrouve avec le même problème de recherche de palindrome sur le mot sans ses extrémités
# 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