2D Maze Minus 1D

27

Tantangan ini adalah tentang mengubah labirin 2D menjadi labirin 1D.

Ikhtisar

+-+-+-+-+-+-+   +-+-+-+-+-+-+                    graph {
| |   |     |   |A|   |    B|   A         B        A -- D
+ + + + +-+-+   + + + + +-+-+    \        |        C -- D
|   | |     |   |   | |     |     \       |        D -- E
+-+-+ +-+-+ +   +-+-+ +-+-+ +      \      |        E -- F
|           |   |C   D E   F|   C---D-E---F        E -- G
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |   |        B -- F
|         | |   |      G  | |     .---G   |        F -- J
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /    |        G -- H
| |       | |   |H|I      |J|   H I-'     J        G -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)        } // (graphviz dot)       
   Figure 1       Figure 2                 Figure 3

Untuk keperluan tantangan ini, labirin 2D tradisional adalah labirin persegi panjang yang dibentuk dari titik-titik kisi tempat semua hal berikut ini berlaku:

  • Tutup (tepi luar dihubungkan oleh dinding).
  • Semua titik kisi terhubung ke dinding
  • Terhubung (untuk setiap dua ruang X dan Y ada jalur di antara mereka)
  • Itu asiklik (tidak ada jalur dari ruang X kembali ke X tanpa mundur)

Gambar 1 menunjukkan labirin 2D tradisional. Labirin ini memiliki tiga bidang minat:

  • Jalan buntu - tempat di mana hanya ada satu jalur yang tersedia
  • Koridor - tempat dari mana ada dua jalur yang tersedia
  • Poin keputusan - tempat dari mana ada tiga atau empat jalur yang tersedia

Untuk setiap labirin seperti itu, seseorang dapat membuat grafik di mana ujung buntu dan titik keputusan adalah simpul, dan ada tepi antara setiap dua simpul yang dihubungkan oleh jalur di sepanjang koridor. Gambar 2 menunjukkan labirin yang sama dengan node tersebut berlabel, dan Gambar 3 grafik labirin (dalam notasi dot ASCII dan Graphviz).

Labirin 1D

Labirin 1D menggabungkan poin warp, yang datang berpasangan, dan diidentifikasi menggunakan huruf (dalam kedua kasus). Gambar 4 menunjukkan contoh labirin 1D. Ini sebaliknya identik dengan labirin 2D dengan ketinggian 1, seperti yang ditunjukkan pada Gambar 5. Perhatikan khususnya pada Gambar 5 posisi titik kisi yang ditandai oleh +, yang bergantian dari kiri ke kanan; di labirin 1D, setiap karakter lain dimulai dengan dinding paling kiri juga merupakan titik kisi.

                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  D|  D E|G E F|  F  |  G  |    |  D|  D E|G E F|  F  |  G  |
                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            Figure 4                         Figure 5

Aturan untuk menavigasi labirin ini adalah sebagai berikut. Setiap gerakan dapat direpresentasikan sebagai maju ( >) atau mundur ( <). Maju dan mundur di sini secara default memiliki arti yang sama dengan kesadaran spasial intuitif kami; maju ke posisi segera ke kanan, dan segera mundur ke kiri.

Warp points mewakili lokasi yang secara asimetris menukar keterhubungan dengan tetangga. Jika Anda datang dari tetangga ke titik lungsin, posisi dua titik lungsin diganti; jika Anda datang dari titik warp ke tetangga, mereka tidak ditukar. Misalnya, pada Gambar 6, bergerak mundur dari 1 membawa Anda ke 2 (karena 1 adalah tetangga G, dan kami bergerak dari tetangga, poin 2 dan @ ditukar). Bergerak maju dari 2 (titik warp G) membawa Anda ke 3 (di sini, kami mulai dari titik warp, jadi tidak ada swap). Demikian juga, bergerak mundur dari 3 membawa Anda ke @.

        54 2367    89^   @1
|  D|  D E|G E F|  F  |  G  |
                     Y     X
          Figure 6

Gambar 6 juga menunjukkan contoh navigasi dari X ke Y, menggunakan urutan gerakan <<>><>>>>>. Langkah-langkah ini membawa Anda ke titik yang diberi label 123456789^masing-masing, dalam urutan itu. Jangan ragu untuk menjelajahinya sendiri menggunakan potongan kode di bagian selanjutnya.

Konversi 2D ke 1D

Dengan diberi labirin 1D, seseorang dapat membuat grafik di mana setiap node merupakan jalan buntu atau pasangan lungsin, dan tepiannya ada di antara dua simpul yang terhubung di sepanjang koridor. Grafik ini memungkinkan kita untuk membandingkan labirin 1D dan 2D.

Misalnya, labirin 1D pada Gambar 4 adalah labirin yang sama pada Gambar 1. Untuk melihat alasannya, Gambar 7 menambahkan label ke jalan buntu. Dengan menggunakan label-label itu untuk membuat grafik, grafik Gambar 7 hanyalah Gambar 3 lagi. Gambar 8 menunjukkan breakout untuk membangun grafik ini.

|  D|  D E|G E F|  F  |  G  |
 A   C           B   J H   I 
          Figure 7

|  D|  D E|G E F|  F  |  G  |
+ + + + + + + + + + + + + + + <- lattice points
|A  |C    |     |B   J|H   I| <- dead ends
|A D|C D E|G E F|B F J|H G I| <- all nodes (dead ends+warp points); i.e.:
                                 "where each end is either a dead end
                                  or a warp point pair"; note that each
                                  pair of warp points is the same node.
|A-D|C-D-E|G-E-F|B-F-J|H-G-I| <- corridors; note each is a connection, since
  1   2 3   4 5   6 7   8 9      "edges exist between any two nodes
                                  connected along a corridor"
   graph {                 graph {                 
     A -- D  // 1 <---->     A -- D                
     C -- D  // 2 <---->     C -- D                
     D -- E  // 3 <---->     D -- E                
     G -- E  // 4 <---->     E -- G                
     E -- F  // 5 <---->     E -- F                
     B -- F  // 6 <---->     B -- F                
     F -- J  // 7 <---->     F -- J                
     H -- G  // 8 <---->     G -- H                
     G -- I  // 9 <---->     G -- I                
   }                ^      }
    Built from      |      From Figure 3
     1D maze         `-> isomorphic mappings
                Figure 8

(Perhatikan bahwa label dan tata letak setiap grafik secara artifisial dipilih untuk disejajarkan untuk tujuan ilustrasi; secara umum ini adalah masalah isomorfisme grafik ).

Cuplikan berikut disediakan untuk membantu memvisualisasikan mekanisme labirin 1D dan koneksi antara labirin 1D, grafik kesetaraan, dan labirin 2D.

Tampilkan cuplikan kode

Saat Anda menavigasi labirin 1D dalam cuplikan ini, dua node terakhir yang Anda sentuh disorot. Node yang sama disorot dengan cara yang sama pada grafik ekivalensi dan labirin 2D.

Secara umum, untuk setiap labirin 2D tradisional, labirin 1D setara dari jenis ini dapat dibuat. Contoh yang sedikit lebih kompleks adalah Gambar 9:

+-+-+-+-+-+-+   +-+-+-+-+-+-+                   graph {
| |   |   | |   |A|   |   |B|   A         B       A -- D
+ + + + + + +   + + + + + + +    \       /        C -- D
|   | | |   |   |   | | |   |     \     /         D -- E
+-+-+ + +-+-+   +-+-+ + +-+-+      \   /          B -- E
|           |   |C   D E    |   C---D-E           E -- F
+-+-+-+ +-+ +   +-+-+-+ +-+ +         |\          E -- I
|         | |   |      F  | |     .---F \         F -- G
+ +-+-+-+ + +   + +-+-+-+ + +   .'   /   \        G -- H
| |       | |   |G|H      |I|   G H-'     I       H -- I
+-+-+-+-+-+-+   +-+-+-+-+-+-+     (ascii)       } // (graphviz dot)
   Figure 9       Figure 10             Figure 11

|  D|  D E  |F E  |  F  |       |  D|  D E  |F E  |  F  |
                                 A   C     I     B G   H
      Figure 12                       Figure 13

Labirin ini memiliki simpul dengan empat jalur (E pada Gambar 10). Gambar 11 menunjukkan grafiknya. Gambar 12 adalah labirin 1D yang setara; dan Gambar 13 menunjukkan labirin yang sama dengan label untuk jalan buntu untuk dibandingkan dengan Gambar 11.

Tantangan

Diberikan Labirin 2D sebagai input, tulis fungsi atau program yang mengubah labirin 2D menjadi labirin 1D dengan titik warp. Poin lungsin dapat menggunakan salah satu dari 52 huruf dalam setiap kasus.

Jaminan input (jika salah satu dari ini tidak terpenuhi dalam input Anda tidak harus menghadapinya):

  • Input maze terhubung (yaitu, Anda selalu dapat pergi dari satu tempat ke tempat lain).
  • Labirin input ditutup.
  • Labirin input berbentuk persegi panjang.
  • Semua poin kisi digunakan +.
  • Semua dinding antara titik-titik kisi pada penggunaan baris yang sama |
  • Semua dinding di antara titik-titik kisi dalam penggunaan kolom yang sama -.
  • Semua ruang adalah bagian dari jalan (dan semua di dalam labirin).
  • Path adalah semua ruang (ini akan selalu tradisional, tidak melengkung)
  • Jalan tepat satu lebar ruang.
  • Labirin dibangun dengan menghubungkan titik-titik pada sebuah kisi.
  • Tidak ada lebih dari 52 total node (yaitu, jalan buntu ditambah titik keputusan) dalam grafik labirin.

Format output:

  1. Output Anda harus berupa satu baris yang menunjukkan labirin 1D.
  2. Output Anda seharusnya tidak memiliki spasi spasi awal / jejak; kecuali bahwa trailing newline baik-baik saja.
  3. Karakter pertama dan setiap karakter lainnya setelahnya adalah poin kisi.
  4. Semua dinding harus pada titik kisi; dan semua titik warp di antara mereka.
  5. Grafik labirin 1D Anda harus setara dengan grafik labirin 2D.
  6. Labirin 1D Anda harus kompak; semua titik non-kisi harus buntu (yaitu, bersebelahan dengan dinding) atau titik warp.
  7. Satu- satunya huruf dalam output Anda harus poin warp. Setiap titik warp muncul di garis tepat dua kali.

Contoh:

|  D|  D E|G E F|  F  |  G  | <- (1,2) The single line output
+ + + + + + + + + + + + + + + <- lattice point spacing... (3) 
                                 (4,6) lattice points are all walls or spaces
                                 (5) See Figure 8
                                 (7) D, E, F, G appear twice; no other labels

Ini adalah kode-golf. Pemenangnya adalah pengiriman non-celah yang benar dengan byte terkecil.

Pengujian

Tidak ada uji kasus untuk tantangan ini, karena ada sejumlah besar output yang benar untuk setiap labirin nontrivial.

Namun, saya telah membangun sebuah checker di C ++ (checker ini membuat grafik kedua solusi melalui kanonik grafik ).

Selain itu, berikut adalah beberapa contoh untuk membantu menggambarkan pemformatan yang tepat:

Contoh 1

+-+-+-+-+-+-+
| |   |     |
+ + + + +-+-+
|   | |     |
+-+-+ +-+-+ +
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E|G E F|  F  |  G  |

Contoh 2

+-+-+-+-+-+-+
| |   |   | |
+ + + + + + +
|   | | |   |
+-+-+ + +-+-+
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E  |F E  |  F  |

Lebih banyak contoh dapat ditemukan di sini .

code-golf graph-theory maze H Walters
sumber
1
Saya tidak berpikir penjelasan labirin 1D sangat jelas sekali ... Mungkin menambahkan contoh yang lebih kecil / sederhana akan membantu.
mbomb007
Itu keren sekali. Ya itu membantu.
mbomb007
Meskipun skrip interaktif Anda membantu, itu masih merupakan masalah yang sulit. Jadi saya lewati saja. Pemahaman saya tentang hal ini masih lemah.
mbomb007
Deskripsi labirin 1D tidak lengkap. Saya harus membaca hingga angka 7 untuk memahami bahwa karakter bilah vertikal dalam labirin 1D adalah dinding yang tidak dapat Anda lewati.
edc65
1
contoh 1 dengan labirin 1d ditumpuk menjadi labirin 2d di mana setiap pasangan huruf adalah tangga: gist.github.com/sparr/36d6355cc4c785a27b12157666169082
Sparr

Jawaban:

3

Python 2 dengan igraph , 492 369 byte

import igraph,string
def f(s):
 C=s.find('\n')/2;N=' ';g=igraph.Graph(0,[(i,i+j)for i in range(len(s)/(4*C+4)*C)for j in(1,C)if s[(i/C*2+1)*(2*C+2)+i%C*2+2*j+j/C*3]==N]);V=g.vs;g.d=g.degree;O='';V(_d=1)[N]=N;V(_d_gt=2)[N]=list(string.ascii_letters)
 while g.es:
    v=V(_d=1)[0];O+='|'+v[N]
    while g.d(v):w=v.neighbors()[0];g-=(v,w);v=w;O+=N+v[N]if v[N]else''
 print O+'|'

(Baris kelima dan keenam masing-masing dimulai dengan tab, bukan empat spasi seperti yang ditunjukkan StackExchange.)

  • Disimpan enam byte mengatur ulang beberapa aritmatika
  • Disimpan tujuh byte menggunakan irisan, bukan zip
  • Disimpan tiga byte menggunakan g+=tuple(v.neighbors())bukang.add_edge(*v.neighbors())
  • Disimpan tujuh byte menggunakan g-=g.es[g.incident(v)]bukang.delete_edges(g.incident(v))
  • Disimpan sebelas byte alias g.d=g.degree
  • Disimpan 52 byte (!) Menghilangkan loop yang dikontrak semua koridor dengan mengganti derajat-2 simpul dengan tepi antara tetangga mereka. Sebagai gantinya, loop keluaran hanya mengabaikan simpul-simpul ini.
  • Disimpan 13 byte memperhatikan bahwa ketika menetapkan nama, igraph tidak peduli jika yang disediakan terlalu panjang
  • Disimpan empat byte dengan tidak memiliki variabel Runtuk jumlah baris, memindahkan perhitungannya ke satu-satunya titik penggunaan
  • Menyimpan dua byte mengubah indentasi tingkat kedua ke tab alih-alih spasi
  • Menyimpan enam byte yang disusun ulang 2*(i%C)menjadi i%C*2, 2*(i/C)ke i/C*2, dan (C-1)*jkej*C-j
  • Menyimpan penamaan empat byte N='n'
  • Disimpan satu byte yang menentukan apakah karakter menggunakan spasi <'-'daripada ==' ', dengan asumsi bahwa hanya karakter yang valid yang muncul.
  • Kemudian menyadari aku dapat nama atribut vertex ' 'bukan 'n', dan penggunaan kembali Nuntuk dua ruang literal dalam sumber, dan ==Nbukan <'-', menghemat lima byte lagi

Versi yang agak tidak ungolf mengikuti. Ide dasarnya adalah pertama-tama membuat grafik pada semua simpul labirin (bintik-bintik dengan baris dan kolom ganjil ketika diindeks nol). Ada tepi dari satu titik ke titik berikutnya pada baris yang sama jika karakter berikut adalah spasi , dan tidak |. Ada tepi dari titik ke yang tepat di bawahnya jika karakter yang sesuai di baris berikut adalah spasi, dan bukan -.

Setelah membuat grafik ini, kami mengambil daun apa saja, dan mengikuti simpul yang berdekatan berturut-turut, menuliskan nama mereka jika bukan koridor, dan menghapus tepi yang digunakan, sampai kami terjebak. Lalu kami mengambil daun lain dan melanjutkan sampai semua ujungnya hilang.

import string
import igraph
def f(s):
  C = s.find('\n')/2 # number of maze vertices in each row
  R = len(s)/(4*C+4) # number of rows
  def strpos(r, c):
    """Index of the vertex at row r, col c in the newline-delimited string s"""
    return (2*r+1)*(2*C+2) + 2*c + 1
  def vertpos(i):
    """Index of the i-th vertex in s"""
    return strpos(i/C, i%C)
  g = igraph.Graph(edges=[(i, i+(C if j else 1))
                          for i in range(R*C)
                          for j in (0, 1)
                          if s[vertpos(i)+(2*C+2 if j else 1)] == ' '])
  V = g.vs # the graph's vertex sequence
  O = ''
  V(_degree=1)['n'] = ' ' # All leaves are named space
  W = V(_degree_gt=2) # All warp points...
  W['n'] = list(string.ascii_letters[:len(W)]) # ...are named successive letters
  while g.es: # while any edges remain...
    v = V(_degree=1)[0] # find a leaf
    O += '|'+v['n'] # start a new 'block'
    while v.degree():
      w = v.neighbors()[0] # pick a neighbor
      g -= (v, w) # delete that edge
      v = w
      if v['n']: # If it's a dead end or warp point...
        O += ' '+v['n'] # ...write out the new neighbor
  print O+'|'

Anda dapat melihat hasil untuk lima labirin contoh . (Sayangnya, igraphtidak tersedia di Try It Online; hasil ini diekspor dari SageMathCloud .)

Nick Matteo
sumber
4

Haskell - 481 405 387 byte

import Data.List
s&t=elemIndices s t
l=last
c!(x:y:z)=l$(y:c)!(x:z):do{[x:p,q]<-mapM([id,reverse]<*>)[[x],[y]];x&[l q];[[]!((q++p):c++z)]}
c![x]=x:[]!c
c!z=z
main=interact(\m->let{g=' '&m;
u=(\\[k|k<-g,length(v>>=(k&))==2])<$>[]!v;
v=[[x,y]|x<-g,y<-g,elem(y-x-1)[0,head$'\n'&m]];
}in '|':(u>>=(++"|").init.(>>=(:" ").toEnum.((+)<*>(+65).(*32).(`div`26)).l.(-1:).(&(nub$u>>=init.tail)))))

Ini membuat daftar ruang yang ada di labirin, diberi nomor berdasarkan indeks dalam string, dan menggunakannya untuk menemukan semua pasangan ruang yang berdekatan. Kemudian menjahit pasangan menjadi urutan poin yang lebih panjang berdasarkan pencocokan elemen pertama / terakhir dan menghilangkan koridor, sehingga setiap urutan adalah satu ruangan di labirin 1D. Urutan kemudian diterjemahkan ke dalam string dengan mengganti titik pada interior setidaknya satu ruangan (titik lungsin) menjadi huruf yang sesuai dan sisanya menjadi spasi.

Labirin 2D dibaca dari STDIN dan labirin 1D dicetak ke STDOUT.

Sunting: Dikurangi oleh 62 byte mengatur ulang banyak hal dan memodifikasi algoritma sedikit, dan 14 lainnya dengan mengganti chrdengantoEnum disarankan oleh Laikoni.

Sunting 2: Menyimpan 13 byte lebih banyak dengan menyederhanakan logikanya (!), 3 dengan menggunakan daftar pola kecocokan gula, dan 2 dengan menggunakan >>=untuk menggabungkan u.

faubi
sumber
Saya pikir Anda tidak perlu baris baru dan spasi sebelum penjaga pola, misalnya o(x:p)q|x==last q=[q++p]|1>0=[]harus bekerja juga.
Laikoni
Juga toEnumharus bekerja, bukan chr, maka import Data.Charbisa dijatuhkan.
Laikoni
Dan terakhir ketika tantangan meminta program atau fungsi, Anda dapat menggantinya main=interact(\m->...)dengan adil f m=.... Ini seharusnya cukup untuk mengalahkan jawaban python, jika itu berarti bagi Anda.
Laikoni