Detective Pikaptcha

Pour résoudre ce puzzle, il m'a d'abord semblé indispensable de disposer de l'intégralité du labyrinthe sous forme de tableau à deux dimensions. En effet, puisque le labyrinthe est renseigné ligne par ligne, afin d'étudier si une case dispose d'un espace libre à sa verticale il faut nécessairement garder l'information des lignes suivantes et précédentes.

Pour ce faire, j'ai créé un tableau de façon dynamique afin de ne pas utiliser plus d'espace que nécessaire que j'ai ensuite rempli ligne après ligne avec les lignes du labyrinthe donné en entrée.

Une fois le labyrinthe stocké sous forme de tableau à deux dimensions, il est assez simple de déterminer le nombre de passages juxtaposés à chaque case vide.

Pour ce faire, je parcours chaque case 0 du tableau grâce à une double boucle for. Puis, pour chaque case parcourue, je compte le nombre de cases voisines dont la valeur est différente de # et j'écrase la valeur de la case actuellement analysée par ce nombre.

Une fois le tableau modifié, il ne reste plus qu'à l'afficher ligne par ligne.

Enfin, je termine mon programme en libérant la mémoire allouée à mon tableau en début de programme.

Pour garder en mémoire les données du labyrinthe, mzbear utilise lui aussi un tableau de deux dimensions. Cependant puisque les contraintes du puzzle n'imposent pas de devoir stocker un tableau de plus de 100 cases, il se contente de déclarer un tableau de 101 cases. Puis, il initialise son tableau ligne par ligne en lisant les lignes entrées.

Notons qu'il évite le fait que son programme essaie de stocker une ligne plus longue que le largeur de son tableau en typant sont entrée à lire par 100s. Ainsi, dans le cas où l'utilisateur entre une ligne plus longue que la largeur du tableau qu'il a déclaré, le programme ne lira que les 100 premiers caractères.

Pour effectuer des tests sur chaque case de son tableau, mzbear utilise une double boucle for.

Pour effectuer ses tests sur les cases du tableau, il utilise les mêmes conditions et opérations que moi, néanmois je trouve que l'utilisation de l'instruction continue et l'alignement des tests suivants rendent le code bien plus lisible que ne peut l'être le mien.

Pour finir, mzbear affiche ligne après ligne son tableau modifié. Notons que chaque ligne aurait aussi pue être affichée juste avant de sortir de la double boucle for, juste après avoir été modifiée.

Pour travailler sur ce puzzle, il m'a d'abord fallu comme pour l'épisode 1, stocker l'intégralité du labyrinthe sous forme d'un tableau à deux dimensions.

Pour ce faire j'ai de la même façon créé un tableau alloué dynamiquement grâce à des malloc que j'ai directement rempli ligne après ligne par les lignes données en entrée et lues par un scanf de l'intégralité de la chaine de caractère.

Ainsi je pouvais disposer d'une représentation sous forme de tableau du labyrinthe auquel il fallait encore effectuer quelques opérations avant de pouvoir travailler sur les déplacements du personnage.

Avant de travailler sur les déplacements du personnage, il me fallait d'abord déterminer sa position ainsi que son orientation de départ dans le labyrinthe puisque ces informations ne sont données qu'implicitement par la position d'un des caractères {>,v,<,^} dans le labyrinthe.

Pour détecter l'emplacement de l'un de ces caractère j'ai créé une double boucle for permettant de parcourir l'intégralité du tableau tant que l'on ne rencontre pas l'un des caractères {>,v,<,^}

En revanche si l'un de ces caractères est rencontré, il est stocké dans une variable de même que sa position dans le tableau, puis ce caractère est remplacé par un 0 dans le tableau.

Afin de parcourir le tableau en faisant longer un mur au personnage, il m'a semblé qu'un protocole récursif était la solution qui se prêtait le mieux à la situation.

Ainsi j'ai créé un protocole explore que l'on peut décomposer en trois parties:

• D'abord une condition qui teste si le protocole a été appelé 4 fois sans que le personnage n'eut eu la possibilité de se déplacer d'une case, auquel cas la variable first passe à 0, ce qui aura pour effet de sortir de la récursive.
• Ensuite le protocole comporte un deuxième test qui vérifie si la position du personnage est la même que sa position de départ l'ayant déjà quitté ou étant bloqué. Si ce test est vrai, alors on quitte la récursive.
• Enfin, le coeur de la récursive vérifie si pour une certaine orientation, position et mur à suivre, le personnage peut se déplacer du coté du mur qu'il doit suivre. S'il le peut on incrémente la case où il était puis on rappelle la récursive avec une nouvelle position et orientation du personnage. Dans le cas contraire, on rappel la récursive en réorientant le personnage dans le sens inverse du mur à suivre.

Enfin, une fois que les modifications sur le tableau ont été effectuées, il ne reste plus qu'à afficher le dît tableau.

Ainsi, de la même manière que pour l'épisode 1, une simple boucle permet d'afficher le tableau modifié ligne après ligne tout en libérant l'espace alloué à chaque ligne juste après leur affichage.

Pour ce qui est du stockage des entrées, mzbear utilise le même procédé que pour l'épisode 1, à savoir de stocker l'intégralité du labyrinthe dans un tableau de deux dimensions.

En revanche, pour déterminer la position ainsi que l'orientation de départ du personnage, il utilise une solution semblable à la mienne mais mise en place différemment. En effet, grâce à la fonction strchr(const char \*str, int c), qui renvoie NULL si le caractère c n'est pas trouvé dans str il peut déterminer à quel moment un des caractères est trouvé dans le tableau et quitter la double boucle for grâce à un goto.

Puis il sauvegarde la position de départ ainsi que l'orientation dans des variables afin de plus tard déterminer si son personnage est de retour à sa case départ.

Si jusqu'ici mzbear a proposé des solutions semblables aux miennes si ce n'est dans l'utilisation d'astuces de programmation différentes, la méthode qu'il utilise pour parcourir son tableau est particulièrement remarquable puisqu'elle ne se compose que d'une dizaine de lignes là où beaucoup, ont comme moi utilisé des méthodes bien plus longues.

Tout d'abord, il définit un entier p égal à la position du caractère de départ du personnage dans la chaine ">v<^", ainsi qu'un tableau de \(2\times 4\) contenant les 4 déplacements d'ne case possible.

Puis, il détermine si en effectuant un déplacement correspondant à la ligne p du tableau précédemment définie, le personnage se situe sur une case vide du tableau. Si c'est le cas, il effectue ce déplacement en modifiant la valeur de p, sinon il modifie seulement la valeur de p. Aussi, ces opérations sont répétées tant que la position actuelle ne correspond pas à la position de départ du personnage.

Nous pouvons finalement remarquer que cette solution effectue les mêmes actions que mon protocole récursif sur le personnage. En revanche cette solution est bien meilleure puisqu'en plus d'être plus courte, elle est plus générale que la mienne, mzbear a codé un seul protocole qui s'adapte à tous les tests qui nous sont soumis tandis que j'ai divisé le problème en sous-cas.

Le premier test est un petit labyrinthe assez simple de dimension \(6\times\ 3\), il permet de vérifier que les deux programmes réalisent bien la tâche voulue:

Le résultat par le premier programme est bien celui auquel on pouvait s'attendre, chaque case qui n'est pas un mur comporte bien le nombre de passages adjacents.

Le résultat par le second programme est le même que celui renvoyé par le premier programme, ce qui est logique puisque chaque case vide du labyrinthe est toujours collée à un mur. Ainsi, le personnage passe bien par toutes les cases du labyrinthe.

Le deuxième test que j'ai sélectionné est intéressant car il permet de mettre en évidence la différence de fonctionnement entre les deux programmes.

En effet, ce labyrinthe de \(9\times\ 3\) cases est composé de deux pièces liées par un couloir de 1 case de largeur:

Par le premier programme, on constate que toutes les cases du labyrinthe comportent bien le nombre de passages adjacents.

En revanche, pour ce qui est du résultat renvoyé par le deuxième programme, on constate que la "pièce" de droite du labyrinthe n'a pas du tout été parcourue par le personnage car en longeant le mur, il retombe sur sa case de départ avant d'arriver au niveau de la "pièce" de droite.

Ainsi, contrairement au résultat renvoyé par le premier programme, toutes les cases du labyrinthe ne contiennent pas le nombre de cases adjacentes.

Enfin, le dernier test que j'ai sélectionné est un labyrinthe de \(10\times\ 6\) cases, ayant la particularité d'avoir certaines de ses cases vides qui ne sont pas collées à un mur.

Ainsi, comme l'on pouvait s'y attendre, le résultat renvoyé par le premier programme est bien un labyrinthe dans lequel toutes les cases du labyrinthe comportent bien le nombre de passages adjacents.

En revanche, le résultat renvoyé par le deuxième programme contient des cases dont la valeur est toujours égale à 0 même si contrairement au deuxième test, elles ne sont pas dans une "pièce" dans laquelle le personnage n'est pas passé.

Ceci s'explique par le fait que ces cases ne sont pas collées à un mur que le personnage a parcouru, et que de ce fait n'ont pas été affectés par son passage.