Évitez de marcher dans un rectangle

Question

Étant donné un rectangle, un point de départ et un point final, recherchez tout chemin du début à la fin qui évite le rectangle.

Exemple

Supposons que vous soyez à \$(1.5, -1.5)\$et vous deviez vous rendre \$(2, 4)\$. Cependant, il y a un rectangle avec le coin supérieur gauche \$(1, 3)\$et coin inférieur droit \$(4, 1)\$Sur ta route. Cela ressemblerait à ceci:

                             

Il y a beaucoup de chemins que vous pouvez emprunter pour aller du début (vert) à la fin (rouge):

• Vous pouvez passer par \$(-3, 3)\$.
• Vous pouvez aller à \$(-1.5, -0.5)\$puis à \$(-1, 4)\$.
• Puisque vous êtes infiniment mince (après avoir perfectionné votre routine d'entraînement), vous pouvez passer par \$(4, 1)\$et \$(4, 3)\$.
• Parmi beaucoup d'autres.

Voici à quoi ressemblent ces trois options (cliquez pour voir la taille réelle):

Défi

Étant donné un point de départ \$S\$, un point final \$E\$, et les coordonnées des coins supérieur gauche et inférieur droit d'un rectangle (dans n'importe quel format raisonnable pour votre langue, y compris les nombres complexes si vous le souhaitez), produisent une série de points \$A_1, A_2, \ldots, A_n\$de n'importe quelle longueur telle que le chemin linéaire par morceaux \$S \rightarrow A_1 \rightarrow A_2 \rightarrow \ldots \rightarrow A_n \rightarrow E\$ne coupe pas l'intérieur du rectangle. Notez que:

• Le point de départ et le point final ne seront pas à l'intérieur du rectangle, ni sur le bord ou le coin du rectangle.
• Votre tracé peut toucher les coins et les bords du rectangle, mais ne doit pas croiser l'intérieur du rectangle.
• Vous ne pouvez rien afficher, une liste vide ou similaire si vous souhaitez parcourir \$S \rightarrow E\$ directement.
• Vous pouvez supposer que le rectangle a une largeur et une hauteur strictement positives.
• Votre approche n'a pas besoin d'utiliser le même nombre de points pour tous les cas de test.
• Le chemin peut avoir des points en double et peut se croiser, si vous le souhaitez.

Cas de test

Ici, (sx,sy)est le point de départ, (ex,ey)est le point final, (tlx,tly)est le coin supérieur gauche du rectangle et (brx,bry)est le coin inférieur droit. Notez qu'à partir de la spécification, nous aurons toujours tlx < brxet tly > bry.

Input                                  -> Sample output (one of infinite valid answers)
(sx,sy), (ex,ey), (tlx,tly), (brx,bry) -> ...

(1.5,-1.5), (2,4), (1,3), (4,1)        -> (-3,3)
                                       or (-1.5,0.5),(-1,4)
                                       or (4,1),(4,3)

(-5,0), (5,0), (-1,1), (2,-2)          -> (0,5)
                                       or (-5,1),(5,1)

(0.5,-2), (0.5,1), (2,2), (4,-3)       -> []
                                       or (0.5,-0.5)
                                       or (-1,-0.5)

Notation

Le code le plus court en octets l'emporte.

Answer 1

JavaScript (ES6),  66  57 octets

Attend (Sx,Sy,Ex,Ey,[Tx,Ty],[Bx,By]). Renvoie 3 points.

(S,s,E,e,T,B,[x,y]=T)=>[S>x&s<y?B:T,[B[0],y],E>x&e<y?B:T]

Essayez-le en ligne!

Méthode

Le premier point est \$(Bx,By)\$si le point de départ est dans la zone grise ou \$(Tx,Ty)\$ autrement.

Le deuxième point est toujours \$(Bx,Ty)\$.

Le troisième point est \$(Bx,By)\$si le point final est dans la zone grise ou \$(Tx,Ty)\$ autrement.

Answer 2

Python 2 , 49 octets

lambda S,E,T,B:[(T*(L<B)+L+T)[::3]for L in S,T,E]

Essayez-le en ligne!

53 octets

def f(S,E,T,B):
 for L in S,T,E:L[L>B]=T[L>B];print L

Essayez-le en ligne!

Nous créons un chemin à partir de segments horizontaux ou verticaux uniquement, ce qui signifie que chaque étape change un style d' échelle de mot de coordonnées .

Notre chemin S->Epasse toujours par le sommet supérieur gauche du rectangle T.

S
?
T
?
E

Nous passons de Sà Tvia un arrêt au stand hybride entre eux, en changeant la première ou la deuxième coordonnée de Sà celle de T:

S0, S1      S0, S1
S0, T1  or  T0, S1
T0, T1      T0, T1

Autrement dit, nous allons de Sà Ten progressant verticalement puis horizontal ou horizontal puis vertical.

Nous en choisissons un pour éviter de traverser l'intérieur du rectangle, bien que dans de nombreux cas, l'un ou l'autre fonctionnerait. La modification de la première coordonnée ne peut échouer que si nous sommes directement à droite du rectangle, et la modification de la seconde ne peut échouer que si nous sommes directement au-dessus. Nous pouvons séparer ces deux cas en vérifiant si nous sommes à gauche ou à droite B.

De la même manière, nous hybridons le point final Epour le connecter T.

Dans le code, chacun des trois points S, T, E est hybridé avec T et imprimé. Pour T, l'hybridation le laisse inchangé. La version 53 octets du code utilise la mutation de liste, ce qui nécessite une non- lambdafonction. La version de 49 octets ci-dessus le fait avec une supercherie de découpage de liste (T*(L<B)+L+T)[::3], équivalente à [L+T,T+L][L<B][::3].

49 octets

def f(B,*R):
 for L in R:L[L>B]=R[1][L>B];print L

Essayez-le en ligne!

Prend les entrées dans l'ordre B,S,T,Esous forme de listes à deux éléments.

Answer 3

R , 86 82 94 81 79 octets

Modifications: -4 octets en ne sortant pas les points de début et de fin, puis +12 -1 octet pour corriger le bogue (voir ci-dessous)

function(p,q,r,s=.5:-1)list(r[1+all(p*s>(z=r[1,]*s)),],r[2:3],r[1+all(q*s>z),])

Essayez-le en ligne!

Va directement du point de départ à l'un des coins rectangulaires spécifiés accessibles *. Va ensuite à l'un des coins non spécifiés (le long du bord du rectangle), et de là à un coin spécifié (cela peut ou non être un retour en arrière), à ​​partir duquel il peut aller directement au point final.

Une version légèrement modifiée du programme peut éviter tout détour si le rectangle n'est pas réellement gênant, pour 90 octets .

(* Le correctif du bogue: j'ai initialement supposé que le coin spécifié le plus proche était toujours accessible, mais ce n'est pas nécessairement le cas si le rectangle est très large et plat, et que le point de départ est en dessous mais proche de la gauche fin, par exemple).

Answer 4

C 125 octets

z(a,b){printf("%d:%d|",a,b);}d(m,n,p,q,r,s,u,v){(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}

essayez-le en ligne

explication du code

z(a,b){printf("%d:%d|",a,b);}   // print routine
d(m,n,p,q,r,s,u,v)              // function take x0 y0 xa ya x1 y1 xb yb
                                // x0 y0  - top left corner of rectangle
                                // xa ya  - start point a
                                // x1 y1  - bottom right corner of rectangle
                                // xa ya  - end point b
{(p-m)*(s-n)>(r-m)*(q-n)?z(m,s):z(r,n);
                                // 1st cross product to decide P1 (see below)
(u-m)*(n-s)>(r-m)*(v-s)?z(r,s):z(m,n);}
                                // 2nd cross product to decide P2 (see below)

méthode

si nous allons de a à b ci-dessous, nous pouvons d'abord choisir un point sur le rectangle qui se connectera définitivement avec a sans croiser en regardant de quel côté de la diagonale a se trouve - ci-dessous, nous choisissons P1 . De même, en comparant la position de b avec l'autre diagonale, nous pouvons choisir un deuxième point P2 qui se connectera avec b sans traverser le rectangle - comme indiqué dans le diagramme. Maintenant P1 et P2 se connecteront toujours sans traverser le rectangle et nous avons terminé. La liste est

P1

P2

(notez pour trouver de quel côté de la diagonale nous sommes nous pouvons utiliser le produit croisé - si positif d'un côté - si négatif de l'autre.)

Answer 5

Charbon , 19 octets

ＩＥ⟦θζη⟧Ｅι⎇⁼μ›ιε§ζμλ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Je voulais faire cela en utilisant au plus deux points, mais je ne pouvais pas trouver un moyen facile de décider dans quelle direction sauter. J'ai ensuite essayé d'ajouter un troisième point, mais cela s'est rapidement simplifié en un portage de l'algorithme de @ xnor. Prend l'entrée sous forme de 4 tuples. Explication:

  ⟦θζη⟧             List of points S, T, E
 Ｅ                  Map over list
        ι           Current point
       Ｅ           Map over coordinates 
            ›ιε     Is the current point to the right of B
          ⁼μ        If this is the appropriate coordinate
               §ζμ  Take the relevant coordinate from T
                  λ Otherwise keep the coordinate
Ｉ                   Cast to string
                    Implicitly print