Catatan: Judul pertanyaan ini harus "Loop It", tetapi karena judul harus minimal 15 karakter, ada beberapa ruang yang tidak terlihat. Catatan ini sedemikian rupa sehingga tantangan dapat dicari.
Tantangan
Diberi daftar terbatas dari titik-titik integral unik dalam pesawat, temukan poligon yang simpulnya persis titik-titik itu, yang tidak saling berpotongan.
Detail
- Sebagai input, Anda dapat mengambil misalnya dua daftar dengan masing-masing koordinat x dan y atau daftar pasangan.
- Daftar input berisi setidaknya 3 poin.
- Perhatikan bahwa ini berarti tidak pernah ada solusi unik.
- Daftar input dapat diasumsikan tidak co-linear (titik-titik tidak dapat terkandung dalam satu baris), ini berarti sebenarnya ada poligon yang tidak berpotongan sendiri.
- Sudut-sudut pada setiap titik adalah arbitrer, ini termasuk 180 °.
- Untuk input panjang
n
, output harus permutasi(p1,p2,p3,...,pn)
di(1,2,3,...,n)
manak
entri -thpk
mewakilip
titik -th dalam daftar input. Ini berarti kita memiliki garis darip1
kep2
, garis darip2
kep3
dll, serta garis daripn
kep1
. (Anda juga dapat menggunakan indeks berbasis 0.) Atau Anda dapat menampilkan daftar titik input dalam urutan yang benar.
Contohnya
Katakanlah kita memiliki poin [(0,0),(0,1),(1,0),(-1,0),(0,-1)]
dan kita ingin mewakili jalur berikut:
Ini berarti kami akan menampilkan daftar [5,1,4,2,3]
Berikut beberapa saran untuk dicoba (Saya sarankan melihat plot yang sesuai untuk memverifikasi tujuan.)
Triangle
[(0,0),(0,1),(1,0)]
S-Curve
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4),(4,0),(4,1),(4,2),(4,3),(4,4)]
L-Shape
[(4,0),(1,0),(3,0),(0,0),(2,0),(0,1)]
Menger Sponge
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,1),(10,1),(11,1),(12,1),(13,1),(14,1),(15,1),(16,1),(17,1),(18,1),(19,1),(20,1),(21,1),(22,1),(23,1),(24,1),(25,1),(26,1),(27,1),(1,2),(3,2),(4,2),(6,2),(7,2),(9,2),(10,2),(12,2),(13,2),(15,2),(16,2),(18,2),(19,2),(21,2),(22,2),(24,2),(25,2),(27,2),(1,3),(2,3),(3,3),(4,3),(5,3),(6,3),(7,3),(8,3),(9,3),(10,3),(11,3),(12,3),(13,3),(14,3),(15,3),(16,3),(17,3),(18,3),(19,3),(20,3),(21,3),(22,3),(23,3),(24,3),(25,3),(26,3),(27,3),(1,4),(2,4),(3,4),(7,4),(8,4),(9,4),(10,4),(11,4),(12,4),(16,4),(17,4),(18,4),(19,4),(20,4),(21,4),(25,4),(26,4),(27,4),(1,5),(3,5),(7,5),(9,5),(10,5),(12,5),(16,5),(18,5),(19,5),(21,5),(25,5),(27,5),(1,6),(2,6),(3,6),(7,6),(8,6),(9,6),(10,6),(11,6),(12,6),(16,6),(17,6),(18,6),(19,6),(20,6),(21,6),(25,6),(26,6),(27,6),(1,7),(2,7),(3,7),(4,7),(5,7),(6,7),(7,7),(8,7),(9,7),(10,7),(11,7),(12,7),(13,7),(14,7),(15,7),(16,7),(17,7),(18,7),(19,7),(20,7),(21,7),(22,7),(23,7),(24,7),(25,7),(26,7),(27,7),(1,8),(3,8),(4,8),(6,8),(7,8),(9,8),(10,8),(12,8),(13,8),(15,8),(16,8),(18,8),(19,8),(21,8),(22,8),(24,8),(25,8),(27,8),(1,9),(2,9),(3,9),(4,9),(5,9),(6,9),(7,9),(8,9),(9,9),(10,9),(11,9),(12,9),(13,9),(14,9),(15,9),(16,9),(17,9),(18,9),(19,9),(20,9),(21,9),(22,9),(23,9),(24,9),(25,9),(26,9),(27,9),(1,10),(2,10),(3,10),(4,10),(5,10),(6,10),(7,10),(8,10),(9,10),(19,10),(20,10),(21,10),(22,10),(23,10),(24,10),(25,10),(26,10),(27,10),(1,11),(3,11),(4,11),(6,11),(7,11),(9,11),(19,11),(21,11),(22,11),(24,11),(25,11),(27,11),(1,12),(2,12),(3,12),(4,12),(5,12),(6,12),(7,12),(8,12),(9,12),(19,12),(20,12),(21,12),(22,12),(23,12),(24,12),(25,12),(26,12),(27,12),(1,13),(2,13),(3,13),(7,13),(8,13),(9,13),(19,13),(20,13),(21,13),(25,13),(26,13),(27,13),(1,14),(3,14),(7,14),(9,14),(19,14),(21,14),(25,14),(27,14),(1,15),(2,15),(3,15),(7,15),(8,15),(9,15),(19,15),(20,15),(21,15),(25,15),(26,15),(27,15),(1,16),(2,16),(3,16),(4,16),(5,16),(6,16),(7,16),(8,16),(9,16),(19,16),(20,16),(21,16),(22,16),(23,16),(24,16),(25,16),(26,16),(27,16),(1,17),(3,17),(4,17),(6,17),(7,17),(9,17),(19,17),(21,17),(22,17),(24,17),(25,17),(27,17),(1,18),(2,18),(3,18),(4,18),(5,18),(6,18),(7,18),(8,18),(9,18),(19,18),(20,18),(21,18),(22,18),(23,18),(24,18),(25,18),(26,18),(27,18),(1,19),(2,19),(3,19),(4,19),(5,19),(6,19),(7,19),(8,19),(9,19),(10,19),(11,19),(12,19),(13,19),(14,19),(15,19),(16,19),(17,19),(18,19),(19,19),(20,19),(21,19),(22,19),(23,19),(24,19),(25,19),(26,19),(27,19),(1,20),(3,20),(4,20),(6,20),(7,20),(9,20),(10,20),(12,20),(13,20),(15,20),(16,20),(18,20),(19,20),(21,20),(22,20),(24,20),(25,20),(27,20),(1,21),(2,21),(3,21),(4,21),(5,21),(6,21),(7,21),(8,21),(9,21),(10,21),(11,21),(12,21),(13,21),(14,21),(15,21),(16,21),(17,21),(18,21),(19,21),(20,21),(21,21),(22,21),(23,21),(24,21),(25,21),(26,21),(27,21),(1,22),(2,22),(3,22),(7,22),(8,22),(9,22),(10,22),(11,22),(12,22),(16,22),(17,22),(18,22),(19,22),(20,22),(21,22),(25,22),(26,22),(27,22),(1,23),(3,23),(7,23),(9,23),(10,23),(12,23),(16,23),(18,23),(19,23),(21,23),(25,23),(27,23),(1,24),(2,24),(3,24),(7,24),(8,24),(9,24),(10,24),(11,24),(12,24),(16,24),(17,24),(18,24),(19,24),(20,24),(21,24),(25,24),(26,24),(27,24),(1,25),(2,25),(3,25),(4,25),(5,25),(6,25),(7,25),(8,25),(9,25),(10,25),(11,25),(12,25),(13,25),(14,25),(15,25),(16,25),(17,25),(18,25),(19,25),(20,25),(21,25),(22,25),(23,25),(24,25),(25,25),(26,25),(27,25),(1,26),(3,26),(4,26),(6,26),(7,26),(9,26),(10,26),(12,26),(13,26),(15,26),(16,26),(18,26),(19,26),(21,26),(22,26),(24,26),(25,26),(27,26),(1,27),(2,27),(3,27),(4,27),(5,27),(6,27),(7,27),(8,27),(9,27),(10,27),(11,27),(12,27),(13,27),(14,27),(15,27),(16,27),(17,27),(18,27),(19,27),(20,27),(21,27),(22,27),(23,27),(24,27),(25,27),(26,27),(27,27)]
Jawaban:
Mathematica
2928 BytesFindShortestTour
(16 Bytes) melakukan trik tetapi memberikan beberapa informasi tambahan yang tidak diminta (panjang jalur, dan kembali ke titik awal).hanya memberikan jawaban (-1 byte terima kasih ke @ user202729)
Untuk memvisualisasikan, gunakan
Graphics@Line[g[[%]]]
, di mana%
permutasi ditemukan di atas dan g adalah daftar titik asli.Berikut adalah visualisasi solusi untuk Menger Sponge:
Berikut adalah solusi pada 1000 poin acak:
Kuncinya di sini adalah mengetahui bahwa solusi masalah wisata atau penjual keliling yang terpendek tidak akan pernah menghasilkan persimpangan ketika jarak Euclidean digunakan sebagai metrik. Salah satu langkah untuk melokalkan solusi dan memastikan optimalitas adalah menghapus persimpangan tersebut.
sumber
@*
tampaknya menghemat satu byte.JavaScript (ES6),
365341 byteTanpa built-in, ini ternyata jauh lebih lama dari yang saya harapkan. Banyak byte yang dihabiskan untuk mendeteksi segmen tumpang tindih collinear.
Mengambil input sebagai array
[x,y]
koordinat. Mengembalikan permutasi input.Demo
Cuplikan ini mencatat output dan menggambar jalur yang sesuai di kanvas.
Tampilkan cuplikan kode
Bagaimana?
Berikut adalah struktur fungsi rekursif utama f () , mengesampingkan kode pengujian persimpangan untuk saat ini:
Di bawah ini adalah detail dari tes persimpangan () . Halaman ini memberikan penjelasan komprehensif tentang algoritma yang digunakan.
Akhirnya, inilah definisi fungsi helper o () :
sumber
APL (Dyalog Classic) ,
4238 byteCobalah online!
Input adalah daftar pasangan koordinat. Output adalah permutasi berbasis 0.
⍵
adalah daftar poin - argumen untuk{ }
⍵[⊃⍋↑⍵]
adalah titik paling kiri-terendah⍵-
menerjemahkan semua poin sehingga paling kiri-terendah adalah pada asal sistem koordinat0j1
unit imajiner i = sqrt (-1)0j1⊥¨
mendekodekan koordinat seolah-olah digit dalam sistem bilangan base-i - yaitu mengubah (x, y) menjadi bilangan kompleks ix + yz←
ditugaskan kepadaz
12○
menghitung argumen bilangan kompleks, alias sudut theta, atau fungsi lingkaran APL 12(⍪,(|z)ׯ1*⊢=⌈/)
adalah kereta yang menghitung topeng boolean di mana sudut maksimum (⊢=⌈/
), mengubah 0 1 di topeng menjadi 1 1 dengan menaikkan 1 ke daya yang sesuai (¯1*
), dikalikan dengan besarnya bilangan kompleks|z
, dan menyimpulkan bahwa ke kanan (,
) dari matriks 1-kolom tipis tinggi (⍪
) dari sudut.⍋
grade - mengembalikan permutasi yang akan mengurutkan baris matriks secara leksikografis dalam urutan menaiksumber