Uwaga: Historia opowiedziana w tym pytaniu jest całkowicie fikcyjna i wymyślona wyłącznie w celu wprowadzenia wstępu.

Mój szef ma nowego robota-zabawkę i chce, żebym pomógł go zaprogramować. Chce mieć możliwość wprowadzania prostych instrukcji strzałek, aby mógł się poruszać. Te instrukcje to: ^ (dla ruchu do przodu) <(dla skrętu w lewo) i> (dla skrętu w prawo). Jednak teraz, gdy zaprogramowałem robota, chce on dodatkowej funkcjonalności. Chce, żebym przekształcił dowolną sekwencję wprowadzanych przez siebie strzał, aby zamiast zmuszać robota do podążenia wskazaną ścieżką, przesuwa się on w pożądane miejsce, wskazane przez miejsce, w którym znalazłby się, gdyby wybrał wprowadzoną ścieżkę, równie skutecznie jak możliwy. Apeluję do was, członków PP&CG, o pomoc w tym zadaniu.

Twoje zadanie:

Napisz program lub funkcję, aby przekonwertować ciąg złożony ze strzałek na ciąg, który dotrze do miejsca wskazanego przez dane wejściowe tak szybko, jak to możliwe. Obracanie zajmuje tyle samo czasu, co cofanie lub przewijanie do przodu.

Wkład:

Ciąg strzałek, jak wskazano powyżej. Jeśli chcesz, różne postacie mogą być zastąpione strzałkami, ale pamiętaj, aby uwzględnić to w swojej odpowiedzi. Wszystkie przypadki testowe używają strzałek normalnie.

Wydajność:

Ciąg strzałek (lub ich odpowiedników), które prowadzą robota do wybranego miejsca docelowego tak skutecznie, jak to możliwe.

Przypadki testowe:

Pamiętaj, że oferowane rozwiązania są tylko możliwościami i że inne rozwiązania mogą być ważne.

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

Punktacja:

Pamięć robota jest ograniczona, więc twój program musi mieć możliwie najmniejszą liczbę bajtów.

Retina , 103 74 71 bajtów

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

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

<
>>>

Skręć w lewo, w trzykrotne w prawo.

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

Zmniejsz wszystkie obroty modulo 4.

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

Anuluj ruchy w przeciwnych kierunkach.

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

Skręć trzykrotnie w prawo z powrotem w skręt w lewo. Dotyczy to również przypadku, >>^>^który musi się stać <^<^.

<?>*$

Usuń niepotrzebne zakręty końcowe.

Mathematica, 135 bajtów

{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]&

Pobiera Listciągi jako dane wejściowe.

Wyjaśnienie

j=0;i=1

Ustaw jna 0 i ustaw ina 1.

/@#

Dla każdego wprowadzanego znaku ...

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

Jeśli postać jest >, pomnóż iprzez jednostkę urojoną. Jeśli postać jest >, podziel iprzez jednostkę urojoną. Jeśli postać jest ^, dodaj ido j.

ReIm[ ... ;j]

Weź prawdziwe i wymyślone części j. Daje to kartezjańską współrzędną robota.

... &@@

Zastosuj następujące do tego wyniku:

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

Ustaw ado funkcji, która generuje ciąg z (input)lub 0znak ^s, w zależności co jest większe.

{ ... }

ListSkładający się z ...

a@#

azastosowane do pierwszego wejścia (część rzeczywista j)

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

Jeżeli drugie wejście (urojonej j) jest większa niż 0, >. W przeciwnym razie <. Ustaw swynikowy znak.

a@Abs@#2

a stosowane do wartości bezwzględnej drugiego wejścia.

If[#<0,s,""]

Jeśli pierwsze wejście jest mniejsze niż 0 s,. W przeciwnym razie pusty ciąg.

a@-#

Zastosuj ado czasów wejściowych ujemnych.

... <>""

Dołącz do strun.

Mathematica 119 bajtów

Ostateczna pozycja JungHwana do kodu ścieżki była krótsza niż moja, więc używając tego. Myślę, że istnieje prawdopodobnie jeszcze krótszy sposób, aby to zrobić ...

Używam wbudowanej AnglePathfunkcji do decydowania o ostatecznej pozycji. Definiuję również symbole L, F i R dla „<”, „^” i „>”, aby zapisać kilka znaków cudzysłowu.

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@#&

Stosowanie:

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

Wydajność:

FFLF

Rubinowy , 130 bajtów

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

Jak to działa

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

Wypróbuj online!

J, 90 bajtów

rozwiązanie

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

wyjaśnienie

fajna sztuczka polega na użyciu liczb zespolonych (pomnożenie przez i to obrót w lewo o 90 stopni, a -i daje prawą).

więc bierzemy nasze dane wejściowe jako liczby zespolone: ​​1 oznacza „iść naprzód”, a i / -i reprezentuje skręt w lewo i w prawo.

pozycja końcowa jest obliczana bez wysiłku dzięki tej reprezentacji. Zauważ, że jest to pierwsza (skrajnie prawa) część mojego ostatniego wyrażenia powyżej:

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

Ta krótka linia powyżej rozwiązuje problem. Cała reszta zastanawia się, jak sformatować odpowiedź, i na pewno można by ją znacznie pograć.

Aby zrozumieć powyższą krótką linię, zwróć uwagę, że */\(skan produktów częściowych) daje listę pozycji, na które patrzysz przy każdym indeksie na wejściu: i to północ, 1 i -1 to wschód i zachód, a -i to południe . Ale odkąd zaczynamy patrzeć na północ, musimy pomnożyć je wszystkie i, które w J jest reprezentowane przez j.(żuć to zdanie przez chwilę).

Mamy tylko faktycznie „ruch”, gdy oryginalne wejście jest 1, więc następnie pomnożyć wynik przez elementwise tablicy logicznej, która wynosi 1, gdzie oryginalne wejście jest 1 i 0 w przeciwnym przypadku: =&1*. Wynik tego zwielokrotnienia jest tablica „kroków kierunkowych”. Nasza ostateczna pozycja to po prostu suma tych kroków:+/

testowanie

Niestety z jakiegoś powodu nie mogę tego uruchomić w TIO, ale wklejenie następujących poleceń w konsoli J sprawdzi, czy to działa:

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

C # (.NET Core) , 349 bajtów

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

Wypróbuj online!

Pobiera ciąg znaków jako dane wejściowe i wyprowadza najkrótszą ścieżkę, jaką wybrałby sygnał wejściowy.

Niegolfowane i komentowane

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

JavaScript (Node.js) , 187 bajtów

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):"")}

Wypróbuj online!

Wersja golfowa z białymi spacjami

-14 bajtów przez @Neil

Nie golfowany:

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

Python 2 , 174 169 165 bajtów

Edytuj bajty 1: -5, pozostawiając kierunek poza zakresem 0-3 i usuwając białe znaki.

Edytuj 2: -4 bajty, zmieniając dane wejściowe na (1, 2, 3) zamiast (<, ^,>), ponieważ PO na to pozwala, a także zmieniając mój układ współrzędnych, aby umożliwić mi zmniejszenie obliczeń odległości.

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]

Wypróbuj online!

Określa końcowe współrzędne na podstawie wykonywanych wartości słownika, a następnie drukuje bezpośrednią ścieżkę do celu końcowego.

Perl 5 , 185 + 1 (-p) = 186 bajtów

/</?$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

Wypróbuj online!

JavaScript (rodzaj document.getElementById ()), 343 znaków

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

rozszerzony:

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)

}

Stosowanie:

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

alerty: >^^>^

Przydałby się robot z cofaniem.