Antecedentes

La mayoría de los editores de texto (medio decentes) le permiten navegar por el texto con las teclas de flecha. Arriba y abajo le permiten navegar por las líneas, mientras que izquierda y derecha se mueven a través de una línea, pero también se envuelven. Además, si la línea es más corta que la posición X de su cursor, el cursor aparece al final de la línea pero vuelve a la misma posición X si continúa moviéndose hacia arriba o hacia abajo. Quizás la siguiente explicación visual ayudará:

Ejemplos de movimiento

Una muestra simple de texto podría verse así. El cursor se insertará entre dos caracteres en este texto, o al final.

-----
---
------

let's put the cursor here:

X-----
---
------

move down (v):

-----
X---
------

move left (<):

-----X
---
------

v

-----
---X
------

v (notice how the X position of the cursor has been maintained)

-----
---
-----X-

^

-----
---X
------

>  (more line wrapping)

-----
---
X------

<

-----
---X
------

^ (the X-position from earlier is no longer maintained due to the left-right motion)

---X--
---
------

El reto

Dadas varias líneas de prueba ASCII, encuentre la ruta más corta desde la ubicación inicial hasta la ubicación final. La ubicación inicial está representada por ^y la ubicación final está representada por $, y solo habrá una de cada una. No se consideran parte del texto y no contribuyen a la "longitud" de esa línea.

La entrada consistirá en varias líneas de texto no en blanco. La salida será una serie de ^v<>caracteres que muestran una de las rutas más cortas. Opcionalmente, puede asumir una nueva línea adicional al final de cada una, pero eso no se incluye como parte del texto navegable.

Puede escribir un programa o una función con nombre. El ganador será el envío más corto, medido en bytes.

Ejemplo de E / S

^Squares
are
fun$ny

vv<v  (which is better than the naive vv>>>)

Squares
^are
funny$

<vv

Alp$habet^
Song

v<^

Mary had a little lamb,
His fleece was white as snow,
And$ everywhere that ^Mary went,
The lamb was sure to go.

^^>>>>v>>>

$^degenerate case

(no output)

CJam, 139 bytes

Bueno, esto tomó muchas horas para llegar a algo que se siente hecho. Parece que el tiempo que se tarda en optimizar agresivamente el código CJam es algo mayor que O (n) con respecto al tamaño del código ...

Puede probarlo en línea , pero para cualquier entrada para la que la mejor ruta sea al menos 6 operaciones más o menos, probablemente debería probarlo fuera de línea con un intérprete más rápido.

Aplastado:

q_'$-_'^-:T;'^#\'^-'$#W{)2$5Y$5b+{:D[L"_T<W%_N#)_@>N+N#X-Ue>+-"_"W%-U"--2'<t2'>t'++'(')]=~0e>T,e<D3/1$T<N\+W%N#X?:X;}/2$-}g5b{" ^v<>"=}%]W=

Ampliado y comentado:

q               "Read the input";
_'$-            "Remove the end marker";
_'^-:T;         "Remove the start marker and save the text";
'^#             "With only the end marker removed, locate the start marker";
\'^-'$#         "With only the start marker removed, locate the end marker";
W               "Initialize the path number to -1";
{               "Do...";
  )               "Increment the path number";
  2$              "Initialize the cursor position to that of the start marker";
  5Y$5b+          "Convert the path number to base 5, then add a leading 5
                   (the leading 5 will act to initialize the column memory)";
  {:D             "For each digit in the path digit string:";
    [               "Begin cases:";
      L               "0: Do nothing";
      "_T<W%_N#)_@>N+N#X-Ue>+-"
"REFS: [   1   ][  2  ][ 3 ]45
                       1: [1] Calculate the distance to the end of the previous
                              line (0 if no such line)
                          [2] Calculate the length of the previous line (0 if
                              no such line)
                          [3] Calculate the distance to move backwards in the
                              previous line as the maximum of the length of the
                              previous line minus the column memory and 0
                          [4] Calculate the total distance to move as the sum 
                              of [1] and [3]
                          [5] Subtract [4] from the cursor position";
      _"W%-U"-        "2: Start with a base of the logic of case 1, but with a
                          few operations adjusted.";
      -2'<t2'>t       "   [1] Calculate the distance to the *start* of the
                              *next* line (0 if no such line)
                          [2] Calculate the length of the *next* line (0 if no
                              such line)
                          [3] Calculate the distance to move *forwards* in the
                              *next* line as the *minimum* of the length of the
                              *next line* and *the column memory*
                          [4] Calculate the total distance to move as the sum 
                              of [1] and [3]";
      '++             "   [5] *Add* [4] *to* the cursor position";
      '(              "3: Decrement the cursor position";
      ')              "4: Increment the cursor position";
    ]=~             "Execute the case corresponding to the path digit mod 5";
    0e>T,e<         "Clamp the cursor position to [0, text length]";
    D3/             "Check if the path digit is not 0, 1, or 2...";
    1$T<N\+W%N#     "Calculate the current column";
    X?:X;           "If the above check succeeded, update the column memory";
  }/              "End for each";
  2$-             "Subtract the end marker position from the cursor position";
}g              "... While the above subtraction is nonzero";
5b              "Convert the path number to base 5";
{" ^v<>"=}%     "Map each digit in the path string to its operation symbol";
]W=             "Clean up";

En general, esta es una solución bastante sencilla. "Ejecuta" los dígitos de la representación de base 5 de un número de ruta que se incrementa en cada iteración, comenzando con 0, hasta que una ruta funciona. Los dígitos 1: se 4asignan a las operaciones arriba, abajo, izquierda y derecha, y 0no hace nada. La primera iteración usando una ruta de solo 0captura el caso degenerado. Todas las demás rutas que contienen a 0nunca se seleccionan porque son solo versiones de rutas ya probadas con no-ops adicionales.

El estado se modela de la manera más minimalista posible: el texto con los marcadores de inicio y fin eliminados, la posición del cursor en el texto y la "memoria de columna". Las líneas nuevas se tratan principalmente como cualquier otro carácter, por lo que no hay un concepto de fila y la posición del cursor es solo un índice. Esto hace que moverse a la izquierda y a la derecha sea simple, que solo se implementan como decremento e incremento (con sujeción al tamaño del texto). Moverse hacia arriba y hacia abajo es un poco más complicado, pero aún manejable.

La reutilización del código fue una táctica de optimización bastante vital. Ejemplos de esto incluyen:

• Escribir el código para subir de manera tal que sea más pequeño generar el código para bajar en tiempo de ejecución que escribir su propio código. Esto se hace copiando el código para subir y eliminar / reemplazar algunos caracteres.
• La actualización de la "memoria de columna" se realiza condicionalmente en función del dígito de ruta dividido por 3 en lugar de codificarse en la lógica de la operación. Esto también permite la inicialización de la memoria de la columna al agregar una 5operación ficticia al inicio de la cadena de ruta, que también utiliza la 0lógica no operativa debido a la indexación de matriz circular y solo hay 5 operaciones definidas.

En general, estoy muy contento con cómo salió esto. Este es definitivamente el mayor trabajo que he puesto en una respuesta de código de golf hasta la fecha (¡por algo que cabe en un tweet !?). Sin embargo, el tiempo de ejecución es bastante abismal. Para empezar, CJam no es exactamente el lenguaje más rápido y este algoritmo tiene una complejidad de algo como O (m * 5 ⁿ ) , donde m es el tamaño de la entrada yn es el tamaño de la salida. ¡Qué bueno que la velocidad no cuenta!

Pitón 2: 446

Q=input().split('\n');
def g(c):l=[l for l in Q if c in l][0];return Q.index(l),l.index(c)
a,b=g('^');c,d=g('$');Q=map(len,Q);Q[a]-=1;Q[c]-=1
if a==c:d-=b<d;b-=d<b
t=-1
while Q:
 l=[];T=t=t+1;x,y,z=a,b,b
 while T:l+=[T%5]*(T%5>0);T/=5
 for T in l:A=":x+=T+T-3;y=min(Q[x],z)";B="x<len(Q)-1";exec"if "+["","x"+A,B+A,"y:y=z=y-1\nelif x:x-=1;y=z=Q[x]","y<Q[x]:y=z=y+1\nelif "+B+":x+=1;y=z=0"][T]
 if(x,y)==(c,d):print''.join(' ^v<>'[x]for x in l);Q=0

Solución directa. Estoy realizando una búsqueda de amplitud. titera sobre todos los caminos diferentes. Convierto ten base 5, pero solo uso las entradas, que no son cero. 1está arriba, 2está abajo, 3está a la izquierda y 4está a la derecha.

Mantengo la posición actual del cursor en 3 variables x, yy z. xes la línea, yla posición de la columna y zla posición de la columna 'oculta', si sube o baja y la línea es demasiado corta. Muchos ifs deciden cómo cambia la variable durante un movimiento.

El preprocesamiento es realmente largo, las primeras 4 líneas realizan solo esta tarea.

El largo caso de prueba lleva mucho tiempo. El algoritmo tiene una complejidad de O (N * 5 ^ N), donde N es la longitud de la solución más corta.

Uso: ingrese las líneas como una sola cadena (líneas separadas por \n) como"Alp$habet^\nSong"

CJam - 274

¿Sin respuesta aún? Ok, aquí hay uno :)

qN/_{0:V;{_'^={[UVV]:B;;}{'$={[UV]:E;}{V):V;}?}?}/U):U;}/"^$"f-:,:A;{:X0=[X0=(_A=X2=_@e<\]X?}:U;{:X0=A,(=X[X0=)_A=X2=_@e<\]?}:D;{:X1=[X~;(_]{X0=[X0=(_A=_]X?}?}:L;{:X1=X0=A=={X0=A,(=X[X0=)0_]?}[X~;)_]?}:R;[[BM]]{_{0=2<E=},_{0=1=o0}{;[{"U^DvL<R>"2/\f{[~@1/~@\+@@~\]}~}/]1}?}g;

Pruébelo en http://cjam.aditsu.net/ ... excepto por el ejemplo de Mary o algo de ese tamaño, probablemente querrá el intérprete de Java .