X/ENS Informatique B MP-PC-PSI 2019

Thème de l'épreuve Tetris Couleurs
Principaux outils utilisés algorithmique, programmation, listes de listes, complexité, fonctions récursives, bases de données
Mots clefs tetris, alignement sur une grille, comptage sur une grille, jeu sur une grille

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                                  

Rapport du jury

(télécharger le PDF)
                             

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYIECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2019

MERCREDI 24 AVRIL 2019 - 16h30 -- 18h30
FILIERES MP, PC et PSI - Epreuve n° 8

INFORMATIQUE B
(XELCR)

Durée : 2 heures

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation sera obligatoirement Python.

Tetris Couleurs

On souhaite programmer un jeu de puzzle dont le principe ressemble au jeu de 
Tetris : des
blocs de couleur apparaissent à l'écran en haut d'une aire de jeu et descendent 
sous l'effet de la
« gravité » jusqu à reposer sur un bloc déjà présent, ou sur le bas de l'aire 
de jeu. Les nouveaux
blocs de couleur apparaissent par groupe de k blocs superposés en une tour 
verticale appelée
« barreau ».

Lors de la descente, le joueur peut déplacer le barreau selon certaines règles. 
Il peut :

e déplacer le barreau vers la gauche ou vers la droite,
e permuter l'ordre des blocs dans le barreau,

e faire descendre le barreau « rapidement ».

Le but du jeu est de réaliser le plus grand nombre possible d'alignements d'au 
moins trois
blocs de la même couleur. Chaque alignement de trois blocs de la même couleur 
(horizontalement,
verticalement ou en diagonale) donne un point au joueur. Les blocs appartenant 
à des alignements
sont retirés de l'aire de jeu, et les blocs restants sont tassés (ils 
descendent sous l'effet de la
gravité). Les blocs ainsi tassés peuvent à nouveau former des alignements 
unicolores qui sont à
leur tour retirés, et ainsi de suite jusqu à ce qu'il n'y ait plus aucun 
alignement unicolore dans
l'aire de jeu.

La partie se termine quand l'aire de jeu est trop remplie pour accueillir un 
nouveau barreau.
Le score du joueur est alors la somme des points accumulés lors de la partie.

Complexité. La complexité, ou le temps d'exécution, d'un programme P (fonction 
ou procé-
dure) est le nombre d'opérations élémentaires (addition, multiplication, 
affectation, test, etc.)
nécessaires à l'exécution de P. Lorsque cette complexité dépend de deux 
paramètres n et m, on
dira que P a une complexité en O(o(n,m)) lorsqu'il existe trois constantes À, 
no et mo telles
que la complexité de P est inférieure ou égale à À : &(n,m), pour tout n > no 
et m > mo.

Lorsqu'il est demandé de donner la complexité d'un programme, le candidat devra 
justifier
cette dernière si elle ne se déduit pas directement de la lecture du code.

Python. Dans ce sujet, nous adopterons la syntaxe du langage Python. On 
rappelle qu'en
Python, les listes sont des tableaux dynamiques à une dimension. Sur les 
listes, on dispose des
opérations suivantes, qui ont toutes une complexité constante :

e [] crée une liste vide (c'est-à-dire ne contenant aucun élément).
e len(liste) renvoie la longueur de la liste Liste.
e liste.append(x) ajoute l'élément x à la fin de la liste Liste.

e liste[i] renvoie le (i + 1)-ième élément de la liste Liste s'il existe ou 
produit une
erreur sinon (noter que le premier élément de la liste est liste[0]).
L'expression [k for i in range(n)] construit une liste de longueur n contenant 
n occur-
rences de K.

Important : L'utilisation de toute autre fonction sur les listes telle que 
Liste.insert(i,x),
liste.remove(x), liste.index(x), ou encore liste.sort (x) est rigoureusement in-
terdite. Ces fonctions devront être réécrites explicitement si nécessaire.

On rappelle que l'on peut récupérer directement les valeurs contenues dans un 
tuple de la
facon suivante : après l'instruction a,b,c = (1,2,4), la variable à contient la 
valeur 1, b
contient la valeur 2 et c contient la valeur 4. Cette instruction engendre une 
erreur si le nombre
de variables à gauche est différent de la taille du tuple à droite.

Dans la suite, nous distinguerons fonctions et procédures : les fonctions 
renvoient une valeur
(un entier, une liste, un couple, etc.) tandis que les procédures ne renvoient 
aucune valeur.

La partie I contient les principales définitions, les parties IT, III, IV et V 
sont indépendantes.

Nous attacherons la plus grande importance à la lisibilité du code produit par 
les candidats ;
aussi, nous encourageons les candidats à utiliser des commentaires et à 
introduire des procédures
ou des fonctions intermédiaires pour faciliter la compréhension du code.
Partie I. Initialisation et affichage de l'aire de jeu

L'aire de jeu est représentée par une grille de dimensions largeurxhauteur. Dans
l'exemple de la Figure 1(a), la grille est de dimensions 6x 12.

Chaque case de la grille contient une valeur qui représente soit une case vide, 
soit une couleur.
On utilisera les constantes entières suivantes pour représenter l'état des 
cases de la grille (une
constante est une variable globale qui n'est jamais modifiée après création) :

e VIDE pour une case vide;

e KR, V, B, N, J pour les couleurs.

On supposera bien sûr que ces constantes sont deux à deux distinctes et on 
n'utilisera aucune
autre variable globale. La Figure 1(b) montre un exemple d'aire de jeu en cours 
de partie. Ci-
dessous, sa représentation en Python sous la forme d'un tableau de tableaux, ou 
plus précisément
d'un tableau de taille largeur (ici 6) contenant dans chaque case une colonne, 
qui est elle-même
un tableau de taille hauteur (ici 12) :

grille = [[Y, R, R, N, ÿ, R, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE],
[R, R, B, J, VIDE, R, N, ÿ, VIDE, VIDE, VIDE, VIDE],
[T, N, N, R, VIDE, J, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE],
[T, J, VIDE, R, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE],
[N, VIDE, R, VIDE, VIDE, R, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE],
[VIDE, V, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE, VIDE]]

À noter que la valeur de la case supérieure droite de la grille est 
grille[5][11].On veillera
à respecter l'ordre des dimensions afin que la case de coordonnées (4, j) avec 
0 < à < largeur et 0 < j < hauteur (voir Figure 1(a)) corresponde bien à la valeur grille[i][;j] dans sa représentation en Python. Question 1. Ecrire une fonction creerGrille (largeur,hauteur) qui renvoie une grille de dimensions largeur xhauteur dont toutes les cases sont vides. largeur 11 10 9 8 7 a 6 £ 5 5 £ 4 3 2 1 0 0 1 2 3 4 5 (a) Aire de jeu représentée par une grille. (b) Grille en cours de partie. FIGURE 1 -- L'aire de jeu. On souhaite pouvoir afficher à l'écran le contenu de l'aire de jeu. Pour cela, on ) suppose l'existence des procédures suivantes : e afficheCouleur(c) qui prend en argument une constante de couleur c EUR {R,V,B,N,y} et affiche le caractère correspondant ; V e afficheBlanc() qui affiche un espace vide: N . Je / RRIJ R e nouvelleLigne() qui déplace le curseur au début de la ligne suivante. V NIJRR Important : Il est rigoureusement interdit d'utiliser toute autre fonction d'affichage,  RBBN à notamment la commande print. RRNIJ V JRUUN Question 2. Écrire une procédure afficheGrille(grille) qui affiche à l'écran le contenu de l'aire de jeu, encodé dans le tableau grille. On veillera à bien res- pecter l'orientation verticale de la grille : la ligne apparaissant en bas de l'écran doit correspondre aux éléments grillefi] [0] pour 0 < ? < largeur. Par exemple, la grille de la Figure 1(b) sera affichée comme le montre la capture d'écran ci-contre. Partie II. Création et mouvement du barreau Au cours d'une partie, le joueur voit apparaître à l'écran un barreau consistant en une tour de k blocs colorés, où £4 > 3. Le barreau apparaît en pointillé sur les 
figures. La valeur de k
et la couleur des blocs du barreau sont choisies aléatoirement. La position 
d'un barreau est
donnée par les coordonnées (x,y) de son bloc inférieur. Dans la suite, on 
supposera toujours
que les coordonnées (x,y) définissent une case dans la grille (c'est-à-dire 0 < x < largeur et 0 < y < hauteur) et que y + k < hauteur (et donc k < hauteur). Un barreau de taille £ peut naître au sommet d'une colonne ayant ses k cases supérieures vides (voir Figure 2). Si aucune colonne n'a ses k cases supérieures vides, la partie s'arrête. Question 3. Écrire une fonction grilleLibre (grille, k) qui renvoie True si dans au moins une colonne de la grille, les k premières cases (en partant du haut de la grille) sont vides, et renvoie False sinon. On ne fait pas d'hypothèse sur le contenu de la grille (en particulier, la grille n'est pas nécessairement tassée). Quelle est la complexité de votre fonction ? zone de naissance des barreaux de hauteur k : les k lignes supérieures de la grille La position d'un barreau est donnée par les coordonnées (x,y) de son bloc inférieur V N R B J B R R FIGURE 2 -- Zone de naissance des barreaux. En l'absence d'intervention du joueur, le barreau descend d'une case à chaque unité de temps. La descente s'arrête dès que le barreau atteint le bas de la grille, ou rencontre un bloc déjà présent (le passage du temps est illustré à la Figure 3). Question 4. Écrire une procédure descente(grille,x,y,k) qui prend en arguments une grille et les coordonnées (x,y) du bloc inférieur d'un barreau de hauteur k, et modifie la grille en faisant descendre le barreau d'une case. Si le barreau ne peut pas descendre, la grille n'est pas modifiée. to +1 to + 2 to +3 FIGURE 3 -- Descente du barreau. Le joueur peut déplacer le barreau d'une colonne vers la gauche (ou vers la droite) en utilisant les flèches du clavier. Le déplacement du barreau vers la droite n'est possible que si le barreau n'est pas contre le bord droit de la grille et que les £ cases se trouvant à sa droite sont toutes vides. Symétriquement, le déplacement du barreau vers la gauche n'est possible que si le barreau n'est pas contre le bord gauche de la grille et que les £ cases se trouvant à sa gauche sont toutes vides (Figure 4). Question 5. Écrire une procédure deplacerBarreau(grille,x,y,k,direction) qui prend en argument une grille et les coordonnées (x,y) du bloc inférieur d'un barreau de hauteur k, et un entier direction EUR {--1,1},et qui modifie la grille en déplaçant le barreau d'une case vers la gauche (si direction -- --1) ou vers la droite (si direction = 1). Si le déplacement du barreau n'est pas possible, la grille reste inchangée. V N R B J B R R D|DIWmW|GWIT|ZzZz|< D|DIWmW|GWIT|ZzZz|< V N R B J B R R FIGURE 4 -- Déplacements possibles du barreau. Le joueur peut aussi modifier l'ordre des blocs dans le barreau par une permutation circulaire qui fait remonter chaque bloc d'un case, sauf le bloc le plus haut qui redescend à la place du bloc le plus bas (Figure 5). Question 6. Écrire une procédure permuterBarreau(grille,x,y,k) qui modifie la grille en effectuant, comme décrit ci-dessus, une permutation circulaire des couleurs du barreau de hauteur k dont le bloc inférieur est en position (x,y) dans la grille donnée en argument. De. >

après permutation

V V
N N
R R
B B
J J
B B
R R
R R

FIGURE 5 -- Permutation circulaire du barreau.
Enfin, le joueur peut faire descendre le barreau « rapidement », ce qui 
signifie que le barreau
descend du nombre maximum possible de cases (Figure 6), pour venir reposer 
au-dessus de la
première case non vide de la grille située sous le barreau, ou sur le fond de 
la grille (si toutes les
cases sous le barreau sont vides). Dans l'exemple de la Figure 6, la première 
case non vide sous
le barreau à pour coordonnées (3,1).

Question 7. Écrire une procédure descenteRapide(grille,x,y,k) qui prend en 
argument
une grille et les coordonnées (x,y) du bloc inférieur d'un barreau de hauteur 
k, et modifie la grille
en faisant descendre le barreau « rapidement ». On demande que la fonction ait 
une complexité
en O(k +hauteur) (et non O(k x hauteur)).

D.
D

descente rapide

V V
N N
R R
B B
J J
B B
R R
R R

FIGURE 6 -- Descente rapide du barreau.
Partie IIT. Détection des alignements et calcul du score

Lorsqu'un barreau ne peut plus descendre, le joueur gagne des points si des 
alignements d'au
moins trois blocs de la même couleur sont réalisés dans la grille. Les 
alignements peuvent être
réalisés sur une ligne, sur une colonne, ou en diagonale. Notre but est 
maintenant de détecter les
alignements unicolores et de calculer le score du joueur.

Chaque alignement unicolore de longueur m > 3 donne m -- 2 points au joueur. 
Cette règle
ne s'applique que si l'alignement de longueur m n'est pas lui-même inclus dans 
un alignement
de longueur plus grande que m, donc on ne prend en considération que les 
alignements de
longueur maximale pour calculer le score. Par exemple l'alignement horizontal 
de quatre blocs
de couleur B dans la Figure 7 donne 2 points, ceux en diagonale de trois blocs 
de couleur B et
V donnent chacun 1 point. Le bloc B de coordonnées (3,4) compte à la fois pour 
l'alignement
horizontal et l'alignement en diagonale. Le joueur marque donc 4 points dans 
cette configuration.

Tous les blocs appartenant à de tels alignements sont ensuite simultanément 
retirés de la grille
et remplacés par des cases vides (deuxième grille de la Figure 7). Les blocs 
restants sont ensuite
tassés, c'est-à-dire qu'ils descendent du maximum possible de cases. Il se peut 
que de nouveaux
alignements se forment après le tassement de la grille (comme les cinq blocs de 
couleur R dans
la troisième grille de la Figure 7). Ces nouveaux alignements donnent à nouveau 
des points
au joueur (selon le même barème que précédemment) et le même processus 
d'élimination des
alignements et de tassement de la grille est réalisé. Ce processus se poursuit 
jusqu'à ce qu'il
n y ait plus d'alignement unicolore de longueur m > 3 dans la grille. Dans 
l'exemple, le joueur
marque au total 7 points.

V

N

R -- bp -- bb

élimination tassement

© des de la

J alignements grille

B

R

R

FIGURE 7 -- Élimination des alignements unicolores et tassement de la grille.

10
Question 8. Calculer le nombre de points marqués par le joueur s'il laisse 
descendre le barreau
dans l'aire de jeu ci-dessous. Justifier votre réponse.

N
N
R
N
V
R
V
V

Pour réaliser la fonction qui va détecter et comptabiliser les alignements 
unicolores de la grille,
on va d'abord construire une fonction qui réalise cela sur un tableau simple (à 
une dimension).

Question 19. Écrire une fonction detecteAlignement (rangee) qui prend en 
argument
un tableau rangee non vide à une dimension contenant des valeurs dans l'ensemble
{VIDE,R,V,B,N,J}, et qui renvoie un tuple (marking, score) de deux éléments :

e marking est un tableau de la même taille que rangee contenant des Booléens, 
tel que
marking[i] = Truesiet seulement si rangeel[i] appartient à un alignement 
unicolore
de longueur au moins 3.

e score est le nombre de points obtenus par le joueur pour les alignements 
présents dans
rangee (selon le barème donné plus haut).

Par exemple, pour le tableau rangee = [B, R, R, R, R, J, J, J, VIDE, VIDE,
VIDE], la fonction detecteAlignement (rangee) renvoie :

e marking -- {[False, True, True, True, True, True, True, 
True,False,False,Falsel]

e Score --= 3.

On demande que lors du traitement, la fonction detecteAlignement (rangee) 
n'accède
qu'une seule fois à chaque élément du tableau rangee.

Indice : Parcourir le tableau et détecter les changements de couleur.

11
Pour détecter les alignements unicolores de la grille et comptabiliser les 
points marqués, nous
allons explorer toutes les lignes, colonnes et diagonales de la grille. Pendant 
le traitement, on va
conserver une copie de travail de la grille dans laquelle on remplacera les 
cases appartenant à un
alignement unicolore par des cases vides. Dans la question suivante, on suppose 
que g est cette
copie de travail.

Question 10. Écrire une fonction scoreRangee (grille, qg, i, j, dx, dy) 
quiprenden
argument une grille grille et une grille g de même dimensions que grille, les 
coordonnées
(i,j) d'une case dans la grille et une direction (ax,dy) donnée par dx,dy EUR 
{--1,0,1}. La fonc-
tion construit un tableau rangee à une dimension contenant les valeur des cases 
de grille
dont les coordonnées sont (i,j), (i+ax,j+dy), (i+ 2dx,j+ 2dy), etc. puis 
utilise la fonction
detecteAlignement (rangee) de la Question 9 pour détecter les alignements 
unicolores dans
le tableau rangee, déterminer le nombre de points marqués et mettre à jour la 
grille g pour
que les cases appartenant à un alignement unicolore dans grille soient vides 
dans g. La grille
grille ne doit pas être modifiée. La fonction renvoie le nombre de points 
marqués.

Question 11. Écrire une fonction effaceAlignement (grille) qui prend en 
argument une
grille et renvoie un tuple (g, score) de deux éléments :

e g est la grille mise à jour où tous les blocs appartenant à un alignement 
unicolore sont
remplacés par des cases vides.

e score est le nombre total de points obtenus par le joueur pour les 
alignements présents
dans la grille.

La grille grille ne doit pas être modifiée. Donner la complexité de votre 
fonction.

Question 12. Écrire une procédure tassementGrille(grille) qui modifie la grille 
donnée
en argument en effectuant le tassement de ses cases non vides.

Question 13. Écrire une fonction calculScore (grille) qui met à jour la grille 
grille après
élimination des alignements et tassement, répétés jusqu'à ce que la grille ne 
contienne plus aucun
alignement unicolore de longueur m > 3, et qui renvoie le nombre total de 
points marqués par
le joueur pour les alignements éliminés de la grille.

12

(a) Voisins d'une case. (b) Une région unicolore maximale.

FIGURE 8 -- Régions unicolores (Partie IV).

Partie IV. Variante du jeu : régions unicolores

Dans cette partie, on considère une variante du jeu où le but du joueur est de 
former des
régions unicolore au lieu d'alignements (par exemple un carré de 2 x 2 cases de 
la même couleur).

Une région unicolore est un ensemble de cases, toutes de la même couleur, qui 
est connexe
pour la relation d'adjacence suivante : deux cases sont adjacentes si elles 
partagent un côté

(Figure 8(a)).
La région grisée de la Figure 8(b) est une région unicolore maximale : si on y 
ajoute une case

quelconque, elle ne reste plus connexe et unicolore. En particulier, la case 
supérieure droite ne
peut être ajoutée car elle n'est adjacente à aucune case de la région grisée.

Question 14. Écrire une fonction récursive tailleRegionUnicolore(grille,x,y) 
quiren-
voie le nombre de cases appartenant à la plus grande région unicolore de la 
grille contenant la
case (x,y). Justifier la terminaison de votre fonction.

Considérons le code Python aux Figure 9 et Figure 10, dont le but est de 
réaliser le même
travail que la fonction tailleRegionUnicolore de la Question 14 sans utiliser 
la récursivité.

Intuitivement, la fonction exploreRegion(grille, x, y) effectue un balayage de 
la grille,
d'abord verticalement à partir de la case (x,y), puis verticalement à partir de 
chaque voisine
horizontale des cases déjà explorées.

Question 15. Déterminer si la fonction exploreRegion(grille,x,y) renvoie le 
nombre de
cases appartenant à la plus grande région unicolore de la grille contenant la 
case (x,y).

Si oui, justifier soigneusement que la fonction renvoie toujours une valeur 
correcte.

Si non, donner un exemple de paramètres grille, x, y pour lesquels la valeur 
renvoyée par
la fonction est incorrecte (on pourra dessiner la grille).

13

def xDansGrille(grille, x): def exploreVertical(grille, x, y, dir):
largeur = len(grille) hauteur = len(grillef0])
return (x >= 0) and (x < largeur) couleur = grille[x][yl] Vv = y + dir while yDansGrille(grille, v): 1f grillefx][v] != couleur: def yDansGrille(grille, y): return v - dir hauteur = len(grillef0]) V = v + dir return (y >= 0) and (y < hauteur) 1f dir == return hauteur - I else: return 0 def exploreRegion(grille, x, y): inf = exploreVertical(grille, x, y, ---1l) # explore vers le bas sup = exploreVertical (grille, x, y, ll) # explore vers le haut d = exploreHorizontal(grille, x, y, 1) # explore vers la droite g = exploreHorizontal(grille, x, y, --l) # explore vers la gauche score = sup --- inf +1+d+g return score FIGURE 9 -- Code Python pour la Question 15. 14 def exploreHorizontal(grille, x, y, dir): largeur = len(grille) couleur = grilleflx]{yl] inf = exploreVertical(grille, x, y, ---1l) # explore vers le bas sup = exploreVertical(grille, x, y, ll) # explore vers le haut score = 0 u = x + dir while xDansGrille(grille, u) and (inf <= sup): v = inf infNew = I # initialement, infNew > supNew
supNew = 0
while (v <= sup) : 1f grilleflu-dir][v] == couleur and grillefu][v] == couleur: infNew = exploreVertical(grille, u, v, -1) # explore vers le bas supNew = exploreVertical(grille, u, v, I) # explore vers le haut score = score + supNew --- infNew + I v = supNew + 2 while (v <= sup) : 1f grilleflu-dir][v] == couleur and grillefu][v] == couleur: supNew = exploreVertical(grille, u, v, 1) +# explore vers le haut score = score + supNew -- v + 1 v = supNew + I V = Vv + 1 V = V + 1 inf = infNew sup -- supNew u = u + dir return score FIGURE 10 -- Code Python pour la Question 15. 15 Partie V. Gestion des scores en SQL On souhaite utiliser une base de données pour stocker les résultats obtenus par une com- munauté de joueurs. On suppose que l'on dispose d'une base de données comportant les tables JOUEURS(id_)j, nom, pays) et PARTIES(id_p, date, duree, score, id_joueur) où : e id_j;, de type entier, est la clé primaire de la table JOUEURS, e nom est une chaîne de caractères donnant le nom du joueur, e pays est une chaîne de caractères donnant le pays du joueur, e id_p, de type entier, est la clé primaire de la table PARTIES, e date est la date (AAAAMMJO) de la partie, e duree, de type entier, est la durée en secondes de la partie, e score, de type entier, est le nombre de points marqués au cours de la partie, e id joueur est un entier qui identifie le joueur de la partie. Question 16. Etant donné une chaîne de caractères cc contenant le nom d'un joueur, écrire une requête SQL qui renvoie la date, la durée et le score de toutes les parties jouées par le joueur cc, listées par ordre chronologique (au choix, croissant ou décroissant). Question 17. Étant donné un entier s (le score que vient de réaliser une joueuse nommée Alice), écrire une requête SQL qui renvoie la position qu'aura le score s dans le classement des parties par ordre de score (on suppose que la dernière partie d'Alice n'a pas encore été insérée dans la table des parties). En cas d'ex aequo pour le score s (une ou plusieurs parties déjà présentes ayant le score s), le rang sera le même que s'il n'y avait qu'une seule partie avec le score 5. Par exemple, la requête renverra 1 (le score d'Alice est "1®") si aucun score n'est meilleur que s. Autre exemple, si la base de données contient 6 parties dont les scores sont 87,19, 19,63, 60, 60, alors le rang de s = 75 sera 2, le rang de s = 70 sera 4 et le rang de s = 60 sera 5. Question 18. Ecrire une requête SQL qui renvoie le record de France de Tetris couleur, c'est-à-dire le meilleur score réalisé par un joueur dont le pays est la France. Question 19. Étant donné une chaîne de caractères cc contenant le nom d'un joueur (ayant déjà joué au moins une partie de Tetris couleur), écrire une requête SQL qui renvoie le rang du joueur cc, c'est-à-dire sa position dans le classement des joueurs par ordre de leur meilleur score dans une partie de Tetris couleur (on traitera les ex aequo de la même manière qu'à la question 17). 16

Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique B MP-PC-PSI 2019 -- Corrigé
Ce corrigé est proposé par Cyril Ravat (professeur en CPGE) ; il a été relu par
William Aufort (professeur en CPGE) et Benjamin Monmege (enseignant-chercheur
à l'université).

Ce sujet a pour objectif la réalisation de fonctions qui pourraient se trouver à
la base d'un jeu de stratégie, dans lequel un barreau vertical de k cases 
colorées
descend, guidé par le joueur, comme dans le célèbre jeu Tetris. Lorsqu'il 
touche le
sol, les alignements de cases de même couleur sont supprimés et des points sont
marqués. Si l'interface graphique et les actions du joueur ne sont pas 
abordées, le
sujet traite néanmoins un grand nombre de problématiques telles que 
l'initialisation
du jeu, les déplacements, la détection d'alignements, les suppressions et le 
comptage
des points. L'étude est divisée en cinq parties de tailles variées.
· La première partie étudie l'initialisation de la grille et son affichage en 
deux
questions plutôt abordables.
· On traite ensuite l'apparition du barreau et ses différents mouvements : 
descente
case par case ou plus rapide, déplacement latéral, permutation des cases. Les
questions sont d'un niveau intermédiaire et contiennent peu de pièges. Elles 
demandent avant tout une manipulation correcte de la liste de listes qui 
modélise
la grille du jeu.
· La troisième partie, plus longue que les autres, constitue le coeur de 
l'épreuve
et nous fait inspecter une grille où un barreau vient de toucher le sol. Il faut
détecter les alignements de couleurs, les supprimer, faire descendre les cases
qui se trouvent alors suspendues et ainsi de suite. Les fonctions à produire 
sont
plus longues et plus élaborées.
· La quatrième partie n'est constituée que de deux questions, traitant une 
variante bien plus complexe de détection des alignements. Ces questions sont 
plus
difficiles car moins directives. La deuxième en particulier requiert l'analyse 
assez fine d'un code de plus de cinquante lignes, peu envisageable en moins de
dix minutes.
· Enfin, la gestion d'une base de données contenant les scores de plusieurs 
parties
et de plusieurs joueurs est abordée. L'ensemble des quatre questions permet
d'évaluer correctement les candidats sur l'écriture de requêtes SQL.
Ce sujet est progressif et intéressant. Le contexte du jeu de grille est 
séduisant,
même si la référence à Tetris ne fonctionne peut-être pas aussi bien avec les 
élèves
qu'avec leurs professeurs, qui d'ailleurs peuvent être déçus du lien finalement 
quelque
peu éloigné avec le jeu original. Si les questions 14 et 15 ne sont accessibles 
qu'aux
meilleurs candidats dans le temps imparti, les autres construisent un sujet 
bien équilibré et classant, accessible (hors partie 4) dès la première année. 
Les chapitres d'ingénierie numérique ne sont pas abordés.

Indications
Partie I
2 Le parcours de la grille doit se faire par deux boucles for imbriquées, dans 
le bon
sens : la boucle la plus interne permet de décrire une ligne.
Partie II
3 Il faut tester chaque colonne séparément sur les k cases les plus élevées, 
mais il est
inutile de tester obligatoirement toutes les colonnes. Un return dans une boucle
for permet une sortie anticipée.
4 Afin de ne réaliser la modification que si la case sous le barreau existe et 
est vide,
il est possible de placer la boucle de déplacement à l'intérieur d'un test if.
5 Si une des cases de destination n'est pas vide, l'algorithme doit s'arrêter 
sans
réaliser le déplacement. L'instruction return None est alors toute indiquée.
6 Il faut remplacer les cases de haut en bas, en faisant très attention à 
traiter toutes
les cases du barreau et seulement celles-là.
7 On doit commencer par parcourir la grille vers le bas à partir de (x,y) pour
déterminer la distance de déplacement du barreau, et le déplacer alors en une
seule boucle. La procédure deplacerBarreau n'est pas utilisable.
Partie III
9 Il faut, lors de l'unique parcours autorisé de rangee, compter le nombre de 
cases
adjacentes de même couleur. À chaque changement de couleur, on peut remettre
à zéro un compteur après avoir modifié marking sur le bon nombre de cases.
Attention à ne pas oublier l'éventuel dernier alignement.
10 Utiliser la fonction detecteAlignement en construisant la bonne rangée avant.
11 Il faut appliquer consécutivement la fonction scoreRangee sur toutes les 
rangées
pouvant exister dans la grille. Il est donc important de les prévoir 
correctement,
en s'aidant de schémas. Attention à ne pas traiter deux fois la même rangée.
12 Plusieurs techniques sont possibles. On peut par exemple parcourir chaque 
colonne de bas en haut en gardant dans une variable supplémentaire la position 
de
la case de destination des déplacements.
Partie IV
14 Pour que la fonction puisse s'exécuter récursivement sans revenir sans cesse 
sur
les mêmes cases, il faut modifier grille en effaçant les cases déjà parcourues. 
Les
codes donnés dans l'énoncé aux figures 9 et 10 ne font pas partie de cette 
question.
15 La principale difficulté est dans la fonction exploreHorizontal. Il faut 
essayer de
comprendre son fonctionnement global et d'en déduire quel genre de disposition
de cases pourrait conduire à en oublier.
Partie V
17 Il faut compter le nombre de scores meilleurs que s.
18 Il s'agit ici d'obtenir la valeur maximale d'un champ.
19 Sélectionner les joueurs ayant un meilleur score que le joueur concerné 
nécessite
l'insertion d'une sous-requête dans la clause WHERE et une agrégation de 
résultats.
Le comptage des joueurs doit s'effectuer dans un deuxième temps, à l'aide d'une
deuxième agrégation.

I. Initialisation et affichage de l'aire de jeu
1 La fonction creerGrille doit créer une par une chaque case de la grille et les
assembler dans les deux directions.
def creerGrille(largeur,hauteur):
grille = []
for i in range(largeur):
colonne = []
for j in range(hauteur):
colonne.append(VIDE)
grille.append(colonne)
return grille
D'après l'énoncé, VIDE est une variable globale, déjà définie. Il ne faut
donc pas l'entourer de guillemets, ni réaliser d'affectation de cette variable.
Attention à ne pas recopier largeur fois la même colonne. En effet, les
colonnes étant des listes, créer une unique colonne et la copier plusieurs fois
conduirait à créer des colonnes aux valeurs toujours identiques. Par exemple,
colonne = [0,0,0]
grille = []
for i in range(4):
grille.append(colonne)
grille[2,1] = 1
construit une grille égale à [[0,1,0],[0,1,0],[0,1,0],[0,1,0]].
Créer chaque colonne en une ligne à l'aide de la syntaxe liste*entier
permet de réaliser un code correct plus compact :
def creerGrille(largeur,hauteur):
grille = []
for i in range(largeur):
grille.append([VIDE]*hauteur)
return grille
L'énoncé rappelle en préambule comment définir en compréhension une
liste contenant n occurrences d'une valeur k. Ce type de syntaxe permet en
effet d'écrire un code bien plus compact avec
def creerGrille(l,h):
return [ [ VIDE for j in range(h) ] for i in range(l) ]
2 La procédure afficheGrille doit lire chaque ligne en partant de la plus « 
haute »,
c'est-à-dire la fin de chaque colonne.
def afficherGrille(grille):
largeur = len(grille)
hauteur = len(grille[0])
for j in range(hauteur-1,-1,-1):
for i in range(largeur):
if grille[i][j] == VIDE:
afficheBlanc()
else:
afficheCouleur(grille[i][j])
nouvelleLigne()

La procédure nouvelleLigne peut aussi être positionnée en début de première 
boucle. Les indications de l'énoncé sont insuffisantes pour choisir la
meilleure position, mais celle adoptée ici correspond à une écriture classique 
des procédures afficheBlanc, afficheCouleur et nouvelleLigne de
la forme
def afficheBlanc():
print(' ',end='')
def nouvelleLigne():
print()
où nouvelleLigne crée ainsi un retour à la ligne, inutile en début d'affichage
mais nécessaire à la fin.

II. Création et mouvement du barreau
3 La fonction grilleLibre permet de déterminer si k cases verticalement 
adjacentes
sont vides en haut de grille. Dès que l'on obtient un tel alignement, il est 
donc possible
d'arrêter la recherche.
def grilleLibre(grille,k):
largeur = len(grille)
hauteur = len(grille[0])
for i in range(largeur):
# Marqueur indiquant si la colonne a assez de cases libres
placelibre = True
# Si une case est prise, on change le marqueur
for j in range(hauteur-k, hauteur):
if grille[i][j] != VIDE:
placelibre = False
# Si on a trouvé une colonne disponible, on s'arrête
if placelibre:
return True
# Si on arrive ici, il n'y a aucune colonne disponible
return False
Dans le pire des cas, on inspecte les k plus hautes cases de chaque colonne de 
la
grille. L'inspection d'une case, contenue dans la deuxième boucle, est de 
complexité
constante. La complexité totale est donc
O(k × largeur)
L'hypothèse de non-tassement de la grille semble étonnante, la grille étant
naturellement toujours tassée lorsqu'un barreau apparaît. On peut imaginer 
qu'il s'agit simplement de s'assurer que la seule réponse correcte soit de
complexité O(k × largeur).