Avertissement: L'histoire racontée dans cette question est entièrement fictive et inventée uniquement dans le but de fournir une intro.

Mon patron a acheté un nouveau robot jouet et il veut que je l'aide à le programmer. Il veut pouvoir saisir des instructions de flèche simples pour le faire bouger. Ces instructions sont: ^ (pour aller de l'avant) <(pour tourner à gauche) et> (pour tourner à droite). Cependant, maintenant que j'ai programmé le robot, il veut des fonctionnalités supplémentaires. Il veut que je transforme toute séquence de flèches qu'il entre, de sorte que plutôt que de demander au robot de prendre le chemin indiqué, il se déplace vers l'emplacement souhaité, indiqué par l'endroit où il se retrouverait s'il avait pris le chemin entré, aussi efficacement que possible. Je fais appel à vous, membres de PP&CG, pour m'aider dans cette tâche.

Ta tâche:

Écrivez un programme ou une fonction pour convertir une chaîne composée de flèches en une chaîne qui arrivera à l'emplacement indiqué par l'entrée le plus rapidement possible. Le virage prend exactement le temps de reculer ou d'avancer.

Contribution:

Une chaîne de flèches, comme indiqué ci-dessus. Si vous le souhaitez, différents caractères peuvent être substitués aux flèches, mais assurez-vous d'inclure le fait que vous le faites dans votre réponse. Tous les cas de test utilisent normalement les flèches.

Sortie:

Une chaîne de flèches (ou vos caractères équivalents), qui emmènent le robot vers la destination souhaitée aussi efficacement que possible.

Cas de test:

Notez que les solutions proposées ne sont que des possibilités et que d'autres solutions peuvent être valides.

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

Notation:

La mémoire du robot est limitée, donc votre programme doit avoir le plus petit nombre d'octets possible.

Rétine , 103 74 71 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. Explication:

<
>>>

Transformez les virages à gauche en triples virages à droite.

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

Réduisez tous les tours modulo 4.

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

Annulez les mouvements dans des directions opposées.

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

Retournez un triple virage à droite en virage à gauche. Cela gère également le cas >>^>^qui doit devenir <^<^.

<?>*$

Supprimez les virages arrière inutiles.

Mathematica, 135 octets

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

Prend une Listchaîne en entrée.

Explication

j=0;i=1

Réglez jsur 0 et isur 1.

/@#

Pour chaque caractère en entrée ...

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

Si le personnage est >, multipliez ipar l'unité imaginaire. Si le personnage est >, divisez ipar l'unité imaginaire. Si le personnage est ^, ajoutez ià j.

ReIm[ ... ;j]

Prenez les parties réelles et imaginaires de j. Cela donne les coordonnées cartésiennes du robot.

... &@@

Appliquez ce qui suit à ce résultat:

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

Défini asur une fonction qui génère une chaîne avec (input)ou un 0caractère ^s, la plus grande des deux.

{ ... }

Un Listcomposé de ...

a@#

aappliqué à la première entrée (partie réelle de j)

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

Si la deuxième entrée (partie imaginaire j) est plus grande que 0, >. Dans le cas contraire, <. Définissez sle caractère résultant.

a@Abs@#2

a appliquée à la valeur absolue de la deuxième entrée.

If[#<0,s,""]

Si la première entrée est inférieure à 0, s. Sinon, chaîne vide.

a@-#

Appliquer aaux temps d'entrée négatifs.

... <>""

Rejoignez les chaînes.

Mathematica 119 octets

La position finale de JungHwan pour le code de chemin était plus courte que la mienne, donc en utilisant cela. Je pense qu'il y a probablement un moyen encore plus court de le faire ...

J'utilise la AnglePathfonction intégrée pour décider de la position finale. Je définis également les symboles L, F et R pour "<", "^" et ">", pour enregistrer quelques guillemets.

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}

Sortie:

FFLF

Rubis , 130 octets

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

Comment ça marche

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

Essayez-le en ligne!

J, 90 octets

Solution

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

explication

il y a une astuce intéressante en utilisant des nombres complexes (multiplier par i est une rotation à gauche de 90 degrés, et -i vous donne une droite).

nous prenons donc notre entrée sous forme de nombres complexes: un 1 représente "marcher en avant" et i / -i représentent les virages à gauche et à droite.

la position finale est calculée sans effort avec cette représentation. Notez que c'est la première partie (la plus à droite) de mon expression finale ci-dessus:

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

Cette courte ligne ci-dessus est ce qui résout le problème. Tout le reste est juste de savoir comment formater la réponse, et pourrait certainement être beaucoup plus bas.

Pour comprendre la courte ligne ci-dessus, notez que */\(l'analyse des produits partiels) vous donne la liste des positions auxquelles vous êtes confronté à chaque index dans l'entrée: i est le nord, 1 et -1 sont l'est et l'ouest, et -i est le sud . Mais puisque nous commençons à faire face au nord, nous devons multiplier tous ceux par i qui, en J, est représenté par j.(mâcher cette phrase pendant un moment).

Nous ne fait « bouger » lorsque l'entrée d' origine est 1, donc nous multipliez ce résultat par le réseau par éléments booléen qui est 1 où l'entrée d' origine est 1 et 0 autrement: =&1*. Le résultat de cette multiplication est un tableau de "pas directionnels". Notre position finale est simplement la somme de ces étapes:+/

essai

Malheureusement, je ne peux pas faire fonctionner cela dans TIO pour une raison quelconque, mais le collage de ce qui suit dans la console J vérifiera que cela fonctionne:

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 octets

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

Essayez-le en ligne!

Prend une chaîne comme entrée et génère le chemin le plus court que l'entrée prendrait.

Non golfé et commenté

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 octets

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

Essayez-le en ligne!

Version golf avec espace blanc

-14 octets par @Neil

Non 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 octets

Modifiez 1: -5 octets en permettant à la direction d'être en dehors de la plage 0-3 et en supprimant les espaces.

Modifiez 2: -4 octets en changeant l'entrée en (1, 2, 3) au lieu de (<, ^,>) puisque l'OP le permettait, ainsi qu'en changeant mon système de coordonnées pour me permettre de réduire mon calcul de distance.

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]

Essayez-le en ligne!

Détermine les coordonnées finales via les valeurs du dictionnaire en cours d'exécution, puis imprime simplement le chemin direct vers l'objectif final.

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

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

Essayez-le en ligne!

JavaScript (type document.getElementById ()), 343 caractères

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

étendu:

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('^<^^<^^<^^^^')

alertes: >^^>^

Un robot avec marche arrière aurait été utile.