Agrégation informatique externe 2025, épreuve 2Sujet et rapport du jury

AGREGATION CONCOURS EXTERNE

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Mastermind

Préliminaires

• -List.map : ('a -> 'b) -> 'a list -> 'b list List.map f [x1; ...; xn] renvoie [f x1; ...; f xn];
• -List.iter : ('a -> unit) -> 'a list -> unit List.iter f [x1; ...; xn] équivaut à f x1; ...; f xn; ();
• -List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a List.fold_left f init [x1; ...; xn] renvoie f (... (f (f init x1) x2) ...);
• -List.filter : ('a -> bool) -> 'a list -> 'a list List.filter pred u renvoie la liste constituée des éléments x de u tels que pred x = true, dans l'ordre de la liste u.

• -('a, 'b) Hashtbl.t est le type d'une table de hachage dont les clés sont de type 'a et les valeurs de type 'b;
• -Hashtbl.create : int -> ('a, 'b) Hashtbl.t
  Hashtbl.create 1 renvoie une table de hachage vide (l'argument entier est une indication sur la taille initiale du tableau sous-jacent et pourra systématiquement être pris égal à 1);
• -Hahstbl.find_opt : ('a, 'b) Hashtbl.t -> 'a -> 'b option
  Hahstbl.find_opt h x renvoie Some y si y est la valeur associée à la clé x dans h, ou None si la clé x n'est pas présente dans h ;
• -Hashtbl.replace : ('a, 'b) Hashtbl.t -> 'a -> 'b -> unit
  Hashtbl.replace h x y associe la clé x à la valeur y dans la table h, en remplaçant l'ancienne association pour x s'il y en avait une (et en créant l'association dans le cas contraire);
• -Hashtbl.iter : ('a -> 'b -> unit) -> ('a, 'b) Hashtbl.t -> unit
  Hashtbl.iter f h équivaut à f x1 y1; ... ; f xn yn; (), où (x_1, y_1), …, (x_n, y_n) sont les associations présentes dans la table h , dans un ordre non spécifié.

Présentation informelle du jeu

• - J_1 propose une combinaison c : par exemple, c = (V, B, V, R, B);
• -l'arbitre répond à J_1 en indiquant le nombre de jetons bien placés et mal placés dans sa combinaison ;
• -ici, il y a un V bien placé :

• -pour déterminer le nombre de jetons mal placés, on commence par éliminer les jetons bien placés puis l'on oublie l'ordre - ici, il y a deux jetons mal placés (un R et un B);

• -si l'arbitre répond que tous les jetons sont bien placés (réponse (N, 0) ), la partie s'arrête ;
• -sinon, J_1 fait une nouvelle proposition et l'on continue.

Formalisation

• -On se donne deux entiers strictement positifs N et P - dans la version standard du jeu, on a N = 4 et P = 6.
• -On appelle combinaison un N-uplet d'éléments de {0, …, P − 1}. Attention, il s'agit bien d'un N-uplet et non d'une combinaison au sens usuel en mathématiques : l'ordre compte et les répétitions sont autorisées.
• -On notera C (ou C(N, P) s'il y a risque d'ambiguïté) l'ensemble de ces combinaisons : C = {0, …, P − 1}^N. On a donc |C| = P^N.
• -On appellera couleurs les éléments de {0, …, P − 1} et jetons les éléments du N-uplet.
• -Étant données deux combinaisons x = (x_0, …, x_(N − 1)) et y = (y_0, …, y_(N − 1)), la similarité sim(x, y) entre x et y est le couple d'entiers (b, m) où :
  • - b est le nombre de jetons bien placés de y (par rapport à x ), c'est-à-dire le nombre d'indices i ∈ {0, …, N − 1} tels que x_i = y_i;
  • - m est le nombre de jetons mal placés de y (par rapport à x ). Ce nombre est tel que b + m soit égal au nombre de jetons en commun entre x et y si l'on ne tient pas compte de l'ordre.

• -Quelques exemples :
  • - sim((2, 3, 0, 2, 3), (3, 3, 3, 1, 2)) = (1, 2) - en effet, il y a au total trois éléments communs (un « 2 » et deux « 3 »), dont l'un est bien placé (le « 3 » à l'indice 1, c'est-à-dire en deuxième position);
  • - sim((1, 2, 3), (2, 2, 2)) = (1, 0) (un seul élément commun, le « 2 » à l'indice 1 qui est bien placé);
  • - sim((1, 2, 3, 1, 4), (2, 4, 3, 1, 1)) = (2, 3) (à l'ordre près, tous les éléments sont communs, et deux d'entre eux sont bien placés).
• -De manière immédiate, on a x = y si et seulement si sim(x, y) = (N, 0). On remarque de plus que sim est symétrique.

• - sim((2, 1, 3, 4), (1, 2, 3, 4));
• - sim((0, 0, 1, 1), (1, 1, 3, 0));
• - sim((0, 3, 3, 2, 3), (3, 0, 3, 4, 4)).

Notations et définitions supplémentaires

• -On note R l'ensemble des similarités (ou réponses) possibles :
  R = {sim(x, y)|x, y ∈ C}.
• -Pour X ⊆ C et c ∈ C, on note
  sim(X, c) = {sim(x, c)|x ∈ X}.
• -Pour X ⊆ C et c ∈ C et r ∈ R, on note
  filtre(X, c, r) = {x ∈ X|sim(c, x) = r}.

• -Pour une liste (éventuellement vide) h = [(c_1, r_1), …, (c_k, r_k)] (appelée historique) de couples (combinaison, similarité), on définit l'ensemble des combinaisons compatibles avec h par
  compat(h) = {x ∈ C|∀i ∈ {1, …, k}, sim(x, c_i) = r_i}.
• -Un tel historique est dit admissible si compat(h) ≠ ∅ et si les r_i avec 1 ≤ i < k sont différents de (N, 0).
• -Un historique admissible est dit inachevé si k = 0 (l'historique est vide) ou r_k ≠ (N, 0).

• -une combinaison but ∈ C est choisie par l'arbitre et gardée secrète;
• -le joueur J_1 doit deviner cette combinaison en un minimum d'essais ;
• -pour ce faire, il propose à chaque coup une combinaison c ∈ C;
• -l'arbitre indique alors au joueur J_1 la valeur de sim(x, but);
• -si cette valeur est (N, 0) (c'est-à-dire si x = but ), la partie s'arrête ;
• -sinon, le joueur J_1 propose une nouvelle combinaison;
• -le score du joueur J_1 est le nombre total d'essais effectués pour trouver but. Le joueur J_1 cherche donc à minimiser ce score. Si la partie ne se termine jamais, on considère que ce score est infini.

• -L'arbitre choisit but = (2, 2, 0) comme combinaison secrète à deviner.
• -Le joueur J_1 joue (0, 0, 0), l'arbitre répond sim((0, 0, 0), but) = (1, 0).
• -Le joueur J_1 joue (0, 1, 2), l'arbitre répond sim((0, 1, 2), but) = (0, 2).
• -Le joueur J_1 joue ( 2, 2, 0 ), l'arbitre répond (3, 0) et la partie se termine. Le score de la partie vaut 3.

Partie I. Programmation des fonctions élémentaires

• -une combinaison par une list de longueur N à valeurs dans {0, …, P − 1};
• -une réponse par un couple (b, m) d'entiers.

I. 1 Calcul de la similarité

I. 2 Stratégie naïve

[([0, 0, 0], (0, 0)), ([1, 1, 1], (1, 0)), ([1, 2, 2], (0, 1)),
    ([3, 1, 3], (1, 2)), ([3, 3, 1], (3, 0))]

Partie II. Généralités sur les stratégies

II. 1 Arbre de stratégie

• -en notant c l'étiquette de la racine, on a un sous-arbre pour chaque r ∈ sim(D, c) (et l'arête reliant la racine à ce sous-arbre est étiquetée r );
• -si (N, 0) ∈ sim(D, c), alors le sous-arbre correspondant est une feuille (que l'on étiquettera parfois c, même si cette étiquette est redondante);
• -pour chaque r ∈ sim(D, c), r ≠ (N, 0) :
  • - |filtre(D, c, r)| < |D|;
  • -le sous-arbre correspondant à r est un filtre(D, c, r)-arbre de stratégie.

• -
  Si D = {c} (singleton), alors la combinaison à la racine est nécessairement c (tout autre choix conduirait à violer la condition | filtre (D, c, r)| < |D| ) et l'unique D-arbre de stratégie est donc :
  

  Figure 1 - Arbre pour un singleton.
• -
  Pour N = 3, P = 4 et D = {(1, 2, 2), (3, 3, 1)}, de nombreux arbres sont possibles, dont les deux représentés ci-dessous :
  

  Figure 2 - Deux arbres possibles pour D = {(1, 2, 2), (3, 3, 1)}.
  On notera en revanche qu'aucun D-arbre ne peut ici avoir de racine étiquetée par c = (0, 0, 0) : pour r = (0, 0), on aurait filtre(D, c, r) = D.
• -Pour N = 2 et P = 3, l'arbre de la figure 3 en page suivante est un C-arbre de stratégie (dans cet arbre, on a noté les couleurs a, b, c au lieu de 0, 1, 2 pour éviter les confusions entre combinaisons et réponses).

Figure 3 - L'arbre de stratégie T_0.

• -On dit qu'un historique h = ((c_1, r_1), …, (c_k, r_k)) est joué suivant l'arbre T s'il existe un chemin partant de la racine et étiqueté c_1, r_1, c_2, …, c_k, r_k (en alternant étiquette des nœuds internes et étiquettes des arêtes). Notons que s'il existe, ce chemin est unique.
• -Pour un D-arbre de stratégie T et une combinaison x ∈ D, il existe une unique feuille de T étiquetée x, et donc un unique chemin de la racine à cette feuille. L'historique associé à ce chemin (qui se termine par (x, (N, 0)) ) est appelé partie jouée suivant T pour le but x.
• -On note alors score(T, x) le score de cette partie.

• -la racine lui indique le premier coup à jouer;
• -il reçoit une réponse r et il sait maintenant que le but est dans filtre(D, c, r);
• -il descend dans le sous-arbre correspondant, qui est soit une feuille (si r = (N, 0), et la partie est alors terminée), soit un filtre(D, c, r)-arbre qui lui indiquera comment jouer la suite de la partie.

• -le joueur J_1 joue ( a, b ) (le coup à la racine);
• -comme sim((a, b), but) = (0, 1), l'arbitre répond (0, 1) et l'on descend dans la branche correspondante;
• - J_1 joue ensuite (b, c);
• -l'arbitre répond sim((b, c), but) = (0, 1), on descend dans cette branche ;
• - J_1 joue (c, a), l'arbitre répond (2, 0) et l'on descend dans cette branche;
• -on arrive sur une feuille, ce qui indique que la partie est terminée.

II. 2 Stratégie optimale

• -Le score dans le pire cas pire_D(T) d'un D-arbre de stratégie T est défini par :
  pire_D(T) = max_(x ∈ D)score(T, x).
• -Le poids total poids _D(T) d'un D-arbre de stratégie T est défini par :
  poids_D(T) = ∑_(x ∈ D)score(T, x).
• -On définit :
  pire_(opt)(D), = min{pire_D(T)|T ∈ T_D}; poids_(opt)(D), = min{poids_D(T)|T ∈ T_D}
• -Un D-arbre de stratégie est dit optimal dans le pire cas s'il vérifie pire _D(s) = pire _(opt)(D), optimal en moyenne s'il vérifie poids_D(s) = poids _(opt)(D).

II. 3 Jeu à deux joueurs

• -Le joueur J_1 choisit librement c_k ∈ C;
• -le joueur J_2 choisit une réponse r_k ∈ sim(compat(h), c_k);
• -si r_k = (N, 0), la partie se termine avec un score final de k, sinon on remplace h par h, (c_k, r_k) et l'on passe au tour suivant.

II. 4 Représentation informatique

val sim : combi -> combi -> reponse

type strat =
    | Gagne
    | Noeud of combi * ((reponse * strat) list)

val joue_un_joueur : strat -> combi -> int

val pire : strat -> int
val poids : strat -> int

II. 5 Calcul naïf de pire _(opt)(D) et poids _(opt)(D)

val reponses_possibles : combi list -> combi -> reponse list

val pire_opt_naif : combi list -> int

val strategie_poids_naive : combi list -> strat

Partie III. Recherche efficace de stratégies

III. 1 Premières optimisations

• -une pour un type combi_int_t permettant de représenter un entier de {0, …, |C| − 1};
• -l'autre pour un type rep_int_t permettant de représenter un entier de {0, …, |R| − 1}.

struct rep_couple_t {
    int bien;
    int mal;
};
typedef struct rep_couple_t rep_couple_t;

const int N = 4; // valeur purement indicative
const int P = 6; // idem
const int NB_COMBIS = ...; //

rep_couple_t similarite(int x[], int y[]);
rep_int_t rep_int_of_rep_couple(rep_couple_t couple);

combi_int_t int_of_combi(int x[]);
int *combi_of_int(combi_int_t x);

rep_int_t sim(combi_int_t x, combi_int_t y);

type combi = int
type reponse = int

• -On suppose de plus disposer de deux constantes globales nb_combis et nb_reponses correspondant respectivement à |C| et |R|.
• -Les combinaisons sont numérotées de 0 à nb_combis - 1 et les réponses de 0 à nb_reponses - 1. On suppose de plus que la constante tous_bons, de type reponse, correspond au codage de la réponse (N, 0).
• -La constante toutes_combis est toujours disponible, et de type combi list.
• -La fonction sim est toujours disponible (et utilise les nouveaux types) mais s'exécute à présent en temps constant.

III. 2 Stratégie gloutonne

• -les liste u_i sont non vides et disjointes;
• -l'union des éléments des listes u_i vaut X∖{c};
• -pour chaque u_i, il existe r_i ≠ (N, 0) tel que v_i = filtre(X, c, r_i).

val repartit : combi list -> combi -> combi list list

val choix_glouton : combi list -> combi list -> combi

III. 3 Majorations et minorations

Algorithme 
1αβ.
    fonction Eval1 (buts, 
α, β )
        si 
| buts 
|=1 alors
            renvoyer 1
        
h_(min) ← β
        pour 
c ∈ split(X) faire
            
h ← Eval2( buts 
, c, α − 1, h_(min) − 1)
            
h_(min) ← min(h + 1, h_(min))
            si 
h_(min) ≤ α alors
                renvoyer 
h_(min)
        renvoyer 
h_(min)
    fonction Eval2(buts, 
c, α, β )
        repartition 
= {(r, filtre 
( buts 
, c, r))|r ∈ sim( buts,
c)}
        
h_(max) ← α
        pour 
(r, buts 
^′) ∈ repartition faire
            si 
r ≠ (N, 0) alors
                
h ← Eval1 
( buts 
^′, h_(max), β)
                
h_(max) ← max(h_(max), h)
                si 
h_(max) ≥ β alors
                    renvoyer 
h_(max)
        renvoyer 
h_(max)

Partie IV. Prise en compte des symétries

IV. 1 Définitions et premières propriétés

• -On appelle permutation des positions une permutation σ de l'ensemble {0, …, N − 1} des positions.
• -On appelle permutation des couleurs une permutation τ de l'ensemble {0, …, P − 1} des couleurs.
• -On dit qu'une application α de C dans C est une transformation s'il existe une permutation des positions σ et une permutation des couleurs τ telles que :
  ∀x ∈ C, α(x) = (τ(x_(σ(0))), …, τ(x_(σ(N − 1)))).
  On note alors α = (σ, τ).
• -On note S l'ensemble des transformations.