ASCII Art - Encodage

Contexte

L’art ASCII consiste à réaliser des images uniquement à l’aide des lettres et caractères spéciaux contenus dans le code ASCII.

Vous pouvez trouver des ASCII art simples sur le site ASCII art archive ou construire les votres à partir d’images et de ce générateur.

Environnement de travail

Pour cet exercice, vous devez utiliser en priorité le fichier squelette ex07-artcode.py. IMPORTANT : Enregistrez le avec Right Click + Save Link As... pour conserver l’encodage.

Selon la convention de structuration des modules, ce fichier sera structuré en quatre parties :

1. Imports et définition des variables globales ;
2. Définition des fonctions secondaires ;
3. Définition de la fonction principale ;
4. Appel protégé de la fonction principale.

Algorithme itératif

Objectifs

L’objectif est d’écrire une fonction artcode_i() mettant en oeuvre un algorithme itératif de codage, c’est à dire de transformation d’une image ASCII Art représentée par une chaine de caractère en une représentation plus compacte :

• qui prend en argument une chaîne de caractères ;
• et qui retourne une liste de tuples, correspondant au codage de la chaîne de caractères.

Chaque tuple est composé d’un caractère (et d’un seul) et du nombre d’occurences consécutives de ce caractère. Par exemple :

• la chaîne MMMMaaacXolloMM
• est représentée par la liste [('M', 4), ('a', 3), ('c', 1), ('X', 1), ('o', 1), ('l', 2), ('o', 1), ('M', 2)].

Vérifier le bon fonctionnement de la fonction en effectuant un appel depuis main() et en affichant la valeur de retour pour l’exemple ci dessus.

Informations complémentaires

On peut construire un algorithme itératif sur la propriété suivante:

\(I(C, O, k)\) : \(C\) est la liste des caractères rencontrés lors du parcours de \(s[0:k]\) et \(O\) est la liste des occurrences correspondantes.

L’initialisation est directe :

• le premier caractère de \(s\) est \(s[0]\), et donc \(C = [ s[0] ]\)
• il a été rencontré une fois, et donc \(O = [ 1 ]\)
• et la chaîne restante à traiter est \(s[1:]\), c’est à dire \(k = 1\)

Si \(n\) est la longueur de la chaîne \(s\) :

• le critère d’arrêt est \(A : k \geq n\)
• et la condition de continuation \(\bar{A} : k < n\).

La progression, en supposant \(I(C, O, k)\) et \(\bar{A}\):

• si le caractère courant est identique au caractère précédent, on augmente le nombre d’occurrences d’une unité:

    SI s[k] = s[k-1]
    ALORS O[-1] += 1

• sinon :

  • on ajoute un nouveau caractère à la liste \(C\) des caractères rencontrés ;
  • et \(1\) à la liste \(O\) des occurrences.

• dans les deux cas, on progresse dans la chaîne : \(k = k+1\).

L’algorithme manipule deux listes distinctes (une liste de caractères et une liste d’occurrences) alors que la consigne est d’en retourner une seule formée de tuples dont le premier élément est pris dans \(C\) et le second dans \(O\). La fonction zip réalise cette opération de façon très compacte.

Doctests

Une fois la fonction opérationnelle pour quelques arguments, ET SEULEMENT DANS CE CAS, lancer les doctests dans un terminal.

$ python -m doctest ex07_artcode.py -v

La totalité des doctests doivent réussir.

Algorithme récursif

Objectifs

Écrire une fonction artcode_r() mettant en oeuvre un algorithme récursif de codage :

• qui prend en argument une chaîne de caractères ;
• et qui retourne une liste de tuples, correspondant au codage de la chaîne de caractères.

Vérifier le bon fonctionnement de la fonction en effectuant un appel depuis main() et en affichant la valeur de retour (les doctests de la fonction donnent des exemples d’appel et les valeurs de retour correspondantes).

Informations complémentaires

Pour l’écriture d’un algorithme récursif, il y a 2 questions essentielles qui structurent le raisonnement :

• Quel est le cas de base ? La valeur retournée dans ce cas ?
• Quel est l’appel récursif permettant de résoudre un problème de taille inférieure ?

On peut penser à rechercher le nombre de caractères identiques au premier caractère de la chaîne passée en argument et recommencer l’opération sur la chaine restante. L’idée est de retourner une liste construite à partir du résultat ci dessus et d’un appel récursif.

Sur les listes, l’opérateur + permet de construire une nouvelle liste constituée des deux opérandes. Cette façon de faire est à privilégier. Attention, la méthode list.extend() modifie la liste sur place.

Doctests

Une fois la fonction opérationnelle pour quelques arguments, ET SEULEMENT DANS CE CAS, lancer les doctests dans un terminal.

$ python -m doctest ex07_artcode.py -v

La totalité des doctests doivent réussir.

Applications

Encoder les images contenues dans les variables globales WWFet APPLE.