Le labyrinthe de Dédale
Cet énoncé a été modifié le 21/04/2016. Le système de navigation a été recodé et déplacé (a priori, il fonctionne bien, mais on n'est pas à l'abri d'une erreur...), et la réponse à donner contient des éléments supplémentaires (pour éviter le bruteforce)

Histoire

Dédale est principalement connu aujourd'hui pour avoir été l'architecte d'un labyrinthe qui enferma le Minotaure.

Mais ce que l'histoire oublie souvent de dire, c'est que le labyrinthe n'a pas été initialement construit pour cela. En effet, le labyrinthe n'était au départ qu'une attraction comme une autre du parc 'Dédale Land'.

Le principe était simple : trouver la sortie. Ariane, responsable de l'attraction, fournissait aux visiteurs un fil accroché à l'entrée du labyrinthe qui leur permettait de faire marche arrière si besoin. Dédale, voulant maximiser ses profits, demanda à Ariane de ne fournir que la longueur de fil nécessaire et pas plus !

Défi

Pouvez-vous aider Ariane à déterminer la longueur de fil nécessaire ?

Dédale, comptant chaque drachme, n'a pas considéré nécessaire de remettre en route l'éclairage du labyrinthe pendant votre travail ; vous allez donc vous déplacer à l'aveugle dans le labyrinthe.

Chaque déplacement dans le labyrinthe comptera pour 1 mètre et vous pourrez obtenir les informations de déplacement à cette adresse.

La longueur de fil doit permettre de sortir par toutes les sorties du labyrinthe

Pour valider le défi, vous devez indiquer deux valeurs :
  • la longueur de fil nécessaire pour qu'on puisse sortir par n'importe quelle sortie du labyrinthe, à condition de s'y prendre au mieux
  • la longueur de fil nécessaire pour sortir par la sortie la plus proche

Testez votre code

Le labyrinthe pour enfants est le numéro 0 et son entrée a pour identifiant : 60dd2d0d-2faa-4611-9b9d-36afbcfad324. En utilisant l'url donnée en entrée du problème, vous pourrez voir tous les paramètres possibles. Pour chaque déplacement vous devez au minimum fournir les 3 paramètres suivants : maze (le numéro du labyrinthe), from (l'identifiant de la position de départ) et to (l'identifiant de la position d'arrivée).

Pour votre premier déplacement, il vous suffit de faire du sur place et d'indiquer l'entrée à la fois comme source (from) et comme destination (to). L'adresse pour obtenir les informations (n'oubliez pas que vous ne voyez rien et que vous vous déplacez à tâtons) est la suivante.

A partir de là, vous pouvez suivre les étapes suivantes :
  • La première adresse vous indique les 3 emplacements adjacents :
    • 5ac5d9ed-531b-4205-ba84-898022c2cd77
    • c5c4d2df-8164-48ee-ae27-dbf382762042
    • 6b58ae96-9924-4b0b-a6dc-f33aa8711b17
    Vous les testez donc les uns après les autres.
  • Vous tâtez dans la première direction via ce lien et tombez sur un mur. Idem avec la deuxième.
  • La troisième vous permet d'avancer et vous découvrez 4 nouvelles positions :
    • 60dd2d0d-2faa-4611-9b9d-36afbcfad324
    • 23b2fe49-9c6f-4fc8-971e-fa1614d875e5
    • e712c09d-c358-4e1c-a81c-9a1190ea1a50
    • 145ad7f2-710c-4b84-a4c0-a8ab45092831
  • De ces 4 nouvelles positions, la première est celle d'où vous venez, il vaut mieux pour vous éviter de rebrousser chemin...
  • Après avoir rencontré deux nouveaux murs ici et , vous atteignez enfin la sortie.

Il faut 2 déplacements pour joindre l'unique sortie, qui est donc à une distance 2. Puisqu'il y a une seule sortie, les deux valeurs à donner (voir l'encadré plus haut) sont les même. La réponse à donner dans ce cas serait donc :

        2, 2
        
Ce problème est tiré de c0d1ng UP 2015

Type de retour

une séquence de deux nombres entiers

Entrée du problème

  • url : "maze"
  • maze : 1
  • entree : '637b4e0c-a38a-47c1-b133-01ed0235c187'

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup15 récursivité defiweb parcours