Descargo de responsabilidad: La historia contada dentro de esta pregunta es completamente ficticia e inventada únicamente con el propósito de proporcionar una introducción.

Mi jefe ha conseguido un nuevo robot de juguete y quiere que lo ayude a programarlo. Quiere poder ingresar instrucciones de flechas simples para que se mueva. Estas instrucciones son: ^ (para avanzar) <(para girar a la izquierda) y> (para girar a la derecha). Sin embargo, ahora que he programado el robot, quiere una funcionalidad adicional. Quiere que transforme cualquier secuencia de flechas que ingrese, de modo que en lugar de que el robot tome la ruta indicada, se mueva a la ubicación deseada, indicada por el lugar donde terminaría si hubiera tomado la ruta ingresada, tan eficientemente como posible. Les pido a ustedes, los miembros de PP&CG, que me ayuden con esta tarea.

Tu tarea:

Escriba un programa o función para convertir una cadena formada por flechas en una cadena que llegue a la ubicación indicada por la entrada lo más rápido posible. Girar lleva exactamente el mismo tiempo que retroceder o avanzar.

Entrada:

Una cadena de flechas, como se indicó anteriormente. Si lo desea, las flechas pueden sustituir diferentes caracteres, pero asegúrese de incluir el hecho de que lo hace en su respuesta. Todos los casos de prueba usan las flechas normalmente.

Salida:

Una serie de flechas (o sus caracteres equivalentes) que llevan al robot al destino deseado de la manera más eficiente posible.

Casos de prueba:

Tenga en cuenta que las soluciones ofrecidas son solo posibilidades, y que otras soluciones pueden ser válidas.

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

Tanteo:

La memoria del robot es limitada, por lo que su programa debe tener el recuento de bytes más bajo posible.

Retina , 103 74 71 bytes

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

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

<
>>>

Gire a la izquierda en triple giro a la derecha.

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

Reducir todas las vueltas módulo 4.

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

Cancelar movimientos en direcciones opuestas.

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

Gire un triple giro a la derecha nuevamente en un giro a la izquierda. Esto también maneja el caso de lo >>^>^que debe hacerse <^<^.

<?>*$

Eliminar giros finales innecesarios.

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

Toma una Listde las cadenas como entrada.

Explicación

j=0;i=1

Establezca jen 0 y establezca ien 1.

/@#

Para cada carácter en la entrada ...

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

Si el personaje es >, multiplíquelo ipor la unidad imaginaria. Si el personaje es >, divídalo ipor la unidad imaginaria. Si el personaje es ^, agregue ia j.

ReIm[ ... ;j]

Tome las partes reales e imaginarias de j. Esto proporciona la coordenada cartesiana del robot.

... &@@

Aplique lo siguiente a este resultado:

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

Establézcalo aen una función que genere una cadena con (input)o 0caracteres ^s, lo que sea mayor.

{ ... }

Un Listcompuesto de ...

a@#

aaplicado a la primera entrada (parte real de j)

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

Si la segunda entrada (parte imaginaria de j) es mayor que 0, >. De lo contrario, <. Establecer sel carácter resultante.

a@Abs@#2

a aplicado al valor absoluto de la segunda entrada.

If[#<0,s,""]

Si la primera entrada es menor que 0 s,. De lo contrario, cadena vacía.

a@-#

Aplicar aa la entrada multiplicada por uno negativo.

... <>""

Únete a las cuerdas.

Mathematica 119 Bytes

La posición final de JungHwan para el código de ruta era más corta que la mía, así que usar eso. Creo que probablemente hay una forma aún más corta de hacer esto ...

Utilizo la AnglePathfunción incorporada para decidir la posición final. También defino los símbolos L, F y R para "<", "^" y ">", para guardar algunos caracteres de comillas.

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

Uso:

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

Salida:

FFLF

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

Cómo funciona

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

Pruébalo en línea!

J, 90 bytes

solución

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

explicación

hay un buen truco con números complejos (multiplicar por i es una rotación a la izquierda de 90 grados, y -i te da una correcta).

entonces tomamos nuestra entrada como números complejos: un 1 representa "caminar hacia adelante" e i / -i representan giros a izquierda y derecha.

La posición final se calcula sin esfuerzo con esta representación. Tenga en cuenta que esta es la primera parte (más a la derecha) de mi expresión final anterior:

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

Esa línea corta de arriba es lo que resuelve el problema. Todo lo demás es descubrir cómo formatear la respuesta, y seguramente podría reducirse significativamente más.

Para comprender la línea corta anterior, tenga en cuenta que */\(el escaneo de productos parciales) le da una lista de las posiciones que enfrenta en cada índice en la entrada: i es norte, 1 y -1 son este y oeste, y -i es sur . Pero dado que comenzamos a mirar hacia el norte, tenemos que multiplicarlos por i que, en J, está representado por j.(masticar esa oración por un momento).

Sólo en realidad "movimiento" cuando la entrada original es 1, por lo que luego se multiplica ese resultado elementwise por la matriz booleana que es 1 donde la entrada original es 1 y 0 de otro modo: =&1*. El resultado de esa multiplicación es una matriz de "pasos direccionales". Nuestra posición final es simplemente la suma de esos pasos:+/

pruebas

Desafortunadamente no puedo hacer que esto funcione en TIO por alguna razón, pero pegando lo siguiente en la consola J verificará que funciona:

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

Pruébalo en línea!

Toma una cadena como entrada y genera la ruta más corta que tomaría la entrada.

No golfista y comentado

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

Pruébalo en línea!

Versión de golf con espacios en blanco

-14 bytes por @Neil

Sin golf:

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 bytes

Edite 1: -5 bytes permitiendo que la dirección esté fuera del rango 0-3 y eliminando espacios en blanco.

Edite 2: -4 bytes cambiando la entrada a (1, 2, 3) en lugar de (<, ^,>) ya que el OP lo permitió, así como cambiando mi sistema de coordenadas para permitirme reducir mi cálculo de distancia.

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]

Pruébalo en línea!

Determina las coordenadas finales a través de los valores del diccionario que se ejecutan, luego simplemente imprime la ruta directa al objetivo final.

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

Pruébalo en línea!

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

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

expandido:

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)

}

Uso:

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

alertas: >^^>^

Un robot con reversa habría sido útil.