Siapa Polygon itu?

14

Cara yang nyaman dan berguna untuk mewakili permukaan topologi adalah dengan poligon dasar . Setiap sisi pada poligon cocok dengan sisi lain dan dapat berupa paralel atau anti-paralel. Misalnya, ini adalah poligon dasar torus :

Torus

Untuk mengetahui mengapa ini adalah torus, kita bisa membayangkan poligon kita menjadi selembar kertas. Untuk membuat permukaan yang tepat, kami ingin menekuk kertas kami sehingga ujung-ujungnya yang sesuai sejajar dengan panahnya. Sebagai contoh torus kita, kita dapat mulai dengan menggulung kertas ke dalam silinder sehingga kedua tepi biru (berlabel b) terhubung. Sekarang kita mengambil tabung kita dan menekuknya sehingga kedua ujung merah (berlabel a) saling terhubung. Kita harus memiliki bentuk donat, juga disebut torus.

Ini bisa menjadi sedikit rumit. Jika Anda mencoba melakukan hal yang sama dengan poligon berikut ini di mana salah satu ujungnya berada di arah yang berlawanan:

Botol Klein

Anda mungkin menemukan diri Anda dalam masalah. Ini karena poligon ini mewakili botol Klein yang tidak dapat disematkan dalam tiga dimensi. Berikut adalah diagram dari wikipedia yang menunjukkan bagaimana Anda dapat melipat poligon ini menjadi botol Klein:

Lipat Botol Klein


Seperti yang sudah Anda tebak, tugas di sini adalah mengambil poligon dasar dan menentukan permukaannya. Untuk empat sisi poligon (satu-satunya permukaan yang Anda harus tangani) ada 4 permukaan yang berbeda.

Mereka

  • Torus

  • Botol Klein

  • Bola

  • Pesawat proyektif

Sekarang ini bukan jadi saya tidak mengharapkan Anda untuk mengambil gambar sebagai input, sebaliknya kita akan menggunakan notasi yang mudah untuk mewakili poligon mendasar. Anda mungkin telah memperhatikan dalam dua contoh di atas bahwa saya menamai tepi yang sesuai dengan huruf yang sama (baik a atau b), dan bahwa saya memberi tanda bengkok sebagai tanda tambahan untuk menunjukkan bengkoknya. Jika kita mulai dari tepi atas dan menuliskan label untuk setiap sisi saat kita bergerak searah jarum jam kita bisa mendapatkan notasi yang mewakili setiap poligon mendasar.

Misalnya Torus yang disediakan akan menjadi abab dan Botol Klein akan menjadi ab - ab . Untuk tantangan kami, kami akan membuatnya lebih sederhana, alih-alih menandai ujung yang bengkok dengan negatif, kami malah akan membuat huruf-huruf tersebut menjadi huruf besar.

Tugas

Diberikan string menentukan apakah itu merupakan poligon dasar dan menghasilkan nilai yang sesuai dengan permukaan yang tepat itu. Anda tidak perlu memberi nama permukaan dengan tepat, Anda hanya perlu 4 nilai output yang berbeda, masing-masing mewakili salah satu dari 4 permukaan dengan nilai kelima mewakili input yang tidak tepat. Semua kasus dasar tercakup dalam bagian Tes Sederhana , setiap mobil akan isomorfik ke salah satu atau tidak valid.

Aturan

  • Sisi tidak akan selalu dilabeli dengan a dan b, tetapi mereka akan selalu dilabeli dengan huruf.

  • Masukan yang valid akan terdiri dari 4 huruf, dua dari satu jenis dan dua lainnya. Anda harus selalu menampilkan permukaan yang benar untuk input yang valid.

  • Anda harus menolak (bukan menampilkan salah satu dari 4 nilai yang mewakili permukaan) input yang tidak valid. Anda dapat melakukan apa saja saat menolak input, asalkan dapat dibedakan dari 4 permukaan

  • Ini adalah sehingga tujuannya adalah untuk meminimalkan jumlah byte dalam kode sumber Anda.

Tes

Tes Sederhana

abab Torus
abAb Klein Bottle
abaB Klein Bottle
abAB Projective Plane
aabb Klein Bottle
aAbb Projective Plane
aabB Projective Plane
aAbB Sphere
abba Klein Bottle
abBa Projective Plane
abbA Projective Plane
abBA Sphere

Tes yang lebih rumit

ABAB  Torus
acAc  Klein Bottle
Emme  Projective Plane
zxXZ  Sphere
aaab  Bad input
abca  Bad input
abbaa Bad input
ab1a  Bad input
Posting Rock Garf Hunter
sumber
Mengapa ababtorus dan aabbbotol Klein?
Neil
@Neil ababadalah contoh di paragraf pertama, Anda bisa mencari penjelasan di sana. Berikut adalah gambar yang menunjukkan mengapa aabbsama dengan abAbbotol Klein.
Post Rock Garf Hunter
1
Masukan buruk apa yang harus kita tangani dan identifikasi sebagai buruk? Semua string yang mungkin? Cetak ASCII? Adakah batasan panjang? Jika kita menulis suatu fungsi, mungkinkah itu dilewatkan objek non-string? Sungguh, seluruh bisnis pemrosesan input ini mengejutkan saya sebagai tantangan bunglon.
xnor
1
@WheatWizard Dalam hal ini, bisakah Anda menjelaskannya dalam judul dan isi? Bunyinya seperti matematika sampai Peraturan, dan bahkan di sana mudah untuk melewatkan persyaratan gamechanging untuk memvalidasi daripada hanya mengklasifikasikan.
xnor
2
Secara terpisah, saya pikir ada penjelasan yang hilang dari apa yang membuat string diklasifikasikan ke dalam kategori tertentu, karena Anda tampaknya tidak mengharapkan orang untuk melakukan perhitungan di belakang klasifikasi. Saya pikir saya bisa memecahkan aturan dari test case, tapi itu jauh dari ideal.
xnor

Jawaban:

6

Retina , 123 byte

i`(.)(\1..)
$2$1
iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$
(..)\1
T
.*(.).\1.*|(.)(.)\3\2
B
(.)..\1|.(.)\2.
P
i`(.)..\1
S
....
P

Cobalah online! Terima kasih kepada @JonathanAllen karena menunjukkan bug dalam kode saya dan juga bagaimana cara menyimpan beberapa byte; Saya juga bermain golf lebih banyak byte sendiri sehingga saya tidak bisa kredit dia untuk angka tertentu. Penjelasan:

i`(.)(\1..)
$2$1

Jika dua huruf pertama sama (mengabaikan case), pindahkan huruf pertama menjadi keempat. Ini mengurangi jumlah kasus yang perlu saya uji.

iG`^([a-z])(?!\1)([a-z])(\1\2|\2\1)$

Jika tidak ada tepat empat huruf, atau dua huruf pertama sama, atau dua huruf terakhir tidak menduplikasi dua huruf pertama, maka hapus semuanya.

(..)\1
T

Torus adalah case mudah: sepasang huruf, case yang cocok berulang.

.*(.).\1.*|(.)(.)\3\2
B

Jika salah satu dari pasangan tersebut cocok dengan kasing (dalam hal ini pasangan lainnya harus cocok dengan kasing), maka itu adalah botol Klein. Atau, jika pasangan cocok dengan case tetapi terbalik, maka itu juga merupakan botol Klein.

(.)..\1|.(.)\2.
P

Jika di sisi lain pasangan terbalik, tetapi hanya satu dari pasangan yang cocok dengan huruf, maka itu adalah bidang proyektif.

i`(.)..\1
S

Dan jika pasangan terbalik tetapi tidak cocok dengan huruf besar, maka itu adalah bola. (i`.(.)\1. juga akan bekerja.)

....
P

Yang lainnya adalah pesawat proyektif.

Neil
sumber
1
@ JonathanAllan Terima kasih atas tipnya; semoga versi ini memiliki validasi yang lebih baik.
Neil
Kalau saja saya bisa mengerjakan sendiri logikanya: p
Jonathan Allan
1

Jelly , 52 51 58 byte

+7 byte, saya menemukan bahwa pemetaan yang saya gunakan tidak bekerja untuk beberapa skenario perubahan kasus (misalnya).

“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€
,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeЀ¢TṪ’:3,8

Tautan monadik yang mengambil string dan mengembalikan lima nilai konsisten dan berbeda berikut:

  • [-1,-1] - input tidak valid
  • [0,0] - Pesawat proyektif
  • [1,0] - Botol Klein
  • [2,0] - bola
  • [2,1] - Torus

Cobalah online! atau lihat test suite .

Bagaimana?

Setiap poligon mendasar adalah:

  • tidak berubah di bawah rotasi - orang dapat membalik kertas seperti setir
  • tidak berubah di bawah refleksi - orang dapat membalik kertas
  • tidak berubah dalam kasus pembalikan - seseorang dapat menukar as dan As dan / atau menukar bs dan Bs tanpa efek - karena kami ingin mencocokkan arah dengan label yang sebenarnya tidak penting.

Dengan demikian ada sembilan kelas kesetaraan. Kode membuat daftar empat bilangan bulat yang masing-masing mewakili contoh dari salah satu dari sembilan kelas ekivalensi, membuat empat rotasi masing-masing, mencerminkan masing-masing dan kemudian memeriksa apakah bentuk terjemahan dari input ada di setiap daftar. Kelas diperintahkan P,P,P,K,K,K,S,S,T, jadi mengambil bilangan bulat indeks berbasis 0 dibagi dengan masing-masing [3,8]menghasilkan empat output yang valid (pengindeksan adalah berbasis 1 dan atom ekembali 0untuk tidak adanya, jadi kurangi1 dan membagi bilangan bulat dengan masing-masing [3,8]hasil [-1,-1]untuk kasus yang tidak valid ).

“nḲ⁾⁶ƥ¦ṃṗḋ’b4s4‘µṙJ;U$µ€ - Link 1, symmetries of the 9 equivalence classes: no arguments
“nḲ⁾⁶ƥ¦ṃṗḋ’              - base 250 number                 1704624888339951310984
           b4            - convert to base 4               [1,1,3,0,1,2,2,0,1,2,3,0,0,2,2,0,1,3,1,0,2,1,2,0,2,3,1,0,3,1,2,0,2,0,2,0]
             s4          - split into 4s                   [[1,1,3,0],[1,2,2,0],[1,2,3,0],[0,2,2,0],[1,3,1,0],[2,1,2,0],[2,3,1,0],[3,1,2,0],[2,0,2,0]]
               ‘         - increment (vectorises)          [[2,2,4,1],[2,3,3,1],[2,3,4,1],[1,3,3,1],[2,4,2,1],[3,2,3,1],[3,4,2,1],[4,2,3,1],[3,1,3,1]]
                µ     µ€ - for €ach:                       ...e.g. [2,2,4,1]:
                  J      -   range of length               [1,2,3,4]
                 ṙ       -   rotate left by (vectorises)   [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1]]
                     $   -   last two links as a monad:
                    U    -     upend (reverse each)        [[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]
                   ;     -     concatenate                 [[2,4,1,2],[4,1,2,2],[1,2,2,4],[2,2,4,1],[2,1,4,2],[2,2,1,4],[4,2,2,1],[1,4,2,2]]

,ŒsṢÞṪµŒlĠL€⁼2,2ȧ⁸i@€ṢeЀ¢TṪ’:3,8 - Main link: string s      e.g. "xOxO"
 Œs                               - swap case                     "XoXo"
,                                 - pair with s                   ["xOxO","XoXo"]
    Þ                             - sort by:
   Ṣ                              -   sort                        ["xOxO","XoXo"]
     Ṫ                            - tail                          "XoXo"
      µ                           - monadic chain separation, call that v
       Œl                         - convert to lowercase          "xoxo"
         Ġ                        - group indices by value        [[2,4],[1,3]]
          L€                      - length of each                [2,2]
             2,2                  - 2 pair 2                      [2,2]
            ⁼                     - equal? (1 if so, 0 if not)    1
                 ⁸                - link's left argument, v       "XoXo"
                ȧ                 - and (v if equal, 0 if not)    "XoXo"
                     Ṣ            - sort v                        "XoXo"
                  i@€             - first index for €ach          [1,3,1,3]
                         ¢        - call the last link (1) as a nilad
                       Ѐ         - map over right:
                      e           -   exists in?                  [0,0,0,0,0,0,0,0,1]
                          T       - truthy indexes                [                9]
                           Ṫ      - tail (empty list yields 0)    9
                            ’     - decrement                     8
                              3,8 - 3 pair 8                      [3,8]
                             :    - integer division (vectorises) [2,1]

Catatan: 11 byte ( ŒlĠL€⁼2,2ȧ⁸) hanya memvalidasi string input sebagai bentuk yang benar - tanpa kode ini setiap contoh kasus melewati kecuali yang ab1adievaluasi seolah-olah itu adalah abBa, bidang proyektif.

Jonathan Allan
sumber