tło

Większość edytorów tekstu (w połowie przyzwoitych) pozwala nawigować po tekście za pomocą klawiszy strzałek. W górę i w dół pozwalają nawigować po liniach, podczas gdy w lewo i w prawo poruszają się po linii, ale także obejmują. Ponadto, jeśli linia jest krótsza niż pozycja X kursora, kursor pojawia się na końcu linii, ale wraca do tej samej pozycji X, jeśli poruszasz się w górę lub w dół. Być może pomocne będą następujące wyjaśnienia wizualne:

Przykłady ruchu

Prosta próbka tekstu może wyglądać tak. Kursor zostanie wstawiony między dwoma znakami w tym tekście lub na końcu.

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

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

Wyzwanie

Biorąc pod uwagę kilka wierszy testu ASCII, znajdź najkrótszą ścieżkę od lokalizacji początkowej do końcowej. Lokalizacja początkowa jest reprezentowana przez, ^a lokalizacja końcowa jest reprezentowana przez $, i będzie tylko jedna z nich. Nie są one uważane za część tekstu i nie wpływają na „długość” tego wiersza.

Dane wejściowe będą składały się z kilku niepustych wierszy tekstu. Wyjście będzie serią ^v<>znaków, które pokazują jedną z najkrótszych ścieżek. Opcjonalnie możesz założyć dodatkowy nowy wiersz na końcu każdego, ale nie jest on zawarty w tekście nawigacyjnym.

Możesz napisać program lub nazwaną funkcję. Zwycięzcą zostanie zgłoszenie najkrótsze, mierzone w bajtach.

Przykład I / O

^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 bajtów

Cóż, zajęło to wiele godzin, aby dojść do czegoś, co wydaje się zrobione. Wydaje się, że czas potrzebny do agresywnej optymalizacji kodu CJam jest większy niż O (n) w odniesieniu do rozmiaru kodu ...

Możesz wypróbować go w trybie online , ale dla każdego wejścia, dla którego najlepsza ścieżka to co najmniej 6 operacji, prawdopodobnie powinieneś spróbować w trybie offline z szybszym tłumaczem.

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=

Rozszerzony i skomentowany:

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

Ogólnie rzecz biorąc, jest to dość proste rozwiązanie. „Wykonuje” cyfry reprezentacji base-5 numeru ścieżki, która jest zwiększana przy każdej iteracji, zaczynając od 0, aż ścieżka zadziała. Cyfry 1- 4odwzorowują operacje w górę, w dół, w lewo i w prawo i 0nic nie robią. Pierwsza iteracja wykorzystująca ścieżkę po prostu 0chwyta zdegenerowany przypadek. Wszystkie inne ścieżki zawierające 0nigdy nie są wybierane, ponieważ są tylko wersjami już przetestowanych ścieżek z dodanymi opcjami.

Stan jest modelowany w możliwie minimalistyczny sposób: tekst z usuniętymi znacznikami początkowym i końcowym, pozycja kursora w tekście oraz „pamięć kolumny”. Znaki nowej linii są w większości traktowane jak każdy inny znak, więc nie ma pojęcia o wierszu, a pozycja kursora jest tylko indeksem. To sprawia, że ​​poruszanie się w lewo i w prawo jest bardzo proste, które są po prostu zaimplementowane jako zmniejszanie i zwiększanie (z mocowaniem do rozmiaru tekstu). Poruszanie się w górę i w dół jest nieco trudniejsze, ale nadal możliwe do opanowania.

Ponowne użycie kodu było dość istotną taktyką optymalizacyjną. Przykłady tego obejmują:

• Pisanie kodu do przejścia w górę w taki sposób, że wygenerowanie kodu do przejścia w dół w czasie wykonywania jest mniejsze niż napisanie własnego kodu. Odbywa się to poprzez skopiowanie kodu przejścia w górę i usunięcia / zamiany kilku znaków.
• Aktualizowanie „pamięci kolumny” odbywa się warunkowo na podstawie cyfry ścieżki podzielonej przez 3 zamiast kodowania jej w logice operacji. Pozwala to również na zainicjowanie pamięci kolumny przez dodanie 5operacji zastępczej na początku ciągu ścieżki, co również zdarza się, że używa 0logiki no-op ze względu na indeksowanie macierzy cyklicznej i tylko 5 zdefiniowanych operacji.

Ogólnie jestem bardzo zadowolony z tego, jak to wyszło. To zdecydowanie jak dotąd najwięcej pracy, jaką włożyłem w odpowiedź na kod do golfa (coś, co pasuje do tweeta !?). Czas działania jest jednak dość fatalny. CJam nie jest na początku najszybszym językiem, a ten algorytm ma złożoność czegoś takiego jak O (m * 5 ⁿ ) , gdzie m jest wielkością wejścia, a n wielkością wyjścia. Dobra rzecz, prędkość się nie liczy!

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

Proste rozwiązanie. Przeprowadzam pierwsze wyszukiwanie. titeruje po wszystkich różnych ścieżkach. Przekształcam tna bazę 5, ale używam tylko wpisów, które są niezerowe. 1jest w górę, 2jest w dół, 3jest w lewo i 4ma rację.

I zachować aktualną pozycję kursora w 3 zmiennych x, yi z. xto linia, ypozycja kolumny i z„ukryta” pozycja kolumny, jeśli przejdziesz w górę lub w dół, a linia jest za krótka. Wiele ifs decyduje o zmianie zmiennej podczas ruchu.

Wstępne przetwarzanie jest naprawdę długie, pierwsze 4 linie wykonują tylko to zadanie.

Długa próba trwa naprawdę długo. Algorytm ma złożoność O (N * 5 ^ N), gdzie N jest długością najkrótszego rozwiązania.

Zastosowanie: Wprowadź linie jako pojedynczy ciąg (linie oddzielone \n) jak"Alp$habet^\nSong"

CJam - 274

Brak odpowiedzi? Ok, oto jeden :)

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;

Wypróbuj na stronie http://cjam.aditsu.net/ ... oprócz przykładu Mary lub czegoś takiego, prawdopodobnie będziesz potrzebował tłumacza Java .