"KNOT" atau "TIDAK"?

144

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 , 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

lubang keras melengking
sumber
36
+1 Pertanyaan bagus. Tergoda untuk memberikan hadiah pada yang satu ini untuk mendorong orang-orang untuk terjun ke teori simpul itu.
Digital Trauma
2
Bisakah kita menganggap itu simpul (mungkin yang tidak tahu) atau dapatkah itu merupakan tautan dari> 1 komponen yang terhubung?
msh210
@ msh210 Ya, Anda dapat menganggap itu adalah simpul tunggal :-)
squeamish ossifrage

Jawaban:

94

Python 3, 457 316 306 byte

E=enumerate
V={'+'}
Q=[[(-j,i,k)for i,u in E(open(0))for j,v in E(u)for k in[{v}&V,'join'][u[j:j+2]=='|-']]]
while Q:
 a,b,c,d,*e=A=tuple(x//2for y,x in sorted((y,x)for x,y in E(Q.pop())));e or exit('NOT')
 if{A}-V:V|={A};Q+=[[c,d,a,b]+e,A,A[2:]+A[:2]][a<c<b<d:][c<a<d<b:]
 if b==d:Q=[[a,c]+e]
exit('KNOT')

Hah?

Program pertama kali mengkonversi simpul ke diagram persegi panjang, yang memiliki batasan sebagai berikut:

  1. Tidak ada dua segmen vertikal atau horizontal terletak pada garis yang sama.
  2. Tidak ada segmen vertikal yang melewati segmen horizontal.

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:

(5,10, 1,9, 8,10, 9,12, 5,12, 1,4, 0,3, 2,4, 3,7, 6,8, 7,11, 2,11, 0,6)

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:

  1. Secara manual mengubah segmen vertikal (atau horizontal);
  2. Bertukar segmen vertikal (atau horizontal) berurutan di bawah batasan konfigurasi tertentu.
  3. Mengganti tiga simpul yang berdekatan yang terletak di sudut diagram dengan satu simpul.

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

$ python3 knot.py <<EOF
+-------+    +-------+    
|       |    |       |    
|   +---|----+   +-------+
|   |   |        |   |   |
+-------|------------|---+
    |   |        |   |    
    +---+        +---+    
EOF
KNOT
$ python3 knot.py <<EOF
+----------+         
|          |         
|    +--------------+
|    |     |        |
|    |   +-|----+   |
|    |   | |    |   |
|    +-----+    |   |
|        |      |   |
|        +------|---+
|               |    
+---------------+    
EOF
NOT
$ python3 knot.py <<EOF  # the Culprit
        +-----+  
        |     |  
+-----------+ |  
|       |   | |  
|   +-+ | +---|-+
|   | | | | | | |
| +-|-------+ | |
| | | | | |   | |
+-|-+ | | +---+ |
  |   | |       |
  +---|---------+
      | |        
      +-+        
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot
    +-----+    
    |     |    
  +-|---------+
  | |     |   |
  | | +-+ |   |
  | | | | |   |
+-|-|---|-|-+ |
| | | | | | | |
| | | +---|---+
| | |   | | |  
+-------+ | |  
  | |     | |  
  | +-------+  
  |       |    
  +-------+    
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot plus trefoil
    +-----+ +-----+
    |     | |     |
  +-|---------+   |
  | |     | | |   |
  | | +-+ | +---+ |
  | | | | |   | | |
+-|-|---|-|-+ +---+
| | | | | | |   |  
| | | +---|-----+  
| | |   | | |      
+-------+ | |      
  | |     | |      
  | +-------+      
  |       |        
  +-------+        
EOF
KNOT
$ python3 knot.py <<EOF  # Thistlethwaite unknot
      +---------+        
      |         |        
    +---+ +---------+    
    | | | |     |   |    
    | +-------+ |   |    
    |   | |   | |   |    
    |   | | +---+   |    
    |   | | | |     |    
    |   | +-------+ |    
    |   |   | |   | |    
    |   +-------+ | |    
    |       | | | | |    
+-----------+ | | | |    
|   |         | | | |    
| +-----------+ | | |    
| | |           | | |    
| | +-------------+ |    
| |             |   |    
| |             +-----+  
| |                 | |  
| |                 +---+
| |                   | |
+---------------------+ |
  |                     |
  +---------------------+
EOF
NOT
$ python3 knot.py <<EOF  # (−3,5,7)-pretzel knot
      +-------------+
      |             |
    +-|-----+       |
    | |     |       |
  +-|-+   +-------+ |
  | |     | |     | |
+-|-+   +---+   +---+
| |     | |     | |  
| |   +---+   +---+  
| |   | |     | |    
| | +---+   +---+    
| | | |     | |      
| +---+   +---+      
|   |     | |        
|   |   +---+        
|   |   | |          
|   | +---+          
|   | | |            
|   +---+            
|     |              
+-----+              
EOF
KNOT
$ python3 knot.py <<EOF  # Gordian unknot
+-------------+                 +-------------+
|             |                 |             |
| +---------+ |                 | +---------+ |
| |         | |                 | |         | |
| | +-------------+         +-------------+ | |
| | |       | |   |         |   | |       | | |
| | | +---------+ |         | +---------+ | | |
| | | |     | | | |         | | | |     | | | |
| +-------+ | +-------+ +-------+ | +-------+ |
|   | |   | |   | |   | |   | |   | |   | |   |
+-------+ | +-------+ | | +-------+ | +-------+
    | | | |     | | | | | | | |     | | | |    
    | +-------+ | | | | | | | | +-------+ |    
    |   | |   | | | | | | | | | |   | |   |    
    +-------+ | | | | | | | | | | +-------+    
        | | | | | | | | | | | | | | | |        
        | +-----+ | | | | | | +-----+ |        
        |   | |   | | | | | |   | |   |        
        +---------+ | | | | +---------+        
            | |     | | | |     | |            
          +---------+ | | +---------+          
          | | |       | |       | | |          
          | | +-----------------+ | |          
          | |         | |         | |          
          | +---------------------+ |          
          |           | |           |          
          +-----------+ +-----------+          
EOF
NOT
Anders Kaseorg
sumber
Wow, ini luar biasa.
ossifrage pelit
3
Bisakah Anda mengeposkan versi kode Anda yang tidak dipisahkan?
J. Antonio Perez
Juga, apa kompleksitas waktu program Anda?
J. Antonio Perez
3
@JorgePerez Saya tidak memiliki versi tanpa ungolfed terpisah; cara terbaik untuk memahami program ini adalah dengan membaca makalah Dynnikov yang saya tautkan. Kompleksitasnya adalah sesuatu yang sangat eksponensial; Sejauh yang saya tahu, apakah ada algoritma waktu polinomial masih merupakan masalah terbuka.
Anders Kaseorg