Tulis sebuah program yang memproses representasi seni ASCII dari string kusut dan memutuskan apakah itu dapat diurai menjadi loop sederhana. Kusut diwakili menggunakan karakter -
dan |
untuk mewakili segmen horisontal dan vertikal, dan +
untuk mewakili sudut. Tempat-tempat di mana string melewati dirinya diwakili sebagai berikut:
| |
------- ---|---
| |
(Horizontal segment on top) (Vertical segment on top)
Ujung-ujung tali dihubungkan bersama; tidak ada ujung yang longgar.
Jika program Anda memutuskan bahwa string tidak dapat diurai menjadi loop sederhana, itu akan menghasilkan kata KNOT
. Kalau tidak, itu akan menampilkan kata NOT
.
Ini adalah tantangan kode-golf , sehingga jawaban valid terpendek (diukur dalam byte kode sumber) akan menang.
Batas
Input ASCII terdiri dari hingga 25 baris dengan 80 karakter. Anda dapat mengasumsikan bahwa semua garis diisi dengan spasi dengan panjang yang sama.
Contohnya
Memasukkan:
+-------+ +-------+
| | | |
| +---|----+ +-------+
| | | | | |
+-------|------------|---+
| | | |
+---+ +---+
Keluaran:
KNOT
Memasukkan:
+----------+
| |
| +--------------+
| | | |
| | +-|----+ |
| | | | | |
| +-----+ | |
| | | |
| +------|---+
| |
+---------------+
Keluaran:
NOT
Referensi
sumber
Jawaban:
Python 3,
457316306 byteHah?
Program pertama kali mengkonversi simpul ke diagram persegi panjang, yang memiliki batasan sebagai berikut:
Misalnya, test case pertama dikonversi ke diagram persegi panjang berikut:
yang kami wakili secara unik oleh urutan koordinat y dari segmen vertikal, dari kanan ke kiri:
Kemudian mencari penyederhanaan diagram segi empat seperti yang dijelaskan dalam Ivan Dynnikov, “Arc-presentations of links. Penyederhanaan monotonik ”, 2004 . Dynnikov membuktikan bahwa dari diagram persegi panjang unknot, ada urutan langkah penyederhanaan yang berakhir pada diagram sepele. Secara singkat, gerakan yang diizinkan meliputi:
Lihat kertas untuk gambar. Ini bukan teorema yang jelas; itu tidak berlaku jika, katakanlah, Reidemeister bergerak yang tidak menambah jumlah penyeberangan yang digunakan sebagai gantinya. Tetapi untuk jenis penyederhanaan tertentu di atas, ternyata benar.
(Kami menyederhanakan implementasinya dengan hanya mengijinkan segmen vertikal, tetapi juga memungkinkan seluruh simpul dialihkan ke interchange horizontal dengan vertikal.)
Demo
sumber