Efficient Robot Movement

Question

Disclaimer: The story told within this question is entirely fictional, and invented solely for the purpose of providing an intro.

My boss has gotten a new toy robot, and he wants me to help program it. He wants to be able to enter simple arrow instructions to get it to move. These instructions are: ^ (for move forward) < (for turn left), and > (for turn right). However, now that I've programmed the robot, he wants additional functionality. He wants me to transform any sequence of arrows he inputs, so that rather than having the robot take the path indicated, it moves to the desired location, indicated by the place it would end up if it had taken the inputted path, as efficiently as possible. I appeal to you, the members of PP&CG, to help me with this task.

Your Task:

Write a program or function to convert a string made up of arrows into a string that will get to the location indicated by the input as quickly as possible. Turning takes exactly as long as moving backwards or forwards.

Input:

A string of arrows, as indicated above. If you wish, different characters may be substituted for the arrows, but be sure to include the fact that you do so in your answer. All test cases use the arrows normally.

Output:

A string of arrows (or your equivalent characters), that take the robot to the desired destination as efficiently as possible.

Test Cases:

Note that the solutions offered are only possibilities, and that other solutions may be valid.

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

Scoring:

The robot's memory is limited, so your program must have the lowest byte count possible.

Answer 1

Retina, 103 74 71 bytes

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

Try it online! Link includes test cases. Explanation:

<
>>>

Turn left turns into triple right turns.

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

Reduce all turns modulo 4.

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

Cancel out movements in opposite directions.

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

Turn a triple right turn back into a left turn. This also handles the case of >>^>^ which needs to become <^<^.

<?>*$

Delete unnecessary trailing turns.

Answer 2

Mathematica, 135 bytes

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

Takes a List of strings as input.

Explanation

j=0;i=1

Set j to 0, and set i to 1.

/@#

For each character in input...

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

If the character is >, multiply i by the imaginary unit. If the character is >, divide i by the imaginary unit. If the character is ^, add i to j.

ReIm[ ... ;j]

Take the real and imaginary parts of j. This gives the Cartesian coordinate of the robot.

... &@@

Apply the following to this result:

---

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

Set a to a function that generates a string with (input) or 0 character ^s, whichever is larger.

{ ... }

A List consisting of...

a@#

a applied to the first input (real part of j)

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

If the second input (imaginary part of j) is larger than 0, >. Otherwise, <. Set s to the resulting character.

a@Abs@#2

a applied to the absolute value of the second input.

If[#<0,s,""]

If the first input is less than 0, s. Otherwise, empty string.

a@-#

Apply a to the input times negative one.

... <>""

Join the strings.

Answer 3

Mathematica 119 Bytes

JungHwan's final position to path code was shorter than mine, so using that. I think there is probably an even shorter way to do this...

I use the built-in AnglePath function to decide the final position. I also define the symbols L, F, and R for "<", "^" and ">", to save a few quote characters.

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

Usage:

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

Output:

FFLF

Answer 4

Ruby, 130 bytes

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

How it works

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

Try it online!

Answer 5

J, 90 bytes

solution

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

explanation

there's a neat trick using complex numbers (multiplying by i is a 90 degree left rotation, and -i gives you a right one).

so we take our input as complex numbers: a 1 represents "walk forward" and i / -i represent left and right turns.

the final position is calculated effortlessly with this representation. Note this is the first (rightmost) part of my final expression above:

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

That short line above is what solves the problem. Everything else is just figuring out how to format the answer, and could surely be golfed down significantly more.

To understand the short line above, note that */\ (the scan of partial products) gives you list of the positions you are facing at each index in the input: i is north, 1 and -1 are east and west, and -i is south. But since we start facing north, we have to multiply all of those by i which, in J, is represented by j. (chew on that sentence for a moment).

We only actually "move" when the original input is 1, so we then multiply that result elementwise by the boolean array which is 1 where the original input is 1 and 0 otherwise: =&1*. The result of that multiplication is an array of "directional steps". Our final position is simply the sum of those steps: +/

testing

Unfortunately I can't get this working in TIO for some reason, but pasting the following into J console will verify that it works:

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

Answer 6

C# (.NET Core), 349 bytes

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

Try it online!

Takes a string as an input and outputs the shortest path that the input would take.

---

Ungolfed & Commented

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

Answer 7

JavaScript (Node.js), 187 bytes

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

Try it online!

Golfed version with whitespace

-14 bytes by @Neil

---

Ungolfed:

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

Answer 8

Python 2, 174 169 165 bytes

Edit 1: -5 bytes by allowing the direction to be outside the range 0-3, and removing whitespace.

Edit 2: -4 bytes by changing input to (1, 2, 3) instead of (<, ^, >) since the OP allowed it, as well as changing my coordinate system to allow me to reduce my distance calculation.

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]

Try it online!

Determines final coordinates via the dictionary's values being executed, then just prints the direct path to the end goal.

Answer 9

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

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

Try it online!

Answer 10

JavaScript (document.getElementById() kind), 343 chars

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

expanded:

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)

}

Usage:

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

alerts: >^^>^

A robot with reverse would have been useful.