Mines Option Informatique MP 2023Sujet et rapport du jury

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARIS, TÉLÉCOM PARIS, MINES PARIS, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.
Concours Mines-Télécom, Concours Centrale-Supélec (Cycle International).

CONCOURS 2023

ÉPREUVE D'INFORMATIQUE MP

Préliminaires

Travail attendu

Description du jeu du hanjie

Voici un exemple, que nous résolvons à la main. Une grille vide est fournie ci-contre. Elle est de dimension 5 × 7. Nous marquons les cases par des symboles «?» tant que nous ignorons leur couleur.
Nous comptons les rangées à partir de 0 , de gauche à droite pour les colonnes et du haut vers le bas pour les lignes.

La colonne 0 et la colonne 5 sont de longueur 5 . Or l'indication est [5] dans les deux cas. Elles doivent donc chacune contenir 5 blocs noirs consécutifs. Nous les noircissons en totalité.

Dans la ligne 0 , il n'y a qu'une seule manière de placer un bloc de 4 cases noires puis 2 cases noires. De même, dans la ligne 2, il n'y a qu'une seule manière de positionner le bloc de longueur 2 : il doit se trouver au milieu entre les deux blocs déjà isolés. Dans la ligne 3, nous avons déjà placé deux cases noires : les autres sont donc toutes blanches. Enfin, dans la ligne 4, il n'y a plus qu'une seule manière de placer un bloc de 6 cases noires.

Enfin, en reprenant les indications des colonnes, nous voyons que dans les colonnes 1,2 et 4 , la dernière case inconnue est blanche. Dans la colonne 3 et 6 en revanche, nous devons noircir la dernière case inconnue. Nous avons obtenu une solution de notre hanjie. Elle est unique.

1. Hanjie et calcul de vérité

Dans cette section, nous raisonnons avec la logique propositionnelle pour déterminer la couleur de certaines cases. Nous nous concentrons sur le hanjie h_0 défini par

1 - Établir, par raisonnement en langue française, que la solution du hanjie h_0 est unique.
Nous introduisons six variables booléennes, nommées x_0, x_1, …, x_5 et correspondant aux cases ci-contre. Nous associons la valeur de vérité V (vrai) à la couleur noire et F (faux) à la couleur blanche.

2. Cadre de résolution systématique du hanjie

2.1. Le hanjie

let $m=5$
let $\mathrm{n}=7$
type presolution = couleur array array
let presolution_init () : presolution $=$ (* cree une presolution *)
    Array.make_matrix m n I (* toute egale a $I *$ )

Dans notre exemple, nous aurions les numéros :

type hanjie = { ind_lig : int list array;
    ind_col : int list array }

let h_escargot = {ind_lig = [| [4;2]; [1;1;2]; [1;2;1]; [1;1]; [6] |];
    ind_col = [| [5]; [1;1]; [1;1;1]; [3;1]; [1] ; [5] ;
        [2] |] }

let p_escargot = [|[|N;N;N;N;B;N;N|];
    [|N; B; B; N; B; N; N|];
    [|N; B; N; N; B; N; Bl];
    [|N; B; B; B; B; N; Bl];
    [|N;N;N;N;N;N;Bl] |]

2.2. Recherche de solutions

type 'a option = None | Some of 'a

type extenseur = hanjie -> presolution ->
    int -> couleur -> presolution option

let resout (h:hanjie) (ext:extenseur) : presolution option =
    let p0 = presolution_init () in
    let rec explore (p:presolution) (z:int) : presolution option =
        (* A COMPLETER *)
    in
    explore p0 0

3. Résolution autonome de lignes et extenseur

La plus grande extension commune est dans ce cas

N	B	I	N	I	B	N	B

type automate = { r : int;
    transitions : (couleur, int) Hashtbl.t array}

Définition : Le déploiement d'un automate A ayant r états par un mot w = w_0 w_1⋯w_(n − 1) ∈ C^–^∗ de longueur n est un nouvel automate, noté A⋈w, qui possède r ⋅ (n + 1) états. Pour toute transition ( q, c, q^′ ) dans l'automate A et pour tout indice i compris entre 0 et n − 1,
pour w_i ∈ C et c = w_i ou encore pour w_i = I, il y a dans l'automate A⋈w une transition (i ⋅ r + q, c, (i + 1) ⋅ r + q^′).
◻20 - Dans cette question uniquement, on considère l'exemple avec n = 4, w_0 = INBI ∈ C^–^∗ et où A_0 est l'automate défini par

A. Annexe : aide à la programmation en OCaml

• length : 'a array -> int

• make : int -> 'a -> 'a array

• make_matrix : int -> int -> 'a -> 'a array array

• init : int -> (int -> 'a) -> 'a array

• copy : 'a array -> 'a array

• mem : 'a -> 'a array -> bool
  mem a l is true if and only if a is structurally equal to an element of l (i.e. there is an x in l such that compare a x = 0 ).
• for_all : ('a -> bool) -> 'a array -> bool

• exists : ('a -> bool) -> 'a array -> bool

• map : ('a -> 'b) -> 'a array -> 'b array

• iter : ('a -> unit) -> 'a array -> unit

• ('a, 'b) Hashtbl.t

• create : int -> ('a, 'b) t

• add : ('a, 'b) t -> 'a -> 'b -> unit

• remove : ('a, 'b) t → 'a -> unit

• mem : ('a, 'b) t → 'a -> bool

• iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit

• find_opt : ('a, 'b) t -> 'a -> 'b option

B. Annexe : règles de la déduction naturelle

Fin de l'Épreuve