Latar Belakang

Kebanyakan editor teks (setengah layak) memungkinkan Anda menavigasi teks menggunakan tombol panah. Naik dan turun memungkinkan Anda untuk menavigasi garis, sementara kiri dan kanan bergerak melintasi garis tetapi juga membungkus. Lebih jauh, jika garis lebih pendek dari posisi X kursor Anda, kursor muncul di akhir baris tetapi kembali ke posisi X yang sama jika Anda terus bergerak ke atas atau ke bawah. Mungkin penjelasan visual berikut akan membantu:

Contoh Gerakan

Contoh teks sederhana dapat terlihat seperti ini. Kursor akan disisipkan di antara dua karakter dalam teks ini, atau di akhir.

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

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

Tantangan

Diberikan beberapa baris tes ASCII, temukan jalur terpendek dari lokasi awal ke lokasi akhir. Lokasi awal diwakili oleh ^dan lokasi akhir diwakili oleh $, dan masing-masing hanya akan ada satu. Ini tidak dianggap sebagai bagian dari teks dan tidak berkontribusi pada "panjang" baris itu.

Input akan terdiri dari beberapa baris teks yang tidak kosong. Output akan menjadi serangkaian ^v<>karakter yang menunjukkan salah satu jalur terpendek. Anda dapat mengasumsikan baris baru tambahan di akhir masing-masing, tetapi itu tidak termasuk sebagai bagian dari teks yang bisa dinavigasi.

Anda dapat menulis program atau fungsi bernama. Pemenang akan menjadi pengiriman terpendek, diukur dalam byte.

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

Nah ini butuh waktu berjam-jam untuk sampai pada sesuatu yang terasa sudah selesai. Rasanya seperti waktu yang dibutuhkan untuk secara agresif mengoptimalkan kode CJam adalah sesuatu yang lebih besar daripada O (n) sehubungan dengan ukuran kode ...

Anda dapat mencobanya secara online , tetapi untuk input apa pun yang jalur terbaiknya setidaknya 6 operasi, Anda mungkin harus mencobanya secara offline dengan juru bahasa yang lebih cepat.

Terjepit:

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=

Diperluas dan dikomentari:

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

Secara keseluruhan, ini adalah solusi yang cukup mudah. Ini "mengeksekusi" digit representasi basis-5 dari nomor path yang ditambahkan setiap iterasi, mulai dari 0, hingga sebuah path bekerja. Digit 1- 4memetakan operasi ke atas, bawah, kiri, dan kanan, dan 0tidak melakukan apa pun. Iterasi pertama menggunakan path of just 0catch the degenerate case. Semua lintasan lain yang berisi a 0tidak pernah dipilih karena itu hanya versi lintasan yang sudah diuji dengan tambahan no-ops.

Keadaan dimodelkan dalam cara seminimal mungkin: teks dengan penanda awal dan akhir dihapus, posisi kursor dalam teks, dan "memori kolom". Baris baru sebagian besar diperlakukan seperti karakter lain, jadi tidak ada konsep baris, dan posisi kursor hanya indeks. Ini membuat bergerak ke kiri dan kanan mati sederhana, yang hanya diimplementasikan sebagai penurunan dan penambahan (dengan menjepit ke ukuran teks). Bergerak ke atas dan ke bawah agak rumit, tetapi masih dapat dikelola.

Penggunaan kembali kode adalah taktik optimisasi yang sangat vital. Contohnya termasuk:

• Menulis kode untuk naik sedemikian rupa sehingga lebih kecil untuk menghasilkan kode untuk bergerak turun saat runtime daripada menulis kode sendiri. Ini dilakukan dengan menyalin kode untuk bergerak ke atas dan menghapus / mengganti beberapa karakter.
• Memperbarui "memori kolom" dilakukan secara kondisional berdasarkan jalur digit dibagi dengan 3 bukannya dikodekan ke dalam logika operasi. Ini juga memungkinkan inisialisasi memori kolom dengan menambahkan 5operasi dummy ke awal string path, yang juga kebetulan menggunakan 0logika no-op karena pengindeksan array array dan hanya ada 5 operasi yang ditentukan.

Secara keseluruhan, saya sangat senang dengan bagaimana ini keluar. Ini jelas merupakan pekerjaan terbanyak yang saya masukkan ke dalam kode golf jawaban terkini (untuk sesuatu yang cocok dengan tweet !?). Namun, jangka waktu berjalan sangat buruk. CJam bukan bahasa tercepat untuk memulai dan algoritma ini memiliki kompleksitas seperti O (m * 5 ⁿ ) , di mana m adalah ukuran input dan n adalah ukuran output. Kecepatan hal yang baik tidak masuk hitungan!

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

Solusi mudah. Saya melakukan pencarian luas pertama. tberalih ke semua jalur yang berbeda. Saya mengkonversi tke basis 5, tetapi hanya menggunakan entri, yang bukan nol. 1naik, 2turun, 3kiri dan 4kanan.

Saya menjaga posisi kursor saat ini dalam 3 variabel x, ydan z. xadalah garis, yposisi kolom, dan posisi kolom z'tersembunyi', jika Anda naik atau turun dan garis terlalu pendek. Banyak ifs yang memutuskan, bagaimana variabel berubah selama pemindahan.

Preprocessing sangat panjang, 4 baris pertama hanya melakukan tugas ini.

Testcase panjang membutuhkan waktu yang sangat lama. Algoritma ini memiliki kompleksitas O (N * 5 ^ N), di mana N adalah panjang dari solusi terpendek.

Penggunaan: Masukkan garis sebagai string tunggal (garis yang dipisahkan oleh \n) seperti"Alp$habet^\nSong"

CJam - 274

Belum ada jawaban? Ok, ini satu :)

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;

Cobalah di http://cjam.aditsu.net/ ... kecuali untuk contoh Mary atau sesuatu yang seukuran itu, Anda mungkin ingin penerjemah java .