from jyquickhelper import add_notebook_menu
add_notebook_menu()

"""
Explanation: 1A.algo - Arbre et Trie (correction)
Correction.
End of explanation
"""


import random
def mot_alea (l) :
    l = [ chr(97+random.randint(0,25)) for i in range(l) ]
    return "".join(l)

taille  = 20
N       = 10000
mots    = [ mot_alea(taille) for _ in range (N) ]
print(len(mots))

"""
Explanation: Exercice 1
End of explanation
"""


import time
debut = time.perf_counter()
for k in mots :
    i = mots.index(k)
fin = time.perf_counter()
print ("recherche simple",fin - debut)

"""
Explanation: Exercice 2
End of explanation
"""


%timeit for k in mots : i = mots.index(k)

"""
Explanation: Avec %timeit :
End of explanation
"""


def dicho (mots, x) :
    a = 0
    b = len(mots)-1
    while a < b :
        m = (a+b)//2
        t = mots[m] 
        if t < x : 
            b = m-1 
        elif t == x :
            return m
        else :
            a = m+1
    return a

mots.sort()

debut = time.perf_counter()
for k in mots :
    i = dicho(mots, k)
fin = time.perf_counter()
print ("dichotomie",fin - debut)

%timeit for k in mots : i = dicho(mots, k)

"""
Explanation: Exercice 3 : recherche dichotomique
End of explanation
"""


import math

for N in [10, 100, 1000, 10000, 100000] :
    mots    = [ mot_alea(taille) for _ in range (N) ]
    tolook  = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,1000) ]
    mots.sort()
    
    debut = time.perf_counter()
    for k in tolook :
        i = mots.index(k)
    fin = time.perf_counter()    
    ds = fin-debut
    
    debut = time.perf_counter()
    for k in tolook :
        i = dicho(mots, k)
    fin = time.perf_counter()    
    dd = fin-debut
    
    print(N, "simple",ds, "dicho",dd, "ratio", ds / max(dd, 1), " ratio théorique ",
          len(mots)/math.log(len(mots)) * math.log(2)/30)

for N in [10, 100, 1000, 10000, 100000] :
    print("N=",N)
    mots    = [ mot_alea(taille) for _ in range (N) ]
    tolook  = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,1000) ]
    mots.sort()
    
    %timeit for k in tolook : i = mots.index(k)
    %timeit for k in tolook : i = dicho(mots, k)

"""
Explanation: Exercice 4
End of explanation
"""


def build_trie(mots) :
    trie = { }
    for m in mots :
        r = trie
        for c in m :
            if c not in r : r[c] = { }
            r = r[c]
    return trie

mots = [ "aaa", "aba", "aab", "baa", "bbb", "bba", "bab" ]

trie = build_trie(mots)
print(trie)

"""
Explanation: Soit $N$ le nombre de mots dans la liste :

coût de la recherche simple : $O(N)$ 
coût de la recherche dichotomique : $O(\ln N)$ 

Le ratio $N/\ln N$ mesuré en pratique devrait être sensiblement égal au ratio théorique à un facteur multiplication près. Le trie du tableau qui précède la recherche dichotomique n'est pas pris en compte. Plus on effectue de recherche, plus son coût devient marginal. Ce coût explique néanmoins pourquoi on ne fait pas toujours une recherche dichotomique.
Exercice 5 : trie
End of explanation
"""


def lookup(trie, m) :
    r = trie
    for c in m :
        if c in r :
            r = r[c]
        else :
            return False
    return True

for k in mots :
    print(k, lookup(trie, k))
print("bcc", lookup(trie, "bcc"))    

"""
Explanation: Quelques explications supplémentaires concernant cette correction :

Question à propos de trie

Exercice 6 : recherche dans un trie
End of explanation
"""


def print_trie(trie, niveau = 0):
    for k,v in sorted(trie.items()):
        print("  " * niveau + k)
        if len(v) > 0 :
            print_trie(v, niveau+1)
print_trie(trie)

"""
Explanation: Pour illustrer la structure d'arbre du trie, on l'affiche avec la fonction suivante :
End of explanation
"""


print_trie (build_trie( ["aaa"]) )

print_trie (build_trie( ["aaa", "aa"]) )

"""
Explanation: Il reste un inconvénient à cette représentation. Si on construire le trie pour le mot ["aaa"] ou les mots ["aa","aaa]", on obtient le même trie :
End of explanation
"""


print_trie (build_trie( ["aaa*"]) )

print_trie (build_trie( ["aaa*", "aa*"]) )

"""
Explanation: Pour éviter cela, le plus simple est de représenter la fin d'un mot comme un caractère à part entière.
End of explanation
"""


for N in [10, 100, 1000, 10000, 100000, 200000, 400000] :
    mots    = [ mot_alea(taille) for _ in range (N) ]
    tolook  = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,10000) ]
    trie    = build_trie(mots)
    mots.sort()
    
    debut = time.perf_counter()
    for k in tolook :
        i = dicho(mots, k)
    fin = time.perf_counter()    
    dd = fin-debut
    
    debut = time.perf_counter()
    for k in tolook :
        i = lookup(trie, k)
    fin = time.perf_counter()
    dt = fin - debut

    print(N, "dicho",dd, "trie", dt)

for N in [10, 100, 1000, 10000, 100000, 200000, 400000] :
    print("N=",N)
    mots    = [ mot_alea(taille) for _ in range (N) ]
    tolook  = [ mots[ random.randint(0,len(mots)-1) ] for i in range(0,10000) ]
    trie    = build_trie(mots)
    mots.sort()
    
    %timeit for k in tolook : i = dicho(mots, k)
    %timeit for k in tolook : i = lookup(trie, k)

"""
Explanation: Exercice 7
Soit $L$ la longueur maximale des mots et $C$ le nombre de lettres distinctes, avec un trie, le coût de la recherche est majoré par : $O(L \ln C)$. On reprend le code de l'exercice 5 et on ajoute le code associé au trie. On effectue 10000 recherches au lieu de 1000 pour avoir une meilleure estimation de la différence (pour vous en convaincre, il suffit comparer les temps obtenus par deux exécution de ce même code).
End of explanation
"""


class Arbre:
    def __init__(self, value):
        self.value = value
        self.children = [ ]
        
    def add_child(self, child):
        self.children.append(child)
        
    def __str__(self):
        rows = [ "value={0}".format(self.value) ]
        for c in self.children:
            s = str(c)
            lines = [ "    " + l for l in s.split("\n") ]
            rows.extend(lines)
        return "\n".join(rows)
    
root = Arbre("racine")
child1 = Arbre("child 1")
child1.add_child ( Arbre("child 2") )
child1.add_child ( Arbre("child 1000") )
root.add_child(child1)
root.add_child( Arbre ("child 3") )
print(root)     

"""
Explanation: Encore une fois, le temps de construction du trie n'est pas pris en compte. Plus il y a de recherche à effectuer, plus il devient négligeable.
Le dictionnaire est un object courant dans la plupart des languages. En python, celui-ci utilise une table de hachage et le coût d'accès à un élément n'est pas en $O(\ln n)$ mais en $O(n)$ (voir time complexity). En C++, le dictionnaire (ou map) utilise un arbre binaire et l'accès à un élément a un coût logarithmique : Standard C++ Containers.
Plus en détails
La recherche dichotomique est équivalente à celle opérée avec un arbre binaire de recherche (si ce dernier est équilibré ou arbre rouge/noir). Ce dernier consiste à classer les éléments par ordre alphabétique. Un arbre est souvent représenté par une classe et non par un dictionnaire comme la dernière partie de cette session le laissait supposer.
End of explanation
"""


class ArbreDicho:
    def __init__(self, value):
        self.value = value
        self.before = None
        self.after = None
        
    def __str__(self):
        return "value={0}".format(self.value)
        
    def add_before(self, child):
        self.before = child

    def add_after(self, child):
        self.after = child
        
    def find(self, word):
        if self.value == word : return self
        elif word < self.value : 
            if self.before is None : return None
            else : return self.before.find(word)
        else : 
            if self.after is None : return None
            else : return self.after.find(word)
            
    def sorted_list(self):
        res = [ ]
        if self.before is not None: res.extend ( self.before.sorted_list() )
        res.append(self.value)
        if self.after is not None: res.extend ( self.after.sorted_list() )
        return res

# on crée un arbre dont les noeuds vérifient la propriété énoncé plus haut (les mots apparaissent dans le bon ordre)
root = ArbreDicho("milieu")
root.add_before(ArbreDicho("avant"))
root.add_after(ArbreDicho("zillion"))
root.before.add_before(ArbreDicho("alphabet"))
root.before.add_after(ArbreDicho("avant après"))

# on vérifie que c'est bien le cas
all = root.sorted_list()
assert all == sorted(all)
print(all)

# on effectue la recherche
for a in all:
    f = root.find(a)
    print(f)

"""
Explanation: Les arbres sont des graphes particuliers car il ne contiennent pas de cycles. Il est possible de parcourir les noeuds, de les numéroter. Ils sont très utilisés en machine learning avec les arbres de décisions ou les random forests. Ils sont parfois cachés comme dans le cas de la recherche dichotomique qui peut être implémentée à partir d'une structure d'arbre.
Dans le cas de le recherche dichotomique, on suppose que le nombre de noeuds fils est toujours 2. L'ordre alphabétique est le suivant : noeuds fils 1, noeud courant, noeud fils 2. Les deux noeuds fils pourraient être nuls. L'implémentation de l'arbre serait la suivante :
End of explanation
"""


