Il est temps pour un autre défi de labyrinthe, mais pas comme vous le savez.
Les règles de ce défi sont un peu différentes de la plupart des défis de labyrinthe. Les types de tuiles sont définis comme suit:
S: L'emplacement sur le labyrinthe où vous commencezE: L'endroit où vous essayez de vous rendre0: Mur que vous ne pouvez pas traverser+: Plancher que vous pouvez traverser
Vous pouvez voyager dans l'une des six directions: haut-gauche, haut-droite, gauche, droite, bas-gauche ou bas-droite.
\ /
-S-
/ \
Le labyrinthe ne s'enroule pas. Le but est de trouver la chaîne de chemin la plus courte pour aller de Sà E.
Contribution:
L'entrée est des lignes séparées par des espaces comme les labyrinthes montrés. Aucun espace de fin ne suivra une ligne.
Sortie:
Une chaîne de R, Let Foù
Rvous fait pivoter à droite (dans le sens des aiguilles d'une montre) de 60 degrésLvous fait tourner à gauche (dans le sens antihoraire) de 60 degrésFvous déplace d'un espace dans la direction vers laquelle vous pointez
Vous commencez à pointer left-up
Le chemin le plus court est compté par la longueur de la chaîne produite et non par le nombre de positions visitées. Votre programme doit imprimer le chemin le plus court comme solution.
Si le labyrinthe est insoluble, vous devez sortir Invalid maze!.
( >>>est la sortie)
0 0 0 0
0 + 0 + 0
0 0 0 + + 0
0 + 0 + 0 + 0
0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
E 0 + 0 0 + + 0
+ + 0 + 0 + 0
0 0 0 0 0 +
+ 0 + + +
0 S 0 0
>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
+ 0 0 0 0 0 0
0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
0 0 0 0 0 0 0 +
0 + 0 0 + + +
0 0 + + 0 0
S + 0 0 0
>>>Invalid maze!
0 E S
>>>LF
E + 0
0 + + +
0 0 S
+ +
>>>FFLF
E
0 +
0 + +
0 +
S
>>>RFFLFF
0 E + 0 0
0 + 0 0 + +
+ 0 + + + 0
+ 0 + 0 + 0
+ + + 0 S
>>>FFLFLFFRFRFFRFF
E 0 + + 0
0 + 0 + + 0
+ + + 0 + 0
+ 0 0 0 0 0
+ + + + 0
+ 0 S 0
>>>FLFFRFFRFLF
(Notez que certains labyrinthes ont d'autres solutions qui sont de la même longueur mais ne sont pas répertoriées ici)
la source
Réponses:
Python 2, 291 octets
Une fonction,
fprenant le labyrinthe comme une liste de lignes et renvoyant une solution, si elle existe.Explication
Effectue une recherche en premier sur le graphique des paires position / direction pour trouver le chemin le plus court de
SàE.Ce qui est intéressant, c'est de trouver un moyen compact de représenter les positions et les directions sur une grille hexagonale, qui admet un simple «pas» (c'est-à-dire se déplacer dans une certaine direction) et une rotation. Il est tentant d'utiliser des nombres complexes ici, pour représenter des coordonnées sur une "vraie" grille hexagonale, mais ce n'est pas une très bonne idée pour un certain nombre de raisons, la plus sérieuse étant le fait que nous devons brancher un √3 quelque part pour le faire fonctionner (sin 60 ° = √3 / 2), ce qui, lorsque vous utilisez des nombres à virgule flottante, est un pas si nous avons besoin d'une précision absolue (par exemple, pour garder une trace des états que nous avons déjà visités;) vous pouvez essayer de lancer votre console JavaScript et de taper
Math.sqrt(3)*Math.sqrt(3) == 3et voyez par vous-même.Mais, nous pouvons utiliser une petite astuce! Au lieu d'utiliser des nombres complexes, définissons des nombres hexagonaux dans une veine similaire, comme une paire de nombres réels a + bh , où h joue un rôle similaire à l'imaginaire i lorsqu'il s'agit de nombres complexes. Tout comme avec les nombres complexes, nous pouvons associer la paire ( a , b ) à un point sur le plan, où l'axe réel pointe à droite, l'axe imaginaire pointe à 60 ° vers le haut, et ils croisent tous les deux l'hexagone régulier de l'unité lorsque le réel et le les parties imaginaires sont égales à 1, respectivement. Le mappage de ce système de coordonnées aux cellules du labyrinthe est trivial.
Contrairement à i , la constante h est définie par la relation h 2 = h - 1 (la résolution de h pourrait révéler certaines informations.) Et c'est tout! Les nombres hexagonaux peuvent être ajoutés et multipliés, en utilisant la relation ci-dessus, un peu comme les nombres complexes: ( a + bh ) + ( c + dh ) = ( a + c ) + ( b + d ) h ,
et ( a + bh ) · ( c + dh ) = ( ac - bd) + ( ad + bc + bd ) h . Ces opérations ont la même interprétation géométrique que leurs homologues complexes: l'addition est l'addition vectorielle, et la multiplication est l'échelle et la rotation. En particulier, pour faire pivoter un nombre hexagonal de 60 ° dans le sens antihoraire, on le multiplie par h :
( a + bh ) · h = - b + ( a + b ) h , et pour faire tourner le même nombre de 60 ° dans le sens horaire, on divise par h :
( a + bh ) / h = ( a +bh ) · (1 - h ) = (a + b) - ah . Par exemple, nous pouvons prendre le nombre hexagonal unitaire pointant vers la droite, 1 = (1, 0), un cercle complet, dans le sens antihoraire, en le multipliant par h six fois:
(1, 0) · h = (0, 1 ); (0, 1) · h = (-1, 1); (-1, 1) · h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).
Le programme utilise des nombres hexagonaux de cette manière pour représenter la position actuelle dans le labyrinthe et la direction actuelle, pour avancer dans la direction spécifiée et pour faire pivoter la direction vers la gauche et vers la droite.
la source
Hexagonie , 2437 octets
Le programme tant attendu est ici:
Essayez-le en ligne!
Version "lisible":
Testé sur IDE ésotérique: TIO peut expirer sur certains des cas de test les plus importants mais tous vérifiés. Merci beaucoup à Timwi, cela n'aurait pas été possible sans l'IDE.
Il y a un peu d'espace vide, donc j'aurais peut-être pu l'ajuster sur un hexagone de côté 28 (au lieu de 29 de côté), mais ce sera une tâche énorme, donc je ne vais probablement pas essayer.
Explication de base
Cliquez sur les images pour une version plus grande et plus détaillée.
Les fonctions
Remarque: Les divisions sont généralement correctes, mais peuvent parfois être approximatives.
Ce code est assez "fonctionnel" - autant que Hexagony le permet. Il y a huit fonctions principales dans ce code étiquetées dans le diagramme ci-dessus, nommées par les numéros avec lesquels elles sont appelées (donc leurs numéros de pointeur d'instructions sont ce numéro mod 6). Dans l'ordre (approximatif) d'appel, ils sont (les noms cités sont des emplacements en mémoire qui seront expliqués plus loin):
F,Ret estLprête pour le traitement principal. Le pointeur d'instruction 0 passe à la fonction 0 tandis que l'exécution passe à la fonction 1.+mouvement dans les 2 premiers mouvements. Retourne à la fonction 1.F. Retourne à la fonction 1.F,RsoitLajouté. Retourne à la fonction 1.FFLF), puis termine le programme.Invalid maze!et se termine.Mémoire
Remarque: Merci encore à Esoteric IDE pour le diagramme
La mémoire se compose de trois parties principales:
0soit un lieu valide auquel on a accédé il y a plus de coups qu'il ne faudrait pour quitter le lieu dans n'importe quelle direction.+qui n'a pas encore été atteint.-1s avec un seul-2sur la gauche, permet au pointeur de mémoire de revenir rapidement à la zone de traitement principale.F,R,Lcomme1,2,3respectivement-1s à droite puis y valeurs vers le haut (bien que y = 0 soit traité comme 1 de toute façon afin de séparer le rail des données de référence)Autres emplacements de mémoire importants:
Eest stocké ici.la source
Python 3, 466 octets
Aurait probablement fini plus petit si j'avais utilisé la recherche en profondeur d'abord ou quelque chose comme ça. Cette monstruosité utilise Dijkstra et est assez rapide, mais très longue.
Le code définit une fonction
Squi prend une chaîne multiligne avec le labyrinthe et renvoie le résultat.Voici un test du code.
Non golfé
la source
L,,R.Groovy, 624 octets. Fore!
Il est temps de faire rouler la balle avec une grosse. Prend la chaîne multiligne comme argument pour
QVersion non golfée:
la source
C #,
600574 octetsProgramme complet, accepte les entrées de STDIN, les sorties vers STDOUT.
Edit: il y avait un bug dans la gestion de l'habillage (ne s'est cassé sur aucun des cas de test donnés) qui aurait ajouté 1 octet, j'ai donc fait un peu plus de golf pour compenser.
Il commence par lire la carte, en ajoutant
(à chaque ligne pour qu'il sache où elle se termine, et peut revenir en arrière et ajouter une charge d'espaces pour rendre la carte rectangulaire, et avec une rangée d'espaces sur le côté droit (cela économise nous effectuons des contrôles d'emballage comme expliqué ci-dessous). Il calcule la largeur du rectangle à un moment donné et détermine la longueur totale de la carte.Ensuite, il initialise tout pour une recherche en largeur. Deux tableaux biggish sont créés, l'un pour stocker tous les états que nous devons explorer dans notre recherche, l'autre pour enregistrer l'itinéraire que nous avons emprunté pour arriver à chaque état. L'état initial est ajouté au tableau dû, avec les pointeurs de tête et de queue prédéfinis quelque part au-dessus. Tout est indexé 1.
Nous répétons ensuite jusqu'à ce que la queue s'écrase dans la tête, ou du moins, elle semble s'être écrasée dans la tête. Pour chaque état que nous avons visité, nous essayons d'ajouter un nouvel état à la même position où nous sommes tournés à gauche ou à droite, puis un où nous avons avancé. Les directions sont indexées, la direction initiale (par défaut à
0) correspondant à "haut-gauche".Lorsque nous essayons de mettre en file d'attente un état, il est vérifié, mais pas encapsulé, en raison des colonnes d'espaces sur le côté droit, qui sont reprises par le "sommes-nous autorisés à être ici?" vérifier (vous n'êtes pas autorisé à être sur les espaces). Si l'état est mis en file d'attente, nous vérifions ensuite s'il se trouve dans la
Ecellule, et si c'est le cas, nous définissons la tête de la file d'attente comme étant elle-même moins, ce qui provoque la sortie de la boucle principale et indique à la dernière ligne du programme d'imprimer sur l'itinéraire correspondant, plutôt que sur le message d'échec (qui montre si nous manquons d'états pour nous développer (la queue s'écrase dans la tête)).Comme la plupart de mes recherches de graphiques sur ce site, je fais bon usage des structures C #, qui par défaut sont comparées par valeur littérale.
la source
Python 2, 703 octets
Pas aussi bon que les deux autres versions, mais au moins ça marche haha. Mis
Mau labyrinthe.Comme je n'ai aucune expérience dans la résolution de labyrinthes, cela passe simplement par une approche par force brute, où il trouvera toutes les solutions possibles sans impliquer un retour en arrière sur lui-même. Il calcule les virages à partir des plus courts, puis choisit le résultat le plus court à partir de cela.
Version désordonnée désordonnée:
la source
if heading != required_heading: while heading != required_heading:par justewhile heading != required_heading: