Palindromes : le code

Nous allons ici mettre en oeuvre des algorithmes de reconnaissance de phrases palindromes. Vous serez certainement amené à coder quelques-uns des algorithmes que vous avez forgés dans la partie algorithmie de ce projet.

Pour le code python, il faudra impérativement :

faire les tests unitaires de chaque fonction. Ils devront tous se lancer via la commande python -m pytest
organiser votre code en autant de fichiers que nécessaire.

Palindromes

Algorithme palindrome

Implémentez l'algorithme palindrome(s: str) -> bool linéaire de la partie algorithmie

Programme principal palindrome

Créez un programme principal nommé main-palindrome.py qui demande à l'utilisateur de donner une chaîne de caractères et le programme répond "oui" si la chaîne est un palindrome et "non" sinon.

Bonus

Que fait la fonction mystère écrite ci-dessous :

def mystère(s):
   return s == s[::-1]

Phrases palindromes

Prétraitement

Pour traiter des phrases palindromes à partir d'un texte en français, il faut commencer par pré-traiter le texte pour qu'il ne contienne plus que des lettres non accentuées en majuscules.

Créez une fonction prétraitement(s: str) -> str qui effectue le prétraitement d'une chaîne de caractères. Pour cela vous pourrez utiliser, dans l'ordre :

le module unidecode (qu'il vous faudra installer avec pip) qui permet de supprimer les accents des caractères
la méthode upper des chaînes de caractères qui majuscule les lettres
l'instruction re.sub("[^A-Za-z]","",s) (sub est une fonction du module re de python) qui rend une chaîne ne possédant que les caractères alphabétiques de s.

le module re de python permet de filtrer une chaîne de caractères selon une expression régulière. Ceci dépasse le cadre de ce cours d'algorithmie mais en deux mots re.sub("[^A-Z]","",s) va rendre une nouvelle chaîne de caractères en :

regardant caractère par caractère le troisième paramètre (ici s).
elle ne conservera que les éléments décrits par le premier paramètre (ici "[^A-Z]" qui signifie toutes les lettres en majuscules)
les autres caractères sont remplacés par le second paramètre (ici "", la chaîne vide)

Programme principal phrase palindrome

Créez un programme principal nommé main-phrase-palindrome.py qui demande à l'utilisateur de donner une chaîne de caractères et le programme répond "oui" si la chaîne est une phrase palindrome et "non" sinon.

Fichier texte

On peut très facilement lire un fichier texte en python en utilisant l'instruction :

s = open(nom_du_fichier, encoding="utf-8").read()

Utilisez cette instruction pour vérifier que le texte contenu dans le fichier perec.txt (cliquez droit sur le lien et choisissez de le télécharger) est une phrase palindrome. On le doit à Georges Perec écrivain et poète Français.

Sous-palindrome

Algorithme

Implémentez l'algorithme le plus efficace que vous êtes arrivé à produire dans la partie algorithmie pour résoudre le problème du sous-palindrome.
Utilisez la question précédente pour créer une fonction sous_palindrome(s: str) -> (int, int) qui rend l'indice de début et la longueur d'un plus grand sous-palindrome de s

Programme principal

Créez un programme principal nommé main-sous-palindrome.py qui demande à l'utilisateur de donner une chaîne de caractères et le programme : écrit la phrase entrée en écrivant en rouge le plus grand sous-palindrome.

Pour changer de couleur dans un affichage à l'écran, il vous faudra utiliser un module que vous devrez installer. Vous pourrez utiliser le module pytermgui par exemple qui permet de faire plein de choses.

En lisant la documentation de son sous-module tim vous devriez comprendre comment faire pour colorer un affichage de plein de façons différentes.

Fichier texte

Créez un programme principal nommé main-sous-palindrome-fichier.py qui demande à l'utilisateur le nom d'un fichier texte se trouvant dans le dossier courant. Le programme :

lit le fichier texte
transforme le texte en une chaîne utilisable par l'algorithme sous-palindrome en utilisant la fonction prétraitement
trouve l'indice et la longueur d'un plus grand sous-palindrome
représente à l'écran le sous-palindrome retenu (écrit en rouge) entouré des 100 caractères le précédant et le succédant (écrits de façon normale).

Vous pourrez utiliser comme textes des grands classiques de la littérature française prises sur le site https://www.gutenberg.org/. Choisissez toujours la version texte brute (plain text) en utf-8.

Pour les fleurs du mal de Baudelaire c'est là : https://www.gutenberg.org/ebooks/6099

Amélioration

Trouver des sous-phrases palindromes d'un texte peut être rigolo, mais sans caractères de ponctuation, il peut être difficile de s'y retrouver.

Créez une fonction correspondance(s12: str, s123:str) -> [int] qui prend deux paramètres :

une chaîne s12 dont les lettres sont sans accents et en majuscules (résultat des étapes 1 et 2 du prétraitement pour une chaîne s)
la chaîne s123 correspondant au prétraitement complet de s12 (s12 auquel on a fait l'étape 3 du prétraitement)

Cette fonction rend un tableau $t$ de correspondance où $t[i]$ correspond à l'indice dans s12 de l'indice i dans s123.

On pourra remarquer que :

$t[0]$ correspond au plus petit indice $i$ tel que s12[i] == s123[0]
$t[u]$ correspond au plus petit indice $i > t[u-1]$ tel que s12[i] == s123[u]

Par exemple, le résultat de correspondance("OH LA LA!", "OHLALA") sera le tableau : [0, 1, 3, 4, 7, 8]

En remarquant qu'entre la chaîne initiale s et la chaîne s12 seules les lettres ont été modifiées ("ôh la là!" et "OH LA LA!") :

Plutôt que d'afficher à l'écran le sous-palindrome de la chaîne après traitement, utilisez le texte initial en écrivant en rouge la portion de texte qui est le sous-palindrome.