Kode terpendek untuk mengurutkan poin berjalan

8

Tantangannya adalah, mengingat daftar poin, mengurutkan sedemikian rupa sehingga, ketika mereka terhubung dalam urutan ini, mereka tidak pernah berpotongan.

Format input (baca dari stdin):

X Y
1 2
3 4
5 6
...

Output harus sama dengan input, tetapi diurutkan.

Aturan:

  • Anda bisa mulai dari titik mana pun.
  • Poin terakhir harus sama dengan yang pertama, membuat sirkuit dekat.
  • Itu harus dilakukan mengingat grid Cartesian.
  • Anda dapat mengasumsikan bahwa titik input tidak semuanya terletak pada satu baris.
  • Titik akhir setiap baris tidak dihitung sebagai berpotongan.

Untuk bantuan lebih lanjut:

diagram

Nacib Neme
sumber
2
@Rusher Mengapa sirkuit tertutup dijamin untuk memotong? (contoh OP tidak)
Martin Ender
2
Jika itu hanya garis, maka solusi dasar adalah menyortir dengan koordinat pertama dan kedua, semacam standar untuk pasangan, jadi itu hanya menyortir dan tidak ada yang lebih mewah di sini.
desir
3
@Rusher: Sirkuit tertutup tidak harus berpotongan sendiri, kecuali dalam arti sepele bahwa titik awal dan akhir adalah sama: gambar "baik" pada postingan menunjukkan sirkuit tertutup yang tidak berpotongan sendiri. Selanjutnya, tanpa persyaratan sirkuit tertutup, tantangan ini menjadi sangat sepele; Saya bisa menyelesaikannya dalam enam karakter GolfScript, lima di antaranya adalah penanganan I / O.
Ilmari Karonen
4
@Rusher: Anda bisa sama baiknya mengklaim bahwa setiap dua baris berturut-turut di jalan harus selalu berpotongan, karena mereka berbagi titik akhir. "Persimpangan" semacam itu (yang "persimpangan" pada titik akhir dari loop tertutup adalah salah satu contoh) adalah sepele, dan tidak dapat dihitung dalam definisi yang berarti dari "jalur yang tidak memotong sendiri". (Pokoknya, jika Anda benar-benar ingin menjadi bertele-tele, cukup tentukan setiap segmen garis untuk memasukkan titik awal tetapi bukan titik akhir. Masalah terpecahkan.)
Ilmari Karonen
2
Pertanyaan yang diedit layak untuk ditutup karena terlalu sepele. Pengeditan seharusnya tidak menghilangkan semua tantangan dari masalah. Karena itu saya menggulungnya kembali. Jika ada yang tidak setuju, saya akan dengan senang hati membahas ini tentang meta.
Peter Taylor

Jawaban:

9

Mathematica - 20 30 karakter

Hanya bagian penyortiran

SortBy[%, ArcTan @@ # &]

Seluruh kode pengujian, yang terdiri dari menghasilkan 100 poin acak dan merencanakan garis

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

+26 karakter

Jika Anda meminta input / ouput yang tepat, maka

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

+2 karakter

Hanya menambahkan N@

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

karena kode di atas hanya berfungsi pada bilangan real dan bukan pada bilangan bulat karena perilaku aneh Matematika ketika menyortir ekspresi simbolik

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

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

EDIT Saya baru menyadari jika poin tidak di sekitar titik asal tidak akan berfungsi, jadi itu juga membutuhkan pergeseran ke pusat poin

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

masukkan deskripsi gambar di sini

desir
sumber
Saya mencoba menemukan contoh tandingan di mana Anda memiliki tiga poin yang sejalan dengan "pusat massa". Mereka semua akan memiliki arctangent yang sama, sehingga pesanan tidak ditentukan oleh kode Anda, yang mungkin menyebabkan koneksi mereka tumpang tindih. Namun, cuplikan Anda sepertinya selalu menyortir kasus-kasus tersebut dari dalam ke luar, meskipun ArcTanhasilnya sebenarnya sama hingga yang terakhir. Apakah Anda tahu mengapa demikian? (Inilah kasusnya jika Anda ingin bermain-main dengannya {{1, 2}, {2, 4}, {3, 6}, {-5, 5}, {-6, -12}, {5, -5}}).
Martin Ender
1
@ m.buettner Dari SortBydokumentasi: Jika beberapa f [e_i] sama, maka urutan kanonik e_i yang sesuai digunakan.
desir
Alangkah nyaman! :)
Martin Ender
5

Pertanyaannya telah berubah, jadi jawaban ini berisi versi yang berbeda, dengan dan tanpa jalur tertutup.

Perl, jalur terbuka, 69 byte

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

Setiap titik diharapkan dalam STDIN sebagai garis, dengan koordinat dipisahkan oleh ruang putih.

Semua format angka didukung oleh Perl yang diinterpretasikan sebagai angka (termasuk angka floating point).

Contoh:

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

Keluaran:

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

Hasil

Tidak Disatukan:

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               

Varian sirkuit

Dalam versi pertanyaan pertama, ada koneksi antara titik terakhir dan pertama untuk membuat sirkuit.

Titik tengah tidak ada, 253 byte

Varian ini bisa gagal, jika pusat adalah salah satu poin, lihat contoh 3.

Suntingan:

  • Dalam jawabannya, swish menyadarinya, bahwa titik harus dipusatkan di sekitar titik asal untuk memastikan sirkuit bebas silang:

    • Penyortiran membutuhkan transformasi koordinat.
    • Representasi string asli dari angka-angka perlu disimpan untuk output.
  • Perbaikan bug: kasus khusus untuk sumbu x negatif telah menyertakan sumbu x positif.

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

Contoh 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

Output 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

Rangkaian hasil 1

Contoh 2:

Menguji representasi angka dan transformasi koordinat.

.9e1 9
7 7.0
8.5 06
7.77 9.45

Output 2:

7 7.0
8.5 06
.9e1 9
7.77 9.45

Rangkaian hasil 2

Tidak Disatukan:

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

Tanpa batasan, 325 byte

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

Dalam versi sebelumnya, pusat diletakkan di awal dan titik-titik terakhir pada sumbu negatif diurutkan dalam urutan terbalik untuk mendapatkan cross-free ke pusat lagi. Namun, ini tidak cukup, karena poin terakhir bisa terletak pada garis yang berbeda. Jadi contoh 3 berikut akan gagal.

Ini diperbaiki dengan memindahkan titik pusat sedikit ke atas dan kanan. Karena keterpusatan, harus ada setidaknya satu titik dengan nilai x positif dan titik dengan nilai y positif. Dengan demikian minimum nilai x dan y positif diambil dan dikurangi menjadi sembilan (setengah atau ketiga bisa cukup). Poin ini tidak dapat menjadi salah satu poin yang ada dan dijadikan asal baru.

Perawatan khusus asal dan sumbu x negatif dapat dihilangkan, karena ada titik yang terletak pada asal baru.

Contoh 3:

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

Output 3:

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

Hasil 3

Contoh 1 sekarang diurutkan secara berbeda:

Hasil 1

Tidak Disatukan:

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
Heiko Oberdiek
sumber
+1 untuk menyertakan varian rangkaian (saya menduga persyaratan pada akhirnya akan menemukan jalannya ke pertanyaan lagi, begitu Rusher merespons)
Martin Ender
3

GolfScript, 6/13 karakter (jalur terbuka; 49 karakter untuk jalur tertutup)

Catatan: Solusi ini untuk versi tantangan saat ini seperti yang diedit oleh Rusher. Ini bukan solusi yang valid untuk tantangan asli , yang mensyaratkan bahwa garis dari titik terakhir ke yang pertama juga tidak boleh memotong garis lainnya. Solusi 49-char di bawah ini juga berlaku untuk tantangan aslinya.

~]2/$`

Kode di atas mengasumsikan bahwa output dapat dalam format yang masuk akal. Jika format output harus sesuai dengan input, versi 13-karakter berikut akan dilakukan:

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

Penjelasan:

  • ~mengevaluasi input, mengubahnya menjadi daftar angka; ]mengumpulkan angka-angka ini menjadi sebuah array, dan 2/membagi array ini menjadi dua blok angka, masing-masing mewakili satu titik.

  • $mengurutkan titik-titik dalam urutan leksikografis, yaitu pertama dengan koordinat x dan kemudian, jika ada ikatan, oleh koordinat y. Sangat mudah untuk menunjukkan bahwa ini akan menjamin bahwa garis-garis yang ditarik di antara titik-titik tidak berpotongan, selama jalur tidak perlu untuk kembali ke awal.

  • Dalam versi 5-karakter, `meringkas array yang diurutkan, menghasilkan representasi string asli dari itu (misalnya [[0 0] [0 4] [4 0] [4 4]]). Dalam versi yang lebih panjang, {" "*n}/gabungkan koordinat setiap titik dengan spasi, dan tambahkan baris baru.

Demo online: versi pendek / versi panjang .


Ps. Inilah solusi 49-char untuk masalah asli, di mana jalur tersebut harus ditutup:

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

Ia bekerja dengan cara yang mirip dengan solusi Perl Heiko Oberdiek , kecuali bahwa, alih-alih menggunakan fungsi trigonometri, kode ini mengurutkan titik dengan kemiringan ( y - y 0 ) / ( x - x 0 ), di mana ( x 0 , y 0 ) adalah titik dengan x- koordinat terendah (dan y- koordinat terendah , jika beberapa poin terikat untuk x terendah ).

Karena GolfScript tidak mendukung titik mengambang, lereng dikalikan dengan konstanta tetap 9 9 = 387420489. (Jika itu tidak cukup presisi, Anda dapat mengganti 9dengan 99untuk mengubah pengali menjadi 99 99 ≈ 3,7 × 10 197. ) Ada juga beberapa kode tambahan untuk memutus ikatan (oleh koordinat x ) dan untuk memastikan bahwa, seperti dalam solusi Heiko, poin dengan x = x 0 diurutkan terakhir, dalam urutan menurun oleh koordinat y .

Sekali lagi, ini demo online .

Ilmari Karonen
sumber
1

Mathematica, 35

Ini bekerja untuk APAPUN daftar poin unik.

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

Anda mengatakan "baca dari stdin", jadi untuk Mathematica, saya berasumsi "baca dari keluaran terakhir".

Input (keluaran terakhir):

"0 0
4 4
0 4
4 0"

Keluaran:

0 0
0 4
4 0
4 4

Jika input dan output tidak perlu dalam format "baris baru", ini dapat menyusut menjadi 6 karakter:

Sort@%

mengambil output terakhir sebagai input, dengan asumsi output terakhir adalah array 2 dimensi.

Input (keluaran terakhir):

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

Ouput:

{{0,0},{0,4},{4,0},{4,4}}
kukac67
sumber
Tidakkah hanya Sortmelakukan hal yang sama?
desir
@ harap saya gunakan SortByagar saya dapat dengan mudah menyortir sehubungan dengan nilai "x" dan nilai "y".
kukac67
Tetapi sort melakukan hal yang sama, mengurutkan berdasarkan x dan y.
desir
Anda dapat menyimpan tujuh karakter dengan mengganti nama StringSplitlagi dan menggunakan sintaks infix Sort@(s=StringSplit)@%~s~"\n".
Martin Ender
@ Berharap Yah, terima kasih sudah memberi tahu saya tentang 'Urutkan'. Itu memperpendek kodenya ...
kukac67
1

PHP (175 109 100 karakter)

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

OK, saya akui, PHP bukan bahasa golf terbaik, tapi saya mencobanya.

Berikut beberapa contoh output:

0000 0000
0000 0004
0004 0000
0004 0004

Apa yang dilakukan adalah menempatkan informasi ke dalam string yang diformat dengan nol sebelumnya.
Kemudian hanya mengurutkan poin secara tekstual.
PS Gagal pada angka di atas 9999.

Robbie Wxyz
sumber
0

Python 2.7, 42B

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

Tidak bisa lebih sederhana; baca STDIN, urutkan garis, garis cetak. NB Saya menghormati persyaratan I / O yang tepat dari pertanyaan itu, tetapi jika Anda secara manual mengisi STDIN, Anda perlu menekan CTRL+duntuk mengakhiri input.

alexander-brett
sumber