Gerakan Robot yang Efisien

24

Penafian: Kisah yang diceritakan dalam pertanyaan ini sepenuhnya fiktif, dan diciptakan semata-mata untuk tujuan memberikan intro.

Bos saya mendapatkan robot mainan baru, dan dia ingin saya membantu memprogramnya. Dia ingin dapat memasukkan instruksi panah sederhana untuk membuatnya bergerak. Instruksi ini adalah: ^ (untuk bergerak maju) <(untuk belok kiri), dan> (untuk belok kanan). Namun, sekarang saya sudah memprogram robot, dia ingin fungsionalitas tambahan. Dia ingin saya mengubah urutan panah apa pun yang dia input, sehingga daripada memiliki robot mengambil jalur yang ditunjukkan, itu bergerak ke lokasi yang diinginkan, ditunjukkan oleh tempat itu akan berakhir jika telah mengambil jalur yang dimasukkan, seefisien mungkin. Saya menghimbau Anda, para anggota PP&CG, untuk membantu saya dengan tugas ini.

Tugas Anda:

Tulis program atau fungsi untuk mengubah string yang terbuat dari panah menjadi string yang akan sampai ke lokasi yang ditunjukkan oleh input secepat mungkin. Memutar membutuhkan waktu selama bergerak mundur atau maju.

Memasukkan:

Sederetan panah, seperti ditunjukkan di atas. Jika Anda mau, karakter yang berbeda dapat diganti dengan panah, tetapi pastikan untuk memasukkan fakta bahwa Anda melakukannya dalam jawaban Anda. Semua test case menggunakan panah secara normal.

Keluaran:

String panah (atau karakter setara Anda), yang membawa robot ke tujuan yang diinginkan seefisien mungkin.

Kasus uji:

Perhatikan bahwa solusi yang ditawarkan hanya kemungkinan, dan bahwa solusi lain mungkin valid.

>^<<^^>^^    -> ^^<^
^^^^>^^^^    -> ^^^^>^^^^
>>>^^^^^^    -> <^^^^^^
>^>^>^>^     -> (empty string)
^<^^<^^<^^^^ -> >^^>^

Mencetak:

Memori robot terbatas, jadi program Anda harus memiliki jumlah byte serendah mungkin.

Gryphon - Pasang kembali Monica
sumber
Karena dalam input, robot berakhir tepat di tempat dimulainya, sehingga tidak ada perintah yang diperlukan untuk memindahkannya seefisien mungkin.
Gryphon - Kembalikan Monica
Oh, salah baca talinya. Salahku.
JungHwan Min
Permintaan uji kasus ^<^^<^^<^^^^-> >^^>^?
JungHwan Min
1
@pizzakingme, maaf, tapi bos saya sangat malas dan hanya ingin mengetik satu karakter per gerakan.
Gryphon - Kembalikan Monica
1
Saya memprogram robot kompetitif dan saya bisa memastikan ini persis cara kerjanya.
Joe

Jawaban:

9

Retina , 103 74 71 byte

<
>>>
+`(>(\^*>){3})\^
^$1
+`\^(>\^*>)\^
$1
>>(\^*)>(\^+)
<$2<$1
<?>*$

Cobalah online! Tautan termasuk kasus uji. Penjelasan:

<
>>>

Belok kiri belok menjadi belok kanan tiga.

+`(>(\^*>){3})\^
^$1

Kurangi semua belokan modulo 4.

+`\^(>\^*>)\^
$1

Batalkan gerakan dalam arah yang berlawanan.

>>(\^*)>(\^+)
<$2<$1

Belok tiga belok kanan kembali menjadi belok kiri. Ini juga menangani kasus >>^>^yang perlu menjadi <^<^.

<?>*$

Hapus putaran trailing yang tidak perlu.

Neil
sumber
Impresif. Saya tahu harus ada cara untuk mendapatkan sub 100 byte ini dalam beberapa bahasa, dan jawaban Anda sangat dekat sebelumnya. +1
Gryphon - Pasang kembali Monica
6

Mathematica, 135 byte

{a="^"~Table~Ramp@#&;a@#,s=If[#2>0,">","<"],a@Abs@#2,If[#<0,s,""],a@-#}<>""&@@ReIm[j=0;i=1;Switch[#,">",i*=I,"<",i/=I,"^",j+=i]&/@#;j]&

Mengambil a Liststring sebagai input.

Penjelasan

j=0;i=1

Set jke 0, dan set ike 1.

/@#

Untuk setiap karakter dalam input ...

Switch[#,">",i*=I,"<",i/=I,"^",j+=i]

Jika karakternya adalah >, kalikan idengan unit imajiner. Jika karakternya adalah >, bagi idengan unit imajiner. Jika karakternya adalah ^, tambahkan ike j.

ReIm[ ... ;j]

Ambil bagian nyata dan imajiner dari j. Ini memberikan koordinat robot Cartesian.

... &@@

Terapkan yang berikut ini untuk hasil ini:


a="^"~Table~Ramp@#&;

Setel ake fungsi yang menghasilkan string dengan (input)atau 0karakter ^s, yang lebih besar.

{ ... }

A Listterdiri dari ...

a@#

aditerapkan pada input pertama (bagian nyata dari j)

s=If[#2>0,">","<"]

Jika input kedua (imajiner bagian dari j) lebih besar dari 0, >. Jika tidak <,. Setel ske karakter yang dihasilkan.

a@Abs@#2

a diterapkan pada nilai absolut dari input kedua.

If[#<0,s,""]

Jika input pertama kurang dari 0 s,. Jika tidak, kosongkan string.

a@-#

Berlaku auntuk kali input yang negatif.

... <>""

Bergabung dengan string.

JungHwan Min
sumber
2

Mathematica 119 Bytes

Posisi akhir JungHwan untuk kode jalur lebih pendek dari saya, jadi gunakan itu. Saya pikir mungkin ada cara yang lebih pendek untuk melakukan ini ...

Saya menggunakan AnglePathfungsi bawaan untuk menentukan posisi akhir. Saya juga mendefinisikan simbol L, F, dan R untuk "<", "^" dan ">", untuk menyimpan beberapa karakter kutipan.

L={0,Pi/2};R=-L;F={1,0};{a="F"~Table~Ramp@#&;a@#,s=If[#2>0,"L","R"],a@Abs@#2,If[#<0,s,""],a@-#}<>""&@@Last@AnglePath@#&

Pemakaian:

%@{R,F,L,L,F,F,R,F,F}

Keluaran:

FFLF
Kelly Lowder
sumber
2

Ruby , 130 byte

->s{w,d=0,1;s.bytes{|b|b>93?w+=d:d*=1i*(b<=>61)};r,c=w.rect;[w=(d=">><"[c<=>0])+?^*c.abs,?^*r.abs+w,w+d+?^*r.abs][r<=>0].chomp ?>}

Bagaimana itu bekerja

->s{
    # We start from (0,0i), direction is +1
    w,d=0,1

    s.bytes{|b|
        # If it's ASCII 94, go one step forward,
        # else multiply direction by +i or -i
        b>93?w+=d:d*=1i*(b<=>61)
    }

    # Get the rectangular representation of the result
    r,c=w.rect

    # Now, create 2 strings of "^" (call them x and y) for horizontal and vertical moves
    # And a single ">" or "<" (call it d) for the direction change
    # If x>0, output x+d+y
    # If x==0, output d+y
    # If x>0, output d+y+d+x
    [w=(d=">><"[c<=>0])+?^*c.abs,?^*r.abs+w,w+d+?^*r.abs][r<=>0]

    #If y==0 we get an extra ">" sometimes
    .chomp ?>
}

Cobalah online!

GB
sumber
2

J, 90 byte

larutan

t=.{&' ><'@*
g=.'^'#~|
(t,g@{.,t@-@(*/),g@{:`g@{:,t@{.,g@|@{.@.(0<:{:))@+.@(+/)@(=&1*j.**/\)

penjelasan

ada trik rapi menggunakan angka kompleks (mengalikan dengan saya adalah rotasi kiri 90 derajat, dan -i memberi Anda yang benar).

jadi kami mengambil input kami sebagai angka kompleks: a 1 mewakili "berjalan maju" dan i / -i mewakili belok kiri dan kanan.

posisi akhir dihitung dengan mudah dengan representasi ini. Perhatikan ini adalah bagian (paling kanan) pertama dari ekspresi terakhir saya di atas:

(+/)@(=&1*j.**/\)

Garis pendek di atas itulah yang memecahkan masalah. Semua yang lain hanya mencari tahu bagaimana memformat jawaban, dan pasti bisa diturunkan secara signifikan.

Untuk memahami garis pendek di atas, perhatikan bahwa */\(pemindaian produk parsial) memberi Anda daftar posisi yang Anda hadapi di setiap indeks dalam input: i adalah utara, 1 dan -1 adalah timur dan barat, dan -i adalah selatan . Tetapi karena kita mulai menghadap ke utara, kita harus melipatgandakan semua itu dengan i yang, dalam J, diwakili oleh j.(mengunyah kalimat itu sejenak).

Kami hanya benar-benar "bergerak" ketika input asli 1, jadi kami kemudian kalikan hasilnya elementwise oleh array boolean yang merupakan 1 di mana input asli adalah 1 dan 0 sebaliknya: =&1*. Hasil yang perkalian array "langkah directional". Posisi akhir kami hanyalah jumlah dari langkah-langkah itu:+/

pengujian

Sayangnya saya tidak bisa menjalankan ini di TIO karena alasan tertentu, tetapi menempelkan yang berikut ke konsol J akan memverifikasi bahwa itu berfungsi:

t=.{&' ><'@*
g=.'^'#~|
f=.(t,g@{.,t@-@(*/),g@{:`g@{:,t@{.,g@|@{.@.(0<:{:))@+.@(+/)@(=&1*j.**/\)

NB. test cases
NB. format input as complex numbers
convert=. {&0j1 0j_1 1@:('<>^'&i.)

s=. '^<^^<^^<^^^^'  NB. >^^>^
echo f convert s
s=. '>^<<^^>^^'     NB. ^^<^
echo f convert s
s=. '^^^^>^^^^'     NB. ^^^^>^^^^
echo f convert s
s=. '>>>^^^^^^'     NB. <^^^^^^
echo f convert s
s=. '>^>^>^>^'      NB. empty string
echo f convert s
Jonah
sumber
1

C # (.NET Core) , 349 byte

n=>{int a=0,b=0,x=0,y=1,t=0,j=0,k=0,w,e,r;var p="";foreach(var c in n){if(c==62){t=x;x=y;y=-t;}if(c<61){t=x;x=-y;y=t;}if(c>63){a+=x;b+=y;}}while(a!=j|b!=k){w=0;e=a-j;r=b-k;if(r>=e&r>=-e){w=b-k;k+=w;}else if(r<=e&r<=-e){p+=">>";w=k-b;k-=w;}else if(r>=e&r<=-e){p+="<";w=j-a;j-=w;}else if(r<=e&r>=-e){p+=">";w=a-j;j+=w;}p+=new string('^',w);}return p;}

Cobalah online!

Mengambil string sebagai input dan menghasilkan jalur terpendek yang akan diambil input.


Tidak Diseret & Dikomentari

n =>
{
    // First, calculate the route that the robot is going to take, represented by xy
    int a = 0, b = 0; // The current coordinates (a=x, b=y)
    int x = 0, y = 1; // The movement vector
    int t = 0; // A temp variable
    var p = ""; // The path we are going to return
    // Calculate the path the robot is going to take by input
    foreach (var c in n)
    {
        if (c == '>') { t = x; x = y; y = -t; } // Turn movement vector right
        if (c == '<') { t = x; x = -y; y = t; } //                      left
        if (c == '^') { a += x; b += y; }       // Move forward
    }
    int j = 0, k = 0; // The new movement coordinates (j=x,k=y)
    // While the target position is not reached, move the robot
    while (a != j | b != k)
    {
        int w = 0; // The forward variable, counting how many times we have to go forward
        int e = a - j, r = b - k; // The target position minus the current position (e=x,r=y)
        if (r >= e & r >= -e) { w = b - k; k += w; } // Up
        else if (r <= e & r <= -e) { p += ">>"; w = k - b; k -= w; } // Down
        else if (r >= e & r <= -e) { p += "<"; w = j - a; j -= w; } // Left
        else if (r <= e & r >= -e) { p += ">"; w = a - j; j += w; } // Right
        p += new string('^', w);
    }
    // Return the final path
    return p;
}
Ian H.
sumber
1

JavaScript (Node.js) , 187 byte

s=>{x=y=t=0;r=x=>"^".repeat(x<0?-x:x);for(c of s){t-=b=c<">"||-(c<"^");if(!b)[z=>++y,z=>++x,z=>--y,z=>--x][t&3]()}t=x<0?"<":">";return (y>0?r(y):"")+(x?t+r(x):"")+(y<0?(x?t:t+t)+r(y):"")}

Cobalah online!

Versi golf dengan spasi putih

-14 byte oleh @Neil


Tidak Disatukan:

s=>{
  // convert turns to up/down/left/right movements to final destination
  let directions = [
    z=>++y, // up
    z=>++x, // right
    z=>--y, // down
    z=>--x  // left
  ];
  let x = y = direction = 0;
  for(c of s){
    let relativeDirection = "<^>".indexOf(c)-1; // relative turn offset: -1 = left, 1 = right
    direction += relativeDirection;
    if(direction<0){direction+=4} // make sure direction%4 > 0
    if(c==="^"){directions[direction%4]()} // do the movement if going forwards
  }
  // convert destination back to turns
  // the most efficient output has up before left/right before down
  let absoluteRepeat = num => "^".repeat(Math.abs(num));
  let turn = x<0 ? "<" : ">";
  let outp = "";
  if (y>0) { outp += absoluteRepeat(y) } // handle up before left/right
  if (x) { outp+=turn+absoluteRepeat(x) } // handle left/right
  if (y<0) { outp += (outp?turn:turn+turn)+absoluteRepeat(y)) } // handle down (including w/o left/right)
  return outp;
}
Birjolaxew
sumber
Gunakan t&3alih-alih t%4karena itu bekerja dengan negatif tsehingga Anda dapat menghapus 4+dan ()s. (x?"":t)+tdapat ditulis (x?t:t+t)untuk penghematan 1 byte. Kode pemindahan arah terlihat terlalu panjang. Juga saya pikir Anda mungkin harus mengganti indexOfdan Math.absdengan perbandingan.
Neil
@Neil Terima kasih! Bisakah Anda menguraikan sedikit tentang penggantian indexOfdengan perbandingan?
Birjolaxew
Yang terbaik yang bisa saya lakukan adalah t-=b=c<'>'||-(c<'^').
Neil
1

Python 2 , 174 169 165 byte

Sunting 1: -5 byte dengan membolehkan arah berada di luar rentang 0-3, dan menghapus spasi.

Sunting 2: -4 byte dengan mengubah input ke (1, 2, 3) alih-alih (<, ^,>) karena OP mengizinkannya, serta mengubah sistem koordinat saya untuk memungkinkan saya mengurangi perhitungan jarak saya.

n,d=[0,0],0
for c in input():exec'd-=1 n[d%2]+=(-1)**(d/2%2) d+=1'.split()[ord(c)-49]
print'2'*n[0]+'13'[n[1]>0]*any(n)+'2'*abs(n[1])+'13'[n[1]>0]*(n[0]<0)+'2'*-n[0]

Cobalah online!

Menentukan koordinat akhir melalui nilai kamus yang dieksekusi, lalu hanya mencetak jalur langsung ke tujuan akhir.

Arnold Palmer
sumber
0

Perl 5 , 185 + 1 (-p) = 186 byte

/</?$d--:/>/?$d++:/\^/?$m[$d%4]++:0for/./g;$y=$m[0]-$m[2];$x=$m[1]-$m[3];$q='^'x abs$x;$_=A.$q.B.('^'x-$y);$x<0?y/AB/</:$x?y/AB/>/:0;$_=('^'x$y).($x<0?'<':$x>0?'>':'').$q if$y>0;y/AB//d

Cobalah online!

Xcali
sumber
0

Jenis JavaScript (document.getElementById ()), 343 karakter

function b(s){s=s.split('');c=[0,0];r=0;p='';w='<';e='>';n='^';for(i in s){r+=s[i]==e?.5:s[i]==w?-.5:0;r=r>1?-.5:r<-.5?1:r;c[1-Math.ceil(Math.abs(r%1))]+=s[i]==n?r>0?1:-1:0;}x=c[0];y=c[1];j=x<0?-x:x;k=y<0?-y:y;f=function(a){p+=a==j?x<0?w:x>0?e:'':j>k?y<0?w:y>0?e:'':y>0?e+e:'';for(i=0;i<a;i++){p+=n}};if(j>k){f(j);f(k)}else{f(k);f(j)}alert(p)}

diperluas:

function b(s){

s = s.split('');
c = [0, 0];
r = 0;
p = '';
w = '<';
e = '>';
n = '^';

for(i in s){

    r += s[i] == e ? .5 : s[i] == w ? -.5 : 0;
    r = r > 1 ? -.5 : r < -.5 ? 1 : r;

    c[1 - Math.ceil( Math.abs( r%1 ) )] += s[i] == n ? r > 0 ? 1 : -1 : 0;

}

x = c[0];
y = c[1];
j = x < 0 ? -x : x;
k = y < 0 ? -y : y;

f = function(a){

    p += a == j ? x < 0 ? w : x > 0 ? e : '' : j > k ? y < 0 ? w : y > 0 ? e : '' : y > 0 ? e+e : '';

    for( i = 0; i < a; i++){
        p += n
    }

};

if( j>k ){

    f(j);
    f(k)

} else {

    f(k);
    f(j)

}

alert(p)

}

Pemakaian:

b('^<^^<^^<^^^^')

peringatan: >^^>^

Robot dengan terbalik akan berguna.

logic8
sumber