pengantar
Tantangan ini terinspirasi oleh Grime , bahasa pencocokan pola 2D saya. Pada dasarnya, Anda diberi "tata bahasa" yang menggambarkan kisi-kisi karakter dua dimensi, dan tugas Anda adalah membuat kisi sesuai dengan tata bahasa. Selain itu, grid harus sekecil mungkin dalam arti lemah tertentu.
Memasukkan
Input Anda adalah string yang berisi karakter ASCII huruf kecil dan simbol |
dan -
. Untuk kesederhanaan, input tidak mengandung karakter huruf kecil berulang. String adalah spesifikasi untuk kelas kotak karakter persegi panjang, dan diurai dari kiri ke kanan menggunakan tumpukan sebagai berikut.
- Diberikan karakter huruf kecil
c
, dorong ke tumpukanm×n
kisi karakterc
, untuk apa sajam, n ≥ 1
. - Diberikan pipa
|
, pop dua gridA
danB
dari tumpukan (B
ada di atas), dan dorong gridAB
diperoleh dengan menyatukanB
ke kananA
. Ini mengharuskan ituA
danB
memiliki ketinggian yang sama. - Diberi tanda hubung
-
, letakan dua kisiA
danB
dari tumpukan (B
ada di atas), dan dorong kisi yangA/B
diperoleh dengan menyatukanB
ke bagian bawahA
. Ini membutuhkan ituA
danB
memiliki lebar yang sama.
Dijamin bahwa untuk beberapa pilihan m
dan n
dibuat selama proses parsing (yang mungkin berbeda untuk setiap huruf), spesifikasi input dengan benar menggambarkan beberapa persegi panjang, yang tersisa di tumpukan di bagian akhir.
Keluaran
Output Anda adalah kotak karakter persegi panjang yang ditentukan oleh input. Kisi harus minimal dalam arti bahwa menghapus baris atau kolom apa pun akan membuatnya tidak valid. Anda dapat mengembalikan string yang dipisahkan baris baru (dengan atau tanpa baris baru), array karakter 2D, atau array string, yang mana adalah format yang paling nyaman.
Perhatikan bahwa Anda tidak perlu memproses input persis seperti yang dijelaskan di atas; satu-satunya hal yang penting adalah bahwa output Anda sudah benar.
Contoh
Pertimbangkan spesifikasinya
par-s||e-
Pertama, kami memilih untuk mendorong 1×2
persegi panjang p
, dan 1×1
persegi panjang a
dan r
(alasan untuk ini akan jelas nanti). Kemudian, kita meletupkan a
dan r
persegi panjang, dan mendorong concatenation vertikal mereka
a
r
Selanjutnya, kami mendorong 1×2
persegi panjang s
, pop itu dan persegi panjang di atas, dan mendorong concatenation horizontal mereka
as
rs
Lalu kita letakan kotak itu dan p
kotak itu, dan dorong pasangan mereka
pas
prs
Akhirnya, kita dorong 3×1
kotak e
, pop, dan kotak di atas, dan dorong concatenation vertikal
pas
prs
eee
Ini adalah output dari program, atau paling tidak salah satu kemungkinan. Perhatikan itu meskipun
ppas
ppas
pprs
eeee
juga dihasilkan oleh spesifikasi, ini bukan output yang valid, karena banyak baris dan kolom dapat dihapus.
Sebagai contoh yang lebih halus, pertimbangkan
co|m|p|il|e|r|-
Spesifikasi ini menghasilkan persegi panjang
comp
iler
yang merupakan output yang valid. Namun, itu juga menghasilkan
commp
iiler
yang juga valid, karena tidak ada baris atau kolom tunggal yang dapat dihapus tanpa membatalkannya.
Aturan
Anda dapat memberikan program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Kasus Uji Ekstra
Anda dapat menggunakan ini untuk menguji program Anda.
Input:
a
Output:
a
Input:
co|mp|l|-ex|i|f|-y|
Example output:
cccoy
mplly
exify
Input:
ja-r|g-o|ni-|ze|d-|
Example output:
jronze
arondd
ggoidd
Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Example output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe
sumber
n
danm
dipilih secara non-deterministik. Dijamin bahwa nilai-nilai yang cocok untuk mereka ada, tetapi itu adalah tugas program Anda untuk menemukannya.un|co|p-|yr|i|gh--t-ab|-|le-||-
tidak mungkin valid. Yang terakhir-
memiliki arity 2, sementara hanya ada 1 elemen di stack.Jawaban:
K,
123110 byteSaya menggunakan pendekatan yang mirip dengan solusi cardboard_box.
Program ini adalah serangkaian definisi pembantu diikuti oleh fungsi diam-diam yang mengambil string sebagai argumen yang benar. Memformat ulang untuk keterbacaan dan menetapkan fungsi akhir sebagai
f
:Gunakan contoh:
Diuji menggunakan Kona, tetapi itu juga akan berfungsi dalam oK jika Anda mengganti
:
definisif
dengan a$
- k5 mengubah sintaks "cond".Titik kunci adalah mengakui bahwa melakukan penambahan vertikal adalah transpose dari penambahan horizontal dari transpose dari kedua matriks. (Lihat definisi
v
.) Saya pikir masih ada ruang untuk memeras beberapa karakter di sana-sini. Kalau ada yang tertarik dengan penjelasan yang lebih rinci saya bisa memberikannya.edit:
Memperbarui program di bagian atas entri ini. Versi tidak disatukan:
Optimalisasi panjang yang penting termasuk penggunaan "dot apply"
a
, mengganti "cond" dengan daftar indeks dif
(kurang efisien, tetapi lebih pendek) dan mengganti syarat formulira[b;c]
kea[b]c
tempat diizinkan oleh pengelompokan. Karena saya tidak lagi menggunakan "cond" atau primitif apa pun yang berbeda antara k3 dan k5 versi ini sekarang berfungsi di oK tanpa modifikasi.sumber
Prolog, 539 byte
Penjelasan
Kita mulai dengan predikat
g
, yang mengambil string, mengubahnya sebagai daftar karakter dan memanggilp
predikat (parse) dengan tumpukan kosong sebagai argumen kedua.Predikat
p
panggilan itu sendiri secara rekursif dengan tumpukan yang dimodifikasi secara tepat (mencari[H|T]
pola destruktor dan konstruktor). Ketika dipanggil pada kasus dasar, di mana daftar input kosong,p
mencetak elemen unik dari tumpukan. Jika tumpukan memiliki kurang atau lebih dari satu elemen pada titik ini, itu berarti bahwa kita memiliki string input kosong, string input buruk atau bug (dengan string emtpy, predikat gagal) (kata PrologNo
), tetapi tidak ada yang dicetak, yang ok, karena kita seharusnya tidak mencetak apa pun untuk string kosong).Memecahkan
Tumpukan berisi deskripsi persegi panjang yang dibangun, dilambangkan
S:W:H
, di manaS
adalah representasi simbolis dari persegi panjang,W
lebar danH
tingginya (catatan,A:B
adalah gula sintaksis untuk:(A,B)
tupel dengan functor bernama:
; hanya lebih pendek untuk menulis daripada memiliki tupel dengan notasi awalan).Dengan
A
danB
spesifikasi sub-persegi panjang,S
dapat berupa:h(A,B)
: concat horizontal A dan Bv(A,B)
: concat vertikal A dan Bf(C)
: isi dengan C, di mana C adalah kode karakterLebar dan tinggi kisi-kisi adalah variabel pemrograman kendala: selama penggabungan vertikal (resp. Horizontal), lebar (resp. Tinggi) dari persegi yang dimanipulasi disatukan, sedangkan tinggi yang dihasilkan (lebar resp) dibatasi menjadi jumlah dari tinggi setiap subgrid (lebar resp.).
Langkah pelabelan di akhir proses akan memunculkan variabel sambil menghormati batasan, menggunakan nilai minimal yang mungkin (ini adalah properti dari urutan di mana solusi dicoba).
Saya mungkin telah memperoleh jawaban yang lebih pendek menggunakan penalaran yang sama yang dilakukan dalam jawaban lain, tanpa kendala, tetapi ini sudah terlambat sekarang.
Perhatikan juga bahwa karena domain default untuk variabel diatur ke
1..100
, ada batasan atas ukuran grid yang mungkin. Batas atas dapat diubah jika perlu. Implikasi kinerja dari hal ini adalah bahwa mungkin perlu banyak waktu untuk menentukan bahwa solusi tertentu tidak mengakui solusi. Saya berkata " bisa " karena kendala kemungkinan akan secara drastis memangkas pencarian eksponensial. Jika Anda menemukan string input yang sulit / mahal untuk ditolak, silakan bagikan.Pencetakan
Bagian pencetakannya menarik karena ada semacam ray-casting algoritma atas struktur: Saya beralih ke setiap sel dari grid yang dihasilkan, dari titik
(1,1)
ke titik(W,H)
dan memanggilw
predikat untuk mencetak konten grid di pohon utama, di lokasi ini (tentu saja, baris baru dicetak setelah memproses setiap baris).Dalam
w
, posisi relatif terhadap kisi saat ini (kisi akar mendefinisikan koordinat absolut).Saat mencetak
h(A,B)
struktur pada titik(X,Y)
, saya mencetak tanpa syarat di kedua cabang:A
pada titik(X,Y)
, danB
pada titik(H,Y)
, di manaH
adalahX
minus lebarA
.Cabang-cabang daun dari grid-tree,
f(C)
akhirnya mencetak karakterC
, jika lokasi relatif berada di dalam grid, atau tidak melakukan apa-apa. Ini adalah bagaimana saya dapat mencetak konten grid ke aliran output, dari atas ke bawah, dari kiri ke kanan. Tidak ada array aktual yang diproduksi.Tes
Tes lari:
sumber
No actual arrays are produced.
itulah yang harus dilakukan. Berlebihan dalam hal ini, karena tata bahasanya sangat sederhana dan ada jalan pintas.Python 2.7, 259
g
adalah fungsi yang mengambil spesifikasi dan memberikan array karakter 2D. Jika Anda menginginkan versi yang lebih ramah pengguna, tambahkan baris ini untuk membuatnya mengambil spesifikasi dari stdin dan cetak kisi:Uji Kasus
Penjelasan
Strateginya sederhana: jika kisi
G
valid untuk spesifikasiS
, maka pengulangan kolom paling kananG
juga memberikan spesifikasi yang valid untukS
, dan hal yang sama berlaku dengan pengulangan baris bawah (buktinya adalah dengan induksi struktural aktifS
). Oleh karena itu, ketika kita ingin menggabungkan dua persegi panjang, kita cukup menambahkan kolom / baris terakhir dari yang lebih kecil sampai mereka cocok dalam ukuran (ini adalah apa fungsi p tidak).sumber
Haskell,
388367352 bytePemakaian:
f "par-s||e-"
->["pas","prs","eee"]
Uji coba dengan pencetakan cantik:
Cara kerjanya: fungsi
#
mem-parsing string input ke dalam struktur pohonC
yang bisa berupa daun yangL
menahan karakter untuk dicetak atau simpulN
.N
dapat berupa a) gabungan berdampingan (t==2
), b) gabungan atas-bawah (t==1
) atau c) satu huruf persegi (t==0
). Semua node memiliki bidang lebar dan tinggi dan anak kiri dan kanan. Setelah parsing,p
cetak simpul akar yang tersisa dengan secara rekursif menyesuaikan ukuran (lebar x tinggi) dari simpul anak itu dan bergabung dengan mereka.Sunting: keluaran sebagai daftar baris alih-alih pencetakan yang cantik
sumber
JavaScript (ES6), 283
295Edit Sekarang, solusi JS (sangat golf) ini setidaknya lebih pendek daripada referensi (cukup golf) solusi Python.
Mirip dengan cardboard_box, cukup ulangi kolom paling kiri atau baris paling atas.
Ungolfed Ini adalah solusi pertama saya, ungolfed.
Uji di Firefox / konsol FireBug
Keluaran
sumber
Python 3, 251 byte
Inilah jawaban referensi yang saya janjikan, bermain golf sedikit lebih jauh.
Ini adalah program lengkap yang mengambil string dari STDIN dan mencetak ke STDOUT. Pendekatannya sama dengan cardboard_box: tekan array 1x1 untuk sebuah karakter, dan duplikat baris jika diperlukan untuk penggabungan.
Penjelasan detail
T
transpos daftar daftar yang diberikan. Sebagian besar pekerjaan dilakukan denganzip(*m)
menukar baris ke kolom, sisanya hanya mengubah hasilnya menjadi daftar daftar, karenazip
mengembalikan generator tupel.E(a,b)
kembalia
dengan elemen pertama yang diulang cukup kali untuk mencocokkan panjangb
. Perhatikan bahwa mengalikan daftar dengan angka negatif memberikan daftar kosong, jadi jikab
lebih pendek daria
, ini kembalia
.H(a,b)
mengembalikan rangkaian horizontala
danb
, yang lebih pendek diperpanjang olehE
jika perlu.s
adalah tumpukan.for
loop, kami beralih pada string input, dan gantis
dengan nilai baru: jika itu|
(lebih besar dariz
), kami memunculkan dua nilai dan mendorongnyaH
, jika itu-
(lebih rendah daria
), kami memunculkan dua nilai, transpos, diumpankan keH
, transpos lagi dan tekan hasilnya, dan sebaliknya dorong array 1x1 dengan huruf.s
.sumber