DS 4 (MP2I 2021-2022) — Pavages par dominos et placement des espaces¶

Devoir surveillé · MP2I · 2021-2022 · partie II du DS 4 (3 h au total)

Autres parties : I. Listes chaînées en C

Domino's Tiling¶

On cherche à générer des pavages d'un rectangle de taille $w \times h$ par des dominos, c'est-à-dire des tuiles de tailles $2\times 1$ et sans recouvrement. Un exemple d'un tel pavage est donné ici :

Un pavage d'un rectangle 4times 5 par des dominos horizontaux (bleu) et verticaux (violet). — Un pavage d'un rectangle $4\times 5$ par des dominos horizontaux (bleu) et verticaux (violet).

Question 7

Donner une condition nécessaire et suffisante sur le couple $(w,h)$ pour qu'un tel pavage existe.

Attention : CNS veut dire qu'il faut donner une condition, montrer qu'elle est vérifiée quand il y a un pavage et montrer que si la condition est vérifiée, alors un pavage existe.

Corrigé

Un tel pavage existe ssi $wh$ est pair.

En effet, si ce n'est pas le cas, le nombre de cases couvertes par des dominos est forcément pair, donc on ne peut pas paver. Si c'est le cas, soit $w$, soit $h$ est pair, et il suffit de placer des dominos régulièrement horizontalement ou verticalement pour paver.

On suppose à partir de maintenant que $(w,h)$ vérifie cette CNS et qu'ainsi il existe un pavage.

On va représenter une telle grille par des cases de trois types :

E si la case est à remplir (E comme empty)
H si la case appartient à un domino horizontal
V si la case appartient à un domino vertical

type case = E | H | V

Ainsi, on a perdu la représentation en dominos en les coupant en deux. Si on considère le pavage de l'exemple précédent, il correspond à la matrice OCaml :

[|
  [| V; H; H; V |];
  [| V; H; H; V |];
  [| V; V; H; H |];
  [| V; V; H; H |];
  [| H; H; H; H |];
|]

Cependant, si on considère la première valeur V elle ne peut venir que d'un seul domino vertical commençant ici, on peut ainsi procéder à l'envers en l'enlevant :

[|
  [| E; H; H; V |];
  [| E; H; H; V |];
  [| V; V; H; H |];
  [| V; V; H; H |];
  [| H; H; H; H |];
|]

Et on continue ensuite avec la première case différente de E en allant de haut en bas et de gauche à droite.

On identifie un domino à un couple de coordonnées $((x_1,y_1),(x_2,y_2))$ indiquant les cases occupées (l'ordre n'est pas important ici).

type domino = (int * int) * (int * int)

Question 8

Écrire une fonction de signature

val extrait_pavage : case array array -> domino list

qui extrait la liste des dominos d'une matrice de pavage éventuellement partielle. On pourra modifier la matrice passée en entrée si c'est plus simple pour vous (indice : ce sera le cas).

Corrigé

let rec extrait_pavage a =
  let w, h = Array.length a.(0), Array.length a in
  let rec non_vide i j =
    if a.(j).(i) <> E
    then Some (i, j)
    else if i <> w-1
    then non_vide (i+1) j
    else if j <> h-1
    then non_vide 0 (j+1)
    else None
  in
  match non_vide 0 0 with
  | Some (i,j) ->
    if a.(j).(i) = H
    then begin
      a.(j).(i) <- E;
      a.(j).(i+1) <- E;
      ( (i,j), (i+1,j) ) :: extrait_pavage a
    end else begin
      a.(j).(i) <- E;
      a.(j+1).(i) <- E;
      ( (i,j), (i,j+1) ) :: extrait_pavage a
    end
  | None -> []

Pour déterminer un pavage, on va utiliser un algorithme de backtracking. Les mouvements sont des dominos.

Question 9

Écrire une fonction de signature

val mouvements : case array array -> domino list

qui étant donnée une grille renvoie tous les dominos qu'on peut placer.

Attention : même si on a le même type, le problème est différent de la fonction précédente.

Corrigé

let mouvements a =
  let m = ref [] in
  let w, h = Array.length a.(0), Array.length a in
  for i = 0 to w-1 do
    for j = 0 to h-1 do
      if a.(j).(i) = E
      then begin
        if i < w-1 && a.(j).(i+1) = E then m := ((i,j),(i+1,j))::!m;
        if j < h-1 && a.(j+1).(i) = E then m := ((i,j),(i,j+1))::!m
      end
    done
  done;
  !m

Question 10

Écrire des fonctions de signature

val place : case array array -> domino -> unit
val enleve : case array array -> domino -> unit

qui place et enlève respectivement un domino.

Corrigé

let place a ((i,j),(k,l)) =
  let c = if i = k then V else H in
  a.(j).(i) <- c;
  a.(l).(k) <- c

let enleve a ((i,j),(k,l)) =
  a.(j).(i) <- E;
  a.(l).(k) <- E

Question 11

Écrire une fonction de signature

val complet : case array array -> bool

qui indique si une grille est complètement pavée.

Corrigé

let complet a =
  let w, h = Array.length a.(0), Array.length a in
  let b = ref true in
  for j = 0 to h-1 do
    for i = 0 to w-1 do
      b := a.(j).(i) <> E && !b
    done
  done;
  !b

Question 12

Écrire une fonction récursive de signature

val enumere : case array array -> unit

qui énumère les pavages de dominos de la grille passée en paramètre et lève l'exception Solution l quand la grille correspond à un pavage et l est la suite de dominos correspondante telle qu'obtenue avec extrait_pavage.

L'exception est définie par :

exception Solution of domino list

Corrigé

exception Solution of domino list

let enumere a =
  let rec aux () =
    if complet a
    then raise (Solution (extrait_pavage (Array.map Array.copy a)))
    else List.iter
        (fun m ->
           place a m;
           aux ();
           enleve a m) (mouvements a)
  in aux ()

Question 13

Écrire une fonction de signature :

val pavage : int -> int -> domino list

telle que pavage w h renvoie une liste de dominos correspondant à un pavage d'une grille de dimension $w \times h$.

Corrigé

let pavage w h =
  try
    enumere (Array.make_matrix h w E);
    failwith "pas de pavage"
  with Solution l -> l

Question 14

Reprendre la fonction enumere pour en déduire une fonction de signature

val enumere_tous : case array array -> domino list list

qui renvoie la liste de tous les pavages depuis une grille donnée.

En déduire ainsi une fonction

val pavages : int -> int -> domino list list

qui renvoie tous les pavages pour une dimension donnée de grille.

Corrigé

Pour ne pas obtenir plusieurs fois le même pavage (une fois pour chaque ordre de pose des dominos), on ne considère que les dominos qui couvrent la première case vide dans l'ordre de lecture : cette case doit être couverte et ne peut l'être que par un domino dont elle est la première case.

let premiere_vide a =
  let w = Array.length a.(0) in
  let rec aux i j =
    if a.(j).(i) = E then (i, j)
    else if i < w-1 then aux (i+1) j
    else aux 0 (j+1)
  in aux 0 0

let enumere_tous a =
  let rec aux l =
    if complet a
    then [ l ]
    else begin
      let c = premiere_vide a in
      let acc = ref [] in
      List.iter
        (fun m ->
           if fst m = c then begin
             place a m;
             acc := aux (m::l) @ !acc;
             enleve a m
           end) (mouvements a);
      !acc
    end
  in aux []

let pavages w h = enumere_tous (Array.make_matrix h w E)

On trouve ainsi 36 pavages pour une grille $4 \times 4$ et 95 pour une grille $4 \times 5$.

Matoucheespaceestcassée¶

Et ma blême araignée, ogre illogique et las
Aimable, aime à régner, au gris logis qu'elle a.

Victor Hugo

On s'intéresse dans cette partie au problème du placement des espaces dans une phrase qui n'en a pas. Par exemple la phrase suivante en anglais

bothearthandsaturnspin

pourrait se décomposer en both earth and saturn spin ou bot heart hands at urns pin.

On va considérer des char array ici pour les chaînes, mais tout marche de la même manière avec des string.

On considère un dictionnaire, ou wordlist, défini globalement :

val dico : char array list

Notation : t[i..j] est le sous-tableau de t constitué des éléments d'indice i à j.

Question 15

Écrire une fonction de signature :

val est_mot : char array -> int -> int -> bool

telle que l'appel à est_mot t i j renvoie true lorsque t[i..j] est dans le dictionnaire.

Corrigé

let est_mot c i j =
  let m = Array.init (j-i+1) (fun k -> c.(i+k)) in
  List.mem m dico

On va résoudre le problème de l'ajout d'espaces par backtracking avec une version plus simple : pour chaque chaîne, on se contente de décider s'il est possible ou non de rajouter des espaces pour qu'elle ne soit composée que de mots dans le dictionnaire. On dit qu'un tableau est séparable quand on peut ajouter ces espaces.

On a donc t séparable s'il existe $i$ tel que t[0..i-1] est un mot et t[i..n-1] est séparable où |t| = n est la longueur de $t$.

Question 16

Écrire une fonction récursive de signature :

val separable : char array -> int -> bool

telle que separable t i indique si t[i..n-1] est séparable où $n =|t|$.

Corrigé

let rec separable t i =
  if i >= Array.length t
  then true
  else begin
    let separe = ref false in
    let j = ref i in
    while not !separe && !j < Array.length t do
      separe := est_mot t i !j && separable t (!j+1);
      incr j
    done;
    !separe
  end

Question 17

On note $T_p$ le nombre d'appels à est_mot dans l'exécution de separable t i quand $p = |t| - i$ est le nombre d'éléments du sous-tableau considéré.

Montrer que $T_p \le \sum_{i=0}^{p-1} T_i + O(p)$.
Quitte à se placer dans un pire cas, on peut supposer qu'il existe une constante $A$ telle que $T_p = \sum_{i=0}^{p-1} T_i + A p$.

Montrer que pour $p > 0$, $T_p = 2 T_{p-1} + A$.
En déduire que $T_p = O(2^p)$.

Corrigé

On considère que $T_p$ correspond à l'appel separable t k. Le pire cas correspond au cas où tous les préfixes de t[k..n-1] sont des mots. Ainsi, pour chaque $j \in \range{k}{n-1}$ on a t[k..j] qui est un mot et on effectue un appel récursif à separable t (j+1) qui va effectuer $T_{n-j-1}$ appels à est_mot. On a donc

\[ T_p \le (n-k) + \sum_{j=k}^{n-1} T_{n-j-1} \le O(p) + \sum_{i=0}^{p-1} T_i \]

en remarquant que $p = n-k$ et en posant $i = n - j - 1$.
On écrit la récurrence pour $p-1$ :

\[ T_{p-1} = \sum_{i=0}^{p-2} T_i + A (p-1) \]

et on soustrait avec la récurrence pour $p$ :

\[ T_p - T_{p-1} = T_{p-1} + A \]
On a $T_0 = 0, T_1 = A, T_2 = 3A, T_3 = 7A, \dots$. On conjecture donc rapidement que $T_p = (2^p - 1)A$ et on le valide par récurrence.
- Initialisation : $T_0 = 0 = (2^0 - 1) A$.
- Hérédité : si $T_p = (2^p - 1) A$ on a $T_{p+1} = 2 T_p + A = 2^{p+1} A - 2 A + A = (2^{p+1}-1)A$.
Ainsi, $T_p = O(2^p)$.