La vie est un labyrinthe: nous prenons le mauvais chemin avant d'apprendre à marcher

30

Contribution:

Un labyrinthe contenant les personnages:

  • -- (mur horizontal);
  • | (mur vertical);
  • + (connexion);
  • (espace de marche);
  • I (entrée);
  • U (sortie).

C'est-à-dire qu'une entrée pourrait ressembler à ceci:

 +--+--+--+--+--+--+--+--+--+--+ 
I               |     |        | 
 +  +--+--+--+  +  +  +  +--+  + 
 |           |     |  |  |     | 
 +--+--+--+  +--+--+  +  +  +--+ 
 |           |     |     |     | 
 +  +--+--+  +  +--+--+  +--+  + 
 |     |     |     |     |     | 
 +--+  +  +--+--+  +--+--+  +  + 
 |     |        |        |  |  | 
 +  +--+--+--+  +--+--+  +  +  + 
 |     |     |     |        |  | 
 +--+  +  +--+--+  +--+--+--+--+ 
 |  |  |                 |     | 
 +  +  +--+--+--+  +--+  +  +  + 
 |     |        |  |  |  |  |  | 
 +--+--+  +  +--+  +  +  +--+  + 
 |        |     |     |  |     | 
 +  +--+--+--+  +  +  +  +  +--+ 
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+

Sortie:

Le plus efficace chemin que vous devez marcher pour aller de l'entrée à la sortie du labyrinthe ( à travers le labyrinthe), indiqué par les caractères indiquant la gauche, à droite, de haut en bas (c. -à- >; <; ^; v).

Règles du défi:

  • Vous pouvez prendre l'entrée dans n'importe quel format raisonnable. Tableau de chaînes, chaîne unique avec des nouvelles lignes, tableau de caractères 2D, etc. sont tous les formats d'entrée possibles.
  • La sortie peut être composée de quatre caractères distincts. C'est à dire ><^v; →←↑↓; ⇒⇐⇑⇓; RLUD; 0123; ABCD; etc.).
  • Vous êtes autorisé à ajouter des espaces ou une nouvelle ligne à la sortie si vous préférez; c'est facultatif.
  • Les pas sont comptés par carré (voir quatre +symboles pour les carrés) et non par caractère.
  • Le labyrinthe peut être de taille 5x5 à 15x15 et sera toujours un carré (il n'y aura donc pas de cas de test pour les labyrinthes 5x10).
  • Vous pouvez supposer que chaque labyrinthe a un ou plusieurs chemins valides du début à la fin, et vous obtenez toujours le plus court (voir les cas de test 4 et 5).
  • S'il existe plusieurs chemins de même longueur, vous pouvez choisir celui à générer (voir le cas de test 6).
  • Vous ne pouvez pas «marcher» hors des frontières du labyrinthe (voir les cas de test 7 et 8).

Règles générales:

  • C'est le code-golf , donc la réponse la plus courte en octets l'emporte.
    Ne laissez pas les langues de golf de code vous décourager de publier des réponses avec des langues autres que le golf de code. Essayez de trouver une réponse aussi courte que possible pour «n'importe quel» langage de programmation.
  • Des règles standard s'appliquent à votre réponse, vous êtes donc autorisé à utiliser STDIN / STDOUT, des fonctions / méthodes avec les paramètres appropriés, des programmes complets. Ton appel.
  • Les failles par défaut sont interdites.
  • Si possible, veuillez ajouter un lien avec un test pour votre code.
  • Veuillez également ajouter une explication si nécessaire.

Cas de test:

1. Input:
 +--+--+--+--+--+--+--+--+--+--+ 
I               |     |        | 
 +  +--+--+--+  +  +  +  +--+  + 
 |           |     |  |  |     | 
 +--+--+--+  +--+--+  +  +  +--+ 
 |           |     |     |     | 
 +  +--+--+  +  +--+--+  +--+  + 
 |     |     |     |     |     | 
 +--+  +  +--+--+  +--+--+  +  + 
 |     |        |        |  |  | 
 +  +--+--+--+  +--+--+  +  +  + 
 |     |     |     |        |  | 
 +--+  +  +--+--+  +--+--+--+--+ 
 |  |  |                 |     | 
 +  +  +--+--+--+  +--+  +  +  + 
 |     |        |  |  |  |  |  | 
 +--+--+  +  +--+  +  +  +--+  + 
 |        |     |     |  |     | 
 +  +--+--+--+  +  +  +  +  +--+ 
 |           |     |  |         U
 +--+--+--+--+--+--+--+--+--+--+ 

1. Output:
>v>>>vv<v>>v>v>>vvv>>>

2. Input:
 +--+--+--+--+--+ 
I   |        |  | 
 +  +--+--+  +  + 
 |        |  |  | 
 +  +--+  +  +  + 
 |  |  |     |  | 
 +  +  +--+  +  + 
 |        |     | 
 +--+  +  +--+--+ 
 |     |         U
 +--+--+--+--+--+ 

2. Output:
>vvv>>v>>>

3. Input:
 +--+--+--+--+--+ 
U      |        | 
 +  +  +--+--+  + 
 |  |     |     | 
 +--+--+  +  +--+ 
 |        |     | 
 +  +--+--+--+  + 
 |  |     |     | 
 +  +  +  +  +--+ 
 |     |         I
 +--+--+--+--+--+ 

3. Output:
<<<^<v<^^>>^<^<<

4. Input (test case with two valid paths):
 +--+--+--+--+--+ 
U      |        | 
 +  +  +--+--+  + 
 |  |           | 
 +--+--+  +  +--+ 
 |        |     | 
 +  +--+--+--+  + 
 |  |     |     | 
 +  +  +  +  +--+ 
 |     |         I
 +--+--+--+--+--+ 

4. Output:
<<^>^<^<<^<<     (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)

5. Input (test case with two valid paths):
                               I
+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+
|     |              |                    |  |
+  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +
|  |     |        |     |        |     |     |
+--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+
|     |  |  |  |     |     |           |     |
+  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +
|  |        |        |  |     |        |     |
+  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+
|  |     |     |        |  |     |     |     |
+  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +
|  |     |        |     |           |        |
+  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+
|     |     |        |        |  |     |     |
+--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +
|              |     |     |        |  |  |  |
+  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +
|     |  |     |  |  |        |        |  |  |
+--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +
|     |     |  |  |  |           |  |     |  |
+--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +
|     |        |  |  |     |        |  |  |  |
+  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +
|        |     |  |     |     |  |     |  |  |
+--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +
|  |        |        |     |        |     |  |
+  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +
|  |              |              |     |     |
+  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+
|     |                                |     |
+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+
                            U

5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v     (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)

6. Input:
 +--+--+--+--+--+
I               |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |              |
 +  +  +  +  +  +
 |               U
 +--+--+--+--+--+

6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)

7. Input:
 I  U
+  +  +--+--+--+
|  |        |  |
+  +--+--+  +  +
|     |     |  |
+--+  +  +--+  +
|        |  |  |
+  +--+  +  +  +
|     |        |
+--+  +--+--+  +
|     |        |
+--+--+--+--+--+

7. Output:
vv>v>^>^<<^

8. Input:
 +--+--+--+--+--+
 |     |        |
 +  +--+  +--+  +
I   |     |  |  |
 +  +  +--+  +  +
U   |     |  |  |
 +--+--+  +  +  +
 |     |     |  |
 +  +--+--+--+  +
 |               
 +--+--+--+--+--+

8. Output:
>v<

Labyrinthes générés à l'aide de cet outil (et dans certains cas légèrement modifiés).

code-golf path-finding maze Kevin Cruijssen
la source
10
J'ai trouvé une solution plus courte pour le troisième cas de test! v<<<<<<^^^^^(pensez toujours en dehors des sentiers battus)
Leo
2
Si l'on peut prouver que leur code fournira la solution la plus courte, avec suffisamment de temps et de mémoire, est-il compétitif? Même dans le cas d'une durée de fonctionnement très longue (fin de la mode de l'univers)?
Yytsi
1
@JackBates C'est une blague. Il marche littéralement autour de la boîte jusqu'à la sortie: D
Yytsi
1
Je pense que le premier cas de test est faux, il devrait l'être >v>>>vv<v>>v>v>>vvv>>>.
smls
1
@KevinCruijssen Par exemple, une solution qui teste chaque combinaison de "v ^ <>" pour une longueur allant jusqu'à la quantité de boîtes vides à l'intérieur du labyrinthe. La bonne solution sera là, mais prend du temps astronomique à calculer.
Yytsi

Réponses:

7

Rétine , 338 281 275 273 261 octets

¶U
¶&
+`·(\w.+)$
|$1
((.)+I.+¶.+¶(?<-2>.)+)·
$1v
+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6
·v
-v
G`1
·U
&
{`\B·\d+.(\w+)
$1K$&
(\w+)·\d+.\B
$&$1r
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v
)`\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A
^.+\d·(\w+)
&$1A
M!`&\w+
I|&

Essayez-le en ligne!

Remarques

  • En raison des espaces blancs importants, tous les espaces ( 0x20) sont remplacés par interpunct ( ·) à la fois dans cette réponse et dans le lien TIO. Le programme fonctionne bien si les espaces sont restaurés.
  • Utilise respectivement AvKrpour haut, bas, gauche et droite. Ceux-ci peuvent être remplacés par toutes les lettres sauf I.
  • Prend environ 40s sur TIO pour le cas de test 15 × 15. Sois patient. Retravaillé la partie pour trouver le chemin le plus court une fois que le chemin a atteint la sortie. Il s'avère que cela prenait beaucoup de temps.
  • Pourrait complètement se briser sur des labyrinthes de 66 cellules ou plus de large, mais peut gérer des labyrinthes de hauteur arbitraire. Un correctif pour une largeur arbitraire prend +1 octet.

Explication

Le programme comprend 3 phases:

  • Une phase de construction pour convertir le labyrinthe en un format compact plus facile à travailler (détaillé ci-dessous).
  • Une phase de remplissage pour réellement résoudre le labyrinthe à l'aide d'un algorithme de remplissage par inondation.
  • Une phase de retour pour retourner le chemin le plus court à la sortie.

Format

Étant donné que le format original du labyrinthe est assez lourd, la première partie du programme le convertit en un format différent.

Cellules

Dans le format d'origine, chaque cellule est représentée comme une région 2 × 3:

+               <top wall>      <top wall>
<left wall>     <data/space>    <space>

Étant donné que la colonne de droite ne contient aucune information, le programme identifie les cellules comme n'importe quelle région 2 × 2 avec un +en haut à gauche.

Cela nous laisse avec 3 types de cellules:

  • I Cellules : Cellules correctement insérées dans le labyrinthe.
  • Cellules R : cellules situées à droite du labyrinthe. Ceux-ci sont créés par le rembourrage utilisé pour abriter l'entrée ou la sortie. Par exemple, la sortie Udans le cas de test 1 se trouve dans une R-Cell.
  • Cellules B : cellules situées sous le labyrinthe. Comme les cellules R, elles sont créées par remplissage.

Dans le nouveau format, les cellules sont représentées sous la forme d'une chaîne de longueur variable:

<left wall> <column number> <top wall/exit marker> <path>

Les murs gauche et supérieur sont copiés à partir du format d'origine. Le numéro de colonne est basé sur la position horizontale de la cellule et est utilisé pour l'alignement (identification des cellules directement les unes sur les autres). Le chemin est une chaîne alphabétique utilisée pendant la phase de remplissage pour enregistrer le chemin le plus court pour atteindre cette cellule. Le chemin et le marqueur de sortie seront expliqués plus en détail.

Demi-cellules

Bien que la plupart du labyrinthe soient des cellules, il existe des régions du labyrinthe qui ne sont pas des cellules:

  • R Demi-cellules : S'il n'y a pas de rembourrage droit, les +s le long du mur de droite ne forment pas de cellules car ils sont sur la dernière colonne.
  • L Demi-cellules : S'il y a un remplissage à gauche, les cellules ne peuvent pas s'y former car il n'y en a pas +à gauche. Par exemple, l'entrée Idans le cas de test 1 est dans une demi-cellule L.

Techniquement, il existe des demi-cellules T au- dessus du labyrinthe (lorsqu'il y a un rembourrage supérieur) et des demi-cellules B (le long de la paroi inférieure lorsqu'il n'y a pas de rembourrage inférieur) mais elles ne sont pas représentées dans le nouveau format.

La ligne supérieure d'une demi-cellule serait supprimée dans le cadre de la construction de cellules complètes dans la même ligne, de sorte que les demi-cellules sont représentées dans le nouveau format comme

<wall/exit marker>? <path>

Un R demi-cellules est juste |. Une demi-cellule L a juste Icomme chemin, juste le marqueur de sortie et un chemin vide, ou juste un mur vide.

Entrées et sorties

Si l'entrée se trouve à gauche, à droite ou en bas du labyrinthe, le marqueur d'entrée Iserait naturellement inclus dans la (demi-) cellule en tant que chemin, qui peut être supprimé lors du retour du chemin final.

Si l'entrée est au-dessus du labyrinthe, la première étape (vers le bas) est effectuée pendant la phase de construction puisque les demi-cellules T sont supprimées pendant la construction. Cela conserve un chemin exploitable dans une cellule pleine. Le mur supérieur est ensuite fermé.

Si la sortie se trouve à gauche, à droite ou en bas du labyrinthe, elle Userait naturellement incluse dans la (demi-) cellule. Pour éviter d'être confondu avec un chemin, le marqueur de sortie non alphanum &est utilisé à la place de U. Le marqueur de sortie est intégré dans une cellule ou une demi-cellule (comme spécifié ci-dessus).

Si la sortie est au-dessus du labyrinthe, ce serait le seul trou qui puisse aller au-dessus de la rangée supérieure de cellules (car celui de l'entrée, s'il était présent, serait déjà fermé). Tout chemin atteignant ce trou peut sortir du labyrinthe en faisant un pas vers le haut.

Enfin, toute cellule B contenant l'entrée ou la sortie doit fermer son mur gauche pour éviter de "résoudre" le labyrinthe en marchant le long des cellules B. Les entrées et les sorties dans les cellules R ou les demi-cellules L ne nécessitent aucun traitement supplémentaire, car l'algorithme de remplissage d'inondation ne permet pas les mouvements verticaux vers / depuis eux.

Exemple

A titre d'exemple, le premier cas de test

·+--+--+--+--+--+--+--+--+--+--+·
I···············|·····|········|·
·+··+--+--+--+··+··+··+··+--+··+·
·|···········|·····|··|··|·····|·
·+--+--+--+··+--+--+··+··+··+--+·
·|···········|·····|·····|·····|·
·+··+--+--+··+··+--+--+··+--+··+·
·|·····|·····|·····|·····|·····|·
·+--+··+··+--+--+··+--+--+··+··+·
·|·····|········|········|··|··|·
·+··+--+--+--+··+--+--+··+··+··+·
·|·····|·····|·····|········|··|·
·+--+··+··+--+--+··+--+--+--+--+·
·|··|··|·················|·····|·
·+··+··+--+--+--+··+--+··+··+··+·
·|·····|········|··|··|··|··|··|·
·+--+--+··+··+--+··+··+··+--+··+·
·|········|·····|·····|··|·····|·
·+··+--+--+--+··+··+··+··+··+--+·
·|···········|·····|··|·········U
·+--+--+--+--+--+--+--+--+--+--+·

est

I·3-·6-·9-·12-·15-|18-·21-|24-·27-·30-|33·
·|3··6-·9-·12-|15··18·|21·|24·|27-·30·|33·
·|3-·6-·9-·12·|15-·18-|21··24·|27··30-|33·
·|3··6-|9-·12·|15··18-|21-·24·|27-·30·|33·
·|3-·6·|9··12-·15-|18··21-·24-|27·|30·|33·
·|3··6-|9-·12-|15··18-|21-·24··27·|30·|33·
·|3-|6·|9··12-·15-·18··21-·24-|27-·30-|33·
·|3··6·|9-·12-·15-|18·|21-|24·|27·|30·|33·
·|3-·6-·9·|12··15-|18··21·|24·|27-·30·|33·
·|3··6-·9-·12-|15··18·|21·|24··27··30-·33&

dans le nouveau format. Vous pouvez convertir d'autres labyrinthes ici .

Phase de construction

La phase de construction constitue les 13 premières lignes du programme.

¶U
¶&

Convertit la sortie en demi-cellule L en marqueur de sortie

+`·(\w.+)$
|$1

Ajoute des murs à gauche de l'entrée et de la sortie dans les cellules B

((.)+I.+¶.+¶(?<-2>.)+)·
$1v

Fait le premier pas si l'entrée est au-dessus du labyrinthe

+`((.)*)\+(.).*(¶(?<-2>.)*.)((\w)|·)·?
$1$4$.4$3$6

Effectue la conversion réelle

·v
-v

Ferme le trou d'entrée supérieur

G`1

Conserve uniquement les lignes avec un 1. Étant donné que les labyrinthes ont au moins 5 cellules de large et que les numéros de colonne se produisent par incréments de 3, une ligne avec des cellules de nouveau format doit contenir un numéro de colonne compris entre 10 et 19.

·U
&

Convertit la sortie en cellule R ou en cellule B pour quitter le marqueur

Phase de remplissage

La phase de remplissage constitue les 8 prochaines lignes du programme. Il utilise un algorithme de remplissage d'inondation pour remplir toutes les cellules avec le chemin le plus court pour y accéder depuis l'entrée.

{`

Met toute la phase de remplissage sur une boucle pour remplir tout le labyrinthe.

\B·\d+.(\w+)
$1K$&

Chaque cellule capable de se déplacer vers la gauche le fait. Une cellule peut se déplacer vers la gauche si

  1. il a un chemin non vide
  2. il a un mur gauche vide; et
  3. la cellule ou demi-cellule L à sa gauche a un chemin vide
(\w+)·\d+.\B
$&$1r

Ensuite, chaque cellule capable de se déplacer vers la droite le fait. Une cellule peut se déplacer vers la droite si

  1. il a un chemin non vide
  2. la cellule à sa droite a un mur gauche vide; et
  3. la cellule à sa droite a un chemin vide
(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v

Ensuite, chaque cellule capable de se déplacer vers le bas le fait. Une cellule peut descendre si

  1. il a un chemin non vide
  2. il a au moins une cellule ou une demi-cellule à sa droite (c'est-à-dire qu'il ne s'agit pas d'une cellule R)
  3. la cellule en dessous (c'est-à-dire la cellule sur la ligne suivante avec le même numéro de colonne) a une paroi supérieure vide ou a le marqueur de sortie; et
  4. la cellule en dessous a un chemin vide

Notez que les demi-cellules L ne peuvent pas descendre car elles n'ont pas de numéro de colonne.

\D(\d+).\B(?=.+¶.*\D\1·(\w+))
$&$2A

Ensuite, chaque cellule capable de se déplacer le fait. Une cellule peut remonter si

  1. il a un chemin non vide
  2. il a un mur supérieur vide
  3. la cellule au-dessus d'elle a au moins une cellule ou demi-cellule à sa droite; et
  4. la cellule au-dessus a un chemin vide

Phase de retour

La phase de retour constitue les 5 dernières lignes du programme. Cette phase recherche et renvoie le chemin d'accès rempli dans la cellule de sortie.

Le motif du chemin à la sortie dépend de l'endroit où se trouve la sortie:

  1. Si la sortie est dans une demi-cellule L, alors cette demi-cellule serait & <path>
  2. Si la sortie se trouve dans une cellule R ou une cellule B, cette cellule serait <left wall> <column number> & <path>
  3. Si la sortie est dans une demi-cellule T, comme indiqué ci-dessus, la cellule I menant à la sortie serait <left wall> <column number> · <path>et sur la ligne supérieure.
^.+\d·(\w+)
&$1A

Recherche une cellule sur la ligne supérieure avec un mur supérieur vide et un chemin non vide. Cela prend en charge le dernier cas en ajoutant la dernière étape et le marqueur de sortie.

M!`&\w+

Correspond et renvoie un chemin non vide après un marqueur de sortie.

I|&

Supprime le marqueur de sortie et le Ipréfixe du chemin.

TwiNight
la source
Pourquoi AvKr? Ont-ils un sens / sont-ils des abréviations pour haut, bas, gauche et droite dans votre langue maternelle, ou y a-t-il une autre raison pour laquelle vous avez choisi ces caractères spécifiques?
Kevin Cruijssen
@KevinCruijssen Tout simplement parce que je dois utiliser des caractères alphanumériques et que je suis AvKrle plus proche des flèches en alphanum.
TwiNight
12

Perl 6 , 259 295 octets

{my \a=S:g/(.)$0+/{$0 x($/.comb+.5)*2/3}/;sub f (\c,\v,*@p) {with (c ne any v)&&a.lines».comb[+c[0];+c[1]] ->$_ {for (/\s/??10011221!!/I/??a~~/^\N*I|I\N*$/??2101!!1012!!'').comb X-1 {f [c Z+$^a,$^b],(|v,c),@p,chr 8592+$++}
take @p if /U/}}
[~] (gather f a~~/(\N+\n)*(.)*I/,[]).min(+*)[1,3...*]}

Comment ça marche

  1. my \a = S:g/ (.) $0+ /{ $0 x ($/.chars + .5) * 2/3 }/;

Cela serre le labyrinthe afin que l'intérieur de chaque cellule soit 1x1 au lieu de 2x1 espaces:

 + - + - + - + - + - + + - + - + - + - + - + 
Je | | | Je | | |
 + + - + - + + + + + - + - + + + 
 | | | | | | | |
 + + - + + + + + + + - + + + + 
 | | | | | -> | | | | |
 + + + - + + + + + + - + + + 
 | | | | | |
 + - + + + - + - + + - + + + - + - + 
 | | U | | U
 + - + - + - + - + - + + - + - + - + - + - +

  1. sub f (\c,\v,*@p) {
    with (c ne any v) &&                   # If the coordinate wasn't visited yet
         lines».comb[+c[0];+c[1]] -> $_ {  # and a character exists there...
        for (                          # For each vector...
             /\s/ ?? 10011221 !!       #  from a cell: (0,-1), (-1,0), (0,1), (1,0)
             /I/  ?? a~~/^\N*I|I\N*$/
                      ?? 2101          #  from a top/bottom entrance: (1,0), (-1,0)
                      !! 1012          #  from a left/right entrance: (0,-1), (0,1)
                  !! ''                #  otherwise: none
            ).comb X-1 {
            f                       #   Recurse with arguments:
                [c Z+ $^a, $^b],    #     c plus the vector
                (|v, c),            #     v with c appended
                @p, chr 8592 + $++  #     p with the correct Unicode arrow appended
        }
        take @p if /U/
    }
}

Il s'agit de la fonction de recherche de chemin récursive. Il prend trois paramètres: la coordonnée actuelle c=(y,x), la liste des coordonnées déjà visitées vet le chemin parcouru pjusqu'à présent (sous forme de liste de flèches).

Si le caractère à la coordonnée actuelle est un espace, il revient à ses quatre voisins.
Si le caractère à la coordonnée actuelle est un I, il revient aux deux voisins qui ne sont pas "le long du bord", pour forcer les solutions à traverser le labyrinthe et non autour.
Si le caractère à la coordonnée actuelle est un U, il fait appel takeà la chaîne de chemin accumulée.

  1. [~] (gather f a ~~ /(\N+\n)*(.)*I/, []).min(+*)[1,3...*]

La fonction récursive est initialement appelée avec la coordonnée de la lettre I, qui se trouve à l'aide d'une expression régulière.

Le gathermot-clé collecte toutes les valeurs sur lesquelles a takeété appelé à l'intérieur de la fonction, c'est-à-dire tous les chemins non cycliques valides à travers le labyrinthe.

Le chemin le plus court est choisi, chaque seconde flèche est supprimée pour tenir compte du fait que deux mouvements identiques sont nécessaires pour passer d'une cellule à la suivante, et les flèches restantes sont concaténées pour former la chaîne renvoyée par le lambda.

smls
la source
Tout d'abord un excellent travail pour être le premier à relever mon défi! :) Smart comment vous avez changé les deux espaces en un pour faciliter le mouvement / comptage réel. +1 de moi. Quoi qu'il en soit, après quelques commentaires, deux nouveaux cas de test ont été ajoutés. Pourriez-vous également vérifier ces travaux avec votre solution? (Aussi, Perl 6 a-t-il un TIO ou un autre compilateur en ligne auquel vous pouvez ajouter un lien?)
Kevin Cruijssen
@KevinCruijssen: Il a fait le tour du labyrinthe dans les nouveaux cas de test. :( J'ai corrigé le code maintenant. Tio.run prend en charge Perl 6, mais pour une raison quelconque, cela ne fonctionne pas là-bas ... peut-être qu'il a une version trop ancienne de Perl 6?
smls
Excellent travail de fixation du code. Désolé d'avoir spécifié la règle de devoir parcourir le labyrinthe après avoir déjà posté votre réponse, mais chapeau pour la corriger si vite. Et en ce qui concerne la version TIO, je n'en ai aucune idée. Pas vraiment mon expertise ..
Kevin Cruijssen
Puisque vous avez été le premier à relever mon défi il y a quatre mois, je vous ai donné la prime. :) Et l'acceptation est pour la réponse Retina légèrement plus courte.
Kevin Cruijssen
5

Python 2: 302 octets

from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1]
z=',l)for l in s]'
def f(s,b=1,o=0,n=0):
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z+"s=r([sub(' I ','+I+'%s);"%z*4)*b+"t=[sub('I  ','@@I'"+z
 if'I U'in`s`or n>3:return`o%4`+n/4*`s`
 return min(`o%4`+f(t,0,o,4*(t==s)),f(r(s),0,o+1,n+1),key=len)

Prend l'entrée comme un tableau de chaînes de même longueur. Imprime 0pour droite, 1pour bas, 2pour gauche et 3pour haut.

Explication

J'ai adopté une approche différente de celle des autres réponses. Idée générale: rechercher récursivement en trouvant le chemin le plus court entre aller droit devant et faire pivoter la planche de 90 degrés.

from re import*
r=lambda x:[''.join(_)for _ in zip(*x)][::-1] #Rotates the board counterclockwise
z=',l)for l in s]'    #Suffix for hacky exec golfing
def f(s,b=1,o=0,n=0): #b is 1 on initial call, 0 on every recursion
                      #o is orientation
                      #n is number of rotations
 exec("s=[sub('(..).(?!$)',r'\\1'%s;"%z  #Squeeze the maze
      +"s=r([sub(' I ','+I+'%s);"%z*4)   #Add walls around the I to keep it in the maze
      *b                                 #Only if b is 1
      +"t=[sub('I  ','@@I'"+z            #Attempt to move right

 if'I U'in`s`or n>3:return`o%4`+n/4*`s`  #If the I is next to the U, return the orientation
                                         #If there were 4 rotations, return a long string
 return min(                             #Return the path with the shortest length:
            `o%4`+f(t,0,o,4*(t==s)),       #Moving forward if possible
            f(r(s),0,o+1,n+1),             #Rotating the board
        key=len)

Essayez-le en ligne!

deltaepsilon3
la source
3
Bienvenue chez PPCG! C'est une excellente première réponse, et je suis impressionné que vous ayez décidé de relever un défi assez difficile comme premier. Aussi intelligent comment vous avez mis des murs autour Ipour empêcher le chemin de sortir du labyrinthe. Profitez de votre séjour, et +1 de moi. :)
Kevin Cruijssen
2

JavaScript (ES6), 356 octets

a=>(a=a.map(s=>s.filter((_,i)=>!i|i%3)),g=([x,y])=>a[y]&&a[y][x],o=[],c=([x,y],m="",v=[])=>[[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(p=[x+j,y+k],!m&(!y|y>a[l="length"]-2)==i%2|v.includes(""+p)||(g(p)<"!"?c(p,m+"v>^<"[i],[...v,""+p]):g(p)=="U"?o.push(m.replace(/(.)\1/g,"$1")):0))),a.map((h,i)=>h.map((k,j)=>k=="I"&&c([j,i]))),o.sort((a,b)=>a[l]-b[l])[0])

Prend l'entrée comme un tableau 2D de caractères. Chaque ligne doit être complétée à gauche par un espace et ne pas avoir d'espace de fin, peu importe où se trouvent les points de début / fin.

Utilise l'idée de smls d'écraser le labyrinthe pour rendre chaque cellule 1x1 et de supprimer les flèches répétées de la sortie.

Non golfé et expliqué

a=>(
    a=a.map(s=>s.filter((_,i)=>!i|i%3)),    // squish the maze to 1x1 cells
    g=([x,y])=>a[y]&&a[y][x],               // helper func to get maze value
    o=[],                                   // resulting movesets
    c=([x,y], m="", v=[]) =>                // recursive func to search
                                            // takes current point, moves, and visited spots
        [[0,1],[1,0],[0,-1],[-1,0]].map(([j,k],i)=>(// for each direction
            p=[x+j,y+k],
            !m & (!y | y>a[l="length"]-2) == i%2 |  // if first move, prevent moving out of maze
                v.includes(""+p) || (               // also prevent if already visited
                    g(p)<"!" ?                      // is this a space?
                        c(p, m+"v>^<"[i], [...v,""+p]) // check this spot recursively
                    : g(p)=="U" ?                   // if this the end?
                        o.push(                     // add moves to moveset
                            m.replace(/(.)\1/g,"$1")) // with double arrows removed
                    : 0
                )
        )),

    a.map((h,i)=>h.map((k,j)=>      // find the starting "I" and
        k=="I" && c([j,i])          // begin recursion at that point
    )),

    o.sort((a,b)=>a[l]-b[l])[0]     // get shortest path
)

Extrait de test

Afficher l'extrait de code

Justin Mariner
la source
1

Rétine , 416 octets

T` `+`^.*| ?¶.|.*$
I
#
{+` (\w)
d$1
+`(\w) 
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!))) 
$1w
^
w¶
w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1
{`^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# 
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2 $5#
}`^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6 
s`U.*

(a|d)\1\1?
$1
ss
s
ww
w

Essayez-le en ligne! Si j'avais vu cette question lorsqu'elle a été publiée à l'origine, c'est probablement la réponse que j'aurais donnée, donc je la poste quand même, même s'il existe une bien meilleure réponse dans Retina. Explication:

T` `+`^.*| ?¶.|.*$

Remplissez la bordure. Cela évite de se promener à l'extérieur du labyrinthe (par exemple pour le cas de test 7).

I
#

Placez un marqueur non alphabétique à l'entrée.

{+` (\w)
d$1
+`(\w) 
$1a
+`(¶(.)*) (.*¶(?<-2>.)*(?(2)(?!))\w)
$1s$3
}+m`(^(.)*\w.*¶(?<-2>.)*(?(2)(?!))) 
$1w

Remplissage d'inondation de la sortie à l'entrée. À chaque étape, utilisez une lettre pour indiquer la meilleure direction à prendre (wasd - cela pourrait être familier aux joueurs; j'avais également envisagé hjkl mais je l'ai trouvé trop déroutant). De plus, préférez répéter la même direction; cela évite d'aller à gauche / droite entre deux cellules verticalement adjacentes.

^
w¶

Supposons que la première étape soit terminée.

w((.|¶)*(¶(.)*#.*¶(?<-4>.)*(?(4)(?!))(s)|#(d)|(a)#))
$4$5$6¶$1

Mais s'il y a une lettre au-dessus, à gauche ou à droite de l'entrée, changez-la à la première étape.

{`^(.*d)(¶(.|¶)*)#(\w)
$1$4$2 #
^(.*a)(¶(.|¶)*)(\w)#
$1$4$2# 
^(.*s)(¶(.|¶)*¶(.)*)#(.*¶(?<-4>.)*(?(4)(?!)))(\w)
$1$6$2 $5#
}`^(.*w)(¶(.|¶)*¶(.)*)(\w)(.*¶(?<-4>.)*(?(4)(?!)))#
$1$5$2#$6

Déplacez le marqueur dans la direction du dernier mouvement, en lisant la direction du mouvement suivant à partir du carré vers lequel le marqueur se déplace, et ajoutez-le à la liste des directions. Cela se répète jusqu'à ce que le Usoit atteint.

s`U.*

Supprimez tout après les instructions car il n'est plus nécessaire.

(a|d)\1\1?
$1
ss
s
ww
w

La grille d'origine est sur une disposition 3 × 2. Tout en se déplaçant verticalement si nous zigzagons horizontalement, le remplissage inondé optimisera le mouvement et ne déplacera que 3n-1 caractères horizontalement, donc lors de la division par trois, nous devons arrondir. Verticalement, nous divisons simplement par 2.

J'ai également étudié une véritable solution de grille carrée, c'est-à-dire où la matrice de caractères est elle-même carrée plutôt que d'être une mise en page 3 × 2 avec une bordure facultative. Bien que probablement non conforme à la question, la possibilité de transposer a réduit le nombre d'octets à 350: essayez-le en ligne!

Neil
la source
Belle réponse, +1! Je vois dans votre lien TIO que vous en avez ajouté deux -autour des caractères d'entrée et de sortie. Étant donné que le défi consiste principalement à traverser le labyrinthe, je suppose que c'est bien, mais je suis curieux: quels étaient les problèmes lorsque vous n'aviez pas placé ces murs au-dessus / en dessous du Iet U? Aussi, pourriez-vous vérifier que cela fonctionne pour le cas de test 7 avec le Iet Uen haut au lieu des côtés? TIO dépasse la limite de 60 secondes, je ne peux donc pas le tester moi-même. Bien que vous ayez lu votre explication sur la première tentative de descendre par défaut, je suppose que cela devrait fonctionner correctement.
Kevin Cruijssen
@KevinCruijssen La réponse "secondaire" fonctionne pour le cas de test 7 mais nécessite des caractères supplémentaires: Essayez-le en ligne! suite ...
Neil
@KevinCruijssen La réponse "principale" comportait un bogue empêchant du tout la sortie de la ligne supérieure. Il a également un bug similaire à la réponse "secondaire" par lequel il préfère se promener à l'extérieur du labyrinthe s'il le peut. (De plus, je ne suis pas allé près de la limite de 60 secondes.)
Neil
En fait, je pouvais corriger les deux réponses en remplissant la bordure. Je le ferai plus tard quand j'aurai le temps.
Neil