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 n ) , gdzie m jest wielkością wejścia, a n wielkością wyjścia. Dobra rzecz, prędkość się nie liczy!