# solutions exercices Recherche textuelle/Prog. Dyn./Diviser pour régner

### recherche textuelle ####################################################

def occurrence(m, t, i):
    """indique s'il y a une occurrence de la chaîne m
       dans la chaîne t à la position i"""
    if i < 0 or i > len(t) - len(m):
        return False
    for j in range(len(m)):
        if t[i + j] != m[j]:
            return False
    return True

def premiere_occurrence(m, t):
    """renvoie la première occurrence de m dans t,
    le cas échéant, et None sinon"""
    for i in range(0, len(t) - len(m) + 1):
        if occurrence(m, t, i):
            return i
    return None

# table BM pour le mot "banane"

#   | a | b | e | n
#---+---+---+---+---
# 0 |   |   |   |
# 1 |   | 0 |   |
# 2 | 1 | 0 |   |
# 3 | 1 | 0 |   | 2
# 4 | 3 | 0 |   | 2
# 5 | 3 | 0 |   | 4

# table BM pour le mot "chercher"

#   | c | h | e | r
#---+---+---+---+---
# 0 |   |   |   |
# 1 | 0 |   |   |
# 2 | 0 | 1 |   |
# 3 | 0 | 1 | 2 |
# 4 | 0 | 1 | 2 | 3
# 5 | 4 | 1 | 2 | 3
# 6 | 4 | 5 | 2 | 3
# 7 | 4 | 5 | 6 | 3

# dérouler Boyer-Morre sur
# recherche("chercher","chercher, rechercher et chercher encore")

# La variable i prend successivement les valeurs
#   0 (occurrence,  qui donne le décalage 1),
#   1 (qui donne le décalage 8),
#   9 (décalage 3),
#  12 (occurrence, décalage 1),
#  13 (décalage 8),
#  21 (décalage 3),
#  24 (occurrence, décalage 1),
#  25 (décalage 8),
#  33
#
#  La dernière valeur prise par i est 33 et on sort
#  alors de la boucle car cette valeur dépasse len(t) - len(m) = 39 - 8 = 31.
#
#  Il y a 29
#  comparaisons au total (certaines positives, d'autres négatives).

### programmation dynamique ################################################

### dérouler rendu_monnaie([1,2], 3) #########

# il y a sept appels au total :

# rendu_monnaie([1,2], 3)
#   rendu_monnaie([1,2], 2)
#     rendu_monnaie([1,2], 1)
#       rendu_monnaie([1,2], 0)
#     rendu_monnaie([1,2], 0)
#   rendu_monnaie([1,2], 1)
#     rendu_monnaie([1,2], 0)

# On constate qu'on a fait deux fois l'appel pour s=1 et
# trois fois l'appel pour s=0.

### le tableau construit par rendu_monnaie([1, 6, 10], 12) #######

# [0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 2]

# La réponse est dans la dernière case, donc 2.

### chemins sur une grille ##########

# idée : dans un tableau de tableaux grille, on stocke la réponse
# pour tous les 0 <= i <= n et 0 <= j <= m

def chemins(n, m):
    grille = [[1] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            grille[i][j] = grille[i - 1][j] + grille[i][j - 1]
    return grille[n][m]

### diviser pour régner ####################################################

### rotation image ########

def rotation_aux(px, x, y, t):
    # On commence par traiter le cas d'une région réduite à un unique
    # pixel. Dans ce cas, il n'y a strictement rien à faire :
    if t == 1:
        return
    # Sinon, on peut découper la région en quatre sous-régions, de
    # dimension deux fois plus petite, dont on effectue la rotation
    # récursivement :
    t //= 2
    rotation_aux(px, x    , y    , t)
    rotation_aux(px, x + t, y    , t)
    rotation_aux(px, x    , y + t, t)
    rotation_aux(px, x + t, y + t, t)
    # Il faut ensuite déplacer chacune des quatre régions, ce que l'on
    # peut faire élégamment avec une double boucle et une affectation
    # simultanée des quatre pixels qui échangent leur position :
    for x in range(x, x+t):
        for y in range(y, y+t):
            px[x,y+t], px[x+t,y+t], px[x+t,y  ], px[x  ,y] = \
            px[x,y  ], px[x  ,y+t], px[x+t,y+t], px[x+t,y]

# La rotation de l'image toute entière est obtenue avec une région qui
# couvre toute l'image :
def rotation(px, taille):
    rotation_aux(px, 0, 0, taille)

### Karatsuba ###############

# Pour la fonction taille, il suffit de diviser x par deux
# jusqu'à obtenir zéro.
def taille(x):
    n = 1
    while x > 0:
        x //= 2
        n += 1
    return n
# Pour la fonction karatsuba, on suit l'algorithme proposé, en
# s'arrêtant lorsqu'il ne reste qu'un seul chiffre.
def karatsuba(x, y, n):
    """multiplie x et y par la méthode de Karatsuba"""
    if n <= 1:
        return x * y
    n //= 2
    m = 1 << n
    a, b = x >> n, x % m
    c, d = y >> n, y % m
    ac = karatsuba(a, c, n)
    bd = karatsuba(b, d, n)
    abcd = karatsuba(a - b, c - d, n)
    return (ac << (2*n)) + ((ac + bd - abcd) << n) + bd
# Enfin, la fonction mult calcule la valeur de n comme le
# maximum des deux tailles (l'algorithme reste correct si l'un des deux
# entiers a moins que n chiffres).
def mult(x, y):
    n = max(taille(abs(x)), taille(abs(y)))
    return karatsuba(x, y, n)

# Remarque : en pratique, on ne parviendra pas à observer de progrès
# par rapport à la multiplication de Python, car celle-ci repose déjà
# sur une bibliothèque de grands entiers qui implémente des
# algorithmes efficaces tels que Karatsuba (et même de plus efficaces
# tels que Toom-Cook).