Фон

Большинство (наполовину приличных) текстовых редакторов позволяют перемещаться по тексту с помощью клавиш со стрелками. Вверх и вниз позволяют перемещаться по линиям, а левый и правый перемещаются по линии, но также могут перемещаться вокруг. Кроме того, если линия короче позиции X вашего курсора, курсор появляется в конце строки, но возвращается к той же позиции X, если вы продолжаете двигаться вверх или вниз. Возможно, поможет следующее визуальное объяснение:

Примеры движения

Простой образец текста может выглядеть следующим образом. Курсор будет вставлен между двумя символами в этом тексте или в конце.

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

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

Соревнование

Учитывая несколько строк теста ASCII, найдите кратчайший путь от начального местоположения до конечного местоположения. Начальное местоположение представлено как, ^и конечное местоположение представлено $, и будет только один из каждого. Они не считаются частью текста и не влияют на «длину» этой строки.

Ввод будет состоять из нескольких непустых строк текста. Вывод будет серией ^v<>символов, которые показывают один из самых коротких путей. При желании вы можете добавить дополнительный символ новой строки в конце каждого, но он не включен в текст навигации.

Вы можете написать программу или именованную функцию. Победителем будет самое короткое представление, измеренное в байтах.

Пример ввода / вывода

^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 байтов

Ну, это заняло много часов, чтобы прийти к тому, что кажется готовым. Похоже, что время, которое требуется для агрессивной оптимизации кода CJam, больше, чем O (n) по отношению к размеру кода ...

Вы можете попробовать его онлайн , но для любого ввода, для которого наилучший путь составляет не менее 6 операций или около того, вам, вероятно, следует попробовать его в автономном режиме с более быстрым интерпретатором.

сплющенные:

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=

Расширено и прокомментировано:

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

В целом, это довольно простое решение. Он «выполняет» цифры представления base-5 номера пути, который увеличивается на каждой итерации, начиная с 0, до тех пор, пока путь не будет работать. Цифры 1- 4отображают операции вверх, вниз, влево и вправо и 0ничего не делают. Первая итерация, использующая путь just, 0ловит вырожденный случай. Все остальные пути, содержащие a 0, никогда не выбираются, потому что это просто версии уже протестированных путей с добавленными no-ops.

Состояние моделируется настолько минималистично, насколько это возможно: текст с удаленными маркерами начала и конца, положение курсора в тексте и «память столбца». Символы новой строки в основном обрабатываются как любой другой символ, поэтому концепция строки отсутствует, а позиция курсора - просто индекс. Это упрощает перемещение влево и вправо, что просто реализуется как уменьшение и приращение (с ограничением по размеру текста). Движение вверх и вниз немного сложнее, но все же управляемо.

Повторное использование кода было довольно важной тактикой оптимизации. Примеры этого включают в себя:

• Написание кода для продвижения вверх таким образом, чтобы меньше генерировать код для перемещения во время выполнения, чем для написания собственного кода. Это делается путем копирования кода для перемещения вверх и удаления / замены нескольких символов.
• Обновление «памяти столбцов» выполняется условно на основе цифры пути, деленной на 3, вместо того, чтобы кодироваться в логику операции. Это также позволяет инициализировать память столбца путем добавления фиктивной 5операции в начало строки пути, которая также использует 0логику запрета операций из-за индексации циклического массива и имеет только 5 определенных операций.

В целом, я очень доволен тем, как это получилось. Это определенно самая большая работа, которую я поместил в ответе по гольфу в коде на сегодняшний день (для чего-то, что вписывается в твит !?). Время выполнения довольно ужасно, хотя. CJam не является самым быстрым языком для начала, и этот алгоритм имеет такую ​​сложность, как O (m * 5 ⁿ ) , где m - размер ввода, а n - размер вывода. Хорошая скорость не считается!

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

Простое решение. Я выполняю поиск в ширину. tперебирает все разные пути. Я конвертирую tв базу 5, но использую только записи, отличные от нуля. 1вверх, 2вниз, 3слева и 4справа.

Я сохраняю текущую позицию курсора в 3 переменных x, yи z. xэто линия, yпозиция столбца и z«скрытая» позиция столбца, если вы идете вверх или вниз, а линия слишком короткая. Много ifs решают, как переменная изменяется во время движения.

Предварительная обработка действительно длительная, первые 4 строки выполняют только эту задачу.

Длинный тестовый сценарий занимает очень много времени. Алгоритм имеет сложность O (N * 5 ^ N), где N - длина кратчайшего решения.

Использование: Введите строки как одну строку (разделенные строки \n), как"Alp$habet^\nSong"

CJam - 274

Ответа пока нет? Хорошо, вот один :)

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;

Попробуйте это на http://cjam.aditsu.net/ ... за исключением примера с Мэри или чего-то такого размера, вам, вероятно, понадобится Java-интерпретатор .