<commit_before>#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function, absolute_import
from itertools import chain
import networkx as nx

letters = list('abcdefghijklmnopqrstuvwxyz')

def leven(word1,word2):
    d = []
    for i in range(len(word1)+1):
        d.append([])
        for j in range(len(word2)+1):
            if i == 0:
                d[i].append(j)
            elif j == 0:
                d[i].append(i)
            else:
                if word1[i-1] == word2[j-1]:
                    cost = 0
                else:
                    cost = 1
                d[i].append(
                    min([
                        d[i-1][j]+1,
                        d[i][j-1]+1,
                        d[i-1][j-1]+cost
                    ])
                )
    return d[-1][-1]

def tri(s) :
    return "".join(sorted(list(s)))

def mots_from_org(ll, depart):
    """renvoie liste des mots depuis depart"""
    tri_depart = tri(depart)
    return [l for l in ll if (leven(depart, l) == 1 or tri(l) == tri_depart) and l != depart]

def mots_from(depart):
    """renvoie liste des mots depuis depart"""
    ch = tri(depart)
    s = set()
    for i, l in enumerate(ch) :
        s.add(ch[:i] + ch[i+1:]) # enlève letters
        for le in letters :
            s.add(tri(ch[:i] + le + ch[i+1:])) # substitue
            s.add(tri(ch + le)) # ajoute
    #return [l for l in ll if tri(l) in s and l != depart]
    #return chain(anag.get(ch, []) for ch in s)
    out = []
    for ch in s :
        out.extend(anag.get(ch, []))
    return out

def cherche(G, ll, debut, fin):
    expand(G, ll, debut, fin)
    flag = False
    for level in range(20):
        flag = explo(G, ll, fin)
        if flag :
            break
    if flag :
        for p in nx.all_shortest_paths(G,source=debut,target=fin):
            print(p)


def explo(G, ll, fin):
    if fin in G :
        print("Fini : ", fin, "trouvé")
        return True

    # Limite recherches
    # On cherche le min des dist

    min_dist = min([G.node[n]['dist'] for n in G])
    print ('min_dist=', min_dist)
    for n in G:
        if G.node[n]['dist'] > min_dist + 1:
            G.node[n]['explore'] = True

    nodes = list([n for n in G if not G.node[n]['explore']])
    print('Explo', sorted(nodes))
    for node in nodes :
        expand(G, ll, node, fin)
    return False

def expand(G, ll, curr, fin):
    """Etend le graphe depuis curr"""
    dist_curr = leven(fin, curr)
    G.add_node(curr, explore=True, dist=dist_curr)
    for u in mots_from(curr):
        if u not in G:
            dist = leven(fin, u)
            G.add_node(u, explore=False, dist=dist)
        G.add_edge(curr, u)

if __name__ == '__main__':
    #import matplotlib.pyplot as plt
    print('Début lecture')
    with open("lmots.txt") as f:
        ll = [l.strip() for l in f if len(l) < 12]
    anag = {}
    for l in ll:
        tll = tri(l)
        if tll not in anag:
            anag[tll] = [l]
        else:
            anag[tll].append(l)
    print('Fin lecture')
    G = nx.Graph()
    cherche(G, ll, 'a', 'alphabet')

    #nx.draw(G)
    #plt.show()
    #print(list(mots_from(anag, 'test')))<commit_msg>Passe ll et anag en global<commit_after>#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function, absolute_import
from itertools import chain
import networkx as nx

letters = list('<KEY>')

def leven(word1,word2):
    """Calcul de la distance de Levenshtein entre 2 mots"""
    word1 = tri(word1)
    word2 = tri(word2)
    d = []
    for i in range(len(word1)+1):
        d.append([])
        for j in range(len(word2)+1):
            if i == 0:
                d[i].append(j)
            elif j == 0:
                d[i].append(i)
            else:
                if word1[i-1] == word2[j-1]:
                    cost = 0
                else:
                    cost = 1
                d[i].append(
                    min([
                        d[i-1][j]+1,
                        d[i][j-1]+1,
                        d[i-1][j-1]+cost
                    ])
                )
    return d[-1][-1]

def tri(s) :
    """ Renvoit le mot trié pour repérage anagramme """
    return "".join(sorted(list(s)))

def mots_from(depart):
    """renvoie liste des mots depuis depart"""
    ch = tri(depart)
    s = set()
    for i, l in enumerate(ch) :
        s.add(ch[:i] + ch[i+1:]) # enlève letters
        for le in letters :
            s.add(tri(ch[:i] + le + ch[i+1:])) # substitue
            s.add(tri(ch + le)) # ajoute
    #return chain(anag.get(ch, []) for ch in s)
    out = []
    for ch in s :
        out.extend(anag.get(ch, []))
    return out

def cherche(G, debut, fin, max_loop=20, opti=2):
    """ Boucle principale """
    expand(G, debut, fin)
    flag = False
    for level in range(max_loop):
        flag = explo(G, fin, opti)
        # si on a trouvé, on sort
        if flag :
            break
    # indique les différents chemins
    if flag :
        for p in nx.all_shortest_paths(G,source=debut,target=fin):
            print(p)

def explo(G, fin, opti):
    if fin in G :
        print("Fini : ", fin, "trouvé")
        return True

    # Limite recherches
    # On cherche le min des dist + opti

    if opti >= 0 :
        min_dist = min([G.node[n]['dist'] for n in G])
        print ('min_dist=', min_dist)
        for n in G:
            if G.node[n]['dist'] > min_dist + opti:
                G.node[n]['explore'] = True

    # liste des nodes non explorés
    nodes = list([n for n in G if not G.node[n]['explore']])
    print('Explo', sorted(nodes))
    for node in nodes :
        expand(G, node, fin)
    return False

def expand(G, curr, fin):
    """Etend le graphe depuis curr"""
    dist_curr = leven(fin, curr)
    G.add_node(curr, explore=True, dist=dist_curr)
    for u in mots_from(curr):
        if u not in G:
            dist = leven(fin, u)
            G.add_node(u, explore=False, dist=dist)
        G.add_edge(curr, u)

if __name__ == '__main__':
    print('Début lecture')
    with open("lmots.txt") as f:
        ll = [l.strip() for l in f if len(l)]
    anag = {}
    for l in ll:
        tll = tri(l)
        if tll not in anag:
            anag[tll] = [l]
        else:
            anag[tll].append(l)
    print('Fin lecture')
    G = nx.Graph()
    cherche(G, 'casse', 'punir', opti=0)
    #cherche(G, 'bebe', 'vieillard')
    #cherche(G, 'mot', 'zeste')
{'fraction_non_alphanumeric': 0.14466965805353552, 'fraction_numerical': 0.010211975862602507, 'mean_word_length': 1.7623931623931623, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4676554', 'n_tokens_mistral': 2358, 'n_tokens_neox': 2303, 'n_words': 638}