Contexte

La plupart des éditeurs de texte (à moitié décents) vous permettent de parcourir le texte à l'aide des touches fléchées. Le haut et le bas vous permettent de naviguer dans les lignes, tandis que la gauche et la droite se déplacent sur une ligne, mais aussi de s'enrouler. De plus, si la ligne est plus courte que la position X de votre curseur, le curseur apparaît à la fin de la ligne mais revient à la même position X si vous continuez à monter ou à descendre. Peut-être que l'explication visuelle suivante vous aidera:

Exemples de mouvement

Un simple exemple de texte pourrait ressembler à ceci. Le curseur sera inséré entre deux caractères dans ce texte, ou à la fin.

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

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

Le défi

Étant donné plusieurs lignes de test ASCII, recherchez le chemin le plus court entre l'emplacement de départ et l'emplacement de fin. L'emplacement de début est représenté par ^et l'emplacement de fin est représenté par $, et il n'y en aura qu'un de chaque. Ceux-ci ne sont pas considérés comme faisant partie du texte et ne contribuent pas à la «longueur» de cette ligne.

L'entrée consistera en plusieurs lignes de texte non vides. La sortie sera une série de ^v<>caractères qui montrent l'un des chemins les plus courts. Vous pouvez éventuellement supposer une nouvelle ligne supplémentaire à la fin de chaque, mais qui n'est pas incluse dans le texte navigable.

Vous pouvez écrire un programme ou une fonction nommée. Le gagnant sera la soumission la plus courte, mesurée en octets.

Exemple d'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 octets

Eh bien, cela a pris plusieurs heures pour arriver à quelque chose qui semble terminé. Il semble que le temps nécessaire pour optimiser agressivement le code CJam soit plus grand que O (n) qui concerne la taille du code ...

Vous pouvez l' essayer en ligne , mais pour toute entrée pour laquelle le meilleur chemin est d'au moins 6 opérations, vous devriez probablement l' essayer hors ligne avec un interprète plus rapide.

Écrasé:

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=

Développé et commenté:

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

Dans l'ensemble, c'est une solution assez simple. Il "exécute" les chiffres de la représentation en base 5 d'un numéro de chemin qui est incrémenté à chaque itération, en commençant par 0, jusqu'à ce qu'un chemin fonctionne. Les chiffres 1- 4mappent les opérations vers le haut, le bas, la gauche et la droite, et 0ne font rien. La première itération utilisant un chemin de 0capture juste le cas dégénéré. Tous les autres chemins qui contiennent un 0ne sont jamais sélectionnés car ce ne sont que des versions de chemins déjà testés avec des no-op ajoutés.

L'état est modélisé de la manière la plus minimaliste possible: le texte avec les marqueurs de début et de fin supprimés, la position du curseur dans le texte et la «mémoire des colonnes». Les retours à la ligne sont généralement traités comme n'importe quel autre caractère, il n'y a donc pas de concept de ligne et la position du curseur n'est qu'un index. Cela rend les déplacements à gauche et à droite simples, qui sont simplement implémentés comme décrémentation et incrémentation (avec serrage à la taille du texte). Monter et descendre est un peu plus délicat, mais toujours gérable.

La réutilisation du code était une tactique d'optimisation assez vitale. En voici quelques exemples:

• Écrire le code pour monter d'une manière telle qu'il est plus petit de générer le code pour descendre vers le bas à l'exécution que d'écrire son propre code. Cela se fait en copiant le code pour remonter et supprimer / remplacer quelques caractères.
• La mise à jour de la "mémoire de colonne" se fait conditionnellement sur la base du chiffre de chemin divisé par 3 au lieu d'être codé dans la logique de l'opération. Cela permet également l'initialisation de la mémoire de colonne en ajoutant une 5opération fictive au début de la chaîne de chemin d'accès, ce qui se produit également en utilisant la 0logique no-op en raison de l'indexation du tableau circulaire et qu'il n'y a que 5 opérations définies.

Dans l'ensemble, je suis très heureux de la façon dont cela s'est produit. C'est certainement le plus de travail que j'ai mis dans une réponse de golf de code à ce jour (pour quelque chose qui tient dans un tweet!?). Le temps d'exécution est cependant assez épouvantable. CJam n'est pas exactement le langage le plus rapide pour commencer et cet algorithme a une complexité de quelque chose comme O (m * 5 ⁿ ) , où m est la taille de l'entrée et n est la taille de la sortie. Heureusement, la vitesse ne compte pas!

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

Solution simple. J'effectue une recherche en premier. titère sur tous les chemins différents. Je convertis ten base 5, mais n'utilise que les entrées, qui sont différentes de zéro. 1est en haut, en 2bas, à 3gauche et à 4droite.

Je garde la position actuelle du curseur dans 3 variables x, yet z. xest la ligne, yla position de la colonne et zla position de la colonne «cachée», si vous montez ou descendez et que la ligne est trop courte. De nombreux ifs décident de la façon dont la variable change lors d'un déplacement.

Le prétraitement est vraiment long, les 4 premières lignes n'effectuent que cette tâche.

Le long testcase prend vraiment beaucoup de temps. L'algorithme a une complexité de O (N * 5 ^ N), où N est la longueur de la solution la plus courte.

Utilisation: Entrez les lignes comme une seule chaîne (lignes séparées par \n) comme"Alp$habet^\nSong"

CJam - 274

Pas encore de réponse? Ok, en voici un :)

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;

Essayez-le sur http://cjam.aditsu.net/ ... sauf pour l'exemple Mary ou quelque chose de cette taille, vous voudrez probablement l' interpréteur java .