Efficient Robot Movement

24

2

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.

Gryphon

Posted 2017-08-02T16:15:32.420

Reputation: 6 697

Because in the input the robot ends up exactly where it started, so no commands are necessary to move it there as efficiently as possible. – Gryphon – 2017-08-02T16:18:30.030

Oh, misread the string. My bad. – JungHwan Min – 2017-08-02T16:18:56.867

Test case request ^<^^<^^<^^^^ -> >^^>^? – JungHwan Min – 2017-08-02T16:41:34.817

@JungHwanMin, done – Gryphon – 2017-08-02T16:48:17.083

Can input use multiple characters for a single direction? i.e. -1 for < – Dave – 2017-08-02T17:38:50.720

1@pizzakingme, sorry, but my boss is very lazy and only wants to type in one character per movement. – Gryphon – 2017-08-02T18:00:00.370

There has got to be a way to get this <100. – Gryphon – 2017-08-02T21:12:21.907

Wow, this is on HNQ already. – Gryphon – 2017-08-02T23:30:16.360

So the inputs must be a single character each, but does your boss care about the characters? Perhaps 0 to turn left, 1 for straight, 2 for right? They are technically less physical buttons pressed, and therefore easier to enter for a lazy boss... – Arnold Palmer – 2017-08-03T01:35:49.673

No, my boss has a special keyboard with extra keys and no shift/caps lock so he only has to press one key per character. – Gryphon – 2017-08-03T11:57:48.883

So, he doesn't care what characters you use. – Gryphon – 2017-08-03T11:57:59.020

1I program competitive robots and I can confirm this is exactly how they work. – Joe – 2017-09-19T17:51:02.167

A little more complex perhaps, but basically the same. – Gryphon – 2017-09-19T23:34:52.597

Answers

9

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.

Neil

Posted 2017-08-02T16:15:32.420

Reputation: 95 035

Impressive. I knew there had to be a way to get this sub 100 bytes in some language, and your answer was so close before. +1 – Gryphon – 2017-08-03T12:03:41.217

6

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.

JungHwan Min

Posted 2017-08-02T16:15:32.420

Reputation: 13 290

2

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

Kelly Lowder

Posted 2017-08-02T16:15:32.420

Reputation: 3 225

2

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!

G B

Posted 2017-08-02T16:15:32.420

Reputation: 11 099

2

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

Jonah

Posted 2017-08-02T16:15:32.420

Reputation: 8 729

1

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

Ian H.

Posted 2017-08-02T16:15:32.420

Reputation: 2 431

1

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

Birjolaxew

Posted 2017-08-02T16:15:32.420

Reputation: 323

Use t&3 instead of t%4 because that works with negative t so you can remove the 4+ and the ()s. (x?"":t)+t can be written (x?t:t+t) for a 1-byte saving. The direction-moving code looks far too long. Also I think you should probably replace indexOf and Math.abs with comparisons. – Neil – 2017-08-03T09:20:48.653

@Neil Thanks! Could you elaborate a bit on replacing indexOf with a comparison? – Birjolaxew – 2017-08-03T10:29:13.333

Best I could do was t-=b=c<'>'||-(c<'^'). – Neil – 2017-08-03T10:41:00.497

1

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.

Arnold Palmer

Posted 2017-08-02T16:15:32.420

Reputation: 443

0

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!

Xcali

Posted 2017-08-02T16:15:32.420

Reputation: 7 671

0

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.

logic8

Posted 2017-08-02T16:15:32.420

Reputation: 601