Tulis sebuah program atau fungsi yang, dengan urutan belokan kanan atau kiri yang tidak kosong , menampilkan panjang jalur penghindaran diri terpendek pada kisi 2D dengan belokan itu.

Input harus diambil sebagai string, dengan masing-masing karakter menjadi Ratau Luntuk belokan kanan atau kiri masing-masing.

Output harus berupa bilangan bulat, panjang jalur terpendek dengan belokan yang diberikan.

Ini adalah golf gode - kode menang paling pendek.

Contoh

Diberikan input

LLLLLLLLLLRRL

Jalur terpendek adalah sebagai berikut (mulai dari #):

+-+-+-+-+-+-+
|           |  
+ . + +-+-+ +
|   | |   | |  
+ +-+ + #-+ +
| |   |     |  
+ +-+ +-+-+-+
|   |          
+-+-+ . . . .

Dan total panjang jalur ini adalah 29(menghitung -s dan |s, bukan +s).

Uji Kasus

L 2
RRRRRRRRRR 23
LRRLRLRRRRL 15
LLRRLRRRRLLL 17
LLRRRRRRLLLL 21
LLLLRLLRRLLRL 16
LRLRLRLLRLRRL 14
RLLRRRRLLRRLRL 17
RRRRLLRLLLRLRL 20
LLLLRRLRLRRRLRL 19
RRRLRRRLRRLRLRL 20

Prolog, 284 byte

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).  
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
n(X):-X=0;n(Y),X#=Y+1.
p(S,L):-n(L),length(X,L),e([0|S],X),c(X,_,_).

Ini adalah pernyataan algoritma yang cukup mudah, dan cukup tidak efisien (tidak semua kasus uji berjalan dalam waktu yang wajar, meskipun sebagian besar melakukannya). Ia bekerja melalui menghasilkan semua panjang yang mungkin untuk output dari 1 ke atas ( n); menghasilkan semua urutan yang mungkin dari kiri / maju / kanan dengan panjang yang konsisten dengan input (diimplementasikan dalam e; jalur baru disebut X); kemudian memeriksa jalur pertama yang valid ( c, yang memanggil vuntuk menangani efek belokan kiri dan kanan pada delta x dan y). Panjang kembali adalah output pertama yang terlihat diL. (+2 penalti jika Anda ingin mencegah fungsi mengembalikan output lain yang mungkin untuk panjang jika Anda mundur ke dalamnya; itu tidak pernah cukup jelas bagaimana pengembalian fungsi istimewa Prolog harus dihitung.)

Tidak banyak cara trik golf di sini, tetapi ada beberapa. ndiimplementasikan dengan pemecah kendala karena memungkinkan lebih banyak ruang kosong untuk dihapus tanpa membingungkan parser; ini mungkin memerlukan GNU Prolog untuk digunakan, tidak yakin tentang itu. (Saya tidak bisa melakukan hal yang sama ckarena perlu menangani angka negatif.) Implementasi eini jauh lebih efisien daripada yang seharusnya, melalui pencocokan daftar dalam berbagai cara; semakin efisien e([],[]).akan menjadi enam byte lebih lama (itu akan memungkinkan S=X;jalur 2 dihapus, tetapi itu hanya keuntungan empat dibandingkan dengan kerugian sepuluh). Untuk memungkinkan saya mencocokkan koordinat dan arah secara keseluruhan, atau hanya sebagian, saya mewakili mereka sebagai X/Y(yaitu AST yang tidak dievaluasi, yang dapat dicocokkan pada), memungkinkan saya untuk menggunakan notasi infiks.

Prolog, 256 byte, terlalu tidak efisien untuk dengan mudah diuji

Tentu saja, karena ini adalah Prolog, banyak fungsi yang dapat dibalik, misalnya cdapat digunakan untuk menghasilkan semua jalur dari asal ke pasangan koordinat tertentu. Selain itu, csecara alami menghasilkan dari terpendek ke terpanjang. Ini berarti bahwa alih-alih meminta panjang minimum secara eksplisit, kita bisa cmembuat semua jalur yang menuju ke mana saja , lalu mencari yang pertama yang konsisten dengan input:

e(S,[0|X]):-e(S,X).
e([A|S],[A|X]):-S=X;e(S,X).
v(X/Y,76,Y/Z):-Z is -X.
v(X/Y,82,Z/X):-Z is -Y.
v(D,0,D).
c([],0/0-0/1,[0/0]).
c([H|T],K/L-D/E,[K/L|C]):-c(T,I/J-X/Y,C),v(X/Y,H,D/E),K is I+X,L is J+Y,\+member(K/L,C).
p(S,L):-c(X,_,_),length(X,L),e([0|S],X).

Ini memiliki kinerja eksponensial (O (3 ⁿ ), di mana n adalah output). Namun, saya berhasil memverifikasi pada beberapa tes yang lebih kecil (dibutuhkan sekitar 7 detik untuk output 14, dan sekitar 20 untuk output 15, di komputer saya).

Pyth , 36 byte

ff{I.u+NYY0f>r8YlQ.C+1*M._m^.j)hCdQT

Cobalah online!

Ini cukup lambat, tetapi bekerja, dan cukup cepat untuk input pendek.

Program ini bekerja dengan merepresentasikan arahan sebagai unit kompleks (1, -1, i, -i), dan poin sebagai bilangan kompleks. Pertama-tama saya mengonversi daftar belokan menjadi daftar arah, kemudian menghasilkan semua daftar n langkah, memfilter untuk mereka dengan setidaknya satu langkah di antara setiap belokan, dan mengonversi arah menjadi daftar poin yang dikunjungi, dan memeriksa apakah daftar itu adalah unik. Saya menambah n dalam satu lingkaran sampai saya berhasil.

Peta ke bilangan kompleks:

m^.j)hCdQ
m       Q    Map over the input
      Cd     Convert to ASCII codepoint
     h       Increment
 ^.j)        Raise i to that power.

Karena Lmemiliki ASCII codepoint 76 dan Rmemiliki ASCII codepoint 82, ini memetakan Lke idan Rke -i.

Peta ke arah absolut:

+1*M._ ...
    ._      Form all prefixes
  *M        Map each to its product
+1          Add the first direction, before any turns

Bentuk daftar n langkah dengan setidaknya 1 langkah antara setiap belokan

f>r8YlQ.C ... T
       .C     T    Form all list of T steps
f                  Filter for lists where
  r8Y              Run length encoding of list
 >   lQ            With the first len(input) removed
                   is nonempty

Seharusnya ada satu gerakan lebih banyak daripada yang ada pada input. Setiap gerakan berada dalam arah yang berbeda, sehingga enkode panjang lari harus lebih panjang dari input.

Peta ke titik-titik yang dikunjungi:

.u+NYY0  ...
.u   Y0   Reduce the following function over
          the list of steps, starting at 0.
          Return all intermediates.
  +NY     Add the new step to the current position.

Filter pada non-self-berpotongan:

f{I ...
f     Filter on
  I   Invariant under
 {    Deduplication

Menemukan pertama Tdi mana ini berhasil: f.