DS 4 — Listes chaînées, pavages et backtracking

MP2I, année scolaire 2021-2022 — devoir surveillé du 1er février 2022 — durée totale 3h.

Consignes

Tout document interdit. Tout dispositif électronique interdit.

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles. Utilisez de préférence plusieurs couleurs. Commentez votre code dès que ce qu'il fait n'est pas évident.

Avant chaque fonction compliquée à écrire, ou quand vous n'y arrivez pas, indiquez avec des phrases ce que vous voulez faire. Cela permet de vous donner éventuellement des points si l'idée était bonne ou si vous y êtes presque.

A link to a past TP

On va reprendre le type des listes chaînées en C :

struct maillon {
    int valeur;
    struct maillon *suivant;
};

typedef struct maillon maillon;

struct liste {
    maillon *debut;
    maillon *fin;
};

typedef struct liste liste;

• Dans un maillon, soit suivant pointe vers le maillon suivant de la chaîne ou vaut NULL.
• La liste vide aura la valeur NULL pour debut et fin.
• Dans une liste non vide, debut pointe sur le premier maillon et fin sur le dernier.

On suppose définies des fonctions

// cree un maillon
maillon *creer_maillon(int valeur, maillon *suivant);
// supprime un maillon
void suppr_maillon(maillon *);
// cree une liste vide
liste *creer_liste(void);
// supprime une liste
void suppr_liste(liste *);

Question 1. Écrire une fonction de prototype

int longueur(liste *);

qui renvoie la longueur d'une liste.

Corrigé

int longueur(liste *l)
{
    int n = 0;
    maillon *m = l->debut;
    while(m != NULL)
    {
        n++;
        m = m->suivant;
    }
    return n;
}

Question 2. Écrire une fonction de prototype

int somme(liste *);

qui renvoie la somme des valeurs des éléments d'une liste.

Corrigé

int somme(liste *l)
{
    int s = 0;
    maillon *m = l->debut;
    while(m != NULL)
    {
        s = s + m->valeur;
        m = m->suivant;
    }
    return s;
}

Question 3. Écrire une fonction de prototype

void liste_ajout_en_tete(liste *l, int valeur);

qui ajoute un maillon en tête de la liste passée en paramètre en \(O(1)\).

On fera attention au cas où la liste est vide.

Corrigé

void liste_ajout_en_tete(liste *l, int valeur)
{
    l->debut = creer_maillon(valeur, l->debut);
    if (l->fin == NULL)
        l->fin = l->debut;
}

Question 4. Écrire une fonction de prototype

maillon *liste_cherche_maillon(liste *l, int valeur);

qui renvoie un pointeur sur le premier maillon de valeur valeur ou renvoie NULL s'il n'y en a pas.

Corrigé

maillon *liste_cherche_maillon(liste *l, int valeur)
{
    maillon *m = l->debut;
    while(m != NULL && m->valeur != valeur)
    {
        m = m->suivant;
    }
    return m;
}

Question 5. Écrire une fonction de prototype

void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur);

qui insère en \(O(1)\) un maillon après le maillon m. On fera en sorte que l'insertion soit valide même si m est le dernier maillon de la liste.

Corrigé

void liste_ajout_maillon_apres(liste *l, maillon *m, int valeur)
{
    m->suivant = creer_maillon(valeur, m->suivant);
    if (l->fin == m)
        l->fin = m->suivant;
}

Question 6. Expliquer comment cette structure permet d'implémenter une pile et donner les différentes complexités des opérations de la structure liste.

Corrigé

L'ajout et la suppression en tête sont en \(O(1)\).

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 $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é.

1. Montrer que \(T_p \le \sum_{i=0}^{p-1} T_i + O(p)\).

2. 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\).

3. En déduire que \(T_p = O(2^p)\).

Corrigé

1. 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\).

2. 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 \]

3. 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)\).