MASTER DAPM   — D22 —  Examen de TP

Lundi 19 février 2018     09:00 → 12:00 (durée 3H00)

Lisez attentivement le contenu de ce paragraphe avant de lire le sujet et de commencer ! Suivez scrupuleusement les instructions en respectant à la lettre les commandes, les noms des fichiers proposés, majuscules/minuscules comprises. Lisez attentivement le sujet. Les réponses aux questions éventuelles doivent être incorporées au fichier source C sous forme de commentaires en début de programme.

NB. Copiez les commandes à la souris, l'expérience prouve que certains étudiants ont du mal à recopier une instruction. Si vous n'avez pas réussi à suivre les instructions ci-dessus et que je dois intervenir pour faire ce travail à votre place, je retirerai 5 points à votre note.

Objectif de l'examen.

Résoudre une énigme pour sortir de la salle de TP.

L'énigme.

Vous êtes enfermé dans la salle de TP et l'ouverture de cette salle est conditionnée par la saisie d'un mot de passe. Dans un sac, vous trouvez 17 dominos numérotés :

  1. L|A
  1. S|T
  2. E|X
  3. O|N
  4. T|E
  1. -|S
  2. I|S
  3. -|E
  4. N|-
  1. X|I
  2. I|O
  3. S|O
  4. U|T
  1. L|U
  2. O|L
  3. A|-
  4. T|I

Il faut reconstituer le mot de passe en mettant les dominos bout-à-bout. On ne peut aligner deux dominos que si les symboles à leur jonction sont identiques et dans le même sens. Avec les dominos de l'énigme, on peut par exemple aligner les dominos 5, 11 et 3 qui coïncident respectivement en le symbole S et symbole O :

-|SS|OO|N

Par convention, le premier domino de la séquence est le domino numéro 0. Le mot de passe est constitué par la suite des symboles des 17 dominos bien ordonnés en ne gardant qu'un seul des deux symboles identiques à chaque jonction. Par exemple le mot associé à la séquence des 3 dominos ci-dessus est "-SON". Le mot de passe contient donc 19 symboles dont les deux premiers sont "LA".

Questions. [3pts]

Les réponses à ces questions devront être intégrées en commentaires dans le code de votre programme. C'est votre programme qui vous permettra d'y répondre :
  1. Pour l'instance du problème fournie, combien y-a-t-il de séquences valides contenant tous les dominos ?
  2. Quels sont ces séquences ?
  3. Parmi ces séquences, une seule a un sens en français, il s'agit du mot de passe. Quel est ce mot de passe ?

Sujet [14pts]

Vous devez écrire un programme en langage C qui cherche l'intégralité des placements valides. Bien entendu, votre programme doit pouvoir résoudre le problème pour une liste arbitraire de dominos, pas uniquement l'instance qui vous est fournie ici. Il sera tenu compte de la simplicité et de la clarté de votre programme.

On suppose que les dominos sont numérotés de 0 à n et fournis dans un fichier texte contenant un domino par ligne codé par une chaîne [X:Y], où X et Y désignent les symboles gauche et droit du domino. Ce fichier contient ceux de l'énigme à chercher. Par convention le premier domino du fichier est le domino 0 par lequel débute la séquence.

Le fichier dominos.lex contient la trame du programme C à écrire, il est fourni avec son fichier makefile. En l'état, ce programme analyse le fichier texte contenant les dominos et les range dans un tableau. Vous devrez utiliser les types, variables et fonctions prédéfinies :

  1. la variable enigme est le tableau contenant les n + 1 dominos dans l'ordre d'apparition du fichier texte. Ce tableau est instancié après la lecture du fichier texte. Les dominos sont codés par une structure à 2 champs tcouple;
  2. l'entier VECTEUR codé sur 64 bits est l'entier dont la décomposition binaire permet de savoir si le domino numéro i est utilisé (1) ou non (0) dans la séquence à trouver. Initialement, aucun des dominos n'est utilisé, la valeur de cet entier est donc nulle. Le nombre de dominos dans l'énigme est donc limité à MAXDOMINOS=64;
  3. la variable solution est un tableau de nbdominos entiers positifs qui devra contenir la liste des dominos solutions de l'énigme; La variable nbdominos est instanciée par le programme après la lecture du fichier contenant les dominos;
  4. la fonction AfficherDomino() affiche le domino dont le numéro est passé en paramètre. En orange s'il est marqué dans la variable VECTEUR, en jaune sinon;
  5. la fonction AfficherSequence() affiche la liste des dominos dont les numéros sont stockés dans le tableau passé en paramètre.

Toutes vos fonctions doivent être commentées !

[1pt] Écrivez une fonction AfficherPhrase() a deux paramètres, un tableau d'entier et sa taille, qui affiche la phrase constituée par les symboles sur les dominos dont les numéros sont contenus dans ce tableau (sans les répétitions, cf. plus haut).
[2pts] Écrivez une fonction EstLibre() a un paramètre, le numéro d'un domino, et qui renvoie la valeur 1 si ce domino est libre ou non. Cette information est à chercher dans l'entier VECTEUR. Utilisez les opérateurs bit-à-bit du langage C. On rappelle que
[2pts] Écrivez une fonction OnOff() avec deux paramètres, le numéro d'un domino et un index. Dans un premier temps, si le domino est libre, la fonction range son numéro dans le tableau solution à l'index donné, sinon elle y range la valeur nulle. Dans un deuxième temps, la fonction met à jour l'entier VECTEUR pour signifier que le domino est à présent utilisé (ou libre à nouveau). C'est cette fonction qui va être utilisée dans l'algorithme de backtracking pour utiliser/libérer les dominos dans la construction du tableau solution.
[3pts] Écrivez une fonction ChercherSuivants() avec deux paramètres, le numéro d'un domino et un entier positif passé par adresse. La fonction doit renvoyer un tableau contenant tous les numéros des dominos libres qui peuvent s'accrocher à droite du domino fourni. La taille de ce tableau est "renvoyée" via l'autre paramètre passé par adresse.
[6pts] Écrivez une fonction récursive Resoudre() utilisant le principe du backtracking dont le seul paramètre est l'indice du tableau solution où il faut placer le bon domino. L'appel initial de cette fonction est donc Resoudre(1) puisque le premier domino dans le tableau solution est initialisé par convention avec le domino 0.