Haz que una serpiente llene cualquier laberinto (hasta que se atasque).

La serpiente

La serpiente comienza en un punto de partida dado, apuntando hacia el ESTE . Se mueve siempre teniendo una pared o una parte de su cuerpo inmediatamente a la IZQUIERDA de su cabeza (" seguidor de la pared de la regla izquierda "), hasta que se atasca porque las cuatro direcciones alrededor de su cabeza están ocupadas. (Nota: una serpiente atascada no puede llenar todo el espacio accesible, ¡pero ese no es el objetivo!)

El reto

Escriba un programa o función que acepte un laberinto como entrada en forma de texto 2D:

• La entrada puede estar en cualquier formato razonable: por ejemplo, una lista de cadenas, una sola cadena con líneas nuevas, un archivo.
• El laberinto tiene paredes (" #"), espacios vacíos (" ") y exactamente un punto de partida (" o").

• Puedes elegir

  • supongamos que la primera y la última fila y columna son completamente paredes;
  • o suponga que cada entrada se considera que tiene una capa externa implícita de paredes

• Puede suponer que el punto de partida tiene un muro (o un muro implícito) directamente encima (NORTE) y que la serpiente puede hacer un movimiento inicial válido en la dirección ESTE o SUR.

• Puede suponer que no hay otros caracteres presentes en el texto (excepto las nuevas líneas si su entrada los necesita).
• Puede suponer que todas las líneas tienen la misma longitud.

e imprime / devuelve un "laberinto lleno" como salida, con una instantánea de la serpiente en el momento en que se atascó :

• El cuerpo de la serpiente está representado por los caracteres que >v<^apuntan hacia dónde está su próximo segmento
• El punto de partida de la serpiente es su dirección al inicio (" >" a menos que tenga que girar de inmediato) o un opersonaje (no es necesario ser coherente)
• El punto final de la serpiente es un opersonaje.

Tanteo

Código de golf habitual: gana el código más corto

Ejemplo

in:
#################################
#                    o          #
#                               #
#     ##       ###       ##     #
#    ##     ##     ##     ##    #
#    ##     ##     ##     ##    #
#    ##      ##   ##      ##    #
#   ##       ##   ##       ##   #
#   ##         ###         ##   #
#    ##       #####       ##    #
#    ##       #####       ##    #
#    ##        ###        ##    #
#     ##                 ##     #
#                               #
#                               #
#################################

out:
#################################
#>>>>>>>>>>>>>>>>>>>v>>>>>>>>>>v#
#^>>>>>>>>>>>>>>>>>v>>>>>>>>>>vv#
#^^   ##>>>>>>v###o>>>>>v##   vv#
#^^  ##>^   ##>>>>^##   >v##  vv#
#^^  ##^    ##     ##    v##  vv#
#^^  ##^     ##   ##     v##  vv#
#^^ ##>^     ##   ##     >v## vv#
#^^ ##^<       ###       v<## vv#
#^^  ##^      #####      v##  vv#
#^^  ##^      #####      v##  vv#
#^^  ##^<      ###      v<##  vv#
#^^   ##^<<<<<<<<<<<<<<<<##   vv#
#^^<<<<<<<<<<<<<<<<<<<<<<<<<<<<v#
#^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<#
#################################

Animada (con fines ilustrativos):

Editar: tenga en cuenta que, en caso de duda, la serpiente debe "mantener su mano izquierda" en la pared en la que ya está, siguiendo las esquinas, sin saltar a una pared a 1 cuadra de distancia.

Gracias Jonathan Allan por mencionarlo, y Draco18s por la instantánea explicativa anterior.

Otros ejemplos

in:
####################
#               o# #  
#                ###
#                  #
#      ##          #
#                ###
####################

out:
####################
#>>>>>>>>>>>>>>vv# #
#^>>>>>>>>>>>>vvv###
#^^   v<<<o<<<<v>>v#
#^^<<<<##^<<<<<<v<<#
#^<<<<<<<<<<<<<<<###
####################

in:
####################
#         o    #####  
#              #####
#                  #
#                 ##
####################

out:
####################
#         >>>>v#####
#             v#####
#             >>>>o#
#                 ##
####################

in:
################
#o             #
#   ########## #
# #          # #
# #          # #
# #          # #
# #  #       # #
# #          # #
# #          # #
# #          # #
# ############ #
#              #
################

out:
################
#>>>>>>>>>>>>>v#
#>>v##########v#
#^#>>>>>>>>>v#v#
#^#>>>>>>>>vv#v#
#^#^>>>>>>vvv#v#
#^#^^#    vvv#v#
#^#^^o<<<<<vv#v#
#^#^^<<<<<<<v#v#
#^#^<<<<<<<<<#v#
#^############v#
#^<<<<<<<<<<<<<#
################

Carbón , 94 68 bytes

Ｆ²⊞υＳＷ¬⁼§υ⁰§υ±¹⊞υＳ≔⪫υ¶θＰθ…θ⌕θo≔⁰θＷ№ＫＶ «≧⁺⊖⌕Ｅ³§ＫＶ⁺θκ θ✳§rdluθ§>v<^θ»o

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Ｆ²⊞υＳＷ¬⁼§υ⁰§υ±¹⊞υＳ≔⪫υ¶θ

Sorba la entrada en una cadena. Esto podría evitarse utilizando un formato de entrada menos conveniente.

Ｐθ…θ⌕θo

Imprima la entrada sin mover el cursor, y luego imprima hacia arriba onuevamente, de modo que el cursor termine debajo de ella.

≔⁰θ

Inicializa la dirección actual.

Ｗ№ＫＶ «

Repita mientras todavía haya un espacio libre en alguna dirección.

≧⁺⊖⌕Ｅ³§ＫＶ⁺θκ θ

Calcule si la serpiente puede girar a la izquierda o si se ve obligada a girar a la derecha. El código ≦⊖θＷ¬⁼§ＫＶθ ≦⊕θtambién funciona para esto para el mismo número de bytes, aunque se considera 0como arriba en lugar de correcto, por lo que el resto del código debe adaptarse.

✳§rdluθ§>v<^θ

Salida del carácter del cuerpo apropiado en la dirección adecuada.

»o

Restaurar la cabeza. Esto también se puede escribir como Ｐoque imprime la cabeza sin mover el cursor cada vez que pasa por el bucle (pero esto permite que el bucle se cierre implícitamente para el mismo recuento de bytes).

Python 2 , 273 253 242 bytes

^{-11 bytes gracias a ArBo}

g=input()
d=0
t=lambda g,k=1:'\n'.join(map(''.join,zip(*g.split('\n')[::k])[::-k]))
h='o '
while 1:
 l,r=t(g,-1),t(g)
 if h in l:g=l;d-=1
 elif h in g:g=g.replace(h,'>v<^'[d%4]+'o')
 elif h in r:g=r;d+=1
 else:break
exec-d%4*'g=t(g);'
print g

Pruébalo en línea!

Esto funciona buscando la cadena 'o 'y reemplazándola por '[>v<^]o', si está en el laberinto.

La misma comprobación también se realizará en el laberinto girado, imprimiendo el laberinto lleno cuando la cadena ya no esté allí.

La función t=lambda g,k=1:'\n'.join(map(j,zip(*g.split('\n')[::k])[::-k]))se usa para rotar la cuadrícula

Jalea , 72 56 bytes

œṣ€⁾o j€ṛị“v<^>”;”oʋ,
UZ$ṛ¡+ƭ€Ɱ3r5¤ç/€ḟ$Ḣß$ṛ¹?
,0ÇZU$ṛ¡/

Pruébalo en línea!

Un programa completo que toma la entrada como una lista de cadenas y devuelve una lista de cadenas con la serpiente final. Tenga en cuenta que el pie de página en TIO convierte una sola cadena separada de nueva línea en la entrada deseada y restaura las nuevas líneas al final; esto es solo por conveniencia.

Solución algo inspirada en el método utilizado por la respuesta Python 2 de @ Rod , aunque la implementación es muy diferente.

Ruby , 126 118 bytes

-8 bytes guardados al abusar en +=lugar de buscarlos manualmente onuevamente después de reposicionarlos.

->s{d=[q=1,1+l=s=~/$/,-1,~l];i=s=~/o/;(s[i]=">v<^"[q];s[i+=d[q]]=?o)while q=[~-q%4,q,-~q%4].find{|e|s[i+d[e]]==' '};s}

Pruébalo en línea!

Consulta T-SQL 2008, 373 371 366 bytes

Tenía una lista de prioridades, siempre deslizar hacia la izquierda, recta, derecha. Cambié esa prioridad para siempre deslizarme hacia atrás, izquierda, derecha, derecha. El deslizamiento hacia atrás siempre estará bloqueado, por lo que la prioridad sigue siendo la misma, excepto el primer deslizamiento. Al bajar la serpiente inicialmente (C = 4), intenta deslizarse hacia arriba cuando retrocede. Este pequeño truco me ahorró 2 bytes. Porque no necesitaba agregar 1 a ~ - ~ -c% 4.

Inserté 2 saltos de línea para que sea legible

DECLARE @ varchar(8000)=
'################
#o             #
#   ########## #
# #          # #
# #          # #
# #          # #
# #  #       # #
# #          # #
# #          # #
# #          # #
# ############ #
#              #
################';

WITH s as(SELECT 0i,4c,@ m 
UNION ALL
SELECT~-i,x,stuff(stuff(m,~-a+x/3*2+(x-3)%2*s,1,'o')
,a,1,char(59+x+~x%2*11*~x))FROM(SELECT
charindex(' ',replicate(stuff(substring(m,~-a,3),2,1,substring(m,a+~s,1))+
substring(m,a-~s,1)+'~',2),-~-~c%4)%5x,*FROM(SELECT*,charindex('o',m)a,charindex('
',M)S FROM S)Q)L
WHERE x>0)SELECT top 1m FROM s
ORDER BY i
OPTION(MAXRECURSION 0)

Tuve que hacer algunos ajustes menores para ejecutar esto en línea, la versión publicada se ejecuta en el estudio de administración del servidor MS-SQL.

Presione Ctrl-T antes de ejecutarlo en el estudio de administración del servidor MS-SQL, esto mostrará el resultado como texto.

Pruébalo en línea

Python 3 , 343 bytes

import sys
X=0,1,0,-1
F,*Y=*X,0
L=3
g=[*map(list,sys.stdin.read().split("\n"))]
e=enumerate
r,c=[[r,c]for r,R in e(g)for c,C in e(R)if"o"==C][0]
while 1:
	if" "==g[r+X[L]][c+Y[L]]:F,L=L,~-L%4
	elif" "<g[r+X[F]][c+Y[F]]:
		if" "<g[r-X[L]][c-Y[L]]:g[r][c]="o";break
		L,F=F,-~F%4
	g[r][c]=">v<^"[F];r,c=r+X[F],c+Y[F]
for r in g:print("".join(r))

Pruébalo en línea!

-11 bytes gracias a ArBo
-4 bytes gracias a Jonathan Frech

05AB1E , 54 52 bytes

[S¶¡øí3FDíø})J€»¼D¾èU¼.Δ.¼„o ©å}DÄiXqë®">^<v"¾è'o«.;

E / S tanto como una sola cadena de varias líneas.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

[                      # Start an infinite loop:
 S                     #  Split the multi-line string into a list of characters
                       #  (which will use the implicit input in the first iteration)
  ¶¡                   #  Then split by newlines
    øí                 #  Rotate the matrix once clockwise
      3F               #  Loop 3 times:
        D              #   Create a copy of the matrix
         íø            #   And rotate this copy once counterclockwise
       })              #  After the loop: wrap all four matrices into a list
 J                     #  Join each inner-most character-list to string-lines again
  €»                   #  And join each inner list of lines by newlines again
    ¼                  #  Increase variable `c` by 1 (variable `c` is 0 by default)
     D¾<è              #  Index the updated variable `c` in a copy of the list of matrices
                       #  (note that indexing wraps around in 05AB1E)
         U             #  Pop and store it in variable `X`
    ¼                  #  Then increase variable `c` again
    .Δ                 #  Find the first multi-line string in the list which is truthy for:
      .¼               #   Decrease variable `c` by 1 first
        „o             #   Push string "o "
           ©           #   Store this string in variable `®` (without popping)
            å          #   Check if the current multi-line string contains this "o "
    }D                 #  Duplicate the result (results in -1 if none were truthy/found)
      Äi               #  If no result was found:
        X              #   Push variable `X`
         q             #   And stop the program, after which this multi-line string of
                       #   variable `X` is output implicitly as result
       ë               #  Else:
         ">^<v"¾è      #   Get the `c`'th character in string ">^<v"
                       #   (note that indexing wraps around in 05AB1E)
                 'o«  '#   Append a trailing "o" to this character
        ®           .; #   And replace the first variable `®` ("o ") in the 
                       #   multi-line string with this

Pyth , 161 bytes

J.zK[Z1Z_1)=Y+tKZVlJFTl@JNIq@@JNT\oA[NT;=N3=TZ#Iq@@J+G@KN+H@YNd=TN=N%tN4.?In@@J+G@KT+H@YTdIn@@J-G@KN-H@YNd XJGX@JGH\oB=NT=T%hT4)) XJGX@JGH@">v<^"TA(+G@KT+H@YT;jJ

Pruébalo en línea!

Puerto de la solución Python 3 de HyperNeutrino . Ahora que he terminado con esto, estoy pensando que tal vez debería haber portado la solución Rod's Python 2, pero ya pasé demasiado tiempo en esto.