Desain Bahasa: Pencocokan Pola 2-D

49

Ini adalah Tantangan Fortnightly # 6 . Tema: Desain Bahasa

Ada ruang obrolan untuk tantangan ini. Datang dan bergabunglah dengan kami jika Anda ingin mendiskusikan ide!

Dan sekarang untuk sesuatu yang sama sekali berbeda ...

Dua minggu ini, kami ingin bereksperimen dengan jenis tantangan baru. Dalam tantangan ini, Anda akan mendesain bahasa! Pencocokan pola adalah masalah yang sangat umum dalam pemrograman, dan seringkali sangat berguna untuk kode golf. Ekspresi reguler, misalnya, dapat digunakan untuk mendeteksi pola dalam satu baris teks. Namun, tidak ada metode yang ditetapkan untuk menggambarkan dan mendeteksi pola dua dimensi.

Tantangan

Anda merancang bahasa yang cocok dengan pola, yang memungkinkan deskripsi pola dua dimensi dalam blok teks. The modus operasi dari bahasa Anda akan mirip dengan ekspresi reguler (meskipun bahasa Anda tidak harus memiliki kesamaan apa pun dengan regex lain):

  • Sebagai input, Anda akan menerima blok teks persegi panjang. Anda dapat berasumsi bahwa teks hanya terdiri dari karakter ASCII yang dapat dicetak (0x20 hingga 0x7E) serta baris baru (0x0A) untuk memisahkan baris kisi.
  • Jika kecocokan, sesuai dengan deskripsi pola, dapat ditemukan sebagai bagian dari blok teks ini, kecocokan ini harus dikembalikan atau dicetak. Jika pertandingan bisa non-persegi panjang, itu harus diisi ke area persegi panjang dengan beberapa karakter yang dipesan. Jika ada beberapa pertandingan yang valid, Anda dapat memutuskan bagaimana pertandingan yang dikembalikan dipilih (terbesar, terkecil, pertama, dll.).

Untuk beberapa aplikasi mungkin berguna jika implementasi Anda dapat mengembalikan posisi pertandingan, bukan pertandingan itu sendiri, tetapi ini bukan persyaratan.

Paling tidak, bahasa Anda harus dapat mencocokkan suatu pola sebagai subkawasan input persegi yang berdekatan.

Jawaban Anda harus berisi:

  • Sebuah deskripsi bahasa.
  • Sebuah implementasi bekerja . Ini bisa berupa program, atau serangkaian fungsi / kelas dalam bahasa pilihan Anda.
  • Anda harus menunjukkan bahasa Anda dengan menunjukkan bagaimana bahasa itu dapat digunakan untuk menyelesaikan contoh yang diberikan di bawah ini . Bahasa Anda tidak harus bisa mencocokkan semuanya, tetapi Anda harus dapat mencocokkan setidaknya 8 dari semuanya. Jika bahasa Anda dapat melakukan sesuatu yang tidak kami pikirkan, jangan ragu untuk memasukkannya juga.

Jika jawaban Anda didasarkan pada ide-ide yang ada, itu baik-baik saja, tapi tolong beri kredit di mana itu jatuh tempo.

Ekstensi

Di atas menggambarkan minimum yang harus dipenuhi oleh kiriman yang valid. Namun, beberapa generalisasi dapat membuat bahasa pencocokan pola seperti itu menjadi lebih bermanfaat, termasuk tetapi tidak terbatas pada:

  • Mampu menjangkar pola ke satu atau lebih tepi, sehingga orang dapat memeriksa apakah seluruh wilayah input memiliki pola tertentu.
  • Memproduksi semua pertandingan, bukan hanya satu. Anda dapat memilih semantik pertandingan yang tumpang tindih.
  • Mengambil teks non-persegi panjang sebagai input.
  • Mengizinkan pola menentukan kecocokan non-persegi panjang. Dalam kasus seperti itu, output harus diisi dengan sebuah persegi panjang dengan beberapa karakter khusus.
  • Mengizinkan pola untuk menentukan kecocokan dengan lubang.
  • Mengizinkan pertandingan yang tidak berdekatan, seperti dua karakter yang muncul dengan offset tertentu.
  • Spesifikasi rotasi dan refleksi yang mudah.
  • Opsional memperlakukan input secara siklis sebagai silinder atau torus, sehingga tepi yang berlawanan dianggap berdekatan.

Mencetak gol

Tujuan utama dari tantangan ini adalah untuk menghasilkan bahasa pencocokan pola 2D yang efektif yang berpotensi digunakan di masa depan. Dengan demikian, sistem penilaian seperti "panjang gabungan terpendek untuk menyelesaikan contoh" akan mengarah pada pengkodean keras fungsionalitas tertentu dengan mengorbankan kegunaan umum. Karenanya, kami telah memutuskan bahwa tantangan ini paling baik dijalankan sebagai kontes popularitas. Pengajuan dengan suara terbanyak menang. Meskipun kami tidak dapat memaksakan cara orang memberikan suara, berikut adalah beberapa pedoman untuk apa yang seharusnya dicari oleh pemilih:

  • Ekspresi. Bisakah bahasa memecahkan berbagai masalah, bahkan di luar contoh yang disajikan dalam pertanyaan ini? Apakah itu mendukung salah satu ekstensi yang disarankan?
  • Keterbacaan. Seberapa intuitif notasi (setidaknya untuk orang yang tahu sintaks dasar)?
  • Golfitude. Ini masih CodeGolf.SE. Untuk keperluan situs ini, tentu akan menyenangkan jika memiliki bahasa yang cocok yang membutuhkan sedikit kode untuk menggambarkan suatu pola.

Contoh Masalah

Cuplikan Stack berikut menunjukkan 16 contoh masalah yang dapat ditangani oleh bahasa pencocokan pola 2-D. Setiap contoh berisi deskripsi masalah singkat dan kemudian biasanya diikuti oleh satu contoh input di mana kecocokan dapat ditemukan dan satu contoh di mana tidak ada kecocokan dapat ditemukan (jika berlaku).

Seperti yang dinyatakan di atas, bahasa Anda hanya perlu dapat menyelesaikan 8 masalah ini. Segala sesuatu di atas itu adalah opsional, tetapi tentu saja harus meningkatkan jumlah suara yang Anda dapatkan.

Tampilkan cuplikan kode

(Tidak, Anda tidak perlu membaca kode HTML itu. Tekan tombol "Run snippet" untuk membuatnya ditampilkan dengan baik oleh browser Anda, yang kemudian dapat Anda lihat juga layar penuh.)

popularity-contest string grid language-design PhiNotPi
sumber
Apakah ada batasan waktu umum untuk masalah ini? Saya sangat tertarik untuk menyelesaikan ini tetapi saya sangat sibuk, bisa dengan mudah saya lakukan 2 minggu.
Devon Parsons
7
@DevonParsons Tidak ada batas waktu entri.
PhiNotPi
Terlihat menarik, terutama karena Anda membuat tag baru untuk ini. Saya pikir harus ada poin bonus untuk membuat bahasa 2-D untuk itu.
mbomb007
1
@ mbomb007 Ada poin bonus untuk membuat bahasa 2-D. Saya cukup yakin itu akan mendapatkan jumlah upvotes yang layak. ;)
Martin Ender
@ MartinBüttner Saya bahkan tidak tahu cara membuat bahasa. Mungkinkah itu sesuatu yang (sederhana?) Seperti membuat program Python yang mengambil file kode bahasa baru Anda (dan menafsirkan / mengeksekusi berdasarkan sintaks yang Anda tetapkan) dan menghasilkan output?
mbomb007

Jawaban:

32

SnakeEx

Memecahkan masalah 15/16 sejauh ini!

Penerjemah Online ! - Spesifikasi Bahasa Lengkap - Sumber Javascript

tangkapan layar juru bahasa

Gagasan di balik bahasa ini adalah untuk mendefinisikan 'ular' yang bergerak di sekitar karakter memeriksa teks menggunakan sintaks seperti regex.

Sebuah program di SnakeEx terdiri dari daftar definisi untuk ular menggunakan urutan perintah yang berbeda. Ular dapat memunculkan ular lain menggunakan definisi ini, yang merupakan tempat SnakeEx mendapatkan sebagian besar kekuatannya - kita dapat mencocokkan struktur percabangan dan bahkan melakukan rekursi (lihat contoh Pencocokan Paren).

Setiap program pada dasarnya akan terlihat seperti seperangkat regex, tetapi dengan penambahan perintah arah dari bentuk <dir>yang mengubah arah ular, dan memanggil perintah dari bentuk {label<dir>params}yang menelurkan lebih banyak ular.

Untuk titik masuk, juru bahasa menelurkan satu ular menggunakan definisi pertama, bergerak ke kanan.

Ini tidak terlalu ringkas, tetapi sangat kuat dan (saya pikir) cukup mudah dibaca.

Pembaruan

  • Berubah! untuk tidak logis dan ~ untuk tidak menandai pertandingan
  • Ditambahkan <!>untuk menyelesaikan colinear
  • Salib Pencocokan yang Diselesaikan
  • Papan catur dipecahkan dengan cara yang tidak begitu mengerikan
  • Menambahkan sintaks penutupan terbatas %{min,max}
  • Menambahkan contoh rekursi

Solusi

15 diselesaikan, 1 sedang berlangsung

Anda dapat dengan mudah mencoba program-program ini menggunakan Penerjemah Online yang ditautkan di atas!

Masalah 1 - Menemukan Papan Catur

m:{v<R>2}{h<>1}
v:{c<L>A1}+
h:{c<R>A2}+
c:_?(#_)+#?

Untuk pengantar terperinci, mulai dari Masalah 3.

Masalah 2 - Memverifikasi Papan Catur

m:{v<R>2}{h<>1}
v:${c<L>A1}+$
h:${c<R>A2}+$
c:$_?(#_)+#?$

Mengakhiri ular yang sesuai dengan simbol di luar batas $adalah salah satu cara untuk membuat program mencocokkan hanya seluruh input.

Masalah 3 - Mendeteksi Rectangle of Digit

m:{c<R>A1}%{2,}
c:[0-9]%{2,}

The mular gerakan yang benar, pemijahan minimal 2 ular ( %{2,}adalah penutupan yang berarti "2 hingga tak terbatas") menggunakan definisi c ( c) dan bergerak kanan ( <R>), atau lebih tepatnya bawah dalam hal ini, karena semua arah yang relatif terhadap ular saat ini. The Aparam adalah gula yang hanya menetapkan bahwa ular pemijahan harus bergerak setelah panggilan. The 1parameter adalah bagaimana kita membatasi pertandingan persegi panjang - jumlah parameter menempatkan ular di "kelompok". Kecocokan tidak dihitung kecuali semua ular dalam kelompok yang sama menempuh jarak yang sama persis.

Masalah 4 - Menemukan Kata dalam Pencarian Kata

m:<*>GOLF

Perintah arah <*>menentukan bahwa ular harus berputar ke arah diagonal atau ortogonal. Kemudian, ia mencari regex sederhana.

Masalah 5 - Mendeteksi Input Kuadrat

m:{v<R>1}{h<>1}
v:${c<L>A1}+$
h:${c<R>A1}+$
c:$.+$

Kuncinya di sini adalah karakter khusus $, yang hanya cocok jika ular itu di luar batas. Kami menelurkan ular horizontal dan vertikal; masing-masing memunculkan lebih banyak ular saat berjalan di sepanjang tepi, dan semua itu berada dalam kelompok yang sama dan harus memiliki panjang yang sama.

Masalah 6 - Temukan Glider dalam Game of Life

m:<+>[({l1<R>A}{l2<R>A}{l3<R>})({l1<L>A}{l2<L>A}{l3<L>})]
l1:##\.
l2:[(#\.)(\.#)]#
l3:#\.\.

mdimulai di salah satu dari empat arah ortogonal ( <+>), mencapai rotasi. Kemudian, tampak kiri atau kanan untuk tiga baris secara berurutan, mencapai refleksi.

(Perhatikan bahwa saya telah mengganti spasi dengan titik hanya karena area teks HTML yang digunakan dalam penerjemah saya tampaknya melakukan hal-hal bodoh jika mereka memiliki beberapa spasi berturut-turut)

Masalah 7 - Match Nether Portal

m:{e<R>A1}{d<R>A1}%{2,22}{e<R>1}
e:~.X%{3,22}~.
d:X\.+X

The mbergerak ular yang tepat, pemijahan ular untuk memeriksa tepi kiri, 2-22 ular untuk memeriksa kolom tengah, dan akhirnya ular untuk memeriksa tepi kanan. The ~Operator menunjukkan bahwa apa pun yang berikut harus diperiksa tetapi tidak harus ditandai sebagai bagian dari solusi.

Penutupan terikat sekarang memungkinkan kita untuk menyelesaikan masalah ini dengan sepenuhnya dan benar!

Masalah 8 - Penempatan Dada Minecraft

m:~{s<>}~!{d<+>}\.
s:<+>.<BR>([$\.]<R>)%{3}
d:.<+>CC

Di sini kami menggunakan logika not ( !), yang cocok jika dan hanya jika token berikut tidak cocok dengan apa pun. Deklarasi dmendeteksi dada ganda di arah tertentu, jadi !{d<+>}pastikan tidak ada dada ganda di arah ortogonal mana pun. sbergerak dalam berlian kecil di sekitar alun-alun saat ini, memverifikasi setidaknya 3 dari ruang tersebut kosong atau tidak terpasang. Trailing \.akhirnya cocok dengan alun-alun, dengan asumsi semua kondisi sebelumnya berhasil.

Masalah 9 - Alignment Horisontal dan Vertikal

m:<R>?#~.*#

Ular mberbelok ke kanan ( <R>?) sebelum mencocokkan urutannya. .adalah wildcard, seperti di regex.

Soal 10 - Poin Colinear

m:<!>#~.*#~.*#

Dengan penambahan <!>arah, kita bisa menyelesaikan ini sekarang! <!>seperti <+>tetapi bukannya bercabang di empat arah, itu bercabang di setiap arah yang memungkinkan.

Masalah 12 - Hindari huruf Q

m:{h<R>A}%{4}
h:[^Qq]%{4}

Hanya memunculkan 4 ular yang masing-masing mencari empat karakter yang bukan huruf Q.

Masalah 13 - Penambangan Intan

m:{tl<RB>1}{tr<RF>1}
tl:X/*{bl<L>1}X
tr:X\\*{br<R>1}X
bl:X\\*X
br:X/*X

Yang ini cukup rapi. mmemunculkan dua ular, satu pergi ke kanan belakang, dan satu ke kanan ke depan. Masing-masing mengikuti garis miring ke X, kemudian memunculkan ular lain pada sudut kanan ke arah saat ini, yang mengikuti garis miring ke X.

Masalah 14 - Mencocokkan Salib

m:{a<R>A}+{b<R>A}+{a<R>A}+
a:{e<>P1}{c<>P2}{e<>P3}
b:{c<>P1}{c<>P2}{c<>P3}
e:\.+
c:#+

Inilah pertama kalinya saya menggunakan Pparameter iggyback. Biasanya ular itu independen, tetapi jika Anda melakukan panggilan dengan parameter ini, ular panggilan akan dipindahkan dengan callee. Jadi e2dapat memeriksa urutan '.', Lalu urutan '#', lalu urutan lain dari '.', Dan meminta mereka semua menjadi panggilan terpisah sehingga kita dapat mengelompokkannya dengan '1,' 2 ', dan' 3 ' , memaksa mereka untuk mencocokkan.

Masalah 15 - Cocokkan Kata di Papan Perundingan

m{I}:<*>p<*>a<*>n<*>a<*>m<*>a

Sederhana, jika bertele-tele. Iparameter menentukan ketidakpekaan huruf (kita dapat menentukan parameter pada definisi serta panggilan). Ular itu berputar ke segala arah, cocok dengan karakternya, berputar lagi, dan sebagainya.

m{EI}:<*>p<*>a<*>n<*>a<*>m<*>a

Ini adalah versi tanpa-penggunaan-karakter. The Eparameter Xclusive melarang ular dari pencocokan karakter yang telah ditandai, seperti jalan lendir feersum ini.

Masalah 16 - Bungkus Tepian

m{W}:{c<R>WA}%{3}
c:###

The Wparameter memungkinkan ular untuk membungkus ketika berjalan out-of-batas. Kami juga memiliki Hdan Vhanya mengizinkan pembungkus horizontal atau vertikal.

Extra - Maze Solver

m{E}:$(<P>\.)+$

Memecahkan labirin ASCII di mana lantai yang bisa dilewati adalah titik. The <P>berarti arah depan, kiri, atau kanan (gula untuk [<F><L><R>]).

Pencocokan Ekstra - Paren

m:\(~{r<>P}\)
r:[^\(\)]*(\({r<>P}\))?[^\(\)]*

Belum tahu bagaimana melakukan Prelude, tapi inilah langkah pertama! Di sini saya menggunakan rular secara rekursif untuk mencocokkan tanda kurung yang sesuai dengan memeriksa bahwa tidak ada tanda kurung yang tidak cocok di antara mereka.

Ekstra - Topologi ASCII: Menghitung Loop

BMac
sumber
Apakah Anda mempertimbangkan untuk menambahkan sintaks sehingga bahasa ini dapat melakukan penggantian daripada hanya mencocokkan? Saya ingin menggunakan beberapa solusi untuk tantangan ini untuk menulis entri untuk codegolf.stackexchange.com/questions/51231/… tetapi tidak ada solusi tunggal di sini yang menemukan dan mengganti. (Saya tahu jawaban saya tidak akan valid karena aturan waktu spesifikasi bahasa)
Sparr
@Parr. Bukan ide yang buruk, tentu akan lebih berguna untuk golf kode. Tidak yakin kapan saya akan punya waktu untuk melakukannya sendiri, tetapi saya akan mengingatnya.
BMac
3
secara terpisah: sintaks untuk perubahan arah membingungkan. karena ular itu berkembang setelah mencocokkan satu karakter, saya sepertinya harus membuat arah saya berubah satu karakter terlebih dahulu di tempat yang masuk akal bagi saya. contoh: string "ABC \ nDEF" dan saya ingin mencocokkan potongan tetris berbentuk L yang didefinisikan oleh ABCF, saya ingin menulis ular saya sebagai "m: ABC <R> F" tetapi saya harus menulis "m: AB <R> CF "sebagai gantinya. Saya mengerti bahwa ini cocok dengan spek, tetapi saya merasa sangat berlawanan dengan intuisi.
Sparr
Saya punya solusi parsial untuk sintaks prelude. Satu-satunya masalah adalah bahwa saya tidak dapat membuatnya tidak cocok jika tidak cocok dengan seluruh input: m:{a<>} a:[({n<R>A})({n<R>A}*{l<R>A}{a<>P}{r<R>A})]*{n<R>A}* l:$[^\(\)]*\([^\(\)]*$ r:$[^\(\)]*\)[^\(\)]*$ n:$[^\(\)]+$
TheNumberOne
21

Slip, Python 3.4 ( Github wiki , juru bahasa online )

Seperti pengajuan feersum ini juga didasarkan pada melintasi grid, tetapi seperti pengajuan CarpetPython ini didasarkan pada regex. Entah bagaimana sepertinya aku berhasil mengambil jalan tengah.

Ada cukup banyak fitur yang tidak diterapkan yang ingin saya tambahkan, jadi di mana relevan saya mencatat apa yang ingin saya lakukan ketika saya punya waktu.

Pembaruan

(Lihat halaman Github untuk berita detail)

  • 5 Apr 2015 : Slip sekarang memiliki juru bahasa online ! Ini masih dalam tahap awal, jadi mungkin ada beberapa bug.

  • 5 Apr 2015 : Pembaruan efisiensi! Sekarang apakah portal input besar jauh lebih cepat (2s). Juga ada sejumlah perubahan sintaks, jadi pastikan untuk memeriksa wiki. Penomoran grup juga diperbaiki.

Slip memiliki pointer pertandingan yang dimulai pada kotak tertentu dan pada awalnya menghadap ke kanan. Ketika char dicocokkan, pointer bergerak maju ke arah saat ini (meskipun implementasi tidak melakukan hal-hal tepat dalam urutan itu).

Arah pertandingan pointer dapat diatur ke arah tertentu dengan ^<digit>, di mana ^0, ^1, ^2, ..., ^7mengatur pointer ke N, NE, E, ..., NW masing-masing (akan searah jarum jam).

Cara pintas berikut juga tersedia:

  • ^* memeriksa semua 8 arah orthogonal atau diagonal,
  • ^+ memeriksa semua 4 arah ortogonal.

(Rencana di masa depan: Izinkan pengaturan arah yang sewenang-wenang, misalnya (1, 2)untuk langkah knight)

Misalnya ( Masalah 4 - Menemukan kata dalam pencarian kata ),

^*GOLF

mencoba semua 8 arah orthogonal atau diagonal, mencari kata "GOLF". Secara default, Slip mencoba semua kotak awal yang mungkin dan mengembalikan satu hasil dari masing-masing, memfilter duplikat, jadi seperti grid

GOLF
O
L
FLOG

mengembalikan hanya baris atas dan baris bawah sebagai pasangan (karena baris atas dan kolom kiri "GOLF" dimulai dari kotak yang sama). Untuk mendapatkan semua kecocokan, omode kecocokan yang tumpang tindih dapat digunakan.

Demikian pula ( Masalah 15 - Cocokkan kata di papan Boggle ),

p^*a^*n^*a^*m^*a

cocok panamadengan mencoba arah yang berbeda setiap kali. Gunakan ibendera untuk ketidaksensitifan kasus. Slip menggunakan ulang karakter secara default, tetapi ini dapat diaktifkan dengan rbendera tanpa-ulangi.

(Rencana mendatang: pengubah mode pencarian yang secara otomatis memeriksa set arah setelah setiap gerakan sehingga pengulangan ^*tidak perlu)

Arah match pointer juga dapat diputar 90 derajat ke kiri atau ke kanan dengan <atau >masing - masing. Misalnya,

 `#`#< `#<  <`#<`#

mencari polanya

  #
## 
 ##

dengan melihat dalam urutan sebagai berikut:

765
894
123

Ini memungkinkan kami untuk menyelesaikan Masalah 6 - Menemukan glider bersama

^+(`#`# >`# > `#>`#> |`#`# <`# < `#<`#< | `#`#> `#>  >`#>`#| `#`#< `#<  <`#<`#)

di mana bagian 1 dan 2 mengkodekan bentuk glider, dan bagian 3 dan 4 mengkodekan rekan-rekan tercermin mereka.

Perhatikan bahwa Slip menggunakan backtick `untuk melarikan diri. Ini karena Slip memiliki bentuk gerakan lain yang memberikan bahasa namanya - perintah slip. /tergelincir pointer pertandingan ortogonal ke kiri, sedangkan \tergelincir pointer pertandingan ortogonal ke kanan.

Sebagai contoh,

abc   ghi
   def

dapat dicocokkan dengan abc\def/ghi.

Meskipun tidak terlalu berguna dengan sendirinya, tergelincir menjadi lebih penting ketika dikombinasikan dengan (?| <regex> )kelompok stasioner, yang bertindak seperti mencari yang cocok. Regex di dalam dicocokkan, kemudian pada akhir itu posisi dan arah pointer pertandingan diatur ulang ke keadaan sebelum kelompok stasioner.

Sebagai contoh,

abc
def
ghi

dapat dicocokkan dengan (?|abc)\(?|def)\(?|ghi).

Demikian pula, Masalah 12 - Hindari huruf Q dapat diselesaikan dengan

%(\(?|[^qQ]{4})){4}

di mana %ada perintah no-slip untuk menghentikan yang pertama \dari pengaktifan.

Slip juga memiliki penegasan panjang (?_(<group num>) <regex> ), yang hanya cocok dengan regex di dalamnya jika panjang kecocokannya sama dengan panjang dari jumlah grup yang diberikan.

Misalnya, Masalah 13 - Penambangan berlian dapat dengan mudah diselesaikan

^1X(`/*)X>(?_(1)`\*)X>(?_(1)`/*)X>(?_(1)`\*)

yang mencoba untuk mencocokkan sisi kiri atas berlian terlebih dahulu, kemudian menegaskan bahwa ketiga sisi lainnya memiliki panjang yang sama.

(Jalankan dengan vflag untuk output verbose)

Match found in rectangle: (8, 0), (12, 4)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 0), (6, 6)
   X
  / \
 /   \
X     X
 \   /
  \ /
   X

Match found in rectangle: (2, 2), (4, 4)
 X
X X
 X

Match found in rectangle: (10, 2), (14, 6)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (5, 3), (9, 7)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 6), (2, 8)
 X
X X
 X

Alternatif pegolf adalah

^1X(`/*)(X>(?_(1)`\*)X>(?_(1)`/*)){2}

yang cocok dengan sisi pertama dua kali.

Banyak masalah lain dapat diselesaikan dengan menggunakan slip, kelompok stasioner dan panjang menegaskan:

Masalah 14 - Mencocokkan salib:

(?|(`.+)(`#+)(`.+))(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))*(\(?|(?_(2)`#+)(?_(3)`#+)(?_(4)`#+)))+(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))+

Setelah Anda menangkap lebar .s dan #s di baris pertama, itu hanya tergelincir ke bawah.

Keluaran:

Match found in rectangle: (0, 1), (5, 5)
.###..
######
######
.###..
.###..

Match found in rectangle: (4, 6), (6, 8)
.#.
###
.#.

Yang ini mungkin bisa golf dengan sedikit rekursi, setelah saya menyelesaikan beberapa bug.

Masalah 3 - Mendeteksi persegi panjang angka:

(?|`d`d+)(\(?|(?_(1)`d+)))+

Cocokkan satu baris teratas dari dua digit atau lebih, lalu pastikan setiap baris di bawah ini memiliki panjang yang sama. `dadalah kelas karakter standar yang setara dengan [0-9].

Perhatikan bahwa ini menemukan semua kecocokan .

Masalah 7 - Mencocokkan portal bawah:

(?|.X{2,22}.)\((?|(?_(1)X`.+X))\){3,22}(?_(1).X+.)

yang menghasilkan, untuk contoh teratas di utas asli :

Match found in rectangle: (2, 1), (5, 5)
XXXX
X..X
X..X
X..X
XXXX

Match found in rectangle: (9, 1), (14, 5)
.XXXX.
X....X
X....X
X....X
.XXXX.

Match found in rectangle: (13, 4), (17, 8)
.XXXX
X...X
X...X
X...X
.XXX.

Akhirnya, beberapa fitur Slip lainnya termasuk:

  • $0, $1, $2, ..., $7jangkar tepi utara, sudut timur laut, tepi timur, dll. $+jangkar setiap tepi dan $*jangkar setiap sudut.
  • $diikuti oleh karakter huruf kecil menetapkan jangkar di posisi saat ini, yang nantinya dapat dicocokkan dengan $diikuti oleh karakter huruf besar yang sesuai, misalnya $adan $A.
  • # matikan flag no-move, yang menghentikan pointer pertandingan untuk bergerak maju setelah pertandingan berikutnya.
  • ,cocok dengan karakter suka ., tetapi tidak menambahkannya ke output, memungkinkan untuk pertandingan non-berdekatan sambil dapat dikenali oleh (?_()).

... dan banyak lagi. Ada terlalu banyak untuk dicantumkan di halaman ini.

Masalah lainnya

Masalah 1 - Menemukan papan catur:

(?|`#?(`_`#)+`_?)(?_(1)(?|...+))(\(?_(1)(?|`#?(`_`#)+`_?$a)))+<(?|`#?(`_`#)+`_?)(?_(9)(?|...+))(\(?_(9)(?|`#?(`_`#)+`_?)))+$A

Dua masalah papan catur jelas bukan keahlian Slip. Kami mencocokkan baris atas kemudian memastikan paling tidak panjangnya 3 dan berganti-ganti di antara , #dan _kemudian terpeleset dan cocok dengan baris berikutnya. Pada akhirnya, $ajangkar harus berada di kanan bawah papan catur.

Kami kemudian belok kiri dan ulangi untuk kolom, memastikan kami cocok $Adi akhir.

Masalah 2 - Memverifikasi papan catur:

$7%(\(?|`_?(`#`_)*`#?$2))+$5<%(\(?|`_?(`#`_)*`#?$0))+$3

Seperti masalah sebelumnya, kami memeriksa bahwa setiap baris sudah benar, lalu putar ke kiri dan lakukan hal yang sama untuk kolom. Jangkar digunakan untuk memastikan hanya seluruh papan yang cocok.

Masalah 9 - Penyelarasan horizontal dan vertikal:

>?`#,*`#

Kami menerapkan opsional? kuantifier ke >perintah rotate sehingga kita dapat mencocokkan ke kanan atau ke bawah. Kami menemukan semua 5 dalam contoh dengan omode tumpang tindih, tetapi hanya 4 tanpa itu sejak #.,##dan #.,#mulai dari posisi yang sama.

Soal 10 - Titik kolinear

^+`#(?|(,*)<(,*))(((?_(2),*)<(?_(3),*),>)+#`#){2}

Cocokkan #beberapa karakter horisontal kemudian dan beberapa karakter vertikal, lalu ulangi sampai yang kedua #, dan ulangi sampai yang ketiga #.

Masalah 5 - Mendeteksi input persegi:

$7.(.*)>(?_(1).*)$3>((?|.*)\)*

Jangkar sudut kiri atas, dan periksa bahwa tepi atas sama panjang dengan tepi kanan, sebelum menjangkar sudut kanan bawah. Jika input melewati ini, maka kita naik mundur untuk mencocokkan seluruh input.

Masalah 8 - Penempatan dada Minecraft:

`.^+(($^|(?|`.))>){3}($^|`.|C<(($^|(?|`.))>){3})

Jalankan dengan pbendera untuk mendapatkan posisi setiap pertandingan. $^adalah jangkar yang cocok jika langkah selanjutnya akan membuat pointer pertandingan keluar dari batas.

Pertama kita mencocokkan ., kemudian memeriksa bahwa kita dikelilingi oleh tiga .s / batas, maka memastikan bahwa persegi sekitarnya keempat juga ./ batas atau dada tunggal (dengan memeriksa nya kotak sekitarnya).

Masalah 11 - Verifikasi Prelude syntax :

$7>%(/(?|[^()]+$4)(?1)?|/(?|[^()]*`([^()]*$4)(?1)?/(?|[^()]*`)[^()]*$4)(?1)?)$1

Butuh beberapa percobaan, tetapi saya pikir yang ini benar. Di sini kita menggunakan rekursi, yang memiliki sintaksis yang sama dengan PCRE.

Pendekatan ini mensyaratkan bahwa input berbentuk persegi panjang, tetapi setelah saya menyelesaikan pencocokan non-persegi panjang, asumsi tersebut tidak diperlukan.

Inilah pendekatan yang sama, bermain golf dengan lebih banyak rekursi:

$7>%((/(?|([^()]*)$4)|/(?|(?4)`((?3))(?1)?/(?|(?4)`)(?3)))*)$1

Masalah 16 - Bungkus di sekitar tepi:

%(\(?|`#{3})){3}

(Catatan: Pembungkus belum didorong ke penerjemah online)

Ini membutuhkan bendera pembungkus w. Secara teknis inisial %untuk tidak ada slip tidak perlu, tetapi kemudian pertandingan akan dihitung sebagai mulai dari satu kotak lebih tinggi.

Masalah EX 1 - Pemecah labirin:

S(^+`.)*^+E

Masalah dari komentar BMac dalam obrolan . Gunakan rbendera tanpa mode ulang sehingga pointer pertandingan tidak macet bolak-balik.

Masalah EX 2 - Pengenalan wajah :

(?|O(,*),(?_(2),*)O)(?_(2)(\(?|,))*)\(?|,(?_(2),*)O)(?_(2)(\(?|,))*)\`\(?_(2)`_*)`_(?_(2)`_*)`/

Perhatikan bahwa saya hanya mencocokkan wajah, tidak melakukan pembersihan. Perhatikan bahwa pertanyaan berisi simbol euro, yang perlu diganti oleh beberapa ASCII yang dapat dicetak agar berfungsi.

Sp3000
sumber
Pola hash itu adalah peluncur Conway
Heimdall
17

PMA / Siput (C ++)

Saya membayangkan bahasa sebagai siput bergerak di sekitar kotak dan menjalankan perintah. Siput meninggalkan jejak lendir pada setiap kotak tempat mereka bergerak, yang secara default menyebabkan kotak menjadi tidak tertandingi. Kecocokan berhasil jika akhir daftar perintah tercapai.

Ada cukup banyak operator sekarang sehingga kita akan memerlukan daftar prioritas untuk melacak mereka. Operasi diselesaikan dengan urutan sebagai berikut:

  1. Di dalam kelompok ( ) [ ]
  2. Membagi karakter bergantian |
  3. Mengevaluasi semua yang ada di sebelah kiri `sebagai grup
  4. Pengukur [m],[n]dann
  5. Penegasan = !
  6. Rangkaian

Penerjemah ditulis dalam bahasa C ++. Kode sumber buruk dapat ditemukan di sini .

Masalah 4: Pencarian Kata

Program

z\G\O\L\F

cukup untuk mendapatkan nilai truey atau falsey untuk apakah kata itu ditemukan. z(salah satu dari 15 perintah arah absolut atau relatif) cocok dengan arah oktilinear apa pun. Beberapa perintah arah berurutan diurutkan secara bersamaan. Misalnya ruldyakan hampir setara dengan z, karena itu adalah perintah untuk kanan, atas, kiri, bawah, dan setiap arah diagonal. Namun, arah akan diuji dalam urutan yang berbeda. Karakter pertama yang cocok selalu karakter siput dimulai, terlepas dari arah. \<character> cocok dengan satu karakter literal.

Strategi default adalah mencoba pola di setiap kotak di kotak pembatas dari input kiri-dibenarkan, dan output jumlah kecocokan. Jika nilai boolean 1atau 0diperlukan, program berikut dapat digunakan:

?
z\G\O\L\F

Jika setidaknya ada satu baris baru di file sumber, baris pertama diperlakukan sebagai opsi untuk konversi awal input ke bentuk persegi panjang. The ?pilihan mencetak 0 atau 1 tergantung pada apakah ada di mana saja pertandingan.

Masalah 15: Kericuhan

Setelah menerapkan pergantian, sekarang mungkin untuk menyelesaikan Boggle. Akan lebih baik menggunakan pencocokan case-insensitive untuk yang satu ini, tetapi menerapkan itu bukan prioritas tertinggi saya.

\p|\P)z(\a|\A)z{\n|\N)z{\a|\A}z(\m|\M)z(\a|\A

|bekerja persis sama dengan regex 1 dimensi. Ada dua pasangan pembatas yang cocok untuk pengelompokan, yaitu ()dan {}. Braket penutup akan menutup semua grup terbuka dari tipe berlawanan yang berdiri di antara itu dan yang terdekat dari tipe yang sama. Misalnya, mengikuti {({{), hanya grup paling kiri tetap terbuka. Seperti yang Anda lihat, simbol pengelompokan yang tak tertandingi di tepi secara implisit ditutup. Ada perintah pengelompokan lain `yang tidak akan saya bahas sekarang.

Masalah 8: Peti Minecraft

Program ini mencetak jumlah penempatan dada yang valid. Ini adalah yang pertama saya benar-benar harus bermain golf, dan mengurangi hitungan byte saya (17) beberapa kali.

\.!(o\C)2o(!\Cw)3
  • \. cocok dengan titik, pada titik awal pertandingan.
  • !(o\C)2setara dengan !((o\C)2)kuantifikasi lebih diutamakan daripada asersi. <atom> <number>berarti mengulang <atom>tepat <number>waktu. omengubah siput ke arah ortogonal. !adalah pernyataan negatif. Dengan demikian bagian ini memeriksa tidak adanya dada ganda yang berdekatan.
  • o berbelok ke beberapa arah ortogonal.
    • (!\Cw)3menegaskan bahwa tidak ada Cdi depan siput, dan kemudian berbalik berlawanan arah jarum jam, 3 kali.

Masalah 2: Memverifikasi papan catur

&
\#!(o^_)|\_!(o^#

The &pilihan set output program seperti 1jika pertandingan berhasil di semua posisi, dan 0sebaliknya. ^ccocok dengan karakter yang tidak csama dengan [^c]di regex. Secara keseluruhan, program ini berarti: Mencetak 1 jika pada setiap posisi dalam persegi panjang pembatas dari input, ada salah satu #yang tidak berdekatan secara orthogonal dengan karakter yang tidak _, atau _yang tidak berdekatan secara orthogonal dengan karakter yang tidak #; jika tidak 0.

feersum
sumber
Ide jejak lendir adalah ide yang bagus untuk berurusan dengan boggle, saya mengalami beberapa masalah dengan itu
BMac
Itu adalah solusi yang bagus untuk masalah Boggle. Saya tidak bisa menyelesaikannya dengan pendekatan saya.
Logic Knight
14

Kelas Re2d, Python 2

Pembaruan: menambahkan masalah "9. Alignment".

Pendekatan saya adalah menggunakan modul Python re untuk melakukan pencarian dan pencocokan. Kelas Re2d menyiapkan teks untuk diproses, menjalankan fungsi kembali, dan memformat hasil untuk output.

Perhatikan bahwa ini bukan bahasa yang sama sekali baru - ini adalah bahasa ekspresi reguler standar yang diproyeksikan menjadi 2 dimensi dengan tanda tambahan untuk mode 2D tambahan.

Kelas memiliki penggunaan sebagai berikut:

re2dobject = Re2d(<horizontal pattern>, [<vertical pattern>], [<flags>])

Kedua pola tersebut adalah pola RE teks standar linier. Jika pola vertikal tidak disediakan, kelas akan menggunakan pola horizontal untuk mencocokkan secara vertikal juga. Bendera adalah bendera RE standar dengan beberapa ekstensi 2D.

Pengujian

1. Finding chessboards
Chessboard pattern at (2, 1, 4, 3)

print '\n1. Finding chessboards'
reob1 = Re2d('#(_#)+_?|_(#_)+#?')
found = reob1.search('~______~\n~##_#_#~\n~#_#_##~\n~##_#_#~\n~______~')
print 'Chessboard pattern at', found
assert not reob1.search('#_##\n_#_#\n__#_\n#_#_\n#_#_')

Metode pencarian menemukan pola papan catur dan mengembalikan posisi 4-tupel. Tuple memiliki x,yposisi karakter pertama dari pertandingan, dan width, heightarea cocok. Hanya satu pola yang diberikan sehingga akan digunakan untuk pencocokan horizontal dan vertikal.

2. Verifying chessboards
Is chess? True

print '\n2. Verifying chessboards'
reob2 = Re2d('^#(_#)*_?|_(#_)*#?$')
print 'Is chess?', reob2.match('_#_#_#_#\n#_#_#_#_\n_#_#_#_#')
assert not reob2.match('_#_#_#__\n__#_#_#_\n_#_#_#__')

Papan catur telah diverifikasi dengan metode pertandingan yang mengembalikan boolean. Perhatikan bahwa ^dan $mulai dan karakter akhir yang diperlukan untuk mencocokkan seluruh teks.

3. Rectangle of digits
Found: [(0, 1, 5, 3), (1, 1, 4, 3), (2, 1, 3, 3), (3, 1, 2, 3), (0, 2, 5, 2), (1, 2, 4, 2), (2, 2, 3, 2), (3, 2, 2, 2), (6, 3, 2, 2)]
Not found: None

print '\n3. Rectangle of digits'
reob3 = Re2d(r'\d\d+', flags=MULTIFIND)
print 'Found:', reob3.search('hbrewvgr\n18774gwe\n84502vgv\n19844f22\ncrfegc77')
print 'Not found:', reob3.search('uv88wn000\nvgr88vg0w\nv888wrvg7\nvvg88wv77')

Kami sekarang menggunakan MULTIFINDbendera untuk mengembalikan semua kecocokan yang mungkin untuk blok 2+ digit. Metode ini menemukan 9 kemungkinan kecocokan. Perhatikan bahwa mereka bisa tumpang tindih.

4. Word search (orthogonal only)
Words: [(0, 0, 4, 1), (0, 3, 4, 1), (3, 3, -4, -1), (3, 2, -4, -1), (3, 0, -4, -1)] [(0, 0, 1, 4), (3, 0, 1, 4), (3, 3, -1, -4), (0, 3, -1, -4)]
Words: ['SNUG', 'WOLF', 'FLOW', 'LORE', 'GUNS'] ['S\nT\nE\nW', 'G\nO\nL\nF', 'F\nL\nO\nG', 'W\nE\nT\nS']
No words: [] []

print '\n4. Word search (orthogonal only)'
words = 'GOLF|GUNS|WOLF|FLOW|LORE|WETS|STEW|FLOG|SNUG'
flags = HORFLIP | VERFLIP | MULTIFIND
reob4a, reob4b = Re2d(words, '.', flags), Re2d('.', words, flags)
matching = 'SNUG\nTEQO\nEROL\nWOLF'
nomatch = 'ABCD\nEFGH\nIJKL\nMNOP'
print 'Words:', reob4a.search(matching), reob4b.search(matching)
print 'Words:', reob4a.findall(matching), reob4b.findall(matching)
print 'No words:', reob4a.findall(nomatch), reob4b.findall(nomatch)

Tes ini menunjukkan penggunaan flipping vertikal dan horizontal. Ini memungkinkan kata-kata yang cocok yang terbalik. Kata-kata diagonal tidak didukung. The MULTIFINDBendera memungkinkan beberapa pertandingan yang tumpang tindih di semua 4 arah. Metode findall menggunakan pencarian untuk menemukan kotak yang cocok kemudian mengekstrak blok teks yang cocok. Perhatikan bagaimana pencarian menggunakan lebar dan / atau tinggi negatif untuk kecocokan dalam arah sebaliknya. Kata-kata dalam arah vertikal memiliki karakter garis baru - ini konsisten dengan konsep blok karakter 2D.

7. Calvins portals
Portals found: [(3, 1, 5, 6)]
Portal not found None

print '\n7. Calvins portals'
reob7 = Re2d(r'X\.{2,22}X|.X{2,22}.', r'X\.{3,22}X|.X{3,22}.', MULTIFIND)
yes = '....X......\n.XXXXXX.XX.\n...X...X...\n.X.X...XXX.\n...X...X.X.\n.XXX...X.X.\nX..XXXXX.X.'
no = 'XX..XXXX\nXX..X..X\nXX..X..X\n..X.X..X\n.X..X.XX'
print 'Portals found:', reob7.search(yes)
print 'Portal not found', reob7.search(no)

Pencarian ini membutuhkan pola terpisah untuk setiap dimensi karena ukuran minimum berbeda untuk masing-masing dimensi.

9. Alignment
Found: ['#.,##', '##'] ['#\n.\n,\n.\n#', '#\n,\n.\n#']
Found: [(3, 4, 5, 1), (6, 4, 2, 1)] [(7, 0, 1, 5), (3, 1, 1, 4)]
Not found: None None

print '\n9. Alignment'
reob9a = Re2d(r'#.*#', r'.', MULTIFIND)
reob9b = Re2d(r'.', r'#.*#', MULTIFIND)
matching = '.,.,.,.#.,\n,.,#,.,.,.\n.,.,.,.,.,\n,.,.,.,.,.\n.,.#.,##.,\n,.,.,.,.,.'
nomatch = '.,.#.,.,\n,.,.,.#.\n.,#,.,.,\n,.,.,.,#\n.#.,.,.,\n,.,.#.,.\n#,.,.,.,\n,.,.,#,.'
print 'Found:', reob9a.findall(matching), reob9b.findall(matching)
print 'Found:', reob9a.search(matching), reob9b.search(matching)
print 'Not found:', reob9a.search(nomatch), reob9b.search(nomatch)

Set 2 pencarian ini menemukan 2 kecocokan vertikal dan horizontal, tetapi tidak dapat menemukan #.,#string yang disematkan .

10. Collinear Points (orthogonal only)
Found: [(0, 1, 7, 1)] [(3, 1, 1, 4)]
Not found: None None

print '\n10. Collinear Points (orthogonal only)'
matching = '........\n#..#..#.\n...#....\n#.......\n...#....'
nomatch = '.#..#\n#..#.\n#....\n..#.#'
reob10h = Re2d(r'#.*#.*#', '.')
reob10v = Re2d('.', r'#.*#.*#')
flags = MULTIFIND
print 'Found:', reob10h.search(matching, flags), reob10v.search(matching, flags)
print 'Not found:', reob10h.search(nomatch, flags), reob10v.search(nomatch, flags)

Di sini kami menggunakan 2 pencarian untuk menemukan kecocokan di kedua arah. Ia dapat menemukan beberapa kecocokan ortogonal tetapi pendekatan ini tidak mendukung kecocokan diagonal.

12. Avoid qQ
Found: (2, 2, 4, 4)
Not found: None

print '\n12. Avoid qQ'
reob12 = Re2d('[^qQ]{4,4}')
print 'Found:', reob12.search('bhtklkwt\nqlwQklqw\nvtvlwktv\nkQtwkvkl\nvtwlkvQk\nvnvevwvx')
print 'Not found:', reob12.search('zxvcmn\nxcvncn\nmnQxcv\nxcvmnx\nazvmne')

Pencarian ini menemukan kecocokan pertama.

13. Diamond Mining
.X.
X.X
.X.

.X.
X.X
.X.

..X..
./.\.
X...X
.\./.
\.X..

..X..
./.\.
X...X
.\./.
..X..

.XX.\
//.\.
X...X
.\./.
..X..

...X...
../.\..
./.X.\.
X.X.X.X
.\.X.//
..\./X.
.X.X..\

Diamonds: [(2, 2, 3, 3), (0, 6, 3, 3)] [(8, 0, 5, 5), (10, 2, 5, 5), (5, 3, 5, 5)] [(0, 0, 7, 7)]
Not found: None None None

print '\n13. Diamond Mining'
reob13a = Re2d(r'.X.|X.X', flags=MULTIFIND)
reob13b = Re2d(r'..X..|./.\\.|X...X|.\\./.', flags=MULTIFIND)
reob13c = Re2d(r'...X...|../.\\..|./...\\.|X.....X|.\\.../.|..\\./..', flags=MULTIFIND)
match = '''
...X......X....
../.\..../.\...
./.X.\..X...X..
X.X.X.XX.\./.\.
.\.X.//.\.X...X
..\./X...X.\./.
.X.X..\./...X..
X.X....X.......
.X.............
'''.strip().replace(' ', '')
nomatch = '''
.X......./....
.\....X.......
...X.\.\...X..
..X.\...\.X.\.
...X.X...X.\.X
../X\...\...X.
.X...\.\..X...
..\./.X....X..
...X..../.....
'''.strip().replace(' ', '')
for diamond in reob13a.findall(match)+reob13b.findall(match)+reob13c.findall(match):
    print diamond+'\n'
print 'Diamonds:', reob13a.search(match), reob13b.search(match), reob13c.search(match)
print 'Not found:', reob13a.search(nomatch), reob13b.search(nomatch), reob13c.search(nomatch)

Masalah berlian lebih sulit. Tiga objek pencarian diperlukan untuk tiga ukuran. Ini dapat menemukan enam berlian dalam set tes, tetapi tidak skala untuk berlian berukuran variabel. Ini hanya solusi parsial untuk masalah berlian.

Kode Python 2

import sys
import re

DEBUG = re.DEBUG
IGNORECASE = re.IGNORECASE
LOCALE = re.LOCALE
UNICODE = re.UNICODE
VERBOSE = re.VERBOSE
MULTIFIND = 1<<11
ROTATED = 1<<12     # not implemented
HORFLIP = 1<<13
VERFLIP = 1<<14
WRAPAROUND = 1<<15  # not implemented

class Re2d(object):
    def __init__(self, horpattern, verpattern=None, flags=0):
        self.horpattern = horpattern
        self.verpattern = verpattern if verpattern != None else horpattern
        self.flags = flags

    def checkblock(self, block, flags):
        'Return a position if block matches H and V patterns'
        length = []
        for y in range(len(block)):
            match = re.match(self.horpattern, block[y], flags)
            if match:
                length.append(len(match.group(0)))
            else:
                break
        if not length:
            return None
        width = min(length)
        height = len(length)
        length = []
        for x in range(width):
            column = ''.join(row[x] for row in block[:height])
            match = re.match(self.verpattern, column, flags)
            if match:
                matchlen = len(match.group(0))
                length.append(matchlen)
            else:
                break
        if not length:
            return None
        height = min(length)
        width = len(length)
        # if smaller, verify with RECURSIVE checkblock call:
        if height != len(block) or width != len(block[0]):
            newblock = [row[:width] for row in block[:height]]
            newsize = self.checkblock(newblock, flags)
            return newsize
        return width, height

    def mkviews(self, text, flags):
        'Return views of text block from flip/rotate flags, inc inverse f()'
        # TODO add ROTATED to generate more views
        width = len(text[0])
        height = len(text)
        views = [(text, lambda x,y,w,h: (x,y,w,h))]
        if flags & HORFLIP and flags & VERFLIP:
            flip2text = [row[::-1] for row in text[::-1]]
            flip2func = lambda x,y,w,h: (width-1-x, height-1-y, -w, -h)
            views.append( (flip2text, flip2func) )
        elif flags & HORFLIP:
            hortext = [row[::-1] for row in text]
            horfunc = lambda x,y,w,h: (width-1-x, y, -w, h)
            views.append( (hortext, horfunc) )
        elif flags & VERFLIP:
            vertext = text[::-1]
            verfunc = lambda x,y,w,h: (x, height-1-y, w, -h)
            views.append( (vertext, verfunc) )
        return views

    def searchview(self, textview, flags=0):
        'Return matching textview positions or None'
        result = []
        for y in range(len(textview)):
            testtext = textview[y:]
            for x in range(len(testtext[0])):
                size = self.checkblock([row[x:] for row in testtext], flags)
                if size:
                    found = (x, y, size[0], size[1])
                    if flags & MULTIFIND:
                        result.append(found)
                    else:
                        return found
        return result if result else None

    def search(self, text, flags=0):
        'Return matching text positions or None'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        result = []
        for textview, invview in self.mkviews(text, flags):
            found = self.searchview(textview, flags)
            if found:
                if flags & MULTIFIND:
                    result.extend(invview(*f) for f in found)
                else:
                    return invview(*found)
        return result if result else None

    def findall(self, text, flags=0):
        'Return matching text blocks or None'
        flags = self.flags | flags
        strmode = (type(text) == str)
        text = text.split('\n') if type(text) == str else text
        result = []
        positions = self.search(text, flags)
        if not positions:
            return [] if flags & MULTIFIND else None
        if not flags & MULTIFIND:
            positions = [positions]
        for x0,y0,w,h in positions:
            if y0+h >= 0:
                lines = text[y0 : y0+h : cmp(h,0)]
            else:
                lines = text[y0 : : cmp(h,0)]
            if x0+w >= 0:
                block = [row[x0 : x0+w : cmp(w,0)] for row in lines]
            else:
                block = [row[x0 : : cmp(w,0)] for row in lines]
            result.append(block)
        if strmode:
            result = ['\n'.join(rows) for rows in result]
        if flags & MULTIFIND:
            return result
        else:
            return result[0]

    def match(self, text, flags=0):
        'Return True if whole text matches the patterns'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        for textview, invview in self.mkviews(text, flags):
            size = self.checkblock(textview, flags)
            if size:
                return True
        return False
Ksatria Logika
sumber
Jika masalah intan tidak jelas, intan dapat berukuran berapa saja, tidak hanya 0, 1, atau 2. Sunting: Saya telah mengedit spesifikasi untuk membuatnya lebih jelas.
PhiNotPi
Mengerti. Saya akan membuat catatan dalam jawaban bahwa Re2d hanya memiliki solusi parsial untuk masalah ini. Itu tidak dapat skala ke ukuran variabel. Apakah itu oke?
Logic Knight
Ya itu baik baik saja.
PhiNotPi
14

Grime , Haskell

pengantar

Grime didasarkan pada tata bahasa Boolean . Ide dasarnya adalah membangun pola persegi panjang dari komponen yang lebih kecil, dan memeriksa apakah mereka ditemukan dalam matriks input. Sejauh ini, Grime hanya mendukung pertandingan persegi panjang, dan menyelesaikan setidaknya 11 masalah kurang lebih elegan.

EDIT: Memperbaiki salib (terima kasih kepada DLosc untuk melihat bug), dan menambahkan penambangan berlian.

EDIT2: Menambahkan kelas karakter, terinspirasi oleh orang-orang dari Slip. Juga mengubah sintaks dari flag opsi, meningkatkan parser ekspresi, dan menambahkan masalah no-Q.

EDIT3: Diimplementasikan kendala ukuran, dan menambahkan masalah Nether portal.

Pemakaian

Program Grime disebut tata bahasa , dan ekstensi file yang benar untuk tata bahasa adalah .gr, meskipun ini tidak diberlakukan. Tata bahasa dievaluasi sebagai

runhaskell grime.hs [options] grammarfile matrixfile

di mana matrixfilefile yang berisi matriks karakter. Sebagai contoh, tata bahasa digit akan dievaluasi sebagai

runhaskell grime.hs digits.gr digit-matrix

Untuk kecepatan ekstra, saya sarankan kompilasi file dengan optimisasi:

ghc -O2 grime.hs
./grime digits.gr digit-matrix

Secara default, juru bahasa mencetak kecocokan pertama yang ditemukannya, tetapi ini dapat dikontrol menggunakan flag opsi:

  • -e: cocokkan hanya seluruh matriks, cetak 1untuk kecocokan dan 0tanpa kecocokan.
  • -n: cetak jumlah kecocokan, atau seluruh matriks jika -ejuga diberikan.
  • -a: cetak semua kecocokan.
  • -p: cetak juga posisi pertandingan, dalam format (x,y,w,h).
  • -s: jangan cetak yang cocok sendiri.
  • -d: cetak informasi debug.

Opsi juga dapat ditentukan dalam tata bahasa, dengan memasukkannya sebelum baris apa pun dan menambahkan koma ,(lihat contoh di bawah).

Sintaks dan Semantik

Tata bahasa Grime terdiri dari satu atau lebih definisi , masing-masing pada baris terpisah. Masing-masing dari mereka mendefinisikan nilai nonterminal , dan salah satunya harus mendefinisikan nonterminal tingkat atas anonim . Sintaks definisi adalah baik N=Eatau E, di mana Nadalah huruf besar dan Emerupakan ekspresi .

Ekspresi dikonstruksi sebagai berikut.

  • Setiap karakter lolos dengan \cocok dengan 1x1persegi panjang yang berisi karakter itu.
  • . cocok dengan satu karakter.
  • $cocok dengan 1x1persegi panjang di luar matriks karakter.
  • _ cocok dengan persegi panjang nol lebar atau tinggi.
  • Kelompok karakter yang telah ditentukan adalah digit, uppercase, lowercase, alphabetic, alpha numeric, dan symbol.
  • Kelas karakter baru dapat didefinisikan oleh sintaks [a-prt-w,d-gu]. Huruf di sebelah kiri disertakan, dan yang di sebelah kanan dikecualikan, jadi ini cocok dengan hurufnya abchijklmnoprtvw. Jika sisi kiri kosong, ini diambil untuk berisi semua karakter. Koma dapat dihilangkan jika sisi kanan kosong. Karakter [],-\harus diloloskan dengan \.
  • Huruf besar yang tidak dilepas adalah huruf nonterminal, dan cocok dengan ekspresi yang diberikan.
  • Jika Pdan Qadalah ekspresi, maka PQitu hanyalah gabungan horizontalnya, dan P/Qmerupakan gabungan vertikalnya, dengan Pdi atasnya.
  • P+adalah satu atau lebih Ps sejajar secara horizontal, dan P/+sama sejajar secara vertikal.
  • Operasi Boolean dilambangkan P|Q, P&Qdan P!.
  • P?adalah singkatan untuk P|_, P*untuk P+|_, dan P/*untuk P/+|_.
  • P#cocok dengan persegi panjang yang berisi kecocokan dari P.
  • P{a-b,c-d}, Di mana abcdadalah bilangan bulat non-negatif, adalah kendala ukuran di P. Jika Padalah kelas karakter, maka ekspresi cocok dengan mxnpersegi panjang yang hanya berisi karakter tersebut, asalkan mada di antara keduanyaa dan binklusif, dan nantara cdan dinklusif. Dalam kasus lain, ekspresi cocok dengan persegi panjang yang memiliki ukuran yang benar dan yang Pjuga cocok. Jika aatau cdihilangkan, mereka dianggap sebagai 0, dan jika batau ddihilangkan, mereka tidak terbatas. Jika tanda hubung antara adan bdihilangkan, maka kami menggunakan angka yang sama untuk kedua ujung interval. Jika semuanyac-dbagian dihilangkan, kedua sumbu dibatasi. Untuk memperjelas, {-b}sama dengan {0-b,0-b}, dan {a-,c}setara dengan {a-infinity,c-c}.

Catatan

Grime memungkinkan definisi paradoks seperti A=A!dengan perilaku yang tidak terdefinisi. Namun, mereka tidak akan menyebabkan crash atau loop tak terbatas.

Grime mendukung input non-persegi panjang; baris hanya disejajarkan ke kiri, dan celahnya bisa dicocokkan dengan menggunakan $.

Di masa depan, saya ingin menerapkan yang berikut:

  • Pencocokan lebih cepat. Saat ini, penerjemah tidak memperhitungkan fakta bahwa, misalnya, .hanya bisa cocok dengan 1x1persegi panjang. Sampai menemukan kecocokan, ia mencoba semua persegi panjang dari semua ukuran secara berurutan, langsung gagal untuk masing-masing.
  • Operasi rotasi dan refleksi, untuk pencarian kata dan tantangan peluncur.

  • Pertandingan non-persegi panjang menggunakan konteks , yang akan membantu dalam tantangan papan Boggle. Misalnya, Pv(Q>R)berarti Pdengan konteks bawah ( Qdengan konteks kanan R). Itu akan cocok dengan pola berbentuk L

    PPP
PPP
QQQRRRR
QQQRRRR
QQQRRRR

Tugas

Diberikan kira-kira dalam urutan kompleksitas.

Persegi panjang digit

d{2-}

Ini sederhana: setidaknya persegi panjang digit 2x2 .

Tidak ada q atau Q

[,qQ]{4}

Ini hampir sesederhana yang pertama; sekarang kami memiliki ukuran yang lebih terbatas dan kelas karakter khusus.

Penjajaran horizontal dan vertikal

\#.*\#|\#/./*/\#

Sekarang kami memiliki beberapa karakter yang lolos. Pada dasarnya, ini cocok dengan satu #, lalu sejumlah karakter apa pun, kemudian #, baik secara horizontal maupun vertikal.

Deteksi input persegi

S=.|S./+/.+
e,S

Tata bahasa ini sangat sederhana, pada dasarnya mendefinisikan bahwa kuadrat adalah a 1x1 panjang, atau persegi yang lebih kecil dengan satu kolom ditempelkan di tepi kanannya, dan satu baris ditempelkan di bagian bawah itu. Perhatikan juga eopsi sebelum level atas nonterminal, yang mengubah verifikasi seluruh input.

Menemukan kata dalam pencarian kata

G=\G
O=\O
L=\L
F=\F
GOLF|FLOG|G/O/L/F|F/L/O/G|G.../.O../..L./...F|...G/..O./.L../F...|F.../.L../..O./...G|...F/..L./.O../G...

Yang ini mengerikan, karena Grime tidak memiliki operasi untuk rotasi atau refleksi. Ini juga sangat lambat, karena Grime tidak tahu bahwa pertandingan hanya dapat berukuran 4x1, 1x4atau4x4 .

Masalah glider dapat diselesaikan dengan cara yang sama, tetapi saya terlalu malas untuk menuliskannya.

Nether Portal

.\X+./\X/+\.{2-22,3-22}\X/+/.\X+.

Dengan operator pembatasan ukuran, yang ini tidak terlalu sulit. Bagian tengah \.{2-22,3-22}cocok dengan persegi panjang .dengan ukuran yang benar, dan kemudian kita tambahkan kolom Xs di kedua sisi, dan paku baris dariX s dengan ujung yang diabaikan di bagian atas dan bawah itu.

Salib yang cocok

E=\.+/+
F=\#+/+
EFE/F/EFE&(E/F/E)F(E/F/E)

Apa yang kita miliki di sini adalah gabungan (logis DAN) dari dua ekspresi. Nonterminal Ecocok dengan persegi panjang kosong .s, dan Fpersegi panjang kosong #s. Sisi kiri konjungsi cocok dengan persegi panjang dari tipe tersebut

...####..
...####..
...####..
#########
#########
.....##..
.....##..

di mana kita memiliki EFEdi atas, lalu F, dan kemudianEFE lagi. Sisi kanan cocok dengan transposes ini, jadi kami mendapatkan persilangannya.

Penambangan intan

C=./+
T=\X|CTC/\/.+\\
B=\X|\\.+\//CBC
CTC/\X.+\X/CBC

Nonterminal Cadalah singkatan untuk setiap 1xnkolom. Setengah bagian atas berlian cocok dengan T: itu adalah satu X, atau yang lain Tdikelilingi oleh kolom di kedua sisi, dan baris di /[something]\bawahnya. Bcocok dengan bagian bawah berlian dengan cara yang sama, dan tingkat atas nonterminal hanyalah deretan bentukX[something]X antara setengah bagian atas dan bagian bawah bagian bawah.

Menemukan papan catur

(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]{3-}

Sisi kanan [#_]{3-}cocok dengan 3x3persegi panjang #s dan _s yang lebih besar, sedangkan sisi kiri menjamin tidak ada dua #s atau s yang berdekatan _.

Memverifikasi papan catur

e,(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]+/+

Ini pada dasarnya sama dengan di atas, kecuali bahwa kita dapat mencocokkan dengan persegi panjang yang tidak kosong, tetapi perlu menggunakan e bendera untuk seluruh verifikasi input.

Verifikasi sintaks Prelude

A=[,()]/*
P=A*|P(A/\(/A)P(A/\)/A)P
e,P

Ini mungkin tata bahasa yang paling menarik sejauh ini. Nonterminal Acocok dengan kolom mana pun yang tidak mengandung (atau ), dan Pcocok dengan sejumlah As, atau dua tanda kurung yang cocok, antara dan di luar yang ada lebih banyak Ps.

Zgarb
sumber
@Dosc Tetap, terima kasih telah menemukan bug!
Zgarb
Akan \#(.*|./*)\#bekerja
seequ
@ Seleg Untuk penyelarasan? Sayangnya tidak, karena itu akan diuraikan sebagai "satu #di sebelah kiri, lalu baris atau kolom apa pun, lalu satu #di sebelah kanan". Saya perlu menentukan bahwa #s secara vertikal digabungkan ke kolom menggunakan garis miring /.
Zgarb
10

TMARL

Pencocokan Templat dan Bahasa Pengakuan

Deskripsi

Penerjemah saya membutuhkan 24K karakter ( potongan kode mengambil karakter? ), Sehingga uraian lengkap dapat ditemukan di sini .

Bagian terbaik: penerjemahnya dalam Javascript, artinya Anda bisa mencobanya di sini!

Tampilkan cuplikan kode

Dan untuk masalah:

# 1 - Menemukan Papan Catur

$#_#
a
$_#_
bvacvbS5&(avcS5)G0G2P

&menambahkan pencarian. G2 pada akhirnya mendapatkan elemen ke-3 dalam elemen kecocokan, kecocokan sebenarnya. 2 elemen pertama adalah koordinat x dan y (1 berbasis, bukan 0).

# 3 - Mendeteksi Rectangle of Digit

$DD
$DD
S1G2P

Saya pikir ini cukup mudah.

# 4 - Menemukan Kata dalam Pencarian Kata

$GO\LF
a
$G
$*O
$**\L
$***F
S6&(aS6)G0G2P

The SArgumen ini bahkan sehingga akan mencari semua rotasi. Ini lebih besar dari 4 karena kemudian dapat ditambahkan ke pencarian berikutnya (pertandingan individu tidak dapat ditambahkan).

# 5 - Mendeteksi Input Kuadrat

IL-(IG0L)!P

Tidak yakin apakah ini sepenuhnya legal, karena hanya menentukan kuadrat dengan benar jika inputnya adalah persegi panjang. Ini membandingkan panjang input ILdengan panjang baris pertama IG0Ldan membalikkannya.

# 6 - Temukan Glider dalam Game of Life

$## 
$# #
$# 
a
$ ##
$## 
$  #
bS6&(bMS6)&(aS6)&(aMS6)G0G2P

Akhirnya, gunakan untuk cermin!

# 12 - Hindari Surat Q

$[^Qq]
~4*4S1G2P

S1 karena hanya 1 pertandingan diperlukan.

Saya akan melakukan beberapa yang lebih sulit nanti.

Regangkan Maniac
sumber