#Question 1
def stock(f):
    """ décorateur stock. CF TP2 """
    val_connu = {}
    def stockage(*args):
        if args in val_connu:
            return val_connu[args]
        val = f(*args)
        val_connu[args] = val
        return val
    return stockage

@stock
def dist1(a,b):
    if a>100 or b>100: #Si a ou b est plus grand que 100
        return 100 #On ne doit pas les considérer
    if a==b: #Si a=b, la distance est nulle
        return 0
    return 1 + min(dist1(2*a,b), dist1(a+1,b), dist1(a,b+1), dist1(a,2*b)) #Sinon la distance est obtenue en faisant soit +1 soir x2 sur a ou b

#Question 2


#L'indication de l'énoncé était pas terrible, voici une meilleure solution
def dist2(a,b):
    if b>a: #Pour ne pas traiter les symmétries on suppose a>b
        return dist2(b,a)
    tab_dist= [abs(a-i) for i in range(5*a+1)] #tableau des distances à a
    puiss = 0 #On veut savoir jusqu'à quelle puissance aller
    while 5**puiss < a: #Pour cela tant que 5**puiss est plus petit que a
        puiss +=1 #On incrémente puiss
    puiss +=1 #On peut potentiellement aller jusqu'à la puissance d'après
    for i in range(5*puiss): #On sait qu'on devra mettre à jour les distance au plus 5*puiss fois
        for j in range(len(tab_dist)): #Pour tous les éléments du tableau
            d = tab_dist[j] #on regarde leur distance à a
            for i in range(puiss): #Pour chaque puissance de 5
                if j+5**i < len(tab_dist): #Si on peut passer par cette puissance en partant depuis a
                    d = min(d, tab_dist[j+5**i]+1) #on met à jour d
                if j-5**i >=0: #Idem en  partant depuis b
                    d = min(d, tab_dist[j-5**i]+1)#On met à jour d
            tab_dist[j] = d #On actualise la distance
    return tab_dist[b] #On renvoie la distance








#Question 3


def dist3(t1, t2):
    n = max(len(t1), len(t2)) #On prend la taille maximale
    d = 0
    try :
        for i in range(n): #Tant qu'on a pas atteint la taille max
            d = max(d, abs(ord(t1[i]) - ord(t2[i]))) #On calcule le nombre de caractères entre les 2 considérés
        return d #On renvoie la distance
    except : #Si il y a une erreur
        print("les 2 chaines ne font pas la même taille")
        return -1 #On renvoie -1

#Question 4

N = 131071

#L'idée de la fonction est de calculer tous les éléments à distance 1 de a, puis à distance 2 etc, jusqu'à atteindre tous les éléments de l'ensemble.
#On fait ensuite de même pour b et on cherche ainsi l'élément le plus proche des 2
def dist(a,b,f):
    d = 0 #On initialise la distance à 0
    dist_a = {a : 0} #Ce dictionnaire contiendra la liste des éléments et leur distance à a
    list_dist_d = [a] #Cette liste contient l'ensemble des élément à distance d de a. C'est en
    for i in range(N): #On sait qu'en au plus N étapes, on a atteint tous les éléments
        d+=1 #On incrémente la distance
        li_aux = [] #liste qui remplacera list_dist_d pour l'étape d'après
        for k in list_dist_d: #Pour tout élément k à distance d
            for image in f(k): #On regarde quel élément on peut atteindre
                if image not in dist_a: #Si on ne connait pas encore sa distance à a
                    dist_a[image] = d #Il est à distance d
                    li_aux.append(image) #Et on devra le considérer pour calculer les éléments à distance d+1
        list_dist_d = li_aux #Enfin on met à jour la liste des éléments à distance d
    #On fait ensuite la même chose pour b
    d = 0
    dist_b = {b : 0}
    list_dist_d = [b]
    for i in range(N):
        d+=1
        li_aux = []
        for k in list_dist_d:
            for image in f(k):
                if image not in dist_b:
                    dist_b[image] = d
                    li_aux.append(image)
        list_dist_d = li_aux
    for i in dist_b: #Pour tout élément atteignable depuis b
        if i in dist_a and dist_a[i] + dist_b[i] < d: #S'il est atteignable depuis a, et que passer par lui est plus rapide que la distance en mémoire
            d = dist_a[i] + dist_b[i] #On met à jour la distance
    return d # On renvoie la distance en question

def f(x):
    return [2*x % N, 3*x % N, 5*x %N ]


def f2(x):
    return [2*x % 131071, x+1 % 131071]