## Récursivité

# Q1
def reste(a, b):
    """
    Reste de a modulo b
    """
    assert (a >= 0 and b > 0)
    if a < b:
        return a
    else:
        return reste (a-b, b)

# Q2
def coeff_binom2(k, n):
    """
    k parmi n
    """
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    return coeff_binom2(k, n-1) + coeff_binom2(k-1, n-1)

"""
Cette méthode ne fait que des additions, en revanche elle
est beaucoup plus lente, car on recalcule de nombreuses fois la
même valeur. Par exemple:

coeff(3, 5) = coeff(3, 4) + coeff(2, 4)
            = coeff(3, 3) + coeff(2, 3) + coeff(2, 3) + coeff(1, 3)

On va donc faire le calcul de coeff(2, 3) deux fois.
Si on déroulait encore, on verrait que certaines valeurs sont calculées
de très nombreuses fois. L'année prochaine, vous verrez une stratégie
algorithmique appelée "programmation dynamique", dont le principe est
de stocker en mémoire les valeurs calculées afin d'éviter de les
recalculer inutilement.
"""

# Q3

def somme_chiffres(n):
    """
    Renvoie la somme des chiffres de n en base 10
    ex: somme_chiffres(1645) = 1+6+4+5 = 16
    """
    assert(n >= 0)
    if n < 10:
        return n
    else:
        unite = n % 10
        tout_le_reste = n // 10 # n privé de son unité
        return unite + somme_chiffres(tout_le_reste)

# Q4
def u(n):
    if n == 0:
        return (0, 0)
    else:
        (x, y) = u(n-1)
        if x == 0:
            return (y+1, 0)
        else:
            return (x-1, y+1)


# Q5
def parties(n):
    """
    Renvoie la liste des parties de l'ensemble {0, 1, ..., n-1}.
    ex: parties(2) = [[], [0], [1], [0, 1]]
        parties(3) = [[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]]
    """
    if n == 0:
        return [[]]
    else:
        p = parties(n-1)
        # pour passer des parties de {0, ..., n-2}
        # aux parties de {0, ..., n-2, n-1}, on prend
        # chaque élément de p, et on le dédouble: une version
        # avec n-1, une sans.
        # par ex, parties(1) = [[], [0]]
        # et parties(2) = [[], [0]] union [[1], [0, 1]]
        p_sans = p[:]
        p_avec = [l + [n-1] for l in p]
        return p_sans + p_avec


# Q6
def dichotomie(t, a, b, x):
    """
    Entrée:
    - t un tableau trié dans l'ordre croissant
    - a, b deux indices du tableau
    - x un élément à chercher
    Sortie: booléen, True si x est dans t entre a et b (inclus), False sinon
    """
    if b < a:
        return False
    m = (a+b)//2
    if t[m] == x:
        return True
    elif t[m] < x:
        return dichotomie(t, a, m-1, x)
    else: # t[m] > x
        return dichotomie(t, m+1, b, x)

"""
A retenir: la complexité de la dichotomie est O(log n),
alors que la recherche dans un tableau quelconque serait
en O(n).
"""

## Tris
import random # pour les tests

def est_trie(T):
    """
    Renvoie True si T est trié dans l'ordre croissant, False sinon
    """
    n = len(T)
    for i in range(1, n):
        if T[i-1] > T[i]:
            return False
    return True

def selection(T, i):
    """
    Entrée: un tableau T, i un indice valide
    Sortie: Indice du maximum de T[0], ... T[i]
    """
    i_m = 0 # indice du max courant
    # invariant: T[i_m] = max(T[0], T[1], ... T[i-1)
    for j in range(1, i+1):
        if T[j] > T[i_m]:
            i_m = j
    return i_m

# Échange les cases i et j de T
def swap(T, i, j):
    tmp = T[i]
    T[i] = T[j]
    T[j] = tmp

"""
Tri par sélection:
Le principe est de trouver l'élément maximal, de le mettre à
la fin, puis de trouver l'élément maximal par les autres,
de le mettre à l'avant dernière case, et ainsi de suite...
"""
def select_sort(T):
    n = len(T)
    for i in range(n):
        i_m = selection(T, n-i-1)
        swap(T, n-i-1, i_m)

def test_tri_selection():
    for k in range(50):
        # tableau aléatoire de 100 valeurs entre 1 et 100
        T = [random.randint(1, 100) for i in range(100)]
        select_sort(T)
        assert(est_triee(T))
    print("Tous les tests ont réussi.")


"""
Tri par insertion:
Le principe est de maintenir une zone triée à gauche du tableau,
et de la faire grandir progressivement en insérant des éléments
un par un.
"""
def insert_sort(T):
    n = len(T)
    for i in range(n-1):
        # T[0], ... T[i] sont dans le bon ordre
        # et on insère T[i+1]
        j = i+1
        while j > 0 and T[j] < T[j-1]:
            swap(T, j, j-1)
            j = j-1

def test_tri_selection():
    for k in range(50):
        # tableau aléatoire de 100 valeurs entre 1 et 100
        T = [random.randint(1, 100) for i in range(100)]
        insert_sort(T)
        assert(est_triee(T))
    print("Tous les tests ont réussi.")



## Tri rapide
"""
Rappel du tri rapide, qu'on a vu au premier semestre.
"""

def partition(T, a, b):
    """
    Entrée:
        - T un tableau
        - a un indice de début
        - b un indice de fin
    Sortie: un indice p. T a été modifié en T', de telle sorte que:
        - T'[p] = T[a]
        - Les cases de T' entre a et p-1 sont <= T'[p]
        - Les cases de T' entre p+1 et b sont > T'[p]
    """
    p = T[a]
    i, j = a+1, b
    # Invariants:
    # T[a+1:i] est < T[0]
    # T[j+1:b+1] est > T[0]
    # T[i:j+1] est à traiter
    while i <= j:
        if T[i] >= p:
            swap(T, i, j)
            j = j-1
        else:
            i = i+1
    swap(T, a, i-1)
    return i-1


def tri_rapide_entre(T, a, b):
    """
    Entrée:
        - T un tableau
        - a un indice de début
        - b un indice de fin
    Sortie: Rien, T est trié entre a et b
    """
    if b <= a:
        return

    p = partition(T, a, b) # indice du pivot
    # p est un indice entre a et b
    # toutes les cases entre a et p-1 sont <= T[p]
    # toutes les cases entre p+1 et b sont > T[p]
    tri_rapide_entre(T, a, p-1)
    tri_rapide_entre(T, p+1, b)

def tri_rapide(T):
    """
    Entrée:
        - T un tableau
        - a un indice de début
        - b un indice de fin
    Sortie: Rien, T est trié
    """
    tri_rapide_entre(T, 0, len(T)-1)


"""
Complexités (à savoir):
Tri selection en O(n²)
Tri insertion en O(n²)
Tri rapide en O(n log n)
"""


"""
La version de gauche de la fonction de fusion est la bonne.
Les deux versions ont le même principe:
on construit la liste fusionnée en y mettant
les éléments dans l'ordre depuis les deux listes
sources. Le problème dans la version de droite
est qu'elle ajoutait systématiquement un élément
de chaque liste, mais ça ne marche pas dans le
cas suivant:
L1 = [1, 2]
L2 = [3, 4]
la fonction de droite ajoute 1 et 3, puis 2 et 4,
ce qui donne 1, 3, 2, 4.
"""


def fusion(T1, T2):
    """
    Entrée: deux tableaux T1, T2 triés
    Sortie: tableau T trié contenant les éléments de T1 et T2
    """
    T = []
    n1 = len(T1)
    n2 = len(T2)
    i1 = 0
    i2 = 0
    while i1 < n1 and i2 < n2:
        if T1[i1] < T2[i2]:
            T.append(T1[i1])
            i1 = i1 + 1
        else:
            T.append(T2[i2])
            i2 = i2 + 1
    return T + T1[i1:] + T2[i2:]

def tri_fusion(T):
    """
    Entrée: T tableau
    Sortie: copie triée de T
    """
    n = len(T)
    if n <= 1:
        return T[:] # fait une copie

    T1 = T[:n//2]
    T2 = T[n//2:]
    return fusion(tri_fusion(T1), tri_fusion(T2))


"""
Complexité: O(n log n) comme le tri rapide !
"""


## Turtle
from turtle import *
import math

# Q6
def polygone(n):
    """ Trace un polygone régulier à n côtés """
    angle = 360/n
    for k in range(n):
        forward(50)
        right(angle)

def demo_polygone():
    TurtleScreen._RUNNING = True
    polygone(6)
    done()

# Q7: sur papier
# Q8
def courbe_koch(l, n):
    """ Trace une courbe de Koch d'ordre n, de longueur l """
    if n == 0:
        forward(l)
    else:
        courbe_koch(l/3, n-1)
        left(60)
        courbe_koch(l/3, n-1)
        right(120)
        courbe_koch(l/3, n-1)
        left(60)
        courbe_koch(l/3, n-1)


def demo_koch():
    TurtleScreen._RUNNING = True
    tracer(1, 0)
    courbe_koch(300, 5)
    done()

# Q9
"""
J'ai rajouté un peu de couleur en utilisant la fonctionnalité fill de
turtle, qui permet de remplir une figure d'une couleur unie
"""
def flocon(l, n):
    fillcolor("orange")
    begin_fill()
    for i in range(3):
        courbe_koch(l, n)
        right(120)
    end_fill()


def demo_flocon():
    TurtleScreen._RUNNING = True
    tracer(1, 0)
    flocon(200, 4)
    done()

# Q10
def dragon(l, n, gd):
    """
    Trace la courbe du dragon d'ordre n, de longueur l. Si gd = True,
    fait tourner la courbe à gauche en premier, sinon, à droite.
    """
    if n == 0:
        forward(l)
    else:
        if gd:
            left(45)
            dragon(l/math.sqrt(2), n-1, True)
            right(90)
            dragon(l/math.sqrt(2), n-1, False)
            left(45)
        else:
            right(45)
            dragon(l/math.sqrt(2), n-1, True)
            left(90)
            dragon(l/math.sqrt(2), n-1, False)
            right(45)

def demo_dragon():
    tracer(1, 0)
    # les 3 instructions suivantes servent à téléporter la tortue
    up()
    setposition(-200, 100)
    down()
    dragon(300, 10, True)
    done()

# BONUS: courbe de Gosper (en.wikipedia.org/wiki/Gosper_curve)
"""
Cette fractale peut se décrire avec une suite de symboles (appelé un mot)
disant quand tourner à gauche (-), à droite (+) ou bien avancer (a ou b).
Le mot d'ordre 0 est "a", et le mot d'ordre n est obtenu à partir du mot
d'ordre n-1 en remplaçant chaque a et chaque b selon les règles suivantes:
"""
regles = {
    'a': 'a-b--b+a++aa+b-',
    'b': '+a-bb--b-a++a+b'
}

"""
chacune des deux règles transforme un symbole a ou b en 7 symboles a/b.
Ainsi, la courbe d'ordre n aura 7**n segments
"""
def mot_de_gosper(n):
    if n == 0:
        return "a"

    res = ""
    prec = mot_de_gosper(n-1)
    for c in prec:
        if c == 'a' or c == 'b':
            res = res + regles[c]
        else:
            res = res + c
    return res

def courbe_gosper(l, n):
    mot = mot_de_gosper(n)
    for c in mot:
        if c == 'a' or c == 'b':
            forward(l)
        if c == '-':
            left(60)
        if c == '+':
            right(60)

def demo_gosper():
    tracer(1, 0)
    speed(10)
    courbe_gosper(5, 4)
    done()