Die Herausforderung besteht darin, anhand einer Liste von Punkten so zu sortieren, dass sie sich niemals überschneiden, wenn sie in dieser Reihenfolge verbunden sind.

Eingabeformat (von stdin gelesen):

X Y
1 2
3 4
5 6
...

Die Ausgabe sollte mit der Eingabe identisch sein, jedoch sortiert sein.

Regeln:

• Sie können von jedem Punkt aus beginnen.
• Der letzte Punkt muss mit dem ersten identisch sein, um einen engen Stromkreis zu bilden.
• Dies sollte unter Berücksichtigung des kartesischen Gitters erfolgen.
• Sie können davon ausgehen, dass die Eingabepunkte nicht alle auf einer einzelnen Linie liegen.
• Die Endpunkte jeder Linie gelten nicht als Schnittpunkte.

Für weitere Hilfe:

Mathematica - 20 30 Zeichen

Nur der Sortierteil

SortBy[%, ArcTan @@ # &]

Ganzer Testcode, der aus dem Generieren von 100 zufälligen Punkten und dem Zeichnen der Linie besteht

RandomReal[{-10, 10}, {100, 2}];
SortBy[%, ArcTan @@ # &];
ListPlot@% /. 
 Point[p_] :> {EdgeForm[Dashed], FaceForm[White], Polygon[p], 
   PointSize -> Large, Point[p]}

+26 Zeichen

Wenn Sie eine korrekte Eingabe / Ausgabe verlangen, dann

"0 0
 4 4
 0 4
 4 0";
Grid@SortBy[%~ImportString~"Table", ArcTan @@ # &]

+2 Zeichen

Einfach hinzufügen N@

Grid@SortBy[%~ImportString~"Table", ArcTan @@ N @ # &]

weil der obige Code aufgrund des seltsamen Verhaltens von Mathematica beim Sortieren symbolischer Ausdrücke nur für reelle Zahlen und nicht für ganze Zahlen funktioniert

N@Sort[{ArcTan[1], ArcTan[-2]}]
Sort[N@{ArcTan[1], ArcTan[-2]}]

{0.785398, -1.10715}
{-1.10715, 0.785398}

BEARBEITEN Ich habe gerade festgestellt, dass es nicht funktioniert, wenn sich die Punkte nicht um den Ursprung befinden. Daher muss auch in die Mitte der Punkte verschoben werden

SortBy[%, ArcTan @@ N[# - Mean@%] &]

Die Frage hat sich geändert, daher enthält diese Antwort verschiedene Versionen mit und ohne geschlossenen Pfad.

Perl, offener Pfad, 69 Bytes

print"@$_$/"for sort{$$a[0]<=>$$b[0]||$$a[1]<=>$$b[1]}map{[/\S+/g]}<>

Jeder Punkt wird in STDIN als Linie erwartet, wobei die Koordinaten durch Leerzeichen getrennt sind.

Es wird jedes Zahlenformat unterstützt, das Perl als Zahl interpretiert (einschließlich Gleitkommazahlen).

Beispiel:

0 0
4 4
0 4
4 0
-2 1
2 -2
2 4
3.21 .56
.035e2 -7.8
0 2

Ausgabe:

-2 1
0 0
0 2
0 4
2 -2
2 4
3.21 .56
.035e2 -7.8
4 0
4 4

Ungolfed:

print "@$_$/" for            # print output line      
    sort {                   # sort function for two points $a and $b
        $$a[0] <=> $$b[0]    # compare x part                           
        || $$a[1] <=> $$b[1] # compare y part, if x parts are identical
    }
    map { [/\S+/g] }         # convert input line to point as array reference
    <>                       # read input lines               

Schaltungsvarianten

In der Version mit der ersten Frage gab es eine Verbindung zwischen dem letzten und dem ersten Punkt, um eine Schaltung herzustellen.

Zentrum ist nicht vorhanden Punkt, 253 Bytes

Diese Variante kann fehlschlagen, wenn die Mitte einer der Punkte ist, siehe Beispiel 3.

Bearbeitungen:

• In seiner Antwort bemerkte Swish, dass die Punkte um den Ursprung zentriert sein sollten, um eine kreuzfreie Schaltung zu gewährleisten:

  • Das Sortieren erfordert transformierte Koordinaten.
  • Die ursprüngliche Zeichenfolgendarstellung der Zahlen muss für die Ausgabe beibehalten werden.

• Fehlerbehebung: Der Sonderfall für die negative x-Achse hatte die positive x-Achse enthalten.

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;(!$X&&!$Y?-1:0)||!$x&&!$y||!$Y&&!$y&&$X<0&&$x<0&&$X<=>$x||atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

Beispiel 1:

4 4
-2 0
2 0
1 1
4 0
-2 -2
-3 -1
1 -2
3 0
2 -4
0 0
-1 -2
3 3
-3 0
2 3
-5 1
-6 -1

Ausgabe 1:

0 0
-6 -1
-3 -1
-2 -2
-1 -2
1 -2
2 -4
2 0
3 0
4 0
1 1
3 3
4 4
2 3
-5 1
-3 0
-2 0

Beispiel 2:

Testen der Zahlendarstellung und Koordinatentransformation.

.9e1 9
7 7.0
8.5 06
7.77 9.45

Ausgabe 2:

7 7.0
8.5 06
.9e1 9
7.77 9.45

Ungolfed:

print "$$_[2] $$_[3]$/" for sort { # print sorted points
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    (!$X && !$Y ? -1 : 0) ||       # origin comes first, test for $a
    !$x && !$y ||                  # origin comes first, test for $b
    !$Y && !$y && $X < 0 && $x < 0 && $X <=> $x ||
        # points on the negative x-axis are sorted in reverse order
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value
        @$_              # original coordinates
] }
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
}
<>                       # read input lines

Ohne Einschränkung 325 Bytes

print"$$_[2] $$_[3]$/"for sort{($X,$Y)=@$a;($x,$y)=@$b;atan2($Y,$X)<=>atan2($y,$x)||$X**2+$Y**2<=>$x**2+$y**2}map{[$$_[0]-$O/9,$$_[1]-$P/9,$$_[2],$$_[3]]}map{$O=$$_[0]if$$_[0]>0&&($O>$$_[0]||!$O);$P=$$_[1]if$$_[1]>0&&($P>$$_[1]||!$P);[@$_]}map{[$$_[0]-$M/$n,$$_[1]-$N/$n,@$_]}map{$n++;$M+=$$_[0];$N+=$$_[1];$_}map{[/\S+/g]}<>

In der vorherigen Version wird die Mitte am Anfang gesetzt und die letzten Punkte auf der negativen Achse werden in umgekehrter Reihenfolge sortiert, um wieder kreuzfrei zur Mitte zu gelangen. Dies reicht jedoch nicht aus, da die letzten Punkte auf einer anderen Linie liegen könnten. Somit würde das folgende Beispiel 3 fehlschlagen.

Dies wird behoben, indem der zentrierte Ursprung ein wenig nach oben und rechts verschoben wird. Aufgrund der Zentrierung muss mindestens ein Punkt mit positivem x-Wert und ein Punkt mit positivem y-Wert vorhanden sein. Somit werden die Minima der positiven x- und y-Werte genommen und auf ein Neuntel reduziert (ein halbes oder drittes könnte ausreichen). Dieser Punkt kann nicht einer der vorhandenen Punkte sein und wird zum neuen Ursprung gemacht.

Die speziellen Behandlungen des Ursprungs und der negativen x-Achse können entfernt werden, da es einen Punkt gibt, der auf dem neuen Ursprung liegt.

Beispiel 3:

-2 -2
-1 -1
-2 2
-1 1
2 -2
1 -1
2 2
1 1
0 0

Ausgabe 3:

0 0
-1 -1
-2 -2
1 -1
2 -2
1 1
2 2
-2 2
-1 1

Beispiel 1 ist jetzt anders sortiert:

Ungolfed:

print "$$_[2] $$_[3]$/" for sort { # print sorted points        
    ($X, $Y) = @$a;                # ($X, $Y) is first point $a 
    ($x, $y) = @$b;                # ($x, $y) is second point $b
    atan2($Y, $X) <=> atan2($y, $x) ||
        # sort by angles; the slope y/x would be an alternative,
        # then the x-axis needs special treatment
    $X**2 + $Y**2 <=> $x**2 + $y**2
        # the (quadratic) length is the final sort criteria
}  
map { [ # make tuple with transformed coordinates
    $$_[0] - $O/9, $$_[1] - $P/9,  # new transformed coordinate
    $$_[2],  $$_[3]                # keep original coordinate
] }
map {
    # get the minimum positive x and y values 
    $O = $$_[0] if $$_[0] > 0 && ($O > $$_[0] || !$O);         
    $P = $$_[1] if $$_[1] > 0 && ($P > $$_[1] || !$P);
    [ @$_ ]               # pass tuple through
}
map { [ # make tuple with transformed and original coordinates
        # the center ($M/$n, $N/$n) is the new origin
        $$_[0] - $M/$n,  # transformed x value
        $$_[1] - $N/$n,  # transformed y value 
        @$_              # original coordinates
] }  
map {
    $n++;                # $n is number of points
    $M += $$_[0];        # $M is sum of x values 
    $N += $$_[1];        # $N is sum of y values
    $_                   # pass orignal coordinates through
}
map {                    # make tuple with point coordinates
    [ /\S+/g ]           # from non-whitespace in input line
} 
<>                       # read input lines

GolfScript, 6/13 Zeichen (offener Pfad; 49 Zeichen für geschlossenen Pfad)

Hinweis: Diese Lösung gilt für die aktuelle Version der Herausforderung , die von Rusher bearbeitet wurde. Es ist keine gültige Lösung für die ursprüngliche Herausforderung , bei der die Linie vom letzten Punkt zurück zum ersten auch die anderen Linien nicht schneiden sollte. Die unten stehende 49-Zeichen-Lösung gilt auch für die ursprüngliche Herausforderung.

~]2/$`

Der obige Code setzt voraus, dass die Ausgabe in einem beliebigen vernünftigen Format erfolgen kann. Wenn das Ausgabeformat mit der Eingabe übereinstimmen muss, reicht die folgende 13-stellige Version aus:

~]2/${" "*n}/

Erläuterung:

• ~wertet die Eingabe aus und wandelt sie in eine Liste von Zahlen um; ]sammelt diese Zahlen in einem Array und 2/teilt dieses Array in Blöcke mit zwei Zahlen auf, die jeweils einen Punkt darstellen.

• $sortiert die Punkte in lexikografischer Reihenfolge, dh zuerst nach der x-Koordinate und dann, wenn es Bindungen gibt, nach der y-Koordinate. Es ist leicht zu zeigen, dass dies garantiert, dass sich die zwischen den Punkten gezogenen Linien nicht schneiden, solange der Pfad nicht zum Anfang zurückgeschleift werden muss.

• `Stringifiziert in der 5- stelligen Version das sortierte Array und erzeugt die native String-Darstellung davon (z [[0 0] [0 4] [4 0] [4 4]]. B. ). {" "*n}/Verbindet in der längeren Version die Koordinaten jedes Punkts durch ein Leerzeichen und fügt eine neue Linie hinzu.

Online-Demo: Kurzversion / Langversion .

Ps. Hier ist eine 49-Zeichen-Lösung für das ursprüngliche Problem, bei dem der Pfad geschlossen werden muss:

~]2/$.0=~:y;:x;{~y-\x-.+.@9.?*@(/\.!@@]}${" "*n}/

Es funktioniert ähnlich wie die Perl-Lösung von Heiko Oberdiek , nur dass dieser Code anstelle der Triggerfunktionen die Punkte nach der Steigung ( y - y ₀ ) / ( x - x ₀ ) sortiert , wobei ( x ₀ , y ₀₎ ) ist der Punkt mit der niedrigsten x- Koordinate (und der niedrigsten y- Koordinate, wenn mehrere Punkte für das niedrigste x gebunden sind ).

Da GolfScript Gleitkomma nicht unterstützt, werden die Pisten durch die feste Konstante multipliziert 9 ⁹ = 387420489. (Wenn das nicht genug Präzision ist, können Sie die ersetzen 9mit , 99um den Multiplikator in 99 ⁹⁹ ≈ 3,7 × 10 ¹⁹⁷ ) . Es ist auch etwas zusätzlichen Code, um Bindungen (durch die x- Koordinate) zu lösen und sicherzustellen, dass wie in Heikos Lösung Punkte mit x = x ₀ zuletzt in absteigender Reihenfolge nach y- Koordinate sortiert werden .

Auch hier ist eine Online-Demo .

Mathematica, 35

Dies funktioniert für JEDE Liste eindeutiger Punkte.

s=StringSplit;Grid@Sort@s@s[%,"\n"]

Sie sagen "read from stdin", also gehe ich für Mathematica von "read from last output" aus.

Eingabe (letzte Ausgabe):

"0 0
4 4
0 4
4 0"

Ausgabe:

0 0
0 4
4 0
4 4

Wenn Eingabe und Ausgabe nicht im Format "Zeilenumbrüche" erfolgen müssen, kann dies auf 6 Zeichen reduziert werden :

Sort@%

Nehmen Sie die letzte Ausgabe als Eingabe, vorausgesetzt, die letzte Ausgabe ist ein zweidimensionales Array.

Eingabe (letzte Ausgabe):

{{0,0},{4,4},{0,4},{4,0}}

Ausgabe:

{{0,0},{0,4},{4,0},{4,4}}

PHP (175 109 100 Zeichen)

while(fscanf(STDIN,'%d%d',$a,$b))$r[]=sprintf('%1$04d %2$04d',$a,$b);sort($r);echo implode('
',$r);

OK, ich gebe zu, PHP ist nicht die beste Golfsprache, aber ich habe es versucht.

Hier einige Beispielausgaben:

0000 0000
0000 0004
0004 0000
0004 0004

Es werden die Informationen in eine Zeichenfolge eingefügt, die mit vorherigen Nullen formatiert ist.
Dann werden die Punkte nur textuell sortiert.
_{PS Es schlägt bei den obigen Zahlen fehl 9999.}

Python 2.7, 42B

import sys
print''.join(sorted(sys.stdin))

Einfacher geht es nicht. STDIN lesen, Zeilen sortieren, Zeilen drucken. NB Ich habe die genauen E / A-Anforderungen der Frage beachtet, aber wenn Sie STDIN manuell ausfüllen, müssen Sie drücken CTRL+d, um die Eingabe zu beenden.