Hintergrund

Mit den meisten (halbwegs anständigen) Texteditoren können Sie mit den Pfeiltasten durch den Text navigieren. Nach oben und unten können Sie durch Linien navigieren, während sich links und rechts über eine Linie bewegen, aber auch umlaufen. Wenn die Linie kürzer als die X-Position Ihres Cursors ist, wird der Cursor am Ende der Linie angezeigt, kehrt jedoch zur gleichen X-Position zurück, wenn Sie sich weiter nach oben oder unten bewegen. Vielleicht hilft die folgende visuelle Erklärung:

Beispiele für Bewegung

Ein einfaches Textbeispiel könnte so aussehen. Der Cursor wird zwischen zwei Zeichen in diesem Text oder an einem Ende eingefügt.

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

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

Die Herausforderung

Suchen Sie bei mehreren ASCII-Testzeilen den kürzesten Weg vom Startort zum Endort. Der Startort wird durch ^und der Endort durch dargestellt $, und es wird jeweils nur einen geben. Diese werden nicht als Teil des Textes betrachtet und tragen nicht zur "Länge" dieser Zeile bei.

Die Eingabe besteht aus mehreren nicht leeren Textzeilen. Die Ausgabe besteht aus einer Reihe von ^v<>Zeichen, die einen der kürzesten Pfade anzeigen. Optional können Sie am Ende jeweils einen zusätzlichen Zeilenumbruch annehmen, der jedoch nicht im navigierbaren Text enthalten ist.

Sie können ein Programm oder eine benannte Funktion schreiben. Der Gewinner ist die kürzeste Einsendung, gemessen in Bytes.

Beispiel E / A.

^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

Nun, es hat viele Stunden gedauert, bis etwas erreicht war, das sich erledigt anfühlt. Es scheint, dass die Zeit, die benötigt wird, um CJam-Code aggressiv zu optimieren, in Bezug auf die Größe des Codes etwas größer als O (n) ist ...

Sie können es online ausprobieren , aber für jede Eingabe, für die der beste Pfad mindestens 6 Operationen sind, sollten Sie es wahrscheinlich offline mit einem schnelleren Interpreter versuchen .

Gequetscht:

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=

Erweitert und kommentiert:

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

Insgesamt ist dies eine ziemlich einfache Lösung. Es "führt" die Ziffern der Basis-5-Darstellung einer Pfadnummer aus, die bei jeder Iteration beginnend mit 0 inkrementiert wird, bis ein Pfad funktioniert. Die Ziffern 1- 4Karte auf die Operationen nach oben, unten, links und rechts, und 0tut nichts. Die erste Iteration unter Verwendung eines Pfades von 0fängt nur den entarteten Fall ab. Alle anderen Pfade, die a enthalten, 0werden nie ausgewählt, da es sich nur um Versionen bereits getesteter Pfade mit hinzugefügten No-Ops handelt.

Der Status wird so minimalistisch wie möglich modelliert: der Text mit entfernten Start- und Endmarkierungen, die Cursorposition im Text und der "Spaltenspeicher". Zeilenumbrüche werden meistens wie jedes andere Zeichen behandelt, daher gibt es kein Konzept für eine Zeile, und die Cursorposition ist nur ein Index. Dies macht das Verschieben nach links und rechts ganz einfach, die nur als Dekrement und Inkrement implementiert werden (mit Klemmung auf die Größe des Textes). Das Auf und Ab zu bewegen ist etwas schwieriger, aber immer noch überschaubar.

Die Wiederverwendung von Code war eine ziemlich wichtige Optimierungstaktik. Beispiele hierfür sind:

• Schreiben Sie den Code für die Aufwärtsbewegung so, dass es kleiner ist, den Code für die Abwärtsbewegung zur Laufzeit zu generieren, als seinen eigenen Code zu schreiben. Dies erfolgt durch Kopieren des Codes zum Aufrücken und Entfernen / Ersetzen einiger Zeichen.
• Das Aktualisieren des "Spaltenspeichers" erfolgt bedingt basierend auf der durch 3 geteilten Pfadziffer, anstatt dass sie in die Logik der Operation codiert wird. Dies ermöglicht auch die Initialisierung des Spaltenspeichers durch Hinzufügen einer Dummy- 5Operation am Anfang der Pfadzeichenfolge, die 0aufgrund der zirkulären Array-Indizierung und nur 5 definierten Operationen zufällig die No-Op-Logik verwendet.

Insgesamt bin ich sehr zufrieden mit dem Ergebnis. Dies ist definitiv die meiste Arbeit, die ich bisher in eine Code-Golf-Antwort gesteckt habe (für etwas, das in einen Tweet passt!?). Die Laufzeit ist allerdings ziemlich miserabel. CJam ist nicht gerade die schnellste Sprache, und dieser Algorithmus hat eine Komplexität von etwa O (m * 5 ⁿ ) , wobei m die Größe der Eingabe und n die Größe der Ausgabe ist. Gut, dass Geschwindigkeit nicht zählt!

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

Einfache Lösung. Ich führe eine Breitensuche durch. titeriert über alle verschiedenen Pfade. Ich konvertiere tin Basis 5, verwende aber nur die Einträge, die ungleich Null sind. 1ist oben, 2ist unten, 3ist links und 4ist rechts.

Ich halte die aktuelle Position des Cursors in 3 Variablen x, yund z. xist die Zeile, ydie Spaltenposition und zdie 'versteckte' Spaltenposition, wenn Sie nach oben oder unten gehen und die Zeile zu kurz ist. Viele Wenns entscheiden, wie sich die Variable während eines Zuges ändert.

Die Vorverarbeitung ist sehr langwierig, die ersten 4 Zeilen führen nur diese Aufgabe aus.

Der lange Testfall dauert sehr lange. Der Algorithmus hat eine Komplexität von O (N * 5 ^ N), wobei N die Länge der kürzesten Lösung ist.

Verwendung: Geben Sie die Zeilen als einzelne Zeichenfolge (Zeilen getrennt durch \n) wie ein"Alp$habet^\nSong"

CJam - 274

Noch keine Antwort? Ok, hier ist einer :)

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;

Probieren Sie es unter http://cjam.aditsu.net/ aus . Mit Ausnahme des Mary-Beispiels oder etwas in dieser Größe möchten Sie wahrscheinlich den Java-Interpreter .