X/ENS Informatique B MP-PC-PSI 2025

ECOLE POLYTECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2025

JEUDI 17 AVRIL 2025
16h30 - 18h30
FILIERES MP-PC-PSI
Epreuve n° 8

INFORMATIQUE B (XELSR)

Durée : 2 heures
L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve

Le jeu de Rockse
On dispose sur les cases d'une grille N  N des penalites et des gains comptes 
comme
des penalites negatives. Le jeu de Rockse debute a la case (0, 0) et cherche un 
chemin vers la
case (N  1, N  1) qui minimise les penalites. A chaque etape du chemin, un 
nombre fini
de deplacements (sauts) est autorise. Des cases bonus ajoutent, une fois 
atteintes, des sauts
possibles pour la suite du chemin. La figure ci-dessous donne un exemple de 
grille et deux
chemins possibles, en supposant que les sauts autorises sur la grille sont (i, 
j)  (i, j + 1) (),
(i, j)  (i + 1, j  1) () et (i, j)  (i + 1, j + 1) (). On suppose par ailleurs 
une case bonus
en (1, 2) (grisee) qui, une fois atteinte, ajoute aux sauts autorises (i, j)  
(i + 1, j) () :

0
0

1

2

3

DEPART

2

4

6

1

1

2

2

2

2

2

3

3

1

4

3

()

0

0

0

3

1

4

2

7

3

ARRIVEE

(a) Grille de jeu

1

2

3

DEPART

2  4  6
0

()
2
1
2
3

2
3
2
4

1
3
4
7

ARRIVEE

0
0
1
2
3

(b) Chemin non-optimal
poids : 6

1

2

3

DEPART

2  4  6
0

()
2  2
1
3

2
3
2
4

1
3  7
4

ARRIVEE

(c) Chemin optimal
poids : 7

Considerons le chemin decrit en (c). On part de la case de depart (0, 0) et, en 
appliquant les
sauts successifs , , , , on arrive sur la case bonus. A partir de cette case, 
le saut  est
desormais autorise. On applique ensuite les sauts , ,  pour atteindre la case 
d'arrivee (3, 3).
Le chemin obtenu est decrit par la liste des cases :
chemin = [(0 ,0) ,(0 ,1) ,(0 ,2) ,(1 ,1) ,(1 ,2) ,(2 ,2) ,(3 ,2) ,(3 ,3)]

Son poids est la somme des penalites contenues dans ces cases, soit 7. On peut 
montrer que
c'est un chemin de poids minimal -- on dit qu'il est optimal. Le chemin decrit 
en (b) est correct,
mais son poids est de 6. Il n'est donc pas optimal.
Representation des donnees. La grille de jeu N  N est representee par une liste 
de listes
d'entiers T telle que T[i][j] est la penalite a la case (i, j). On suppose que 
cette representation
est bien formee, c'est-a-dire que toutes les listes ont la meme taille N . Sur 
notre exemple :
T = [[2 , -4 , -6 ,0] ,[1 , -2 ,2 ,3] ,[ -2 ,2 , -3 ,4] ,[ -1 ,4 , -3 ,7]]

Un saut (i, j)  (i + i, j + j) est represente par le couple d'entiers (i, j). 
L'ensemble des
sauts possibles est ainsi une liste de couples. Sur notre exemple, l'ensemble 
des sauts possibles
par defaut (avant d'avoir atteint une case bonus) est :
sauts = [(0 ,1) ,(1 , -1) ,(1 ,1)]

Les sauts actives par les cases bonus sont enregistres dans un dictionnaire 
bonus tel que
bonus[(i,j)] est la liste des sauts actives par la case bonus (i,j). Sur notre 
exemple :
bonus = { (1 ,2): [(1 ,0)] }

1

Complexite. La complexite d'une fonction F est le nombre d'operations 
elementaires (addition, multiplication, a!ectation, test, etc.) necessaires a 
l'execution de F . Lorsque cette complexite depend de plusieurs parametres n et 
m, on dira que F a une complexite en O((n, m))
lorsqu'il existe trois constantes A, n0 et m0 telles que la complexite de F est 
inferieure ou egale
a A · (n, m), pour tout n  n0 et m  m0 . Lorsqu'il est demande de donner la 
complexite d'un
programme, le candidat devra justifier sa reponse en utilisant le code du 
programme.
Rappels sur Python. L'utilisation de toute fonction Python sur les listes ou 
sur les dictionnaires autre que celles mentionnees dans ce paragraphe est 
interdite. Sur les listes, on autorise
les operations suivantes, dont la complexite est en O(1) :
-- len(l) renvoie la longueur de la liste l.
-- l[i] designe l'element d'indice i de la liste l, pour 0  i < len(l). -- l.append(e) ajoute en place l'element e a la fin de la liste l. Les operations suivantes sont egalement autorisees et leur complexite est en O(n) : -- l1 + l2 renvoie une nouvelle liste (de longueur n) qui est la concatenation des listes l1 et l2. -- range(n) renvoie la liste [0,1, ..., n-1]. -- range(n-1,-1,-1) renvoie la liste [n-1, ..., 0]. -- l.pop(0) retire le premier element e de la liste l (de longueur n) et renvoie e. -- (e in l) renvoie True si l'element e est dans la liste l (de longueur n), et False sinon. -- l[:] renvoie une copie de la liste l (de longueur n). On autorise egalement les constructions suivantes : -- La construction for e in l parcourt (itere sur) les elements de la liste l du premier element (d'indice 0), au dernier element (d'indice len(l)-1) avec la complexite O(len(l)). -- La construction [f(e) for e in l] produit la meme liste que le code suivant, et avec la complexite len(l) fois la complexite de f : result = [] for e in l : result . append ( f ( e )) return result Sur les dictionnaires, on autorise uniquement les operations suivantes, dont la complexite est en O(1) : -- Le test (e in d) renvoie True si e est une cle du dictionnaire d, et False sinon. -- L'acces d[e] a l'element associe a la cle e dans le dictionnaire d. On autorise egalement les constructions suivantes sur les dictionnaires : -- La construction for (k,v) in d parcourt les elements du dictionnaire d. -- La construction d[k] = v a!ecte la valeur v a la cle k. Enfin, on supposera donnee une variable globale INFINI qui contient un entier superieur ou egal a tout entier utilise dans les programmes de ce sujet. Organisation. Les parties peuvent etre traitees independamment. La partie I porte sur les fonctions de base sur les chemins et les sauts. Ensuite, la partie II propose de trouver un chemin optimal avec une recherche exhaustive. La partie III utilise les resultats de la partie II pour construire une methode de recherche gloutonne. Enfin, la partie IV etudie une resolution du probleme par programmation dynamique. On rappelle que le code doit etre commente. 2 Partie I : Sauts et chemins Question 1 Ecrire une fonction poids(T,chemin) qui, etant donne un plateau de jeu T et un chemin chemin, renvoie le poids de ce chemin. Donner la complexite de cette fonction. Question 2 Ecrire une fonction appliquer sauts(i,j,sauts) qui, etant donne une case (i, j) et une liste de sauts sauts, applique les sauts dans l'ordre donne par la liste sauts, en partant de la case (i, j) et renvoie la case atteinte. On suppose que le chemin indique par sauts reste dans la grille. Question 3 Ecrire une fonction sauts corrects(sauts,bonus,chemin) qui, etant donne l'ensemble des sauts par defaut represente par la liste sauts, les sauts associes aux cases bonus bonus et un chemin chemin, renvoie True si les sauts utilises dans le chemin sont corrects et False sinon. On suppose que le chemin reste dans la grille. On dit qu'un ensemble de sauts C est bien forme s'il ne peut pas mener a un cycle. Autrement dit, s'il n'existe pas de suite de sauts construite a partir des sauts de C qui, en partant de la case (0, 0) permettrait d'arriver sur une case (i, j) puis de revenir a cette case. Une condition su!sante est que chaque saut (i, j) de l'ensemble de sauts C soit strictement positif lexicographiquement, condition notee (i, j)  0 et definie par : i > 0 ou bien (i = 0 et j > 0)

(*)

Une suite de sauts  est positive lexicographiquement, propriete notee   0, si 
chaque saut
(i, j) de  satisfait (*).
Question 4 Ecrire une fonction sauts bien formes(sauts,bonus) qui, etant donne 
la liste
des sauts par defaut sauts et les sauts associes aux cases bonus bonus, verifie 
que chaque saut
de ces listes satisfait la condition (*). La fonction renvoie True si c'est le 
cas et False sinon.
Dans le reste du sujet, on suppose que les sauts utilises satisfont la 
condition (*).

Partie II : Recherche exhaustive
On cherche maintenant a calculer un chemin optimal. Une premiere solution est 
de tester
tous les chemins corrects et de retenir le chemin de poids minimum. 
L'enumeration de tous les
chemins corrects se fera avec la fonction auxiliaire recursive suivante :
trouve_complet_rec(T,sauts,bonus,sauts_max,i,j)
Etant donnes une grille de jeu T, les sauts par defaut sauts, les sauts 
associes aux cases
bonus bonus, une valeur entiere sauts max et une case (i, j), la fonction 
ci-dessus calcule un
chemin p de poids minimum partant de (i, j) et n'arrivant pas forcement a (N  
1, N  1),
mais ayant au plus sauts max+1 cases. La fonction renvoie le couple (poids 
min,sauts min)
ou poids min est le poids de p et sauts min est la liste des sauts pour 
construire p.
La valeur sauts max est utilisee pour limiter la complexite de la recherche. 
Ainsi, la longueur
du resultat sauts min sera inferieure ou egale a sauts max. Cette limite est 
appelee horizon. Si
l'horizon est assez grand, la fonction renvoie un chemin optimal partant de (i, 
j).
Question 5 Quelle est la longueur maximale L d'un chemin de (0, 0) a (N  1, N  
1) pour
n'importe quel ensemble de sauts satisfaisant (*) ? Donner un exemple 
d'ensemble de sauts par
defaut pour lequel se realise ce chemin de longueur L.
3

Question 6 Ecrire la fonction auxiliaire trouve complet rec(T,sauts,bonus,sauts 
max,i,j)
et la fonction principale trouve complet(T,sauts,bonus,sauts max) qui renvoie 
le couple
(poids,sauts) ou poids est le poids du chemin trouve et sauts est la liste des 
sauts du chemin
trouve. Quelle est la complexite de cette fonction ?
Question 7 La fonction trouve complet rec perd beaucoup de temps a refaire les 
memes calculs. On peut l'ameliorer en enregistrant les resultats deja calcules 
pour une valeur fixee de
sauts max. Expliquer en quelques lignes comment proceder. Quelle serait alors 
la complexite ?
La recherche exhaustive d'un chemin optimal est obtenue en appelant trouve 
complet(T,
sauts, bonus, L) avec L la longueur maximale d'un chemin dans T.

Partie III : Recherche gloutonne
On peut reduire la complexite de la recherche exhaustive en limitant, a chaque 
etape, l'horizon de la recherche, c'est-a-dire le nombre de sauts regardes a 
partir de la case courante. D'ou
l'idee de construire un algorithme glouton pour trouver une solution. En 
partant de la case (0, 0),
on utilise la recherche exhaustive avec un  petit horizon  k pour determiner la 
meilleure suite
locale de k sauts, c'est-a-dire la suite de poids minimal et d'au plus k sauts. 
On joue les sauts
de la meilleure suite locale, puis on recommence sur la case atteinte, jusqu'a 
la case d'arrivee
(N  1, N  1). Si la recherche exhaustive avec l'horizon k ne trouve pas une 
suite locale, alors
l'algorithme abandonne la recherche.
Question 8 Sur l'exemple donne en introduction, quel est le chemin trouve pour 
k = 2 ? Est-il
optimal ? Memes questions pour k = 3. En augmentant k, obtient-on forcement un 
chemin de
poids plus petit ?
Question 9 Ecrire une fonction trouve glouton(T,sauts,bonus,k) qui, etant 
donnes la
grille de jeu T, la liste des sauts par defaut sauts, les sauts associes aux 
cases bonus bonus
et l'horizon k, e"ectue cette recherche gloutonne et renvoie le couple 
(poids,sauts) ou poids
est le poids du chemin trouve et sauts est la liste des sauts du chemin trouve. 
Quand la recherche
exhaustive avec l'horizon k ne trouve pas de suite locale, la fonction renvoie 
(INFINI,[]).

Partie IV : Recherche par programmation dynamique
On se propose maintenant de construire une methode par programmation dynamique 
pour
trouver un chemin optimal. Comme la solution optimale en partant de (i, j) 
depend des cases
bonus deja rencontrees (dites activees), on va remplir un tableau poids 
opt[i][j][code bonus]
qui contient le poids du chemin optimal en partant de la case (i,j) et ou la 3e 
dimension
(code bonus) encode l'ensemble des cases bonus activees. En parallele, on 
remplira un tableau
saut opt[i][j][code bonus] qui contient un saut optimal a jouer en partant de 
la case (i,j).
Ce tableau permettra de retrouver un chemin optimal.

1) Encodage des cases bonus activees
Soit n le nombre de cases bonus. On numerote les cases bonus de 0 a n  1. On 
represente les
cases bonus activees par une liste de booleens (masque binaire) [b0 , . . . , 
bn1 ] ou bk vaut True si
et seulement si la case bonus k est activee. L'ensemble des cases bonus 
activees est encode par
^ = 1 et False
^ = 0. Ce code est note
l'entier dont la representation binaire est bn1 . . . b0 , ou True
b0 . . . bn1 . Par exemple, le code associe au masque [False, False] est 0, le 
code associe au
masque [True, False] est 1, etc.
4

Question 10 Ecrire la fonction code bonus(masque bonus) qui renvoie le code 
associe au
masque binaire masque bonus representant l'ensemble des cases bonus activees.

2) Recurrence
On
va
maintenant
donner
une
recurrence
pour
calculer
les
valeurs
poids opt[i][j][code bonus] pour tout case (i, j) et valeur de code bonus. 
Cette recurrence
sera utilisee dans la section suivante pour construire un algorithme.
Pour simplifier l'explication, ignorons les cases bonus dans un premier temps. 
Si un chemin
partant de la case (i, j) a un poids minimal, alors le chemin obtenu en lui 
retirant (i, j) (en
partant de la case suivante) a lui-meme un poids minimal. Une fois poids opt 
calcule pour tous
les successeurs possibles de la case (i, j), il su"t de garder le plus petit et 
de lui ajouter le poids
de la case T[i][j]. On obtient ainsi poids opt pour la case (i, j).
Avec les cases bonus, c'est le meme principe sauf qu'il faut gerer les sauts 
supplementaires
des cases bonus activees. Deux cas sont possibles :
-- (i, j) n'est pas une case bonus. Dans ce cas, il su"t de calculer
poids opt[i s][j s][code bonus] pour tous les successeurs possibles (i s,j s)
de la case (i, j) avec les sauts par defaut et les sauts associes a chaque case 
bonus
activee de code bonus. Le poids opt[i][j][code bonus] est alors le minimum de 
ces
poids opt[i s][j s][code bonus] auquel s'ajoute la penalite T[i][j] de la case 
(i, j).
-- (i, j) est une case bonus. Dans ce cas, c'est le meme processus, sauf que : 
1) parmi les
sauts possibles, on ajoute ceux actives par la case bonus et 2) on considere 
les successeurs
(i s,j s) avec un nouveau code bonus code bonus' dans lequel la case bonus (i, 
j) est
activee : le minimum doit ainsi etre calcule parmi les poids opt[i s][j s][code 
bonus'].
Si code bonus = b0 . . . bn1 , en notant k le numero de la case bonus (i, j), 
on changera
bk a True pour obtenir code bonus' = b0 . . . bk . . . bn1 , ou bk = True.
Question 11 Ecrire la definition de poids opt[i][j][b0 . . . bn1 ]. On notera # 
l'ensemble
des sauts par defaut et $k l'ensemble des sauts associe a la k-ieme case bonus.

3) Algorithme
On evalue iterativement les di!erentes cases poids opt[i][j][code bonus] de 
poids opt
a l'aide de trois boucles imbriquees iterant respectivement sur i, j et le 
masque de bonus (d'ou
on tirera code bonus). La di"culte est de trouver un ordre d'evaluation 
correct. A partir de la
recurrence, on voit que poids opt[i][j][b0 . . . bn1 ] doit etre evalue apres 
avoir obtenu les
poids des successeurs : poids opt[i+i][j+j][b0 . . . bn1 ].
-- Comme (i, j)  0 (condition (*)), alors i + i > i ou bien i = 0 et j + j > j, 
donc les
iterations sur i et j doivent etre  a l'envers , de N  1 a 0.

-- Soit [b0 , . . . , bn1 ] est egal a [b0 , . . . , bn1 ], soit [b0 , . . . , 
bn1 ] est obtenu a partir de
[b0 , . . . , bn1 ] en mettant un bk a True. En d'autres termes, le choix de 
bonus represente par
[b0 , . . . , bn1 ] est inclus dans le choix de bonus represente par [b0 , . . 
. , bn1 ]. La boucle sur
les masques de bonus doit donc iterer par choix de bonus decroissant au sens de 
l'inclusion.
Avec 3 cases bonus, un ordre est le suivant :
[True,True,True], puis
[False,True,True], [True,False,True], [True,True,False], puis
[False,False,True], [False,True,False], [True,False,False], puis
[False,False,False]
5

Noter que les choix rassembles sur une ligne ne sont pas classables entre eux. 
Par contre, les
choix d'une ligne sont strictement superieurs au sens de l'inclusion a l'un des 
choix de la ligne
suivante.
Un algorithme pour calculer l'ordre d'evaluation des masques de bonus peut 
proceder comme
suit. On commence par le choix total, dans notre exemple [True,True,True]. On 
construit la
ligne suivante en inserant les choix obtenus en basculant une coordonnee True a 
False. Par
exemple, on insere [False,True,True], [True,False,True], [True,True,False]. On 
itere
ensuite sur chaque choix obtenu pour construire la ligne d'apres. On s'arrete 
lorsqu'on atteint le
choix vide, dans notre exemple [False,False,False]. On pourra utiliser une file 
pour defiler
les choix de bonus a traiter et enfiler progressivement les choix de bonus de 
la ligne suivante.
Question 12 Ecrire une fonction combinaisons bonus(nb bonus) qui, etant donne 
le nombre
total de cases bonus nb bonus, renvoie la liste de masques bonus ordonnee de 
maniere
decroissante dans le sens de l'inclusion, en codant l'algorithme ci-dessus.
On suppose qu'il existe une fonction ranger bonus(bonus) qui renvoie un couple
(bonus au rang,rang du bonus) tel que :
-- bonus au rang[k] est la liste des sauts actives par la case bonus dont le 
numero est k,
-- rang du bonus[(i,j)] est le numero de la case bonus (i, j) dans un masque de 
bonus.
Le resultat de cette fonction est utilise comme parametre pour la question 
suivante et pour la
fonction ajouter bonus decrite apres.
Question 13 Ecrire une fonction
trouver_sauts_possibles(sauts,bonus_au_rang,masque_bonus)
qui, etant donnes les sauts par defaut sauts, la liste bonus au rang renvoyee 
par
ranger bonus(bonus) et le masque des bonus actives masque bonus, renvoie 
l'ensemble des
sauts possibles.
On suppose donnee une fonction
ajouter_bonus(bonus,rang_du_bonus,i,j,bonus_actifs,code_bonus_actifs)
qui active la case bonus (i, j) dans le code des cases bonus activees code 
bonus actifs.
Si (i, j) n'est pas une case bonus, la fonction renvoie code bonus actifs. 
L'argument
rang du bonus est la structure renvoyee par ranger bonus(bonus) et l'argument 
bonus actifs
est le masque des bonus actifs dont le code est code bonus actifs.
Question 14 Le code Python incomplet de la page suivante implemente la fonction
trouve_dynamique(T,sauts,bonus) qui, etant donnes une grille de jeu T, la liste 
des sauts
par defaut sauts et les sauts associes aux cases bonus bonus, calcule le chemin 
optimal par
programmation dynamique en utilisant la recurrence trouvee en question 11. Le 
resultat de la
fonction est le couple (poids opt,sauts opt) ou poids opt est le poids du 
chemin optimal
trouve et sauts opt est la liste des sauts de ce chemin.
1. Donner les sept parties manquantes indiquees par  ...  dans le code.
2. Quelle est la complexite de cette fonction ?

6

def trouve_dynamique (T , sauts , bonus ):
N = len ( T )
nb_bonus = len ( bonus )
nb_code_bonus = ...
# A COMPLETER ( 1 )
poids_opt = [[[ INFINI for bonus_code in range ( nb_code_bonus )]
for j in range ( N )] for i in range ( N )]
saut_opt = [[[(0 ,0 ,0) for bonus_code in range ( nb_code_bonus )]
for j in range ( N )] for i in range ( N )]
( bonus_au_rang , rang_du_bonus ) = ranger_bonus ( bonus )
for bonus_actifs in combinaiso ns _b on us ( nb_bonus ):
code_bonus_actifs = code_bonus ( bonus_actifs )
poids_opt [N -1][ N -1][ code_bonus _actif s ] = ...
# A COMPLETER ( 2 )
sauts_possibles = ...
# A COMPLETER ( 3 )
for i in range (...):
# A COMPLETER ( 4 )
for j in range (...):
# A COMPLETER ( 5 )
code_bonus_dest = ajouter_bonus ( bonus , rang_du_bonus ,i ,j ,
bonus_actifs , co de_bon us_ac tifs )
if (i , j ) in bonus :
s a u t s _ p o s s i b l e s _ f i n a l = sauts_possibles + bonus [( i , j )]
else :
s a u t s _ p o s s i b l e s _ f i n a l = sauts_possibles
for ( delta_i , delta_j ) in s a u t s _ p o s s i b l e s _ f i n a l :
i_dest = i + delta_i
j_dest = j + delta_j
if ( i_dest in range ( N ) and j_dest in range ( N )):
poids_opt_dest = poids_opt [ i_dest ][ j_dest ][ code_bonus_dest ]
if ( poids_opt [ i ][ j ][ code_bonus_actifs ] > poids_opt_dest ):
poids_opt [ i ][ j ][ code_bonus_actifs ] = ... # A COMPLETER ( 6 )
saut_opt [ i ][ j ][ cod e_bonu s_acti fs ] = ... # A COMPLETER ( 7 )
poids_opt [ i ][ j ][ code_bonus _actif s ] += T [ i ][ j ]
return ( poids_opt , saut_opt )

Question 15 Ecrire la fonction solution dynamique(saut opt,N) qui, etant donnes 
la structure saut opt calculee dans la question precedente et la dimension N de 
la grille, renvoie le
chemin optimal correspondant. La fonction renvoie le chemin vide [] s'il 
n'existe pas de chemin
entre la case de depart et celle d'arrivee.
­

F

I

7

N

­