INF3105 — Structures de données et algorithmes
Été 2024
UQAM
Département d'informatique

TP2 : Déplacements dans un univers virtuel

Objectifs

Contexte

Dans ce travail pratique, vous devez implémenter un agent (ex.: un robot) qui explore un univers constitué de salles liées par des portails (ou téléporteurs).

Chaque salle est identifiée par un numéro (son indice dans le tableau de salles) et composée de cellules. Une cellule est caractérisée par ses coordonnées, c'est-à-dire un triplet d'entiers: le numéro de la salle dans laquelle elle se trouve ainsi que sa position (i,j) dans la salle. Il existe trois types de salles, selon leur forme : carré, diamant ou triangle. La forme d'une salle donnée est déterminée par le nombre de cellules et leur disposition. Un paramètre d'entrée n (entier) donne les dimensions d'une salle, selon sa forme. À titre d'exemple, la figure ci-dessous illustre les salles carre 4 (Salle 0), diamant 5 (Salle 1) et triangle 7 (Salle 2). Notez que n doit être impair pour les salles de type Diamant et Triangle (ce sera toujours le cas dans les tests) mais peut être pair ou impair pour les carrés. Une salle de type triangle est toujours orientée comme dans l'image, c'est-à-dire que la "pointe" du triangle (position (3,3) dans la figure 1) est toujours dirigée vers le bas.

Par défaut, les seuls déplacements possibles se font d'une cellule courante vers une cellule adjacente, à l'horizontale ou à la verticale, dans la même salle. Par exemple, à partir de la position (i,j), il est possible de se rendre (en un déplacement unitaire) aux positions (i-1,j), (i+1,j), (i,j-1) et (i,j+1), sous réserve bien sûr que ces positions soient valides dans la salle courante.

En outre, certaines cellules contiennent un portail permettant de se rendre directement à une autre cellule (située dans la même salle, ou dans une salle différente). Par exemple, dans la figure suivante, l'espace constitué des trois salles contient trois portails, identifiés ici par les lettres A, B et C. Le portail A permet d'aller de la cellule (1,0) dans la salle 0 à la cellule (0,2) dans la salle 1, et vice versa. On peut se rendre de la salle 0 à la salle 2 directement en utilisant le portail B, ou via la salle 1 en empruntant les portails A et C. On peut aussi se déplacer sur une cellule sans emprunter le portail qui s'y trouve. En l'absence de portail, il n'y a aucune façon de se rendre d'une salle à l'autre.

Le nombre de salles contenues dans chaque univers n'est pas connu à l'avance par l'agent, tout comme le nombre de portails et les tailles des salles.

Structure du programme

Un squelette de départ est disponible dans tp2.zip.

Syntaxe d'appel du programme tp2

Votre programme doit pouvoir être lancé en ligne de commande avec la syntaxe suivante : 

./tp2 univers.txt [requetes.txt]

où univers.txt est le nom du fichier décrivant l'univers (salles et portails), et requetes.txt (optionnel) est le nom du fichier contenant les requêtes.

Si requetes.txt est spécifié, alors votre programme doit lire dans requetes.txt au moyen d'un flux de lecture C++ std::ifstream. Sinon, votre programme doit lire dans l'entrée standard (stdin) au moyen du flux d'entrée C++ std::cin. À noter que cette fonctionnalité est déjà implémentée dans le squelette de départ.

Format d'un fichier d'univers

Un fichier d'univers contient une liste de salles, suivie d'une liste de portails. Un portail est représenté par les deux cellules qu'il relie, séparées par une flèche bilatérale. Pour chaque cellule, on donne le numéro s (id) de salle suivi de la position (i,j) dans la salle. Par exemple, le fichier univers0.txt ci-bas décrit l'univers de l'exemple de la section "Contexte". 

carre 4
diamant 5
triangle 7
-----
0 (1,0) <--> 1 (0,2)
0 (0,3) <--> 2 (0,6)
1 (3,3) <--> 2 (3,3)

Le numéro d'une salle devrait être son indice dans le tableau, considérant qu'on ajoute chaque nouvelle salle à la fin du tableau en lisant le fichier d'univers. Les numéros de salles doivent être corrects pour correspondre à ceux des portails lus en entrée.

Format d'un fichier de requêtes

Une requête est constituée de deux cellules, sur le même modèle que dans le fichier d'univers. La première cellule est le point de départ d et la seconde le point d'arrivée a dans l'algorithme principal. Par exemple, le fichier univers0-req0.txt ci-dessous contient deux requêtes (une par ligne). 

0 (3,0) --> 2 (2,3)
1 (2,1) --> 2 (0,0)

Format de sortie

Pour chaque requête, votre programme doit écrire sur une ligne le nombre de chemins possibles permettant de se rendre de d à a sans passer deux fois par une même cellule.

Le résultat de la commande ./tp1 univers0.txt univers0-req0.txt produit le résultat suivant :

6050
45370

Algorithme principal

Pour chaque requête, il suffit de chercher tous les chemins possibles de d à a et incrémenter un compteur nbChemins chaque fois qu'on en trouve un nouveau. La variable nbChemins peut être une variable globale ou une référence int& passée en paramètre de la fonction. Afin de ne pas passer plus d'une fois par une même cellule dans un même chemin, on utilise un marqueur visité (voir section 3.7).

Algorithme général pour une requête :

nombreChemins(Cellule d, Cellule a)
  si d et a sont dans l'univers:
    nbChemins ← 0
    d.visité ← vrai
    nombreCheminsRec(d, a)
    retourner nbChemins
  retourner -1

nombreCheminsRec(Cellule c1, Cellule c2)
  si c1 == c2:
    nbChemins ← nbChemins + 1
  sinon:
    pour chaque v dans les voisins de c1  // voir section 3.6
      si v.visité == faux:
        v.visité ← vrai
        nombreCheminsRec(v, c2)
        v.visité ← faux
Notes : si d ou a n'est pas dans l'univers, on retourne -1. Si d == a (dans l'univers) alors on considère que le nombre de chemins est 1. C'est ce qu'on obtient avec l'algorithme ci-dessus.

Voisins

Les voisins de c1 sont les cellules adjacentes à c1 dans la salle où elle se trouve, telles que décrites à la section 2, ainsi que la cellule liée à c1 par un portail le cas échéant (s'il y a un portail sur c1). Une cellule aura donc entre 0 et 5 voisines, selon la présence ou non d'un portail, et selon que les positions adjacentes sont valides ou non dans la salle.

Marqueurs visité

La solution la plus simple est d'avoir une variable booléenne visite dans la struct Cellule. Évidemment, il ne faut pas oublier de remettre la variable visite à false au début ou à la fin de l'algorithme. Le mot clé mutable dans la déclaration permet de rendre une variable «modifiable» même si elle est modifiée dans un contexte constant. Par exemple, les paramètres de la fonction nombreChemins() peuvent être des références constantes, et tout attribut mutable pourra quand même être modifié. On utilise typiquement ce mot pour des variables d'instance ne servant qu'à des algorithmes particuliers (ceci sera vu plus en détail au lab11).

Contraintes

Bibliothèques permises

L'objectif est d'appliquer votre propre classe générique Tableau au TP2. En théorie, vous pourriez utiliser la classe Matrice faite au TP1. Or, pour les salles de types Diamant et Triangle, cela impliquerait un gaspillage de mémoire, car certaines cellules de la matrice ne seraient pas utilisées. La consommation mémoire de vos programmes sera évaluée (un des critères dans le critère B de la grille de correction), et pour cette raison, il vous est fortement recommandé d'utiliser votre classe Tableau pour ce TP.
L'utilisation des conteneurs de la bibliothèque standard de C++ (ex.: std::vector ou std::list) et de la bibliothèque algorithm (#include <algorithm>) est permise, mais sujette à pénalités (voir critère F dans la grille d'évaluation).

Environnement de développement

Relisez les Politiques et les directives sur les outils informatiques dans le cours INF3105. Votre TP2 doit pouvoir être compilé avec g++ version 11 (version installée sur le serveur java.labunix.uqam.ca).

Taille des équipes

Vous pouvez faire ce travail en équipe de 1 ou 2. Toutefois, tous les membres de l'équipe doivent contribuer à l'ensemble du travail et non à seulement quelques parties. Le travail d'équipe vise à favoriser les discussions et l'entraide. Le travail d'équipe ne vise pas à réduire la tâche. Ainsi, se diviser la tâche en deux n'est pas une méthode de travail d'équipe appropriée dans ce cours. La participation inadéquate des membres de l'équipe peut être considérée comme du plagiat. Le professeur et le correcteur pourront sélectionner quelques équipes au hasard afin de vérifier que tous les membres sont capables d'expliquer l'ensemble du travail.

Tests

Des tests sont fournis avec le squelette de départ dans tp2.zip.

Pour lancer les tests, lancez le script evaluer.py sur une machine Linux. Notez que le package time doit être installé, ce qui est généralement le cas par défaut. Vous pouvez par exemple vous connecter sur le serveur java : 

ssh codeMS@java.labunix.uqam.ca
Que vous soyez sur java ou votre propre machine Linux, suivez les instructions suivantes : 
cd tp2
make
unzip tests.zip
cd tests
g++ -O3 -o valideur valideur.cpp
cd ..
./tests/evaluer.py
Voici un exemple de résultat d'exécution (sur java) : 
Évaluation du programme tp2 d'INF3105
Mode etudiant_evaluer
Nom_test	CPU	Mém	nbReqs	nbExistenceOK	NbCheminsOK
C1_1c-req0	0.00	3524	20	20	20
C1_1d-req0	0.00	3484	15	15	15
C1_1t-req0	0.00	3516	15	15	15
C1_2-req0	0.02	3368	10	10	10
C1_3-req0	0.22	3444	10	10	10
C1_4-req0	0.21	3532	10	10	10
C1_5-req0	20.25	3528	10	10	10
C1_6-req0	39.61	3440	10	10	10
...
C2_9-req0	2.02	3468	10	10	10
...
C3_5-req0	0.02	3432	10	10	10
C4_1-req0	112.16	3440	20	20	20
...
C4_6-req0	4.43	3660	15	15	15

Signification des colonnes:

Notez que l'exemple donné dans l'énoncé n'est pas le plus simple pour commencer. Les fichiers sont nommés en référence au critère C de la grille de correction (section 7.1). Les trois premiers fichiers (commençant par "C1_1") contiennent respectivement 1 carré, 1 diamant et 1 triangle, afin de tester votre représentation pour chaque forme, sur une salle sans portail.

Remise

Vous devez au plus tard le 16 juin 2024 à 23h59m59s EST (heure de Montréal) :

  1. remettre votre travail via le formulaire de remise du TP2,
  2. répondre aux questions sur l'analyse et la complexité via le questionnaire du TP2.

Fichiers à remettre:

  1. tp2.zip: fichier ZIP contenant tous vos fichiers sources (*.{h,cpp}) et votre fichier Makefile (incluant ceux que vous n'avez pas modifiées par rapport au squelette de départ).

Vous pouvez soumettre votre TP et les réponses au questionnaire autant de fois que vous voulez. Seule la dernière soumission sera considérée.

Évaluation

Ce travail pratique compte pour 10% de la note finale.

Grille de correction

Critère Description Points
A. Respect des directives pour la remise
  • Fichiers sources seulement (ex.: .h, .cpp, Makefile). Aucun fichier source manquant (les fichiers fournis doivent être soumis, même si non modifiés). Aucun fichier binaire (ex.: .o, .obj, .gch, exécutable, etc.). Aucun fichier test. Aucun fichier caché.
  • Remise par le formulaire Web. Pas de remise par courriel.
  • Compilable avec make sans modification.
  • Exécutable sans modification.
 10
B. Appréciation générale
  • Structure du programme + Qualité du code :
    • Découpage du programme (tout n'est pas dans la fonction main()); pas de fonction trop longue; éviter la duplication de code.
    • Choix des types de données; identificateurs (noms) significatifs, lisibilité du code, pertinence des commentaires; etc.
    • Justesse de l'usage du mot clé const, des références (&) et des pointeurs (*).
  • Encapsulation :
    • Respect des principes de l'abstraction;
    • Cachez le maximum de la représentation des objets en rendant un maximum d'attributs privés;
    • Évitez autant que possible les bris d'abstraction, comme des getters et setters qui retournent ou affectent directement des attributs d'un type abstrait de donnée. Par exemple, les fonctions getX() et getY() ne devraient pas exister dans une classe Point. Mais, une fonction getNom()dans une classe Region peut être justifiée/tolérée.
    • Utilisation appropriée des modificateurs d'accès public, protected et private, et du mot clé friend, etc.
  • Gestion de la mémoire:
    • Toute la mémoire allouée dynamiquement doit être correctement libérée au moment approprié et avant la fin du programme.
    • Éviter de consommer inutilement de la mémoire (e.g., en utilisant un objet Matrice pour stocker les salles Triangle et Diamant plutôt qu'un objet Tableau).
 20
C. Fonctionnement correct
Le programme retourne les bons résultats :
  • C1: Détecte correctement s'il existe au moins un chemin dans un univers avec une seule salle et aucun portail. (5 point)
  • C2: Détecte correctement s'il existe au moins un chemin dans un univers avec plusieurs salles et des portails. (15 points)
  • C3: Retourne le bon nombre de chemins dans un univers avec une seule salle et aucun portail. (15 points)
  • C4: Retourne le bon nombre de chemins dans un univers avec plusieurs salles et des portails. (15 points)
Pour C1 et C2, le nombre affiché doit être >0 s'il y a au moins un chemin, 0 sinon (ou -1 si hors univers).

L'efficacité n'est pas directement évaluée. Cependant, l'efficacité peut être indirectement évaluée lorsqu'un programme ne parvient pas à produire des résultats dans des délais raisonnables. Votre programme doit également consommer une quantité de mémoire raisonnable.

50
D. Exactitude de l'auto-évaluation déclarée dans le formulaire de remise
Vous déclarez que votre programme fonctionne
Correctement Partiellement Aucunement (Déclaration absente)
À la correction, votre programme fonctionne correctement (C=50) 1 0.5 0 0
À la correction, votre programme fonctionne partiellement (0<C<50) 0.5 1 0.5 0
À la correction, votre programme ne fonctionne aucunement (C=0) 0 0 1 0

Attention : les tests fournis ne sont pas nécessairement ceux qui seront utilisés pour la correction. De nouveaux tests pourront être utilisés.

10
E. Analyse et complexité
Réponses correctes au questionnaire du TP2. 		10

Total 100
F Non-respect de la contrainte 4.1 «Bibliothèques permises»

Voir Section 4.1 «Bibliothèques permises» plus haut. Par exemple, utilisation de std::vector plutôt que Tableau. Jusqu'à 10 points peuvent être retranchés.

-10

Pénalités

Crédits et licences