fundo

A maioria dos editores de texto (meio decentes) permite navegar pelo texto usando as teclas de seta. Para cima e para baixo, você pode navegar pelas linhas, enquanto a esquerda e a direita se movem através de uma linha, mas também se movimentam. Além disso, se a linha for menor que a posição X do seu cursor, o cursor aparecerá no final da linha, mas retornará à mesma posição X se você continuar se movendo para cima ou para baixo. Talvez a seguinte explicação visual ajude:

Exemplos de movimento

Uma simples amostra de texto pode ser assim. O cursor será inserido entre dois caracteres neste texto ou no 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--
---
------

O desafio

Dadas várias linhas de teste ASCII, encontre o caminho mais curto desde o local inicial até o local final. O local inicial é representado por ^e o local final é representado por $, e haverá apenas um de cada. Eles não são considerados parte do texto e não contribuem para o "comprimento" dessa linha.

A entrada consistirá em várias linhas de texto não em branco. A saída será uma série de ^v<>caracteres que mostram um dos caminhos mais curtos. Opcionalmente, você pode assumir uma nova linha adicional no final de cada uma, mas que não está incluída como parte do texto navegável.

Você pode escrever um programa ou função nomeada. O vencedor será o envio mais curto, medido em bytes.

Exemplo 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

Bem, isso levou muitas horas para chegar a algo que parece feito. Parece que o tempo necessário para otimizar agressivamente o código CJam é algo maior que O (n) em relação ao tamanho do código ...

Você pode experimentá-lo on-line , mas, para qualquer entrada cujo melhor caminho seja pelo menos seis operações, provavelmente você deve experimentá-lo off-line com um intérprete mais rápido.

Squished:

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=

Expandido e 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";

No geral, esta é uma solução bastante direta. Ele "executa" os dígitos da representação da base 5 de um número de caminho que é incrementado a cada iteração, começando com 0, até que um caminho funcione. Os dígitos 1- são 4mapeados para as operações para cima, baixo, esquerda e direita e 0não fazem nada. A primeira iteração usando um caminho de apenas 0captura o caso degenerado. Todos os outros caminhos que contêm a 0nunca são selecionados porque são apenas versões de caminhos já testados com não operações adicionais.

O estado é modelado da maneira mais minimalista possível: o texto com os marcadores de início e fim removidos, a posição do cursor no texto e a "memória da coluna". As novas linhas são tratadas principalmente como qualquer outro caractere, portanto não há conceito de linha e a posição do cursor é apenas um índice. Isso simplifica a movimentação da esquerda e da direita, que são implementadas apenas como decremento e incremento (com fixação do tamanho do texto). Mover para cima e para baixo é um pouco mais complicado, mas ainda gerenciável.

A reutilização de código foi uma tática de otimização bastante vital. Exemplos disso incluem:

• Escreva o código para subir de uma maneira que seja menor gerar o código para descer no tempo de execução do que escrever seu próprio código. Isso é feito copiando o código para subir e remover / substituir alguns caracteres.
• A atualização da "memória da coluna" é feita condicionalmente com base no dígito do caminho dividido por 3, em vez de ser codificado na lógica da operação. Isso também permite a inicialização da memória da coluna adicionando uma 5operação fictícia ao início da cadeia de caminho, que também usa a 0lógica no-op devido à indexação circular da matriz e apenas cinco operações definidas.

No geral, estou muito feliz com o resultado. Esse é definitivamente o maior trabalho que eu coloquei em uma resposta de código de golfe até o momento (para algo que se encaixa em um tweet !?). O tempo de execução é bastante abismal, no entanto. CJam não é exatamente o idioma mais rápido para começar e esse algoritmo tem uma complexidade de algo como O (m * 5 ⁿ ) , onde m é o tamanho da entrada en é o tamanho da saída. Ainda bem que a velocidade não conta!

Python 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

Solução simples. Estou realizando uma pesquisa pela primeira vez. titera sobre todos os caminhos diferentes. Eu converto tem base 5, mas apenas uso as entradas que são diferentes de zero. 1está alto, 2baixo, 3esquerda e 4direita.

Eu mantenho a posição atual do cursor em 3 variáveis x, ye z. xé a linha, ya posição da coluna e za posição da coluna 'oculta', se você subir ou descer e a linha for muito curta. Muitos ifs decidem como a variável muda durante um movimento.

O pré-processamento é realmente demorado, as 4 primeiras linhas executam apenas esta tarefa.

O longo caso de teste leva muito tempo. O algoritmo tem uma complexidade de O (N * 5 ^ N), onde N é o comprimento da solução mais curta.

Uso: insira as linhas como uma única sequência (linhas separadas por \n) como"Alp$habet^\nSong"

CJam - 274

Ainda não há resposta? Ok, aqui está um :)

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;

Experimente em http://cjam.aditsu.net/ ..., exceto pelo exemplo de Mary ou algo desse tamanho, você provavelmente desejará o interpretador java .