Programmer en Python
Leçon 2 - Python : les listes en deux dimensions
Des listes dans des listes : grilles, tableaux et plateaux de jeu
Python : les listes en deux dimensions
Des listes dans des listes : grilles, tableaux et plateaux de jeu
Ce mini cours complémentaire prolonge le cours "Python : fonctions et listes". Il introduit une seule idée nouvelle, mais elle ouvre la porte aux jeux de plateau, aux images et aux tableurs : une liste peut contenir d'autres listes.
for (avec range()), les fonctions avec def et return, et surtout les listes : création, index, len(), append(), parcours avec for element in liste.
Objectifs du cours
- Comprendre ce qu'est une liste en deux dimensions et à quoi elle sert.
- Lire et modifier une case d'une grille avec la notation à double index.
- Parcourir une grille entière grâce aux boucles imbriquées.
- Construire une grille de n'importe quelle taille avec une fonction.
- Projet final : afficher un plateau de morpion de dimension N×N.
Dans le cours 2, vous avez appris qu'une liste peut contenir des nombres, des chaînes de caractères ou des booléens. Voici la révélation du jour : une liste peut aussi contenir... d'autres listes. Cette simple idée change tout, car elle permet de représenter des grilles : un plateau d'échecs, une feuille de tableur, une image, une salle de classe avec ses rangées de tables.
Le problème que cela résout
Imaginons trois élèves qui ont chacun trois notes. Avec une liste simple, il faudrait tout mélanger : [12, 15, 9, 14, 8, 17, 10, 16, 13]. Il devient impossible de savoir où s'arrêtent les notes du premier élève. La solution : une liste par élève, et une grande liste qui les rassemble.
notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]]
La variable notes est une liste de trois éléments, et chacun de ces éléments est lui-même une liste de trois nombres. On parle de liste en deux dimensions, car les données s'organisent selon deux directions : les lignes et les colonnes.
Visualiser la grille
Pour bien comprendre, écrivons notre liste sur trois lignes (Python l'accepte sans problème) et plaçons-la en face du tableau qu'elle représente.
notes = [[12, 15, 9], # ligne 0 : élève A [14, 8, 17], # ligne 1 : élève B [10, 16, 13]] # ligne 2 : élève C
| colonne 0 | colonne 1 | colonne 2 | |
|---|---|---|---|
| ligne 0 | 12 | 15 | 9 |
| ligne 1 | 14 | 8 | 17 |
| ligne 2 | 10 | 16 | 13 |
Comme pour les listes simples, la numérotation commence à 0 : la première ligne est la ligne 0, la première colonne est la colonne 0.
Accéder à une case : le double index
Pour lire une valeur précise, on utilise deux paires de crochets, dans cet ordre : d'abord la ligne, ensuite la colonne. L'expression notes[1] renvoie la ligne complète d'index 1, c'est-à-dire la liste [14, 8, 17]. La notation notes[1][2] va plus loin : elle prend cette ligne, puis y sélectionne l'élément d'index 2.
notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]] print(notes[0]) # la ligne 0 en entier print(notes[1][2]) # ligne 1, colonne 2 print(notes[2][0]) # ligne 2, colonne 0
17
10
Attention au piège classique : l'ordre est ligne puis colonne, alors que dans la vie courante on dit souvent l'inverse ("la troisième place de la deuxième rangée"). Retenez la lecture de gauche à droite : notes[1][2] se lit "dans la grille notes, prends la ligne 1, puis la colonne 2". Et si l'un des deux index n'existe pas, Python provoque la même erreur IndexError que pour les listes simples.
Chaque photo numérique est une liste en deux dimensions. Une image en niveaux de gris est une grille de nombres : chaque case, appelée pixel, contient une valeur entre 0 (noir) et 255 (blanc). Pour une image en couleurs, chaque pixel contient trois nombres (rouge, vert, bleu). Quand vous appliquez un filtre sur une photo, votre téléphone parcourt cette grille et recalcule chaque case, selon le principe que vous allez découvrir au chapitre 2.
En 1978, Dan Bricklin, étudiant à la Harvard Business School, regarde son professeur tracer au tableau un grand quadrillage de lignes et de colonnes rempli de chiffres. À chaque modification d'un nombre, le professeur doit effacer et recalculer toute une partie du tableau à la main. Bricklin imagine alors un programme où la grille se recalculerait toute seule. Avec son ancien camarade Bob Frankston, qui se charge de la programmation, il crée VisiCalc, commercialisé en 1979 sur l'ordinateur Apple II : le premier tableur destiné aux ordinateurs individuels. Vendu à plus de 700 000 exemplaires en six ans, VisiCalc a transformé le micro-ordinateur, jusque-là réservé aux passionnés, en véritable outil de travail. Au cœur de ce logiciel historique : une grille de cases, l'ancêtre direct de vos listes en deux dimensions.
- Une liste peut contenir d'autres listes : c'est une liste en deux dimensions.
- Chaque liste intérieure est une ligne ; la position dans la ligne est la colonne.
grille[1]renvoie la ligne 1 complète (une liste).grille[1][2]renvoie la valeur située ligne 1, colonne 2.- L'ordre des crochets est ligne d'abord, colonne ensuite. La numérotation commence à 0.
Lire une case à la fois, c'est un bon début. Mais la vraie puissance des grilles apparaît quand on les parcourt en entier : calculer un total, chercher une valeur, afficher un plateau. Pour cela, il faut une idée nouvelle : placer une boucle à l'intérieur d'une autre boucle.
Première étape : une boucle simple
Commençons par ce que vous savez déjà faire. Une boucle for sur la grille parcourt ses éléments un par un. Or, chaque élément de la grille est... une ligne entière.
notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]] for ligne in notes: print(ligne)
[14, 8, 17]
[10, 16, 13]
À chaque tour, la variable ligne reçoit une liste complète. C'est déjà utile, mais nous voulons atteindre les valeurs une par une. La solution : puisque ligne est une liste, rien n'empêche de la parcourir avec une deuxième boucle, écrite à l'intérieur de la première.
notes = [[12, 15, 9], [14, 8, 17]] for ligne in notes: for valeur in ligne: print(valeur)
15
9
14
8
17
Suivre l'exécution pas à pas
Pour comprendre l'ordre des opérations, suivons l'exécution dans un tableau. Observez bien : la boucle intérieure fait tous ses tours pendant que la boucle extérieure reste sur la même ligne.
| Étape | Contenu de ligne |
Contenu de valeur |
Affichage |
|---|---|---|---|
| 1 | [12, 15, 9] | 12 | 12 |
| 2 | [12, 15, 9] | 15 | 15 |
| 3 | [12, 15, 9] | 9 | 9 |
| 4 | [14, 8, 17] | 14 | 14 |
| 5 | [14, 8, 17] | 8 | 8 |
| 6 | [14, 8, 17] | 17 | 17 |
Un exemple utile : le total général
Combinons les boucles imbriquées avec le motif de l'accumulateur vu au cours 2 (la variable total qui grandit à chaque tour).
notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]] total = 0 for ligne in notes: for valeur in ligne: total = total + valeur print(f"Total de toutes les notes : {total}")
Mesurer une grille
La fonction len() s'applique aussi aux grilles, à condition de bien comprendre ce qu'elle compte : len(notes) compte les éléments de la grande liste, donc le nombre de lignes. Pour connaître le nombre de colonnes, on mesure une ligne : len(notes[0]) donne la longueur de la ligne 0.
notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]] print(len(notes)) # nombre de lignes print(len(notes[0])) # nombre de colonnes de la ligne 0
3
Nuance importante : Python n'oblige pas les lignes à avoir la même longueur. Une grille peut très bien contenir une ligne de 3 éléments et une ligne de 5 éléments. L'expression len(notes[0]) mesure donc la ligne 0, pas "les colonnes de la grille" en général. Dans ce cours, nous travaillerons avec des grilles régulières, où toutes les lignes ont la même longueur.
Un écran dit "Full HD" affiche une grille de 1080 lignes de 1920 pixels chacune, soit 1920 × 1080 = 2 073 600 pixels (le calcul est exact). Pour produire une seule image, l'ordinateur doit déterminer la couleur de chacune de ces cases. Les boucles imbriquées que vous venez d'apprendre sont, dans leur principe, ce qui se cache derrière chaque image de chaque écran que vous regardez.
Nommez vos variables de boucle d'après ce qu'elles contiennent : for ligne in grille puis for valeur in ligne se lit presque comme une phrase. Vous croiserez souvent, dans les programmes des autres, les noms courts i pour la boucle extérieure et j pour la boucle intérieure : c'est une convention héritée des mathématiques, acceptable pour de simples compteurs, mais des noms explicites rendent vos premiers programmes bien plus faciles à relire.
- Une boucle simple sur une grille parcourt ses lignes, pas ses valeurs.
- Pour atteindre chaque valeur, on imbrique une seconde boucle dans la première.
- La boucle intérieure termine tous ses tours avant que l'extérieure ne change de ligne.
len(grille)compte les lignes ;len(grille[0])mesure la ligne 0.- Les boucles imbriquées se combinent avec l'accumulateur pour calculer sur toute la grille.
Jusqu'ici, nos grilles étaient écrites à la main dans le code. Pour un plateau de morpion de 3 cases sur 3, c'est encore faisable. Pour un plateau de 10 sur 10, ce serait pénible. Et si la taille doit être choisie par le joueur, c'est impossible : il faut que le programme construise la grille lui-même.
Modifier une case
Première brique : le double index ne sert pas qu'à lire, il sert aussi à écrire. On remplace le contenu d'une case en la plaçant à gauche du signe =, tout comme liste[1] = 25 au cours 2.
grille = [[0, 0, 0], [0, 0, 0]] grille[0][2] = 5 grille[1][0] = 8 print(grille)
Construire une grille de taille N
Seconde brique : la construction. Le principe est le même que pour remplir une liste simple avec append(), mais en deux temps. Pour chaque ligne à construire, on part d'une liste vide, on y ajoute les cases une à une, puis on accroche la ligne terminée à la grille. Des boucles imbriquées, encore elles : l'extérieure fabrique les lignes, l'intérieure les remplit.
def creer_plateau(n): plateau = [] for i in range(n): ligne = [] for j in range(n): ligne.append(".") plateau.append(ligne) return plateau print(creer_plateau(3))
Le point "." représente une case vide. Suivons la construction pour n = 3 : à chaque tour de la boucle extérieure, une nouvelle ligne de trois points est fabriquée puis ajoutée.
| Tour de la boucle extérieure | Contenu de plateau à la fin du tour |
|---|---|
| Avant le premier tour | [] |
| Tour 1 (i = 0) | [['.', '.', '.']] |
| Tour 2 (i = 1) | [['.', '.', '.'], ['.', '.', '.']] |
| Tour 3 (i = 2) | [['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']] |
Le projet final : afficher le plateau
Dernière brique : l'affichage. L'instruction print(plateau) montre la grille sur une seule ligne, ce qui est illisible pour jouer. Nous voulons une vraie présentation en carré : une ligne de texte par ligne du plateau. La technique réutilise l'accumulateur du cours 2, appliqué cette fois à une chaîne de caractères : on part d'un texte vide, et on y ajoute chaque case suivie d'un espace.
def creer_plateau(n): plateau = [] for i in range(n): ligne = [] for j in range(n): ligne.append(".") plateau.append(ligne) return plateau def afficher_plateau(plateau): for ligne in plateau: texte = "" for case in ligne: texte = texte + case + " " print(texte) plateau = creer_plateau(3) plateau[0][0] = "X" plateau[1][1] = "O" plateau[2][0] = "X" afficher_plateau(plateau)
. O .
X . .
Voici la récompense de tout ce cours : un vrai plateau de jeu, lisible, construit et affiché par vos propres fonctions. Et le plus beau, c'est la lettre N du titre : pour obtenir un plateau géant, il suffit de changer un seul nombre. Avec creer_plateau(5) et deux coups joués, on obtient ceci.
grand = creer_plateau(5) grand[2][2] = "X" grand[0][4] = "O" afficher_plateau(grand)
. . . . .
. . X . .
. . . . .
. . . . .
Cambridge, 1952. Alexander "Sandy" Douglas prépare une thèse de doctorat sur les interactions entre l'humain et l'ordinateur. Pour illustrer ses idées, il programme un jeu de morpion sur l'EDSAC, l'un des premiers ordinateurs à programme enregistré, une machine qui occupe une pièce entière. Le joueur entre son coup à l'aide d'un cadran de téléphone, et la grille s'affiche sur un minuscule écran cathodique de quelques centaines de points lumineux. Son programme, baptisé Noughts and Crosses (le nom anglais du morpion), joue sans commettre d'erreur. C'est l'un des tout premiers jeux à affichage graphique de l'histoire : la même année, Christopher Strachey faisait fonctionner un jeu de dames, et les historiens ignorent lequel des deux a précédé l'autre. Le nom "OXO", sous lequel ce jeu est célèbre aujourd'hui, n'est apparu que des décennies plus tard : c'est le titre donné par l'historien Martin Campbell-Kelly au fichier de sa reconstitution de l'EDSAC. Au cœur du programme de Douglas : une grille 3×3, l'exact ancêtre de votre plateau.
Le morpion est ce que les mathématiciens appellent un jeu résolu : on a démontré que si les deux joueurs jouent parfaitement, la partie se termine forcément par un match nul. C'est pourquoi le programme de Douglas, en 1952 déjà, ne perdait pas. Les échecs, en revanche, ne sont pas résolus à ce jour : leur grille 8×8 engendre un nombre de parties possibles si gigantesque qu'aucun ordinateur n'a pu toutes les explorer.
- Le double index permet aussi de modifier une case :
grille[0][2] = 5. - On construit une grille avec deux boucles : l'extérieure crée les lignes, l'intérieure les remplit avec
append(). - Une fonction
creer_plateau(n)fabrique un plateau de n'importe quelle taille. - Pour un affichage lisible, on accumule chaque ligne dans une chaîne de caractères avant de l'afficher.
- Tout le projet repose sur des notions des cours 1 et 2 : fonctions,
return,append(), boucles et accumulateur.
Exercices
Soit la grille g = [[3, 7, 1], [9, 4, 6]]. Sans exécuter de code, donnez la valeur de g[0][1], de g[1][2], de g[1][0], de len(g) et de len(g[0]). Vérifiez ensuite vos réponses dans l'éditeur.
g[0][1] vaut 7 (ligne 0, colonne 1). g[1][2] vaut 6. g[1][0] vaut 9. len(g) vaut 2 (deux lignes) et len(g[0]) vaut 3 (la ligne 0 contient trois éléments).
Reprenez la grille notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]], où chaque ligne contient les notes d'un élève. Réutilisez la fonction calculer_moyenne du cours 2 (ou réécrivez-la) pour afficher la moyenne de chaque élève, ligne par ligne.
def calculer_moyenne(liste): total = 0 for note in liste: total = total + note return total / len(liste) notes = [[12, 15, 9], [14, 8, 17], [10, 16, 13]] for ligne in notes: print(f"Moyenne : {calculer_moyenne(ligne)}")
Le programme affiche Moyenne : 12.0, puis Moyenne : 13.0, puis Moyenne : 13.0. Rappel du cours 2 : la division / renvoie un nombre décimal, d'où le .0. Remarquez l'élégance : la fonction du cours 2 travaille sur une liste simple, et chaque ligne de la grille est justement une liste simple.
Écrivez une fonction compter_grille qui prend une grille et une valeur en paramètres, et renvoie le nombre de fois où cette valeur apparaît dans la grille entière. Testez avec la grille [[1, 0, 1], [0, 1, 1], [1, 0, 0]] et la valeur 1.
Indication : combinez les boucles imbriquées du chapitre 2 avec le compteur de la réflexion 4 du cours 2.
def compter_grille(grille, valeur): compteur = 0 for ligne in grille: for element in ligne: if element == valeur: compteur = compteur + 1 return compteur g = [[1, 0, 1], [0, 1, 1], [1, 0, 0]] print(compter_grille(g, 1))
Le programme affiche 5 : la valeur 1 apparaît cinq fois dans la grille. Cette fonction servirait, dans un vrai morpion, à compter les pions de chaque joueur.
La fonction creer_plateau(n) du cours fabrique des grilles carrées. Écrivez une fonction grille_zeros qui prend deux paramètres, nb_lignes et nb_colonnes, et renvoie une grille rectangulaire remplie de zéros. Testez avec grille_zeros(2, 4).
def grille_zeros(nb_lignes, nb_colonnes): grille = [] for i in range(nb_lignes): ligne = [] for j in range(nb_colonnes): ligne.append(0) grille.append(ligne) return grille print(grille_zeros(2, 4))
Le programme affiche [[0, 0, 0, 0], [0, 0, 0, 0]] : deux lignes de quatre colonnes. La boucle extérieure tourne nb_lignes fois, la boucle intérieure nb_colonnes fois.
Exercices de réflexion
Lisez ce programme et prédisez son affichage sans l'exécuter.
m = [[2, 4], [6, 8]] m[0][1] = m[1][0] + m[1][1] print(m[0]) print(m[0][1] + m[0][0])
Soit tableau = [[1, 2, 3], [4, 5, 6]]. Un programmeur veut lire la valeur 6, située ligne 1, colonne 2. Il hésite entre tableau[1][2] et tableau[2][1]. Que renvoie chacune de ces deux expressions ? Expliquez pourquoi l'une des deux ne renvoie rien du tout.
Corrigés des exercices de réflexion
Suivons l'exécution ligne par ligne :
m[1][0] + m[1][1]vaut6 + 8, c'est-à-dire 14. Cette valeur remplace le contenu de la casem[0][1], qui passe de 4 à 14.print(m[0])affiche donc la ligne 0 modifiée :[2, 14].m[0][1] + m[0][0]vaut14 + 2, soit 16.
Affichage : [2, 14], puis 16.
L'expression tableau[1][2] est la bonne : ligne 1 ([4, 5, 6]), colonne 2, soit la valeur 6.
L'expression tableau[2][1], elle, provoque une erreur IndexError: list index out of range avant même d'arriver au second crochet : la grille ne contient que deux lignes, d'index 0 et 1, donc tableau[2] n'existe pas. C'est l'une des erreurs les plus fréquentes avec les listes en deux dimensions : inverser la ligne et la colonne. Moyen mnémotechnique : on lit les crochets de gauche à droite, et on descend d'abord (ligne) avant d'aller vers la droite (colonne).
À retenir
- Une liste en deux dimensions est une liste de listes : chaque liste intérieure est une ligne de la grille.
- Le double index lit et modifie une case :
grille[ligne][colonne]. La ligne vient en premier, et la numérotation commence à 0. - Deux boucles imbriquées parcourent toute la grille : l'extérieure choisit la ligne, l'intérieure parcourt ses valeurs.
len(grille)compte les lignes ;len(grille[0])mesure la longueur de la ligne 0.- On construit une grille de taille variable avec deux boucles et
append(): c'est le cœur de la fonctioncreer_plateau(n).
Lexique
- Boucle imbriquée
- Boucle écrite dans le bloc indenté d'une autre boucle. La boucle intérieure effectue tous ses tours à chaque tour de la boucle extérieure.
- Case
- Emplacement unique d'une grille, repéré par sa ligne et sa colonne :
grille[ligne][colonne]. - Colonne
- Position d'une valeur à l'intérieur de sa ligne. C'est le second index de la notation à double crochet.
- Double index
- Notation à deux paires de crochets pour atteindre une case d'une grille :
grille[1][2]désigne la ligne 1, colonne 2. - Grille
- Nom courant d'une liste en deux dimensions, par analogie avec un quadrillage de lignes et de colonnes.
- Grille N×N
- Grille carrée de N lignes et N colonnes, soit N × N cases.
- Ligne
- Liste intérieure d'une liste en deux dimensions.
grille[1]renvoie la ligne 1 complète. - Liste en deux dimensions
- Liste dont les éléments sont eux-mêmes des listes. Elle représente des données organisées en lignes et en colonnes.
- Pixel
- Case élémentaire d'une image numérique. Une image est une grille de pixels, chacun décrit par un ou plusieurs nombres.
range()- Fonction qui produit une suite de nombres pour une boucle
for.range(n)produit les nombres de 0 à n−1, soit n tours de boucle. - Tableur
- Logiciel organisant les données dans une grille de cases qui se recalculent automatiquement. VisiCalc (1979) en a été le premier représentant sur ordinateur individuel.