Entrada:

Un laberinto que contiene los personajes:

-- (pared horizontal);
| (pared vertical);
+ (conexión);
(espacio para caminar);
I (Entrada);
U (salida).

Es decir, una entrada podría verse así:

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

Salida:

El más eficiente ruta debe caminar para llegar desde la entrada hasta la salida del laberinto (a través del laberinto), indicado por los caracteres que indican la izquierda, derecha, arriba y abajo (es decir >; <; ^; v).

Reglas de desafío:

Puede tomar la entrada en cualquier formato razonable. String-array, Single String con nuevas líneas, 2D char-array, etc., son todos los formatos de entrada posibles.
La salida puede constar de cuatro caracteres distintos. Es decir ><^v; →←↑↓; ⇒⇐⇑⇓; RLUD; 0123; ABCD; etc.)
Se le permite agregar espacios o arrastrar nueva línea a la salida si lo prefiere; Esto es opcional.
Los pasos se cuentan por cuadrado (ver cuatro +símbolos para los cuadrados), y no por carácter.
El laberinto puede tener un tamaño de 5x5 a 15x15, y siempre será un cuadrado (por lo que no habrá casos de prueba para laberintos de 5x10).
Puede suponer que cada laberinto tiene una o más rutas válidas de principio a fin, y siempre genera el más corto (consulte los casos de prueba 4 y 5).
Si hay varias rutas con la misma longitud, puede elegir cuál generar (consulte el caso de prueba 6).
No puede "caminar" fuera de los límites del laberinto (vea los casos de prueba 7 y 8).

Reglas generales:

Este es el código de golf , por lo que la respuesta más corta en bytes gana.
No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolf. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
Se aplican reglas estándar para su respuesta, por lo que puede usar STDIN / STDOUT, funciones / método con los parámetros adecuados, programas completos. Tu llamada.
Las lagunas predeterminadas están prohibidas.
Si es posible, agregue un enlace con una prueba para su código.
Además, agregue una explicación si es necesario.

Casos de prueba:

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<

Laberintos generados con esta herramienta (y en algunos casos ligeramente modificados).

code-golf path-finding maze Kevin Cruijssen
fuente

10

¡He encontrado una solución más corta para el tercer caso de prueba! v<<<<<<^^^^^(siempre piensa fuera de la caja)

Leo

2

Si se puede demostrar que su código producirá la solución más corta, con suficiente tiempo y memoria, ¿compite? ¿Incluso en el caso de un tiempo realmente largo (fin de la moda del universo)?

Yytsi

1

@JackBates Es una broma. Literalmente camina alrededor de la caja hasta la salida: D

Yytsi

1

Creo que el primer caso de prueba está mal, debería estarlo >v>>>vv<v>>v>v>>vvv>>>.

sonríe

1

@KevinCruijssen Por ejemplo, una solución que prueba cada combinación de "v ^ <>" para una longitud de hasta la cantidad de cajas vacías dentro del laberinto. La solución correcta estará allí, pero toma tiempo astronómico para computar.

Yytsi

7

Retina , 338 281 275 273 261 bytes

¶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|&

Pruébalo en línea!

Notas

Debido a espacios en blanco significativos, todos los espacios ( 0x20) se reemplazan con interpunct ( ·) tanto en esta respuesta como en el enlace TIO. El programa funciona bien si se restauran los espacios.
Usos AvKrpara arriba, abajo, izquierda y derecha, respectivamente. Esos pueden ser reemplazados con cualquier letra excepto I.
~~Toma alrededor de 40 años en TIO para el caso de prueba 15 × 15. Se paciente.~~ Se rediseñó la parte para encontrar el camino más corto una vez que el camino llegó a la salida. Resulta que eso estaba tomando mucho tiempo.
Podría romperse por completo en laberintos que tienen 66 o más celdas de ancho, pero pueden manejar laberintos de altura arbitraria. Una solución para ancho arbitrario toma +1 byte.

Explicación

El programa consta de 3 fases:

Una fase de construcción para convertir el laberinto a un formato compacto con el que es más fácil trabajar (detallado a continuación).
Una fase de relleno para resolver realmente el laberinto usando un algoritmo de relleno de inundación.
Una fase de retorno para devolver el camino más corto en la salida.

Formato

Dado que el formato original del laberinto es bastante difícil de manejar, la primera parte del programa lo convierte a un formato diferente.

Células

En el formato original, cada celda se representa como una región 2 × 3:

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

Dado que la columna derecha no contiene información, el programa identifica las celdas como cualquier región 2 × 2 con un +en la esquina superior izquierda.

Esto nos deja con 3 tipos de células:

I Células : Células que están correctamente dentro del laberinto.
Celdas R : Celdas que están a la derecha del laberinto. Estos son creados por el relleno utilizado para albergar la entrada o salida. Por ejemplo, la salida Uen el caso de prueba 1 está en una R-Cell.
Células B : Células que están debajo del laberinto. Al igual que las células R, estas se crean mediante relleno.

En el nuevo formato, las celdas se representan como una cadena de longitud variable:

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

La pared izquierda y superior se copian del formato original. El número de columna se basa en la posición horizontal de la celda y se utiliza para la alineación (identificando celdas directamente una encima de la otra o debajo de la otra). La ruta es una cadena alfabética utilizada durante la fase de relleno para guardar la ruta más corta para llegar a esa celda. La ruta y el marcador de salida se explicarán más adelante

Medias celdas

Aunque la mayoría del laberinto son células, hay regiones del laberinto que no son células:

R Medias celdas : si no hay relleno derecho, las +s a lo largo de la pared derecha no forman celdas, ya que están en la última columna.
L Medias celdas : si hay relleno izquierdo, las celdas no se pueden formar allí ya que no hay ninguna +a la izquierda de ellas. Por ejemplo, la entrada Ien el caso de prueba 1 está en una L Media Celda.

Técnicamente, hay medias celdas T sobre el laberinto (cuando hay relleno superior) y medias celdas B (a lo largo de la pared inferior cuando no hay relleno inferior) pero no están representadas en el nuevo formato.

La fila superior de una media celda se eliminaría como parte de la construcción de celdas completas en la misma fila, por lo que las medias celdas se representan en el nuevo formato como

<wall/exit marker>? <path>

Un R Half-cell es justo |. Un L Half-cell tiene solo Iel camino, solo el marcador de salida y un camino vacío, o simplemente una pared vacía.

Entradas y salidas.

Si la entrada está a la izquierda, a la derecha o al fondo del laberinto, entonces el marcador de entrada se Iincluiría naturalmente en la (media) celda como el camino, que se puede eliminar al regresar el camino final.

Si la entrada está por encima del laberinto, se toma el primer paso (hacia abajo) durante la fase de construcción, ya que las semicélulas T se eliminan durante la construcción. Esto mantiene una ruta viable en una celda llena. La pared superior se cierra después.

Si la salida está a la izquierda, a la derecha o al fondo del laberinto, entonces Unaturalmente se incluiría en la (media) celda. Para evitar ser confundido con una ruta, &se usa el marcador de salida no alfanumérico en lugar de U. El marcador de salida está incrustado en una celda o media celda (como se especificó anteriormente).

Si la salida está por encima del laberinto, entonces sería el único agujero que puede pasar por encima de la fila superior de celdas (ya que el de la entrada, si está presente, ya estaría cerrado). Cualquier camino que llegue a ese agujero puede salir del laberinto dando un paso hacia arriba.

Por último, cualquier celda B que contenga la entrada o la salida debe cerrar su pared izquierda para evitar "resolver" el laberinto caminando por las celdas B. Las entradas y salidas en celdas R o medias celdas L no necesitan más procesamiento ya que el algoritmo de relleno de inundación no permite movimientos verticales hacia / desde ellas.

Ejemplo

Como ejemplo, el primer caso de prueba

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

es

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&

en el nuevo formato. Puedes convertir otros laberintos aquí .

Fase de construcción

La fase de construcción conforma las primeras 13 líneas del programa.

¶U
¶&

Convierte la salida en L Media celda para salir del marcador

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

Agrega paredes a la izquierda de la entrada y sale en las celdas B

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

Da el primer paso si la entrada está por encima del laberinto

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

Realiza la conversión real

·v
-v

Cierra el orificio de entrada superior

G`1

Mantiene solo líneas con a 1. Dado que los laberintos tienen al menos 5 celdas de ancho y los números de columna se producen en incrementos de 3, una línea con celdas de nuevo formato debe contener un número de columna entre 10 y 19.

·U
&

Convierte la salida en la celda R o la celda B para salir del marcador

Fase de llenado

La fase de llenado conforma las siguientes 8 líneas del programa. Utiliza un algoritmo de relleno de inundación para llenar todas las celdas con el camino más corto para llegar allí desde la entrada.

{`

Pone toda la fase de llenado en un bucle para llenar todo el laberinto.

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

Cada celda capaz de moverse hacia la izquierda lo hace. Una celda puede moverse a la izquierda si

tiene una ruta no vacía
tiene una pared izquierda vacía; y
la celda o media celda L a su izquierda tiene una ruta vacía

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

Entonces, cada celda capaz de moverse hacia la derecha lo hace. Una celda puede moverse hacia la derecha si

tiene una ruta no vacía
la celda a su derecha tiene una pared izquierda vacía; y
la celda a su derecha tiene un camino vacío

(?<=\D\2.(\w+).+?¶.*\D(\d+)[·&])\B
$1v

Entonces, cada celda capaz de moverse hacia abajo lo hace. Una celda puede moverse hacia abajo si

tiene una ruta no vacía
tiene al menos una celda o media celda a su derecha (es decir, no es una celda R)
la celda debajo de ella (es decir, la celda en la siguiente línea con el mismo número de columna) tiene una pared superior vacía o tiene el marcador de salida; y
la celda de abajo tiene un camino vacío

Tenga en cuenta que las medias celdas L no pueden moverse hacia abajo ya que no tienen números de columna.

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

Entonces, cada celda capaz de moverse hacia arriba lo hace. Una celda puede moverse hacia arriba si

tiene una ruta no vacía
tiene una pared superior vacía
la celda superior tiene al menos una celda o media celda a su derecha; y
la celda de arriba tiene un camino vacío

Fase de retorno

La fase de retorno constituye las últimas 5 líneas del programa. Esta fase busca y devuelve la ruta rellenada en la celda de salida.

El patrón de la ruta en la salida depende de dónde está la salida:

Si la salida está en una media celda L, entonces esa media celda sería & <path>
Si la salida está en una celda R o celda B, entonces esa celda sería <left wall> <column number> & <path>
Si la salida está en una media celda T, entonces, como se señaló anteriormente, la celda I que conduce a la salida estaría <left wall> <column number> · <path>y en la fila superior.

^.+\d·(\w+)
&$1A

Encuentra una celda en la línea superior con una pared superior vacía y una ruta no vacía. Esto se encarga del último caso agregando el último paso y el marcador de salida.

M!`&\w+

Coincide y devuelve una ruta no vacía después de un marcador de salida.

I|&

Elimina el marcador de salida y el Iprefijo de la ruta.

TwiNight
fuente

¿Por qué el AvKr? ¿Tienen un significado / son abreviaturas para arriba, abajo, izquierda y derecha en su idioma nativo, o hay alguna otra razón por la que ha elegido esos caracteres específicos?

Kevin Cruijssen

@KevinCruijssen Simplemente porque debo usar caracteres alfanuméricos y AvKrson lo más parecido a las flechas en alfanumérico.

TwiNight

12

Perl 6 , 259 295 bytes

{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...*]}

Cómo funciona

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

Esto exprime el laberinto para que el interior de cada celda sea 1x1 en lugar de 2x1 caracteres de espacio:

 + - + - + - + - + - + + - + - + - + - + - + 
Yo | El | El | Yo | El | El |
 + + - + - + + + + + - + - + + + 
 El | El | El | El | El | El | El | El |
 + + - + + + + + + - + + + + 
 El | El | El | El | El | -> | El | El | El | El |
 + + + - + + + + + + - + + + 
 El | El | El | El | El | El |
 + - + + + - + - + + - + + + - + - + 
 El | El | U | El | U
 + - + - + - + - + - + + - + - + - + - + - +

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/
    }
}

Esta es la función recursiva de búsqueda de rutas. Toma tres parámetros: la coordenada actual c=(y,x), la lista de coordenadas ya visitadas vy la rutap tomada hasta ahora (como una lista de caracteres de flecha).

Si el carácter en la coordenada actual es un espacio, recurre a sus cuatro vecinos.
Si el carácter en la coordenada actual es a I, recurre a los dos vecinos que no están "a lo largo del borde", para obligar a las soluciones a atravesar el laberinto y no a su alrededor.
Si el carácter en la coordenada actual es a U, llama takea la cadena de ruta acumulada.

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

La función recursiva se llama inicialmente con la coordenada de la letra I, que se encuentra usando una expresión regular.

La gatherpalabra clave recopila todos los valores en los que takese llamó dentro de la función, es decir, todas las rutas no cíclicas válidas a través del laberinto.

Se elige el camino más corto, cada segunda flecha se suelta para tener en cuenta el hecho de que se requieren dos movimientos idénticos para pasar de una celda a la siguiente, y las flechas restantes se concatenan para formar la cadena que se devuelve desde el lambda.

smls
fuente

En primer lugar, ¡excelente trabajo para ser el primero en completar mi desafío! :) Inteligente cómo ha cambiado los dos espacios a uno para facilitar el movimiento / conteo real. +1 de mi parte De todos modos, después de algunos comentarios, se agregaron dos nuevos casos de prueba. ¿Podría verificar que estos funcionen también con su solución? (Además, ¿Perl 6 tiene un TIO u otro compilador en línea al que podría agregar un enlace?)

Kevin Cruijssen

@KevinCruijssen: dio la vuelta al laberinto en los nuevos casos de prueba. :( He arreglado el código ahora tio.run soporta Perl 6, pero por alguna razón, esto no funciona allí ... tal vez haya una versión demasiado viejo Perl 6.?

sin costura

Gran trabajo arreglando el código. Perdón por especificar la regla de tener que pasar por el laberinto después de que ya hayas publicado tu respuesta, pero chapeau por arreglarlo tan rápido. Y con respecto a la versión TIO, no tengo idea. No es realmente mi experiencia ..

Kevin Cruijssen

Como fuiste el primero en responder mi desafío hace cuatro meses, te di la recompensa. :) Y el Aceptar es para la respuesta de Retina un poco más corta.

Kevin Cruijssen

5

Python 2: 302 bytes

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)

Toma la entrada como una matriz de cadenas, todas con la misma longitud. Imprime 0para derecha, 1para abajo, 2para izquierda y 3para arriba.

Explicación

Tomé un enfoque diferente al de las otras respuestas. Idea general: busque de forma recursiva encontrando el camino más corto entre avanzar y rotar el tablero 90 grados.

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)

Pruébalo en línea!

deltaepsilon3
fuente

3

Bienvenido a PPCG! Esta es una excelente primera respuesta, y estoy impresionado de que hayas decidido hacer un desafío bastante difícil como el primero. También es inteligente cómo has colocado paredes alrededor Ipara evitar que el camino salga del laberinto. Disfruta tu estadía y +1 de mi parte. :)

Kevin Cruijssen

2

JavaScript (ES6), 356 bytes

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])

Toma la entrada como una matriz 2D de caracteres. Cada línea debe ir rellenada a la izquierda por un espacio y no tener espacio final, sin importar dónde se encuentren los puntos de inicio / finalización.

Utiliza la idea de smls de aplastar el laberinto para hacer que cada celda sea 1x1 y eliminar las flechas repetidas de la salida.

No golfista y explicado

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
)

Fragmento de prueba

Mostrar fragmento de código

f=
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])

let tests = [" +--+--+--+--+--+--+--+--+--+--+\nI               |     |        |\n +  +--+--+--+  +  +  +  +--+  +\n |           |     |  |  |     |\n +--+--+--+  +--+--+  +  +  +--+\n |           |     |     |     |\n +  +--+--+  +  +--+--+  +--+  +\n |     |     |     |     |     |\n +--+  +  +--+--+  +--+--+  +  +\n |     |        |        |  |  |\n +  +--+--+--+  +--+--+  +  +  +\n |     |     |     |        |  |\n +--+  +  +--+--+  +--+--+--+--+\n |  |  |                 |     |\n +  +  +--+--+--+  +--+  +  +  +\n |     |        |  |  |  |  |  |\n +--+--+  +  +--+  +  +  +--+  +\n |        |     |     |  |     |\n +  +--+--+--+  +  +  +  +  +--+\n |           |     |  |         U\n +--+--+--+--+--+--+--+--+--+--+"," +--+--+--+--+--+\nI   |        |  |\n +  +--+--+  +  +\n |        |  |  |\n +  +--+  +  +  +\n |  |  |     |  |\n +  +  +--+  +  +\n |        |     |\n +--+  +  +--+--+\n |     |         U\n +--+--+--+--+--+"," +--+--+--+--+--+\nU      |        |\n +  +  +--+--+  +\n |  |     |     |\n +--+--+  +  +--+\n |        |     |\n +  +--+--+--+  +\n |  |     |     |\n +  +  +  +  +--+\n |     |         I\n +--+--+--+--+--+"," +--+--+--+--+--+\nU      |        |\n +  +  +--+--+  +\n |  |           |\n +--+--+  +  +--+\n |        |     |\n +  +--+--+--+  +\n |  |     |     |\n +  +  +  +  +--+\n |     |         I\n +--+--+--+--+--+","                                I\n +--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+\n |     |              |                    |  |\n +  +  +  +--+--+--+  +  +--+--+  +--+--+  +  +\n |  |     |        |     |        |     |     |\n +--+--+--+  +--+  +  +--+--+--+--+  +--+--+--+\n |     |  |  |  |     |     |           |     |\n +  +  +  +  +  +--+  +  +  +  +--+--+  +--+  +\n |  |        |        |  |     |        |     |\n +  +--+--+--+  +--+--+  +  +--+  +--+--+  +--+\n |  |     |     |        |  |     |     |     |\n +  +--+  +  +--+  +--+--+  +--+--+  +  +--+  +\n |  |     |        |     |           |        |\n +  +  +--+--+--+--+  +  +--+--+--+  +--+  +--+\n |     |     |        |        |  |     |     |\n +--+--+--+  +  +--+--+  +--+  +  +--+  +--+  +\n |              |     |     |        |  |  |  |\n +  +--+--+--+--+  +  +  +--+--+--+  +  +  +  +\n |     |  |     |  |  |        |        |  |  |\n +--+  +  +  +  +  +  +--+--+  +  +  +--+  +  +\n |     |     |  |  |  |           |  |     |  |\n +--+  +--+--+  +  +  +  +--+--+--+  +  +  +  +\n |     |        |  |  |     |        |  |  |  |\n +  +--+  +--+--+  +  +--+--+  +  +--+  +  +  +\n |        |     |  |     |     |  |     |  |  |\n +--+--+--+  +  +  +--+  +  +--+--+  +--+  +  +\n |  |        |        |     |        |     |  |\n +  +  +--+--+--+--+  +--+--+  +--+--+  +--+  +\n |  |              |              |     |     |\n +  +  +  +--+--+--+--+--+--+--+--+  +--+  +--+\n |     |                                |     |\n +--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+\n                             U"," +--+--+--+--+--+\nI               |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |              |\n +  +  +  +  +  +\n |               U\n +--+--+--+--+--+","  I  U\n +  +  +--+--+--+\n |  |        |  |\n +  +--+--+  +  +\n |     |     |  |\n +--+  +  +--+  +\n |        |  |  |\n +  +--+  +  +  +\n |     |        |\n +--+  +--+--+  +\n |     |        |\n +--+--+--+--+--+"," +--+--+--+--+--+\n |     |        |\n +  +--+  +--+  +\nI   |     |  |  |\n +  +  +--+  +  +\nU   |     |  |  |\n +--+--+  +  +  +\n |     |     |  |\n +  +--+--+--+  +\n |               \n +--+--+--+--+--+"];
S.innerHTML="<option>Tests"+Array(tests.length).fill().map((_,i)=>"<option>"+(i+1)).join``;

<select id=S oninput="I.value=S.selectedIndex?tests[S.value-1]:''"></select><br>
<textarea id=I rows=20 cols=50></textarea><br><button onclick="O.innerHTML=f(I.value.split`\n`.map(x=>[...x]))">Run</button>
<pre id=O>

Expandir fragmento

Justin Mariner
fuente

1

Retina , 416 bytes

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

Pruébalo en línea! Si hubiera visto esta pregunta cuando se publicó originalmente, esta es probablemente la respuesta que habría dado, así que la estoy publicando de todos modos, a pesar de que hay una respuesta mucho mejor en Retina. Explicación:

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

Completa el borde. Esto evita caminar alrededor del exterior del laberinto (por ejemplo, para el caso de prueba 7).

I
#

Coloque un marcador no alfabético en la entrada.

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

Las inundaciones se llenan desde la salida hasta la entrada. En cada paso, use una letra para indicar la mejor dirección a seguir (wasd; esto podría ser familiar para los jugadores; también había considerado hjkl pero me pareció demasiado confuso). Además, prefiere repetir la misma dirección; Esto evita ir hacia la izquierda / derecha entre dos celdas adyacentes verticalmente.

^
w¶

Suponga que el primer paso está abajo.

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

Pero si hay una letra arriba, izquierda o derecha de la entrada, cámbiela al primer paso.

{`^(.*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

Mueva el marcador en la dirección del último movimiento, leyendo la dirección del siguiente movimiento desde el cuadrado al que se mueve el marcador, y agréguelo a la lista de direcciones. Esto se repite hasta que Use alcanza.

s`U.*

Elimine todo después de las instrucciones ya que ya no es necesario.

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

La cuadrícula original está en un diseño de 3 × 2. Mientras nos movemos verticalmente si zigzagueamos horizontalmente, el relleno de inundación optimizará el movimiento y solo moverá 3n-1 caracteres horizontalmente, por lo que al dividir entre tres, debemos redondear. Verticalmente solo dividimos por 2.

También investigé una verdadera solución de cuadrícula cuadrada, es decir, donde la matriz de caracteres es cuadrada en lugar de ser un diseño de 3 × 2 con un borde opcional. Aunque probablemente no sea conforme a la pregunta, la capacidad de transposición redujo el recuento de bytes a 350: ¡ Pruébelo en línea!

Neil
fuente

Buena respuesta, +1! Veo en su enlace TIO que ha agregado dos -alrededor de los caracteres de entrada y salida. Dado que el desafío se trata principalmente de atravesar el laberinto, supongo que está bien, pero tengo curiosidad: ¿cuáles fueron los problemas cuando no había colocado esas paredes encima / debajo del Iy U? Además, ¿podría verificar que esto funciona para el caso de prueba 7 con Iy Uen la parte superior en lugar de los lados? TIO excede el límite de 60 segundos, por lo que no puedo probarlo yo mismo. Aunque lea su explicación de intentar primero bajar por defecto, supongo que debería funcionar bien.

Kevin Cruijssen

@KevinCruijssen La respuesta "secundaria" funciona para el caso de prueba 7 pero requiere caracteres adicionales: ¡ Pruébelo en línea! continúa ...

Neil

@KevinCruijssen La respuesta "principal" tenía un error por el cual no podía hacer frente a la salida en la línea superior. También tiene un error similar a la respuesta "secundaria" por la cual prefiere caminar por el exterior del laberinto si puede. (Además, no llegué a ninguna parte cerca del límite de 60 segundos.)

Neil

En realidad, podría solucionar ambas respuestas completando el borde. Lo haré más tarde cuando tenga tiempo.

Neil

La vida es un laberinto: tomamos el camino equivocado antes de aprender a caminar

Entrada:

Salida:

Respuestas:

Retina , 338 281 275 273 261 bytes

Explicación

Formato

Fase de construcción

Fase de llenado

Fase de retorno

Perl 6 , 259 295 bytes

Cómo funciona

Python 2: 302 bytes

Explicación

JavaScript (ES6), 356 bytes

No golfista y explicado

Fragmento de prueba

Retina , 416 bytes