PYTHON : EXERCICES NIVEAU D

Les exercices proposés sur cette page permettent une mise en oeuvre en Python, des concepts du paradigme de la programmation par objets. Pour chaque exercice, il s'agit de créer une classe (ou parfois, plusieurs classes) regroupant les attributs et les méthodes nécessaires pour fournir les fonctionnalités demandées. Pour chaque classe, on implémentera également une série de tests d'exécution permettant de valider les fonctionnalités implémentées (cf. la section Exemple d'utilisation pour chaque exercice). La fonction testcode issue dans le module ezCLI permet de faciliter grandement la gestion de ces tests d'exécution. Enfin, un soin particulier devra être porté sur la généricité des classes qui seront développées, une propriété qui garantit que la classe offre des fonctionnalités qui soient les plus indépendantes possibles de la quantité et de la nature des données manipulées.

Pour bien démarrer, il est fortement conseillé de s'inspirer de quelques exemples de programmes. Deux sources de documentation sont disponibles :

Exercice D0

L'objectif de cet exercice d'introduction est de réaliser une série de modifications simples sur les codes sources fournis dans la rubrique "Exemples Niveau D" :

Exercice D1

En s'inspirant de la classe dice, écrire une classe deck qui permet la simulation d'un tirage aléatoire dans un jeu de cartes. Pour identifier les cartes, on utilisera la notation standard où chaque carte est définie par une chaîne de 2 caractères: sa valeur parmi l'ensemble "AKQJT98765432" et sa couleur parmi l'ensemble "SHDC" (spade, heart, diamond, club). Mais l'utilisateur pourra spécifier d'autres chaînes de caractères pour définir l'ensemble des valeurs, et l'ensemble des couleurs. L'exemple d'utilisation (testcode) ci-dessous illustre le comportement souhaité des différentes méthodes à implémenter.

Comme pour la classe dice, on écrira d'abord une version "draft" qui ne s'occupe pas des critères de robustesse (autrement dit, uniquement des attributs publics, sans contrôle des valeurs, sans "getter" ni "setter), puis une version plus robuste, qui stocke les données utilisées dans des attributs cachés accessibles par "setter" et/ou "getter", et met en place un contrôle des valeurs fournies par l'utilisateur, à l'aide de la commande assert.

Exemple d'utilisation :
────────────────────────────────────────────────────────────────────────────────
DECK : card deck simulator
────────────────────────────────────────────────────────────────────────────────
>>> a = deck()
>>> a
deck(values='AKQJT98765432', colors='SHDC')
>>> a.values, a.colors, len(a)
('AKQJT98765432', 'SHDC', 52)
>>> a.deck
2H TC 4H 7C 2C TH 9S QH 3D 8S 9C KH QD 3C JC 4C AC KD TS AS 3H 2D 7D AH 6H 8D
5C 4D 6S AD JH 3S 6D 4S QS 2S KC JS 7H 8H 9H TD 5S 6C 9D 8C 7S KS 5H QC JD 5D
>>> a.shuffle()
>>> a.deck
8S 4H 4S 9H KS 6S 9C TD 4C 5H 9S 3D 5D 7C TS 3C JH 8C TH 7D AD AH 5S 2S QH 9D
3H KC 6H 5C JD 2C 6D QC KH 2H 4D 8H KD JC 3S JS AC AS 6C QD 7H 2D QS 8D 7S TC
>>> b = deck('ABCD', '1234')
>>> b
deck(values='ABCD', colors='1234')
>>> b.values, b.colors
('ABCD', '1234')
>>> b.deck, len(b)
('D3 B3 D2 D4 C3 C1 C2 A1 B4 B1 B2 A3 A4 A2 C4 D1', 16)
>>> b.draw(), b.draw(), b.draw(), b.draw(5)
('D3', 'B3', 'D2', ('D4', 'C3', 'C1', 'C2', 'A1'))
>>> b.deck, len(b)
('B4 B1 B2 A3 A4 A2 C4 D1', 8)
>>> b.draw(8)
('B4', 'B1', 'B2', 'A3', 'A4', 'A2', 'C4', 'D1')
>>> b.deck, len(b)
('', 0)
>>> b.draw()
AssertionError: no more card in deck 

Exercice D2

Ecrire une classe counter qui permet la gestion d'un compteur numérique dont le comportement est illustré par l'exemple d'exécution ci-dessous. Faire d'abord une première implémentation sans contrôle d'accès ni contrôle de typage, puis une seconde qui rajoute ces éléments.

Remarque: Une instruction Python de type "self()" va appeler la méthode spéciale __call__(self). De même, une instruction de type "self += value" va appeler la méthode spéciale __iadd__(self, value). Enfin, une instruction de type "self -= value" va appeler la méthode spéciale __isub__(self, value).

Exemple d'utilisation :
────────────────────────────────────────────────────────────────────────────────
COUNTER : a basic numerical counter
────────────────────────────────────────────────────────────────────────────────
>>> a = counter()
>>> a, a()
(counter(0), 0)
>>> a += 5
>>> a, a()
(counter(5), 5)
>>> b, c = counter(-5), counter(9.0)
>>> b, b(), c, c()
(counter(-5), -5, counter(9.0), 9.0)
>>> a -= 1; b += 2; c -= 1.5
>>> a, a(), b, b(), c, c()
(counter(4), 4, counter(-3), -3, counter(7.5), 7.5)
>>> a.reset(), b.reset(), c.reset()
(0, -5, 9.0)
>>> a, a(), b, b(), c, c()
(counter(0), 0, counter(-5), -5, counter(9.0), 9.0)
>>> a = counter('zzz')
AssertionError: data type must be integer, float or complex
>>> a += 'zzz'
AssertionError: data type must be integer, float or complex
>>> a, a()
(counter(0), 0)

Exercice D3

Ecrire une classe color qui permet de manipuler une couleur en mode RGB. Cette couleur peut être définie de deux manières équivalentes: soit par une triplet (r,g,b) dont les trois valeurs sont des entiers compris dans l'intervalle [0,255], soit par une chaîne de caractères de la forme '#RRGGBB' dans laquelle les trois composantes RGB sont exprimées en hexadécimal. Comme pour l'exercice précédent, on implémentera d'abord une première version sans contrôle d'accès ni contrôle de typage, puis une seconde qui rajoutera ces éléments supplémentaires.

Exemple d'exécution :
────────────────────────────────────────────────────────────────────────────────
COLOR : a class for manipulating RGB colors
────────────────────────────────────────────────────────────────────────────────
>>> a = color()
>>> a, a(), str(a)
(color(0, 0, 0), (0, 0, 0), '#000000')
>>> b, c = color(64, 32, 16), color('#FF00FF')
>>> a(), b(), c()
((0, 0, 0), (64, 32, 16), (255, 0, 255))
>>> str(a), str(b), str(c)
('#000000', '#402010', '#FF00FF')
>>> a(64,128,192), b('#012345'), c(500,240,-32)
((64, 128, 192), (1, 35, 69), (255, 240, 0))
>>> a(), b(), c()
((64, 128, 192), (1, 35, 69), (255, 240, 0))
>>> str(a), str(b), str(c)
('#4080C0', '#012345', '#FFF000')
>>> a(0.5)
AssertionError: 0.5 = invalid value for color
>>> a(64,64)
AssertionError: (64,64) = invalid value for color
>>> b('#0123')
AssertionError: '#0123' = invalid value for color
>>> c('#ZZZZZZ')
AssertionError: '#ZZZZZZ' = invalid value for color

Exercice D4

Ecrire une classe deq (double ended queue) qui permet la gestion d'une file à double entrée. La classe doit définir deux séries de méthodes (l'une préfixée par head et l'autre par tail) qui permettent d'effectuer les opérations de lecture, insertion et suppression, soit en tête de file, soit en queue de file.

Exemple d'utilisation :
────────────────────────────────────────────────────────────────────────────────
DEQ : a generic double-ended queue
────────────────────────────────────────────────────────────────────────────────
>>> a, b = deq(), deq('x', 'y', 'z', 'y', 'x')
>>> a, b, a(), b()
(deq(), deq('x', 'y', 'z', 'y', 'x'), (), ('x', 'y', 'z', 'y', 'x'))
>>> type(a), type(a())
(<class 'deq'>, <class 'tuple'>)
>>> len(a), a.head(), a.head(1), a.tail(), a.tail(3)
(0, None, (), None, ())
>>> len(b), b.head(), b.head(1), b.tail(), b.tail(3)
(5, 'x', ('x',), 'x', ('z', 'y', 'x'))
>>> a = b.clone(); b.clear()
>>> a, b, a(), b()
(deq('x', 'y', 'z', 'y', 'x'), deq(), ('x', 'y', 'z', 'y', 'x'), ())
>>> b.headpush(1, 2, 3); b.tailpush(2, 1)
>>> a.headpush(b.head(3)); a.tailpush(*b.tail(3))
>>> a, b
(deq((1, 2, 3), 'x', 'y', 'z', 'y', 'x', 3, 2, 1), deq(1, 2, 3, 2, 1))
>>> a.headpull(), a.tailpull(3), b.headpull(), b.tailpull(1)
((1, 2, 3), (3, 2, 1), 1, (1,))
>>> a, b
(deq('x', 'y', 'z', 'y', 'x'), deq(2, 3, 2))
>>> a.rotate(2); b.rotate(-1)
>>> a, b
(deq('z', 'y', 'x', 'x', 'y'), deq(2, 2, 3))

Exercice D5

Ecrire une classe olist (ordered list) qui permet la gestion d'une liste contenant des données qui sont toutes de même nature (par exemple, 'int', 'float', 'str', etc) et triées selon leur relation d'ordre naturelle (ordre croissant pour les valeurs numériques, ordre lexicographique pour les chaînes de caractères, etc). L'exemple d'utilisation ci-dessous donne le comportement souhaité des différentes méthodes à implémenter (comme d'habitude, à vous d'analyser l'exemple d'exécution pour trouver les méthodes à implémenter, ainsi que leurs arguments et retours).

Quatre implémentations sont envisageables pour la classe olist (notées A, B, C, et D) et on pourra comparer l'efficacité de ces différentes implémentations:
  1. A - Les données sont stockées dans une liste standard que l'on trie après chaque insertion
  2. B - Les données sont stockées dans une liste standard triée et l'on utilise une recherche dichotomique pour l'insertion et la recherche de valeurs
    (cf. la page Wikipedia associée à cette notion)
  3. C - Les données sont stockées dans une structure d'arbre binaire de recherche
    (cf. la page Wikipedia associée à cette notion)
  4. D - Les données sont stockées dans une structure de tas
    (cf. la page Wikipedia associée à cette notion)
Exemple d'utilisation :
================================================================================
OLIST : a generic ordered list
================================================================================
### test code for class "olist"
>>> a, b = olist(), olist(3, 2, 1)
>>> a, type(a), len(a)
(olist(), <class 'olist'>, 0)
>>> tuple(a), list(a), str(a)
((), [], '')
>>> b, type(b), len(b)
(olist(1, 2, 3), <class 'olist'>, 3)
>>> tuple(b), list(b), str(b)
((1, 2, 3), [1, 2, 3], '1,2,3')
>>> b.insert(5,2); a.insert(2,7,9,4,7)
>>> a, b
(olist(2, 4, 7, 7, 9), olist(1, 2, 2, 3, 5))
>>> 1 in a, 4 in a, a.count(7), a.count(8)
(False, True, 2, 0)
>>> [x**2 for x in a]
[4, 16, 49, 49, 81]
>>> a.delete(7); b.delete(3,2)
>>> a, b
(olist(2, 4, 7, 9), olist(1, 2, 5))
>>> b = a.clone(); a.clear()
>>> a, b
(olist(), olist(2, 4, 7, 9))

Exercice D6

Ecrire une classe floatN qui permet la gestion d'un vecteur (i.e tableau monodimensionnel) de taille N dont les composantes sont des attributs de type float . La taille d'un vecteur sera définie au moment de l'appel au constructeur et ne pourra pas être modifiée par la suite. Toutes les opérations classiques sur les vecteurs doivent être implémentées, notamment par surcharge des opérateurs standards. De plus, lors de ces opérations, la compatibilité des tailles des deux vecteurs devra être vérifiée. A partir de cette classe floatN, dériver les classes float2 et float3 permettant d'implémenter des vecteurs de taille 2 et 3 respectivement.

Exemple d'utilisation :
================================================================================
FLOATN : a floating point vector of length N
================================================================================
### test code for class "floatN"
>>> a = floatN()
>>> a, type(a)
(floatN(0.0,), <class 'floatN'>)
>>> b, c, d = floatN(5, n=2), floatN(1, 3), floatN(1, 2, n=2)
>>> a, b, c, d
(floatN(0.0,), floatN(5.0, 5.0), floatN(1.0, 3.0), floatN(1.0, 2.0, 1.0, 2.0))
>>> a(), len(a), b(), len(b), c(), len(c), d(), len(d)
((0.0,), 1, (5.0, 5.0), 2, (1.0, 3.0), 2, (1.0, 2.0, 1.0, 2.0), 4)
>>> e = floatN('zzz')
ValueError : incorrect value in 'floatN' object
>>> a + 2, b - (2.5, -10), c * (2.5, 5), d ** 3
(floatN(2.0,), floatN(2.5, 15.0), floatN(2.5, 15.0), floatN(1.0, 8.0, 1.0, 8.0))
>>> a += 2; b -= (2.5, -10); c *= (2.5, 5); d **= 3
>>> a, b, c, d
(floatN(2.0,), floatN(2.5, 15.0), floatN(2.5, 15.0), floatN(1.0, 8.0, 1.0, 8.0))
>>> b is c, b is b.clone(), b == c, b == b.clone()
(False, False, True, True)
>>> c/5, 3 - b, -b + c%2, abs(-b + c%2)
(floatN(0.5, 3.0), floatN(0.5, -12.0), floatN(-2.0, -14.0), floatN(2.0, 14.0))
>>> b[0], b[1], c[:]
(2.5, 15.0, (2.5, 15.0))
>>> a[0] = 5
TypeError : 'floatN' object does not support item assignment

Exercice D7

Ecrire une classe minmax qui permet la gestion des opérations arithmétiques standards sur une valeur numérique (entière ou réelle) de telle manière à ce que le résultat des opérations effectuées soit toujours tronqué pour être compris dans un intervalle [min,max] dont les bornes sont fournies au moment de la création de l'objet.

Exemple d'utilisation :
================================================================================
MINMAX : numerical value clamped to range [min, max]
================================================================================
>>> a, b, c = minmax(), minmax(50, 0, 100), minmax(0, -5, 5)
>>> a, b, c
(minmax(0, -1, 1), minmax(50, 0, 100), minmax(0, -5, 5))
>>> a(), a.range, a.min, a.max, b(), b.range, c(), c.range
(0, (-1, 1), -1, 1, 50, (0, 100), 0, (-5, 5))
>>> a += b; b -= 10; c -= b
>>> a, b, c
(minmax(1, -1, 1), minmax(40, 0, 100), minmax(-5, -5, 5))
>>> b/2 + a, -c - b%3
(minmax(21, 0, 100), minmax(4, -5, 5))

Exercice D8

Ecrire une classe grid qui permet la gestion d'une grille rectangulaire générique (i.e. pouvant contenir des données arbitraires). La classe grid doit contenir un attribut row (nombre de lignes dans la grille), un attribut col (nombre de colonnes dans la grille), un attribut none (valeur par défaut stockée dans les cellulles de la grille) et un attribut caché _grid (structure contenant les données de la grille). Les fonctionnalités demandées pour la classe grid sont résumées dans l'exemple d'utilisation ci-dessous. Comme pour les exercices précédents, on implémentera d'abord une première version sans contrôle d'accès ni contrôle de typage, puis une seconde qui rajoutera ces éléments supplémentaires.

On pourra tester trois implémentations différentes en termes de structure de données: Remarque 1 : Une instruction Python de type "self[index]" appliquée à un objet self va appeler la méthode spéciale __getitem__(self, index). De même, une instruction de type "self[index] = value" va appeler la méthode spéciale __setitem__(self, index, value). Enfin, une instruction de type "del self[index]" va appeler la méthode spéciale __delitem__(self, index). Dans le cas de la classe grid, le paramètre index ne sera pas un entier, mais sera soit un couple d'entiers définissant une cellule, soit un couple de "slices" définissant un groupe de cellules.

Remarque 2 : Une instruction Python de type "tuple(x)" ou "list(x)" va appeler la méthode spéciale __iter__(self) qui renvoie un itérateur permettant d'énumérer les éléments contenu dans la structure x

Exemple d'utilisation :
================================================================================
GRID : a simple rectangular 2D grid
================================================================================
>>> a, b = grid(), grid(3, 6, 0)
>>> a, a.row, a.col, a.none, a.size
(grid(row=1, col=1, none=None), 1, 1, None, 1)
>>> b, b.row, b.col, b.none, a.size
(grid(row=3, col=6, none=0), 3, 6, 0, 18)
>>> a()
[[None]]
>>> str(a)
┌────┐
│None│
└────┘
>>> b()
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
>>> str(b)
┌─┬─┬─┬─┬─┬─┐
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
└─┴─┴─┴─┴─┴─┘
>>> a('A','B','C','D','E'), b(1,2,3,4,5,6,7,8,9)
([['A']], [[1, 2, 3, 4, 5, 6], [7, 8, 9, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
>>> str(a)
┌─┐
│A│
└─┘
>>> str(b)
┌─┬─┬─┬─┬─┬─┐
│1│2│3│4│5│6│
├─┼─┼─┼─┼─┼─┤
│7│8│9│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
└─┴─┴─┴─┴─┴─┘
>>> len(a), len(b)
(1, 9)
>>> tuple(b)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0)
>>> list(b)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> a[0,0], b[0,-1], b[1,:], b[:,1]
('A', 6, [7, 8, 9, 0, 0, 0], [2, 8, 0])
>>> a.clear(), b.clear()
([[None]], [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
>>> b[1,0] = b[1,-1] = 1; b[0,:] = 2; b[:,1] = 3; b[1:,2:4] = 4; b[-1,::5] = 5
>>> str(b)
┌─┬─┬─┬─┬─┬─┐
│2│3│2│2│2│2│
├─┼─┼─┼─┼─┼─┤
│1│3│4│4│0│1│
├─┼─┼─┼─┼─┼─┤
│5│3│4│4│0│5│
└─┴─┴─┴─┴─┴─┘
>>> c, d = b.clone(), b.copy()
>>> c, d
(grid(row=3, col=6, none=0), grid(row=3, col=6, none=0))
>>> str(c)
┌─┬─┬─┬─┬─┬─┐
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
└─┴─┴─┴─┴─┴─┘
>>> str(d)
┌─┬─┬─┬─┬─┬─┐
│2│3│2│2│2│2│
├─┼─┼─┼─┼─┼─┤
│1│3│4│4│0│1│
├─┼─┼─┼─┼─┼─┤
│5│3│4│4│0│5│
└─┴─┴─┴─┴─┴─┘

Exercice D9

Ecrire une classe GravityGrid qui permet d'implémenter la structure de données "grille à gravité" dans laquelle les éléments d'une grille 2D partiellement remplie subissent l'influence de la gravité pour tomber le long de chaque colonne. On pourra baser l'implémentation sur l'utilisation de la classe grid de l'exercice D8.

Exemple d'utilisation :
================================================================================
GRAVITYGRID : a 2D rectangular grid with gravity
================================================================================
>>> a = GravityGrid(3, 6, 0)
>>> a, a.row, a.col, a.none, len(a)
(GravityGrid(row=3, col=6, none=0), 3, 6, 0, 0)
>>> a()
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
>>> str(a)
┌─┬─┬─┬─┬─┬─┐
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
└─┴─┴─┴─┴─┴─┘
>>> a(1,2,3,4,5,6,7,8,9) # set initial items
[[1, 2, 3, 4, 5, 6], [7, 8, 9, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
>>> len(a)
9
>>> str(a)
┌─┬─┬─┬─┬─┬─┐
│1│2│3│4│5│6│
├─┼─┼─┼─┼─┼─┤
│7│8│9│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
└─┴─┴─┴─┴─┴─┘
>>> a.gravity() # apply gravity
>>> str(a)
┌─┬─┬─┬─┬─┬─┐
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│1│2│3│0│0│0│
├─┼─┼─┼─┼─┼─┤
│7│8│9│4│5│6│
└─┴─┴─┴─┴─┴─┘
>>> a[0,1] = a[0,3] = a[0,4] = a[0,5] = 1 # add 4 items on top row
>>> a[2,1] = a[2,3] = 0 # remove 2 items on bottom row
>>> del a[2,0] # alternative way to remove item
>>> len(a)
10
>>> str(a)
┌─┬─┬─┬─┬─┬─┐
│0│1│0│1│1│1│
├─┼─┼─┼─┼─┼─┤
│1│2│3│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│9│0│5│6│
└─┴─┴─┴─┴─┴─┘
>>> a.gravity() # apply gravity
>>> str(a)
┌─┬─┬─┬─┬─┬─┐
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│1│3│0│1│1│
├─┼─┼─┼─┼─┼─┤
│1│2│9│1│5│6│
└─┴─┴─┴─┴─┴─┘
>>> a.clear()
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
>>> len(a)
0
>>> str(a)
┌─┬─┬─┬─┬─┬─┐
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
├─┼─┼─┼─┼─┼─┤
│0│0│0│0│0│0│
└─┴─┴─┴─┴─┴─┘
...
Christophe Schlick