Seekor ular melar terlihat seperti ini:
<||=|||:)~
Setiap urutan bar vertikal yang terpisah ( |
) dalam ular melar, yang dikenal sebagai bagian melar , dapat diperpanjang secara individual hingga dua kali lebarnya, dan digambar dengan garis miring bergantian ( /
, \
) setelah diperpanjang.
Ular tertentu di atas memiliki dua bagian melar seperti itu, memberikannya empat kemungkinan pose:
<||=|||:)~
</\/\=|||:)~
<||=/\/\/\:)~
</\/\=/\/\/\:)~
Bentuk umum ular melar dengan pose paling tidak melar ditentukan oleh regex ini :
<(\|+=)*\|+:\)~
Yang dapat dinyatakan dengan kata-kata sebagai:
<
, Diikuti oleh sejumlah urutan|
's bergabung dengan=
tanda-tanda, diikuti oleh:)~
.
Jadi <|:)~
dan <||:)~
dan <|=|:)~
dan <|=|=||=|||||=||:)~
adalah ular melar, tetapi <=:)~
dan <=|:)~
dan <||=:)~
dan <|==||:)~
tidak.
Ular melar juga bisa menghadap ke kiri, bukan ke kanan, misalnya ~(:|||=||>
. Bentuknya sama, hanya dicerminkan.
Tantangan
Tulis sebuah program yang mengambil satu baris string dari dua ular melar yang saling berhadapan, dengan beberapa ruang di antaranya. Kedua ular akan berada dalam posisi paling tidak melar (semua batang vertikal, tanpa garis miring). Tali akan mulai dengan ekor ular yang menghadap ke kanan dan diakhiri dengan ekor ular yang menghadap ke kiri (Anda dapat mengasumsikan ada juga baris baru yang tertinggal).
Misalnya, inilah input yang mungkin dengan lima spasi di antara ular:
<|=||:)~.....~(:||||>
Saya menggunakan titik ( .
) alih-alih karakter spasi aktual untuk kejelasan.
Tanpa spasi antar ular juga merupakan input yang valid:
<|=||:)~~(:||||>
Kami mengatakan ular-ular itu berciuman ketika lidah mereka bersentuhan seperti ini.
Program Anda perlu memperpanjang beberapa kombinasi bagian melar dari kedua ular sehingga ular memiliki jumlah ruang paling sedikit di antara mereka (tanpa tumpang tindih), yaitu sedemikian rupa sehingga ular sedekat mungkin dengan ciuman .
Kedua ekor ular itu tetap tetapi kepala dan tubuhnya dapat bergerak - tepat untuk ular yang menghadap ke kanan, kiri untuk ular yang menghadap ke kiri - sesuai dengan bagian melar yang telah diperpanjang.
Output dari program Anda adalah string garis tunggal (plus baris tambahan opsional) yang menunjukkan ular sedekat mungkin dengan ciuman, dengan garis miring berganti-ganti di tempat garis vertikal untuk bagian melar yang telah diperpanjang.
Misalnya, output untuk <|=||:)~.....~(:||||>
(dari atas) adalah:
</\=||:)~~(:/\/\/\/\>
Ini adalah satu - satunya solusi di sini karena dengan kombinasi lain dari bagian melar diperpanjang, ular akan tumpang tindih atau lebih jauh dari ciuman.
Jika ada beberapa solusi yang mungkin, hasilnya mungkin salah satunya.
Misalnya, jika inputnya
<|=||:)~.....~(:|||=|>
outputnya bisa
<|=/\/\:)~~(:/\/\/\=|>
atau
</\=||:)~~(:/\/\/\=/\>
Ingatlah bahwa ular tidak akan selalu bisa ciuman, tetapi Anda masih harus membuatnya sedekat mungkin.
Misalnya, jika inputnya
<||=||||:)~...~(:||>
outputnya bisa
</\/\=||||:)~.~(:||>
atau
<||=||||:)~.~(:/\/\>
Jika ular sudah berciuman, hasilnya akan sama dengan input. misalnya
<|=||:)~~(:||||>
Secara umum, output akan sama dengan input jika ekstensi dari setiap bagian melar akan membuat ular tumpang tindih. misalnya
<|||=|||:)~..~(:||||=|||||=||||||>
Catatan
- Mengambil input dari stdin atau baris perintah seperti biasa, atau menulis fungsi yang mengambil string. Cetak atau kembalikan hasilnya.
- Anda dapat menggunakan titik (
.
) pada input dan output sebagai ganti spasi () jika diinginkan.
- Ini hanya penting bahwa garis miring berganti dalam barisan vertikal yang mereka ganti. Pemesanan mereka pada ular pada umumnya atau apakah tebasan maju atau mundur datang pertama tidak masalah.
- Bagian melar tidak dapat memanjang sebagian - persis dua atau tidak ada ekstensi sama sekali.
Mencetak gol
Ini adalah kode-golf . Pengajuan terpendek dalam byte menang. Tiebreaker adalah jawaban sebelumnya.
sumber
>
tidak tidak akan menjadi<
, sama untuk untuk(
dan)
), tetapi ia juga mengatakan "Hanya penting bahwa garis miring berganti dalam urutan bilah vertikal yang mereka ganti. Pemesanan mereka di ular pada umumnya atau apakah tebasan maju atau mundur datang pertama tidak masalah. "Jawaban:
CJam,
87717068 byteCobalah online di juru bahasa CJam .
Bagaimana itu bekerja
sumber
Retina ,
209107999792 byteUntuk tujuan penghitungan, setiap baris memiliki file terpisah, tetapi Anda dapat menjalankan kode dari satu file dengan
-s
flag.Membawa fitur-fitur terbaik dari .NET regex dan Retina bersama-sama: menyeimbangkan kelompok, melihat panjang sewenang-wenang dan mengulangi penggantian regex.
Pada dasarnya, regex panjang mengkode solusi yang valid dan backtracker mesin regex menemukan salah satu yang optimal bagi saya.
Penjelasan
Pertama, mari kita pertimbangkan bagaimana kita dapat menemukan solusi yang valid (belum tentu menghasilkan output yang benar) dengan sebuah regex. Kita dapat menggunakan grup penyeimbang .NET untuk membantu kita menghitung bagian melar. Pertimbangkan regex sederhana berikut ini:
Kita bisa memotongnya.
Ini cocok dengan seluruh string, mendorong satu tangkapan ke
1
tumpukan kelompok untuk setiap ruang di input. Kami akan menggunakan tumpukan itu untuk memastikan bahwa bagian yang melar benar-benar mengisi ruang yang ditangkap ke dalam kelompok tersebut.Selanjutnya adalah melihat di belakang. Tangkapannya adalah bahwa lookbehinds dicocokkan dari kanan ke kiri di .NET (jadi itulah bagaimana Anda harus membacanya). Ini memberi kita kesempatan untuk melintasi string untuk yang kedua kalinya, mencari tahu apakah ada subset bagian melar yang berjumlah jumlah ruang yang cocok. Melihat dari belakang ke kanan:
Ini hanya memastikan bahwa kita benar-benar mulai dari ujung tali (ekor ular).
Untuk setiap bagian melar, ini hanya cocok dengan seluruh bagian tanpa melakukan apa-apa (
\|+
), atau cocok dengan seluruh bagian sambil muncul menangkap tumpukan1
((?<-1>\|)*
). Memiliki pergantian ini memastikan bahwa kami hanya dapat sepenuhnya memperpanjang bagian melar atau membiarkannya tidak berubah, dan tidak mendapatkan barang-barang seperti|/\|
. Kemudian kita beralih ke bagian melar berikutnya dengan[^|]+
.Akhirnya, kami memastikan bahwa kami telah melintasi seluruh string (keduanya ular), dan tumpukan
1
itu benar-benar kosong. Yaitu bahwa kita telah menemukan subset dari bagian melar yang tepat jumlah jumlah ruang yang telah kita tangkap sebelumnya.Pelacak mundur akan bolak-balik melalui string mencoba semua kombinasi bagian tidak berubah dan diperpanjang sampai masalah jumlah subset diselesaikan. Jika subset seperti itu tidak ada, tampilan di bawah akan gagal. Ini akan menyebabkan backtracker kembali ke
\S+( )+.+
bagian dan mencoba menangkap satu ruang lebih sedikit dengan( )+
(yang hanya akan ditutupi oleh.+
sebagai gantinya). Karena keserakahan+
kami berusaha mengisi ruang sebanyak mungkin.Anda dapat memeriksa validitas pendekatan ini dengan substitusi yang sedikit dimodifikasi ini:
Yang akan memberi Anda string
=spaces=
dengan tepat jumlah ruang yang bisa diisi dengan ular yang diberikan.Saya harus menambahkan beberapa tipu daya untuk benar-benar memperluas
|
s yang benar . Pada dasarnya, saya ingin mengganti semua|
yang cocok menggunakan(?<-1>\|)+
cabang. Idenya adalah untuk mencocokkan karakter individu, menempatkan solver di lookaround dan mengatur bendera jika pertandingan kebetulan berada di dalam cabang itu. Jika bendera itu tidak disetel, kami membatalkan pertandingan pada akhirnya untuk menghindari penggantian karakter lain.Untuk melakukan ini, kami menggunakan banyak pencarian yang bersarang. Sekali lagi, tampilan variabel-panjang NET. Dicocokkan dari kanan ke kiri, jadi jika kita bersarang lookaheads dan lookbehinds, kita dapat membiarkan mesin regex melintasi string beberapa kali. Untuk alasan bermain golf, solver dibalik dalam solusi saya yang sebenarnya (mulai dari akhir, mengambil spasi dari kanan ke kiri, dan kemudian memecahkan jumlah himpunan bagian dari kiri ke kanan), tetapi sebaliknya struktur solver persis sama . Mari kita membedah regex lengkap:
Kami mencocokkan satu karakter, lalu menangkap sisa string dan memindahkan kursor ke ujung string. Kami akan menggunakan grup ini
1
nanti untuk memeriksa solver apakah kami ada di posisi pertandingan.Ini seperti bagian pertama dari pemecah sederhana di atas, kecuali bahwa kita mengambil spasi dari kanan ke kiri. Pengulangan jumlah ruang bekerja sama persis seperti sebelumnya, kecuali bahwa kami menggunakan grup
5
sekarang.Ini sama dengan sebelumnya, kecuali kita bergerak dari kiri ke kanan, dan setiap kali kita mencocokkan dengan
|
di cabang yang berkembang, kita memeriksa apakah itu yang cocok denganIni adalah lookahead opsional. Ia mencoba untuk mencocokkan grup
1
lagi (yang, di sini, hanya mungkin jika kita tepat setelah karakter dicocokkan), dan jika kita lakukan, kita menangkap string kosong ke dalam grup4
, yang menunjukkan bahwa kita memang menemukan karakter saat ini dalam satu bit diperluas. Jika\1
tidak cocok,4
tidak akan menangkap apa pun, dan?
memastikan bahwa lookahead yang gagal tidak akan mempengaruhi pemecah sama sekali.Akhirnya, setelah semua penyelesaian dilakukan, kami hanya memeriksa
\4
apakah lookahead ini digunakan. Jika demikian, kami ingin mengganti karakter saat ini dengan/\
.Satu kesulitan tetap: menghapus jumlah ruang yang tepat. Cara terpendek untuk melakukan ini yang saya temukan sejauh ini adalah menyisipkan spasi bersama dengan
/\
dan kemudian menyingkirkan satu ruang antara lidah untuk masing-masing ruang penanda tersebut dalam langkah terpisah:sumber
Ruby
191 187 186 170162Ini adalah fungsi yang mengambil string sebagai parameter dan mengembalikan string.
Tes online: http://ideone.com/uhdfXt
Ini versi yang bisa dibaca:
Dalam versi golf, fungsi utama adalah setara dengan
KISS
fungsi di atas, danCOMBINATIONS
fungsi tersebut telah digariskan.sumber
<|=||:)~~(:||||>
, yang menyebutkan spesifikasi adalah input yang valid.Python, 205 byte
Memiliki satu lambda terlihat rapi, tapi saya hampir yakin ini bukan cara terbaik untuk melakukannya. Tapi saya memposting ini karena semua yang saya dapatkan sejauh ini terlihat cukup layak.
Ini adalah kekuatan kasar sederhana atas semua kemungkinan penggantian
|
dengan/\
, memfilter konfigurasi yang tidak valid. Satu-satunya bit yang rapi saya kira adalah bahwa kita tidak benar-benar mengganti apa pun|
dengan/\
langsung - pertama kita ganti|
denganX
dan lepaskan a.
dari tengah untuk setiap penggantian, ambil string panjang minimum di atas semua string yang valid, lalu gantiX
dengan/\
.Saya mencoba beberapa pendekatan lain, termasuk yang rekursif, tetapi mereka akhirnya cukup berantakan. Saya juga belajar bahwa
re.split
saat ini tidak terpecah pada string kosong, yang sangat disayangkan, karena salah satu ide saya melibatkan pemisahan pada\b
batas kata.sumber
Mathematica, 381 byte
Fungsi murni mengambil string sebagai argumennya. Mengharapkan
.
daripada diantara ular.
Saya tidak berpikir itu akan seburuk ini ... Inilah yang saya miliki sebelum saya hancurkan bersama-sama dan melekatkan semuanya.
Berikut adalah contoh run-through dengan penjelasan:
sumber
a=StringReplace;b=StringSplit;c=StringLength;d=Total;
dan kemudian menggantikan yang diperlukan di tempat lain di dalam:a=StringReplace;b=StringSplit;c=StringLength;d=Total;a[MapAt[a[#,"|"->"/\\"]&,b[#<>"="<>#2,"="],#3]~StringRiffle~"=",")="->")~"<>If[#4>0,"."~StringRepeat~#4,""]<>"~"]&[#1,#3,Sequence@@Function[{l,s},{#,#2-d@Extract[l,#]}&[Flatten[l~Position~#~Take~#2&@@@Tally@#&@@Select[Subsets@l,d@#<=s&]~MaximalBy~d,1],s]][c/@StringCases[#1<>#3,"|"..],c@#2]]&@@#~b~"~"&
Prolog (ECLiPSe), 438 byte
Jawaban saya yang lain adalah memecahkan masalah yang salah (maaf untuk kebisingan). Berikut adalah upaya lain dalam Prolog yang benar-benar menghormati semua aturan.
Tes
(format: input, output, baris baru)
Penjelasan
Predikat utama adalah
s/2
, yang mengambil input sebagai argumen pertama dan tidak cocok dengan argumen kedua (kedua string). Input dikonversi ke daftar kode karakterE
,.Kemudian,
s(E,Z,X,Y,L)
rusak daftar menjadi elemen-elemen berikut:Z
jumlah spasi di antara ularX
danY
, representasi abstrak dari tubuh kiri dan kananFormat tubuh adalah daftar
n:N
ataus:N
ekspresi, di manaN
panjangnya positif;n
sarananormal
dans
saranastretched
.L
total panjang daftarYang menarik
s/5
adalah bahwa ia berjalan dua arah , yaitu kita dapat membuat ular jika argumen lain dilemahkan:Q
yang memisahkan ular baru. Panjang total string yang dihitung dibatasi sehingga pencarian berakhir.sumber
Python 2.7.3
427421400371 BytesKode non-golf di sini -
Menguji solusi golf -
Tentunya ini bisa dilakukan dengan lebih baik (saya tidak tahu caranya :)).
Beri tahu saya jika saya melewatkan sesuatu yang jelas saat bermain golf (Ini codegolf pertama saya, saya mungkin melakukan sesuatu yang bodoh: P)
sumber
exit
untuksys.exit()
(lupaexit
ada). Dan Anda benar,__import__
dapat dihapus, yang dihilangkan seperti 20 karakter :)> 6
karakter untuk bernilai aliasing jika Anda menggunakannya dua kali,> 3
karakter jika Anda menggunakannya tiga kali. Saya tidak yakinf=' '
alias itu sepadan (saya hitung dua kali)05AB1E , 93 byte
Terlalu lama ..>.>
Cobalah secara online atau verifikasi semua kasus uji atau verifikasi semua hasil yang mungkin untuk semua kasus uji .
Penjelasan:
sumber