s1-tp/S2/TP2/tp2.py

# PREUD'HOMME Geoffrey
# BEAUSSART Jean-loup
# Donné le 27/01/2015

# TP2 Anagrammes - Dictionnaires

# http://www.fil.univ-lille1.fr/~L1S2API/CoursTP/tp2_dictionnaires.html


def partie(nom):
    print('\n', nom, '=' * len(nom), sep='\n')


def section(nom):
    print('\n', nom, '-' * len(nom), sep='\n')


def question(numero):
    print('\n***', 'Question', numero, '***')


partie('Quelques méthodes sur les listes et les chaînes')  # Geoffrey


section('Méthode split')

question(1)
print(">>> s = 'la méthode split est parfois bien utile'")
s = 'la méthode split est parfois bien utile'
print(">>> s.split (' ')")
print(s.split(' '))
print(">>> s.split ('e')")
print(s.split('e'))
print(">>> s.split ('é')")
print(s.split('é'))
print(">>> s.split ()")
print(s.split())
print(">>> s.split ('')")
print('ValueError: empty separator')
print(">>> s.split ('split')")
print(s.split('split'))

question(2)
print('La méthode `split` renvoie la liste des chaînes de la découpe de la chaîne sur laquelle est \
appliquée la fonction par la chaîne passée en argument (ou à défaut le caractères d\'espacement')

question(3)
print(">>> s = 'la méthode split est parfois bien utile'")
s = 'la méthode split est parfois bien utile'
print(">>> s.split(' ')")
print(s.split(' '))
print('>>> s')
print('\'' + s + '\'')

print('De par cet exemple, on remarque que s reste la même chaîne de caractère, `split` ne modifie \
donc pas la chaîne de caractères à laquelle elle s\'applique (ce qui est logique vu le caractère \
non-mutable des chaînes de caractères')


section('Méthode join')

question(1)
print(">>> s = 'la méthode split est parfois bien utile'")
s = 'la méthode split est parfois bien utile'
print('>>> l = s.split()')
l = s.split()
print('>>> "".join (l)')
print("".join(l))
print('>>> " ".join (l)')
print(" ".join(l))
print('>>> ";".join (l)')
print(";".join(l))
print('>>> " tralala ".join (l)')
print(" tralala ".join(l))
print('>>> "\n".join (l)')
print("\n".join(l))
print('>>> "".join (s)')
print("".join(s))
print('>>> "!".join (s)')
print("!".join(s))
print('>>> "".join ()')
print('TypeError: join() takes exactly one argument (0 given)')
print('>>> "".join ([])')
print("".join([]))
print('>>> "".join ([1,2])')
print('TypeError: sequence item 0: expected str instance, int found')

question(2)
print('La méthode join concatène les chaînes de caractères contenues dans la liste passée en \
paramètre, en insérant entre deux la chaîne de caractère sur laquelle elle est appliquée.')

question(3)
print('>>> chaine = \'!\'')
chaine = '!'
print('>>> chaine.join(l)')
print(chaine.join(l))
print('>>> chaine')
print('\'' + chaine + '\'')


print('De par cet exemple, on remarque que chaine reste la même chaîne de caractères, `join` ne \
modifie donc pas la chaîne de caractères à laquelle elle s\'applique (ce qui est logique vu le \
caractère non-mutable des chaînes de caractères')

question(4)


def join(chaine, sequence):
    """
    Retourne la concaténation des éléments de séquence en insérant chaine entre eux.
    str, [str *] → str
    """
    res = ''
    l = len(sequence)
    for i in range(l):
        res += sequence[i]
        if i < l - 1:
            res += chaine
    return res

print(">>> join('.', ['raymond', 'calbuth', 'ronchin', 'fr'])")
print(join('.', ['raymond', 'calbuth', 'ronchin', 'fr']))


section('Méthode sort')

question(1)
print('>>> l = list (\'timoleon\')')
l = list('timoleon')
print('>>> l.sort()')
l.sort()
print('>>> l')
print(l)

print('La méthode sort semble trier les lettres par ordre alphabétique')

print('>>> s = "Je n\'ai jamais joué de flûte."')
s = "Je n'ai jamais joué de flûte."
print('>>> l = list (s)')
l = list(s)
print('>>> l.sort()')
l.sort()
print('>>> l')
print(l)

print('La méthode sort trie aussi les caractères spéciaux : ponctuation au début, accents à la fin')

print('Il semblerait que la méthode sort trie les caractères de s selon l\'ordre croissant de leur \
numéro de code ASCII (ou tout encodage utilisé)')

question(2)
print('>>> l = [\'a\', 1]')
print('>>> l.sort()')
print('TypeError: unorderable types: int() < str()')

print('On obtient une erreur comme quoi les types str et int ne sont pas ordonnable. En effet, il \
n\'est pas logique d\'ordonner des caractères avec des chiffres.')
print('Notons qu\'il aurait très bien pu être possible que cette méthode utilise le code des \
caractères, puisque celui-ci est de type int, comme c\'était le cas avec Python 2.')


section('Une fonction sort pour les chaînes')

question(1)


def sort(chaine):
    """
    Trie les caractères de chaine par ordre de codage.
    str → str
    """
    t = list(chaine)
    t.sort()
    return ''.join(t)

print('>>> sort(\'timoleon\')')
print(sort('timoleon'))


partie('Anagrammes')  # Jean-loup

question(1)


def sont_anagrammes1(chaine1, chaine2):
    """
    Indique si chaine1 et chaine2 sont anagrammes
    str, str → bool
    CU : chaine1 et chaine2 sont des str
    """

    assert(type(chaine1) == type(chaine2) ==
           str), 'chaine1 et chaine2 doivent être des str'

    # Si la longueur est différente, ça ne peut pas être des anagrammes
    if len(chaine1) != len(chaine2):
        return False

    c1 = sort(chaine1)
    c2 = sort(chaine2)

    return c1 == c2

question(2)


def sont_anagrammes2(chaine1, chaine2):
    """
    Indique si chaine1 et chaine2 sont anagrammes
    str, str → bool
    CU : chaine1 et chaine2 sont des str
    """

    assert(type(chaine1) == type(chaine2) ==
           str), 'chaine1 et chaine2 doivent être des str'

    # Si la longueur est différente, ça ne peut pas être des anagrammes
    if len(chaine1) != len(chaine2):
        return False

    occu1 = dict((i, chaine1.count(i)) for i in chaine1)
    occu2 = dict((i, chaine2.count(i)) for i in chaine2)

    return occu1 == occu2

question(3)


def sont_anagrammes3(chaine1, chaine2):
    """
    Indique si chaine1 et chaine2 sont anagrammes
    str, str → bool
    CU : chaine1 et chaine2 sont des str
    """

    assert(type(chaine1) == type(chaine2) ==
           str), 'chaine1 et chaine2 doivent être des str'

    # Si la longueur est différente, ça ne peut pas être des anagrammes
    if len(chaine1) != len(chaine2):
        return False

    for i in chaine1:
        if chaine1.count(i) != chaine2.count(i):
            return False

    return True


section('Casse et accentuation')

question(1)
EQUIV_NON_ACCENTUE = {'é': 'e', 'è': 'e', 'à': 'a', 'ç': 'c', 'î': 'i', 'ï':
                      'i', 'ô': 'o', 'ê': 'e', 'ë': 'e', 'â': 'a', 'û': 'u', 'ü': 'u', 'ù': 'u'}

question(2)


def bas_casse_sans_accent(chaine):
    """
    Renvoie l'équivalent minuscule non accentuée de la chaîne passée en paramètre
    str → str
    CU : chaine est un str
    """

    assert(type(chaine) == str), 'chaine doit être un str'

    chaineCpy = chaine.lower()

    ret = ""

    for i in chaineCpy:
        if i in EQUIV_NON_ACCENTUE:
            ret += EQUIV_NON_ACCENTUE[i]
        else:
            ret += i
    return ret

question(3)


def sont_anagrammes_sans_casse_ni_accent(chaine1, chaine2):
    """
    Indique si chaine1 et chaine2 sont anagrammes sans de tenir compte de la casse ni des accents
    str, str → bool
    CU : chaine1 et chaine2 sont des str
    """

    assert(type(chaine1) == type(chaine2) ==
           str), 'chaine1 et chaine2 doivent être des str'

    # Si la longueur est différente, ça ne peut pas être des anagrammes
    if len(chaine1) != len(chaine2):
        return False

    chaine1Cpy = bas_casse_sans_accent(chaine1)
    chaine2Cpy = bas_casse_sans_accent(chaine2)

    return sont_anagrammes2(chaine1Cpy, chaine2Cpy)


partie('Recherche d\'anagrammes')  # Jean-loup


section('Le lexique')

question(1)

question(2)
from lexique import *

question(3)
print('Il y a %d mots dans le lexique' % len(LEXIQUE))

question(4)
test = len(LEXIQUE) == len(set(LEXIQUE))
# Bien que l'on ai vu en cours que cette méthode n'est pas la plus économique en mémoire, c'est
# bizarrement la plus rapide
print('Le test a retourné %s.' % test)


section('Anagrammes d\'un mot : première méthode')

question(1)


def anagrammes(mot):
    """
    Recherche les anagrammes de mot
    str → [str *]
    CU : mot est un str
    """

    assert(type(mot) == str), 'mot doit être un str'

    return [i for i in LEXIQUE if sont_anagrammes_sans_casse_ni_accent(i, mot)]

question(2)
for a in ['Orange', 'Calbuth']:
    print('Les anagrammes de %s sont %s.' % (a, ', '.join(anagrammes(a))))


section('Anagrammes d\'un mot : seconde méthode')

question(1)
print('Il se peut que certains mots du lexique soient des anagrammes d\'autres mots du lexique,\
 or on se retrouverait alors avec plusieurs fois la même liste d\'anagrammes \
 pour des clés différentes.')

question(2)


def cle(mot):
    """
    Renvoie la version triée des lettres en minuscule et sans accents de mot
    str → str
    CU : mot est un str
    """

    assert(type(mot) == str), 'mot doit être un str'

    cpy = bas_casse_sans_accent(mot)

    return sort(cpy)

question(3)
ANAGRAMMES = dict()

for m in LEXIQUE:
    k = cle(m)
    if not k in ANAGRAMMES:
        ANAGRAMMES[k] = [m]
    else:
        ANAGRAMMES[k] = ANAGRAMMES[k] + [m]


print('Le dictionnaire des anagrammes contient %d entrées' % len(ANAGRAMMES))

question(4)


def anagrammes2(mot):
    """
    Recherche les anagrammes de mot
    str → [str *]
    CU : mot est un str
    """

    assert(type(mot) == str), 'mot doit être un str'

    k = cle(mot)

    if k in ANAGRAMMES:
        return ANAGRAMMES[k]
    else:
        return []

question(5)
for a in ['Orange', 'Calbuth']:
    print('Les anagrammes de %s sont %s.' % (a, ', '.join(anagrammes2(a))))


section('Comparaison des deux méthodes')

question(1)
NB_TESTS = 30  # Mettre à 0 pour réduire l'attente

import time

debut = time.time()
for t in range(NB_TESTS):
    anagrammes(LEXIQUE[t])
temps1 = time.time() - debut

debut = time.time()
for t in range(NB_TESTS):
    anagrammes2(LEXIQUE[t])
temps2 = time.time() - debut

print('La première méthode a duré %s secondes, et la deuxième %s secondes.' % (temps1, temps2),
      'La deuxième méthode est %0.2f fois plus efficace que la première.' % (
          temps1 / temps2),
      'En effet, la première vérifie %d combinaisons d\'anagrammes, alors que la deuxième ne \
réalise qu\'un accès à un dictionnaire. Notons que la construction dudit dictionnaire a lui aussi \
pris un certain temps, mais reste négligeable par rapport à la première méthode.' % len(LEXIQUE),
      sep='\n')

partie('Phrases d\'anagrammes')  # Geoffrey

question(1)

def liste_possibilites(arbre, precede):
    """
    Renvoie la liste des possibilités à partir d'un arbre de possibilités.
    dict, list → list

    >>> liste_possibilites(annagrammes_arbre(['mange', 'ton']), [])
    [['mange', 'ton'], ['mange', 'ont'], ['mangé', 'ton'], ['mangé', 'ont']]
    """
    possibilites = []
    for branche in arbre:
        if type(arbre[branche]) == dict:
            possibilites = possibilites + \
                liste_possibilites(arbre[branche], precede + [branche])
        elif arbre[branche] == None:
            possibilites = possibilites + [precede + [branche]]
    return possibilites


def annagrammes_arbre(liste):
    """
    Renvoie l'arbre des anagrammes possibles à partir d'une liste de mots.
    list → dict

    >>> annagrammes_arbre(['mange', 'ton'])
    {'mange': {'ton': None, 'ont': None}, 'mangé': {'ton': None, 'ont': None}}
    """
    anagrammesPremier = anagrammes2(liste[0])
    if len(liste) > 1:  # Si il y a des anagrammes après
        return dict((i, annagrammes_arbre(liste[1:])) for i in anagrammesPremier)
    else:
        return dict((i, None) for i in anagrammesPremier)


def annagrammes_phrase(phrase):
    """
    Renvoie la liste des anagrammes possibles à partir d'une phrase.
    str → str

    >>> annagrammes_phrase('mange ton')
    ['mange ton', 'mange ont', 'mangé ton', 'mangé ont']
    """
    mots = phrase.split()
    arbre = annagrammes_arbre(mots)
    liste = liste_possibilites(arbre, [])
    return [' '.join(i) for i in liste]

print('>>> annagrammes_phrase(\'Mange ton orange\')')
print(annagrammes_phrase('Mange ton orange'))


partie('Sauvegarde et récupération')

ANAGRAMMES_FICHIER = 'anagrammes.txt'

question(1)


def sauver_dico():
    """
    Sauvegarde le dictionnaire des anagrammes dans un fichier.
    ∅ → ∅
    """
    fichier = open(ANAGRAMMES_FICHIER, 'w')
    for i in ANAGRAMMES:
        fichier.write(i + ':' + ':'.join(ANAGRAMMES[i]) + '\n')
    fichier.close()

question(2)
sauver_dico()
from os.path import getsize
taille = getsize(ANAGRAMMES_FICHIER)
print('Le dictionnaire fait %d octets, soit %0.3f Mio.' %
      (taille, taille / 1024 / 1024))

question(3)


def charger_dico():
    """
    Lit le dictionnaire des anagrammes depuis un fichier.
    ∅ → ∅
    """
    ANAGRAMMES = dict()
    fichier = open(ANAGRAMMES_FICHIER, 'r')
    for ligne in fichier:
        decoupe = ':'.split(str(ligne))
        ANAGRAMMES[decoupe[0]] = decoupe[1:]
    fichier.close()