Escriba un programa o función que, dada una secuencia no vacía de giros a la derecha o izquierda, emite la longitud del camino más corto que se evita a sí mismo en una red 2D con esos giros.

La entrada debe tomarse como una cadena, con cada carácter siendo Ro Lpara un giro a la derecha o izquierda respectivamente.

La salida debe ser un número entero, la longitud del camino más corto con los giros dados.

Este es un gode golf: el código más corto gana.

Ejemplo

Dada la entrada

LLLLLLLLLLRRL

La ruta más corta es la siguiente (a partir de #):

+-+-+-+-+-+-+
|           |  
+ . + +-+-+ +
|   | |   | |  
+ +-+ + #-+ +
| |   |     |  
+ +-+ +-+-+-+
|   |          
+-+-+ . . . .

Y la longitud total de este camino está 29(contando los -s y |s, no la +s).

Casos de prueba

L 2
RRRRRRRRRR 23
LRRLRLRRRRL 15
LLRRLRRRRLLL 17
LLRRRRRRLLLL 21
LLLLRLLRRLLRL 16
LRLRLRLLRLRRL 14
RLLRRRRLLRRLRL 17
RRRRLLRLLLRLRL 20
LLLLRRLRLRRRLRL 19
RRRLRRRLRRLRLRL 20

Prólogo, 284 bytes

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).  
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
n(X):-X=0;n(Y),X#=Y+1.
p(S,L):-n(L),length(X,L),e([0|S],X),c(X,_,_).

Esta es una declaración bastante directa del algoritmo y bastante ineficiente (no todos los casos de prueba se ejecutaron en un tiempo razonable, aunque la mayoría lo hizo). Funciona mediante la generación de todas las longitudes posibles para la salida de 1 hacia arriba ( n); generar todas las secuencias posibles de izquierda / adelante / derecha de esa longitud que sean consistentes con la entrada (implementado en e; se llama a la nueva ruta X); luego verificando la primera ruta de ese tipo que sea válida ( cque llama vpara manejar los efectos de los giros izquierdo y derecho en los deltas x e y). La longitud de retorno es la primera salida vista enL. (Penalización de +2 si desea evitar que la función devuelva otras salidas posibles para la longitud si retrocede en ella; nunca está claro cómo se debe contar la función idiosincrásica de Prolog).

Aquí no hay muchos trucos de golf, pero hay algunos. nse implementó con un solucionador de restricciones porque permite eliminar más espacios en blanco sin confundir el analizador; esto podría requerir el uso de GNU Prolog, no estoy seguro de eso. (No podría hacer lo mismo cya que necesita manejar números negativos). La implementación de ees considerablemente menos eficiente de lo que debe ser, al hacer coincidir una lista de múltiples maneras; el más eficiente e([],[]).sería seis bytes más largo (permitiría S=X;eliminar la línea 2, pero eso es solo una ganancia de cuatro en comparación con una pérdida de diez). Para permitirme X/Yunir las coordenadas y las direcciones como un todo, o solo como parte, las represento como (es decir, un AST no evaluado, que se puede combinar), lo que me permite utilizar la notación infija.

Prolog, 256 bytes, demasiado ineficiente para probar fácilmente

Por supuesto, como se trata de Prolog, muchas de las funciones son reversibles, por ejemplo, cse pueden utilizar para generar todas las rutas desde el origen hasta un par de coordenadas en particular. Además, cnaturalmente genera desde el más corto al más largo. Esto significa que, en lugar de pedir explícitamente una longitud mínima, podemos cgenerar todos los caminos que van a cualquier parte y luego buscar el primero que sea coherente con la entrada:

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
p(S,L):-c(X,_,_),length(X,L),e([0|S],X).

Esto tiene un rendimiento exponencial (O (3 ⁿ ), donde n es la salida). Sin embargo, logré verificarlo en algunas de las pruebas más pequeñas (toma alrededor de 7 segundos para la salida 14 y alrededor de 20 para la salida 15, en mi computadora).

Pyth , 36 bytes

ff{I.u+NYY0f>r8YlQ.C+1*M._m^.j)hCdQT

Pruébalo en línea!

Esto es bastante lento, pero funciona, y es lo suficientemente rápido para entradas cortas.

El programa funciona representando direcciones como unidades complejas (1, -1, i, -i) y puntos como números complejos. Primero convierto la lista de giros en una lista de direcciones, luego genero toda la lista de n pasos, filtro para aquellos con al menos un paso entre cada turno, y convierto las direcciones en una lista de puntos visitados, y verifico si esa lista es único. Incremento n en un bucle hasta tener éxito.

Mapa a números complejos:

m^.j)hCdQ
m       Q    Map over the input
      Cd     Convert to ASCII codepoint
     h       Increment
 ^.j)        Raise i to that power.

Como Ltiene el punto de código ASCII 76 y Rtiene el punto de código ASCII 82, esto se correlaciona Lhacia iy Rhacia -i.

Mapa a direcciones absolutas:

+1*M._ ...
    ._      Form all prefixes
  *M        Map each to its product
+1          Add the first direction, before any turns

Forme listas de n pasos con al menos 1 paso entre cada turno

f>r8YlQ.C ... T
       .C     T    Form all list of T steps
f                  Filter for lists where
  r8Y              Run length encoding of list
 >   lQ            With the first len(input) removed
                   is nonempty

Debería haber un movimiento más que giros en la entrada. Cada movimiento está en una dirección diferente, por lo que la codificación de la longitud de ejecución debe ser más larga que la entrada.

Mapa de puntos visitados:

.u+NYY0  ...
.u   Y0   Reduce the following function over
          the list of steps, starting at 0.
          Return all intermediates.
  +NY     Add the new step to the current position.

Filtrar en no auto-intersección:

f{I ...
f     Filter on
  I   Invariant under
 {    Deduplication

Encuentra la primera Tdonde esta tiene éxito: f.