L o o p I t

22

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)mana kentri -th pkmewakili ptitik -th dalam daftar input. Ini berarti kita memiliki garis dari p1ke p2, garis dari p2ke p3dll, serta garis dari pnke p1. (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:

masukkan deskripsi gambar di sini

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)]
cacat
sumber
Jika kita memiliki 4 poin O (0,0), A (1,0), B (0,1), C (0,2), apakah poligon OABC berpotongan sendiri?
ngn
@ ngn Itu poin bagus yang tidak saya pertimbangkan! Saya harus memikirkannya. Jika Anda memiliki argumen untuk atau menentangnya, beri tahu saya.
flawr
@ ngn Saya akan menghitung poligon ini sebagai berpotongan sendiri. Alasannya adalah bahwa saya mendefinisikan poligon untuk berpotongan sendiri jika ada titik umum dua sisi yang bukan titik akhir.
flawr
@ flawr Saya harus menarik jawaban saya kemudian, gagal ketika ada beberapa titik co-linear pada sudut maksimum dari titik referensi.
ngn

Jawaban:

10

Mathematica 29 28 Bytes

FindShortestTour (16 Bytes) melakukan trik tetapi memberikan beberapa informasi tambahan yang tidak diminta (panjang jalur, dan kembali ke titik awal).

Most@*Last@*FindShortestTour

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: masukkan deskripsi gambar di sini

Berikut adalah solusi pada 1000 poin acak:

masukkan deskripsi gambar di sini

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.

Kelly Lowder
sumber
6
Gunakan algoritma NP untuk menyelesaikan masalah P hanya karena lebih pendek. +1 (???).
user202729
1
@*tampaknya menghemat satu byte.
user202729
6

JavaScript (ES6), 365 341 byte

Tanpa 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.

f=(a,p=[],o=([p,P],[q,Q],[r,R])=>Math.sign((S=[(p>q?r<q|r>p:r<p|r>q)|(P>Q?R<Q|R>P:R<P|R>Q),...S],Q-P)*(r-q)-(q-p)*(R-Q)))=>[...p,p[0]].some((A,i,P)=>P.some((C,j)=>j>i+1&&P[++j+!i]&&[E=o(A,B=P[i+1],C,S=[]),F=o(A,B,D=P[j]),G=o(C,D,A),H=o(C,D,B)].some(v=>!v&!S.pop())|E!=F&G!=H))?0:a[0]?a.some((_,i)=>r=f(b=[...a],p.concat(b.splice(i,1))))&&r:p

Demo

Cuplikan ini mencatat output dan menggambar jalur yang sesuai di kanvas.

Bagaimana?

Berikut adalah struktur fungsi rekursif utama f () , mengesampingkan kode pengujian persimpangan untuk saat ini:

f = (a, p = []) =>                    // a = array of points, p = current path
  [...p,                              // build a closed path array P[] by adding the first
         p[0]]                        // point at the end of p[]
  .some((A, i, P) =>                  // for each point A at position i in P:
    P.some((C, j) =>                  //   for each point C at position j in P:
      j > i + 1 &&                    //     test whether C is at least 2 positions after A
      P[++j +                         //     and C is not the last point
              !i] &&                  //     and i > 0 or C is not the penultimate point
      intersection(                   //     and there's an intersection between
        A, P[i + 1], C, P[j]          //     the segments (A, P[i + 1]) and (C, P[j + 1])
      )                               //     (j was incremented above)
    )                                 //   end of inner some()
  ) ?                                 // end of outer some(); if truthy:
    0                                 //   discard this path by stopping recursion
  :                                   // else:
    a[0] ?                            //   if there's at least one remaining point:
      a.some((_, i) =>                //     for each remaining point at position i:
        r = f(                        //       do a recursive call with:
          b = [...a],                 //         a copy b[] of a[] without a[i] and
          p.concat(b.splice(i, 1)))   //         the extracted point added to the path
      ) && r                          //     end of some(); return the result, if any
    :                                 //   else:
      p                               //     this is a valid path: return it

Di bawah ini adalah detail dari tes persimpangan () . Halaman ini memberikan penjelasan komprehensif tentang algoritma yang digunakan.

[                                     // build an array containing:
  E = o(A, B = P[i + 1], C, S = []),  //   E = test of (A, B, C) (+ initialization of S[])
  F = o(A, B, D = P[j]),              //   F = test of (A, B, D)
  G = o(C, D, A),                     //   G = test of (C, D, A)
  H = o(C, D, B)                      //   H = test of (C, D, B)
]                                     //
.some(v =>                            // the segments are collinear and overlapping if:
  !v &                                //   any value above is 0
  !S.pop()                            //   and the corresponding entry in S[] is falsy
) |                                   // the segments intersect if:
E != F & G != H                       //   E is not equal to F and G is not equal to H

Akhirnya, inilah definisi fungsi helper o () :

o = (                                             // given three points represented by
  [p, P], [q, Q], [r, R]                          // a lowercase letter for x
) =>                                              // and an uppercase letter for y:
  Math.sign(                                      //
    (                                             //   1) prepend to the array S[]
      S = [                                       //      a boolean which is true if the
        (p > q ? r < q | r > p : r < p | r > q) | //      segment (P, Q) would not contain
        (P > Q ? R < Q | R > P : R < P | R > Q),  //      the point R, assuming that the
        ...S                                      //      3 points are collinear
      ],                                          //
                                                  //   2) return the orientation of P, Q, R:
      Q - P                                       //        -1 = counterclockwise
    ) * (r - q) - (q - p) * (R - Q)               //         0 = collinear
  )                                               //        +1 = clockwise
Arnauld
sumber
... mohon penjelasannya?
user202729
1
@ user202729 (* tisu di dahi *) Selesai!
Arnauld
5

APL (Dyalog Classic) , 42 38 byte

{⍋(⍪,(|z)ׯ1*⊢=⌈/)12z0j1⊥¨⍵-⍵[⊃⍋↑⍵]}

Cobalah 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 koordinat

0j1 unit imajiner i = sqrt (-1)

0j1⊥¨ mendekodekan koordinat seolah-olah digit dalam sistem bilangan base-i - yaitu mengubah (x, y) menjadi bilangan kompleks ix + y

z← ditugaskan kepada z

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 menaik

ngn
sumber
@ user202729 mereka akan diurutkan sesuai dengan kriteria kedua - jarak (yaitu fungsi melingkar 10, alias besarnya kompleks)
ngn