Code source de jouets.anagrammes

# Copyright 2014-2018 Louis Paternault
#
# This file is part of Jouets.
#
# Jouets is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# Jouets is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Jouets.  If not, see <http://www.gnu.org/licenses/>.

"""Recherche d'anagrammes : classes principales."""

import collections
import copy
import logging
import math
import re
import subprocess
import textwrap

from unidecode import unidecode


[docs]class Alphabet: """Ensemble de lettres avec répétition. Cet ensemble est stocké dans l'attribut :attr:`Alphabet._elements`, qui est un dictionnaire dont les clefs sont les lettres, et les valeurs sont le nombre d'occurence de ces lettres. Les lettres qui ont une occurence nulle sont considérées comme absentes, et ignorées dans la plupart des méthodes. >>> alpha = Alphabet("aabc") >>> alpha -= "ab" >>> alpha Alphabet("ac") >>> ("a" in alpha, "b" in alpha, "c" in alpha) (True, False, True) >>> alpha += "ad" >>> alpha Alphabet("aacd") >>> (alpha["a"], alpha["d"], alpha["X"]) (2, 1, 0) """ def __init__(self, initial=None): if isinstance(initial, dict): self._elements = collections.defaultdict(int, initial) elif isinstance(initial, collections.Iterable): self._elements = collections.defaultdict(int) for i in initial: self._elements[i] += 1 else: self._elements = collections.defaultdict(int) def __contains__(self, value): return self._elements.get(value, 0) != 0 def __sub__(self, other): newelements = copy.copy(self._elements) for char in other: newelements[char] -= 1 return self.__class__(newelements) def __add__(self, other): newelements = copy.copy(self._elements) for char in other: newelements[char] += 1 return self.__class__(newelements) def __isub__(self, other): return self - other def __iadd__(self, other): return self + other def __str__(self): return str(dict(self._elements))
[docs] def keys(self): """Itére sur les lettres présentes.""" yield from (key for key in self._elements.keys() if self._elements[key])
def __bool__(self): return sum(count for count in self._elements.values()) > 0 def __getitem__(self, key): return self._elements.get(key, 0)
[docs] def items(self): """Itère sur les couples ``(lettre, effectif)`` (uniquement pour les effectifs non nuls).""" for key in self._elements.keys(): yield key, self[key]
def __repr__(self): return """{}("{}")""".format( self.__class__.__name__, "".join(key * value for key, value in sorted(self.items())), )
[docs]class Intervalle: """Intervalle (borne minimale et maximale). Ajouter ou soustraire un nombre à l'intervalle applique cette opération aux deux bornes. >>> Intervalle(0, 2) Intervalle(0, 2) >>> Intervalle(-math.inf, 2) Intervalle(-math.inf, 2) >>> Intervalle(3, 5) + 2 Intervalle(5, 7) >>> Intervalle(-math.inf, 5) - 2 Intervalle(-math.inf, 3) >>> str(Intervalle(2, math.inf)) '2:' >>> Intervalle(2, math.inf).pprint() '[2 ; +∞[' """ def __init__(self, mini, maxi): if mini is None: self.mini = -math.inf else: self.mini = mini if maxi is None: self.maxi = math.inf else: self.maxi = maxi def __add__(self, other): return self.__class__(self.mini + other, self.maxi + other) def __sub__(self, other): return self.__class__(self.mini - other, self.maxi - other) def __str__(self): texte = "" if self.mini != -math.inf: texte += str(self.mini) texte += ":" if self.maxi != math.inf: texte += str(self.maxi) return texte def __eq__(self, other): if not isinstance(other, self.__class__): return False return self.mini == other.mini and self.maxi == other.maxi def __repr__(self): if self.mini == -math.inf: strmini = "-math.inf" else: strmini = str(self.mini) if self.maxi == math.inf: strmaxi = "math.inf" else: strmaxi = str(self.maxi) return "{}({}, {})".format(self.__class__.__name__, strmini, strmaxi)
[docs] def pprint(self): """Représentation mathématique de l'intervalle. Au moment où j'écris ces mots, je ne l'utilise pas, mais je trouvais ça élégant. """ if self.mini == -math.inf: strmini = "]-∞" else: strmini = "[" + str(self.mini) if self.maxi == math.inf: strmaxi = "+∞[" else: strmaxi = str(self.maxi) + "]" return "{} ; {}".format(strmini, strmaxi)
[docs]class DictionnaireArborescent: """Dictionnaire arborescent.""" def __init__(self): self.mot = False self.suffixes = {} @staticmethod def _iter_lignes(nom): if nom.startswith("aspell://"): with subprocess.Popen( ["aspell", "-d", nom[len("aspell://") :], "dump", "master"], stdout=subprocess.PIPE, universal_newlines=True, ) as proc: yield from proc.stdout.readlines() else: with open(nom) as fichier: yield from fichier.readlines()
[docs] def charge(self, nom, *, accents=False): """Charge un dictionnaire. :param str nom: Nom du fichier contenant le dictionnaire (sous la forme d'une liste de mots séparés par des espaces ou sauts de lignes). Si ce nom commence par ``aspell://``, le dictionnaire aspell de la langue donnée est utilisé à la place. """ for ligne in self._iter_lignes(nom): for match in re.compile(r"\w+").finditer(ligne): mot = match.group().lower() if not accents: mot = unidecode(mot) self.ajoute(mot)
[docs] def clean(self): """Supprime tous les mots du dictionnaire.""" for branche in self.suffixes.values(): branche.clean() self.suffixes = {} self.mot = False
[docs] def ajoute(self, lettres): """Ajoute un mot au dictionnaire Les dictionnaires suffixes sont créés si nécessaire. """ if not lettres: self.mot = True return if lettres[0] not in self.suffixes: self.suffixes[lettres[0]] = DictionnaireArborescent() self.suffixes[lettres[0]].ajoute(lettres[1:])
[docs] def itere_mots(self): """Itérateur sur les mots de cet arbre.""" if self.mot: yield "" for lettre, branche in sorted(self.suffixes.items()): for suffixe in branche.itere_mots(): yield lettre + suffixe
[docs] def anagrammes(self, alphabet, options): """Itérateur sur les anagrammes. :param list alphabet: Lettres (sous la forme d'une liste de mots) dont on recherche les anagrammes. :param dict options: Options de la recherche. Les options sont : - ``options['accents']`` : Booléen : les accents sont-ils pris en compte, ou ignorés. - ``options['mots']`` : Intervalle (sous la forme d'un tuple ``(min, max)``) : nombre de mots acceptés (entre `min` et `max`). - ``options['lettres']`` : Intervalle (sous la forme d'un tuple ``(min, max)``) : chaque mot doit avoir entre `min` et `max` lettres. """ alphabet = "".join(alphabet) if not options.get("accents", True): alphabet = unidecode(alphabet) yield from self._multi_anagrammes( Alphabet(alphabet.lower()), mots=options.get("mots", Intervalle(None, None)), lettres=options.get("lettres", Intervalle(None, None)), )
[docs] def _multi_anagrammes(self, alphabet, mots, lettres, *, apres=None): """Recherche de plusieurs mots formant une anagramme à l'argument `alphabet`. :param Alphabet alphabet: Lettres à utiliser pour former les anagrammes. :param Intervalle mots: Nombre de mots acceptés. :param Intervalle lettres: Nombre de lettres (par mot) acceptées. :param str apres: Si différent de ``None``, les anagrammes doivent être plus grandes que cet argument (dans l'ordre lexicographique). """ if not alphabet: # Plus de lettres disponibles : # - soit on a trouvé une anagramme, # - soit on abandonne. if mots.mini <= 0: yield [] return # Si l'on continue, nous auront plus de mots que la limite à respecter. # On abandonne. if mots.maxi == 0: return # Recherche d'anagrammes for (mot, reste) in self._anagrammes(alphabet, lettres, apres=apres): # Pour chacun des anagrammes trouvées, # on cherche des anagrammes avec les lettres restantes. for suite in self._multi_anagrammes(reste, mots - 1, lettres, apres=mot): yield [mot] + suite
[docs] def _anagrammes(self, alphabet, lettres, *, apres=None): """Recherche d'un seul mot formant une anagramme à `alphabet`. Cette fonction est une fonction similaire à :meth:`DictionnaireArborescent.anagramme`, mais de plus bas niveau. :param Alphabet alphabet: Lettres à utiliser pour former l'anagramme. :param Intervalle lettres: Nombre de lettres (par mot) acceptées. :param str apres: Si différent de ``None``, les anagrammes doivent être plus grandes que cet argument (dans l'ordre lexicographique). """ if self.mot and lettres.mini <= 0: # On a trouvé un mot, qui est assez grand. yield ("", alphabet) if lettres.maxi < 0: # Le mot courant est trop long ; on ne trouvera plus de mot assez court. return if not apres: # Si ``apres`` n'est pas défini, on lui assigne une valeur arbitraire, # plus petite que toutes les autres qui seront rencontrées plus tard. # Tous les mots seront donc supérieurs à ``apres``. apres = [chr(0)] # Pour chacune des lettres possibles for debut in sorted(self.suffixes): # On exclut les cas impossibles : if debut not in alphabet: # La lettre n'est pas disponible dans l'aphabet continue if debut < apres[0]: # Le mot serait situé trop tôt dans le dictionnaire continue # Construction du mot après lequel on peut chercher if debut == apres[0]: suivant = apres[1:] else: suivant = None # Recherche des anagrammes dans les suffixes for (mot, reste) in self.suffixes[ # pylint: disable=protected-access debut ]._anagrammes(alphabet - debut, lettres - 1, apres=suivant): yield (debut + mot, reste)
[docs] def dot(self, prefixe=""): """Renvoie le code Graphviz correspondant à l'objet.""" texte = "" for lettre in self.suffixes: if prefixe: noeud = prefixe else: noeud = "#root#" texte += """"{}" -> "{}";\n""".format(noeud, prefixe + lettre) texte += self.suffixes[lettre].dot(prefixe + lettre) if prefixe: # pylint: disable=no-else-return if self.mot: forme = "doublecircle" else: forme = "circle" return texte + """"{}"[label="{}", shape={}];\n""".format( prefixe, prefixe[-1], forme ) else: return textwrap.dedent( """ digraph {{ "{}" [label="", shape=point]; {} }} """ ).format(noeud, texte)