Suatu kegiatan yang kadang-kadang saya lakukan ketika saya bosan adalah menulis beberapa karakter berpasangan. Saya kemudian menggambar garis (di atas tidak pernah di bawah) untuk menghubungkan karakter ini. Sebagai contoh saya dapat menulis dan kemudian saya akan menggambar garis sebagai:
Atau saya mungkin menulis
Setelah saya menggambar garis-garis ini, saya mencoba menggambar loop tertutup di sekitar potongan sehingga loop saya tidak memotong garis yang saya gambar. Sebagai contoh, pada yang pertama, satu-satunya loop yang dapat kita gambar ada di sekitar semuanya, tetapi pada yang kedua kita bisa menggambar lingkaran di sekitar hanya s (atau yang lainnya)
Jika kita bermain-main dengan ini sebentar, kita akan menemukan bahwa beberapa string hanya dapat ditarik sehingga loop tertutup berisi semua atau tidak ada huruf (seperti contoh pertama kami). Kami akan menyebut string tersebut sebagai string yang terhubung dengan baik.
Perhatikan bahwa beberapa string dapat ditarik dengan berbagai cara. Misalnya dapat ditarik dalam dua cara berikut (dan yang ketiga tidak termasuk):
Jika salah satu dari cara-cara ini dapat digambar sedemikian sehingga loop tertutup dapat dibuat untuk mengandung beberapa karakter tanpa memotong salah satu garis, maka string tidak terhubung dengan baik. (jadi tidak terhubung dengan baik)
Tugas
Tugas Anda adalah menulis sebuah program untuk mengidentifikasi string yang terhubung dengan baik. Input Anda akan terdiri dari string di mana setiap karakter muncul beberapa kali, dan output Anda harus menjadi salah satu dari dua nilai konsisten yang berbeda, satu jika string terhubung dengan baik dan yang lainnya sebaliknya.
Selain itu, program Anda harus memiliki makna string yang tertaut dengan baik
Setiap karakter muncul beberapa kali dalam program Anda.
Itu harus menampilkan nilai kebenaran ketika melewati itu sendiri.
Program Anda harus dapat menghasilkan output yang benar untuk string apa pun yang terdiri dari karakter dari ASCII yang dapat dicetak atau program Anda sendiri. Dengan setiap karakter muncul beberapa kali.
Jawaban akan dinilai sebagai panjangnya dalam byte dengan lebih sedikit byte menjadi skor yang lebih baik.
Petunjuk
Sebuah string tidak terhubung dengan baik jika ada substring ketat yang tidak kosong yang berdekatan sehingga setiap karakter muncul beberapa kali dalam substring tersebut.
Uji Kasus
abcbac -> True
abbcac -> False
bbbb -> False
abacbc -> True
abcbabcb -> True
abcbca -> False
sumber
abcbca -> False
.there
.Jawaban:
Regex (ECMAScript 2018 atau .NET),
1401261181009882 byte^(?!(^.*)(.+)(.*$)(?<!^\2|^\1(?=(|(<?(|(?!\8).)*(\8|\3$){1}){2})*$).*(.)+\3$)!?=*)
Ini jauh lebih lambat daripada versi 98 byte, karena
^\1
kiri dari lookahead dan karenanya dievaluasi setelah itu. Lihat di bawah untuk switcheroo sederhana yang mendapatkan kembali kecepatan. Tetapi karena ini, dua TIO di bawah ini terbatas untuk menyelesaikan set kasus uji yang lebih kecil daripada sebelumnya, dan .NET terlalu lambat untuk memeriksa regexnya sendiri.Cobalah online! (ECMAScript 2018)
Cobalah online! (.BERSIH)
Untuk menjatuhkan 18 byte (118 → 100), saya tanpa malu-malu mencuri optimasi yang sangat bagus dari regex Neil yang menghindari perlunya menempatkan lookahead di dalam tampilan negatif (menghasilkan regex tanpa batas 80 byte). Terima kasih, Neil!
Itu menjadi usang ketika menjatuhkan 16 byte lebih luar biasa (98 → 82) berkat ide-ide jaytea yang menyebabkan regex tanpa batas 69 byte! Jauh lebih lambat, tapi itu golf!
Perhatikan bahwa
(|(
no-ops untuk membuat regex-linked dengan baik memiliki hasil membuatnya mengevaluasi sangat lambat di bawah .NET. Mereka tidak memiliki efek ini dalam ECMAScript karena kecocokan dengan lebar nol diperlakukan sebagai tidak cocok .ECMAScript melarang penjumlah pada pernyataan, jadi ini membuat bermain golf persyaratan sumber terbatas lebih sulit. Namun, pada titik ini sangat baik bermain golf sehingga saya tidak berpikir mengangkat batasan tertentu akan membuka kemungkinan golf lebih lanjut.
Tanpa karakter tambahan yang diperlukan untuk membuatnya melewati batasan (
10169 byte):^(?!(.*)(.+)(.*$)(?<!^\2|^\1(?=((((?!\8).)*(\8|\3$)){2})*$).*(.)+\3))
Ini lambat, tetapi pengeditan sederhana ini (hanya untuk 2 byte tambahan) mendapatkan kembali semua kecepatan yang hilang dan lebih banyak lagi:
^(?!(.*)(.+)(.*$)(?<!^\2|(?=\1((((?!\8).)*(\8|\3$)){2})*$)^\1.*(.)+\3))
Saya menulisnya menggunakan molekuler lookahead (
10369 bytes) sebelum mengubahnya menjadi variabel-lookbehind di belakang:^(?!.*(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$))
Dan untuk membantu membuat regex saya sendiri terhubung dengan baik, saya telah menggunakan variasi dari regex di atas:
(?*(.+)(.*$))(?!^\1$|(?*(.)+.*\2$)((((?!\3).)*(\3|\2$)){2})*$)\1
Ketika digunakan dengan
regex -xml,rs -o
, ini mengidentifikasi substring ketat dari input yang berisi angka genap setiap karakter (jika ada). Tentu, saya bisa menulis program non-regex untuk melakukan ini untuk saya, tetapi di mana kesenangannya?sumber
Jelly, 20 byte
Cobalah online!
Baris pertama diabaikan. Itu hanya ada untuk memenuhi syarat bahwa setiap karakter muncul beberapa kali.
Baris berikutnya pertama
Ġ
roups indeks dengan nilainya. Jika kita kemudian mengambil panjang setiap sublist di daftar yang dihasilkan (Ẉ
), kita mendapatkan berapa kali setiap karakter muncul. Untuk memeriksa apakah semua ini adalah non-genap, kami mendapatkan yang terakhirḂ
dari setiap penghitungan dan menanyakan apakah ada nilaiẸ
kebenaran (bukan nol).Oleh karena itu, tautan helper ini mengembalikan apakah suatu substring tidak dapat dilingkari.
Di tautan utama, kami mengambil semua substring dari input (
Ẇ
),Ṗ
op off yang terakhir (sehingga kami tidak memeriksa apakah seluruh string dapat dilingkari), dan menjalankan helper link (Ç
) pada€
substring lainnya. Hasilnya kemudian apakahẠ
substring ll tidak dapat dilingkari.sumber
J , 34 byte
Cobalah online!
-8 Bytes berkat FrownyFrog
asli
J , 42 byte
Cobalah online!
penjelasan
sumber
abc
, hanya entri Perl tidak "gagal" di atasnya. (Ini memiliki masalah lain.)1:@':.,02|~*'=1(#.,)*/@(0=2|#/.~)\.\
2:@':.,|~*'>1(#.,)*/@(1>2|#/.~)\.\
juga tampaknya validPython 3.8 (pra-rilis) , 66 byte
Cobalah online!
Era Ekspresi Penugasan ada pada kita. Dengan PEP 572 termasuk dalam Python 3.8, golf tidak akan pernah sama. Anda dapat menginstal pratinjau pengembang awal 3.8.0a1 di sini .
Ekspresi penugasan memungkinkan Anda gunakan
:=
untuk menetapkan inline variabel saat mengevaluasi nilai itu. Misalnya,(a:=2, a+1)
memberi(2, 3)
. Ini tentu saja dapat digunakan untuk menyimpan variabel untuk digunakan kembali, tetapi di sini kita melangkah lebih jauh dan menggunakannya sebagai akumulator dalam pemahaman.Misalnya, kode ini menghitung jumlah kumulatif
[1, 3, 6]
Perhatikan bagaimana setiap lulus melalui pemahaman daftar, jumlah kumulatif
t
meningkat sebesarx
dan nilai baru disimpan dalam daftar yang dihasilkan oleh pemahaman.Demikian pula,
b:=b^{c}
memperbarui set karakterb
untuk beralih apakah itu termasuk karakterc
, dan mengevaluasi ke nilai barub
. Jadi, kode ini[b:=b^{c}for c in l]
lebih dari satu karakterc
dalaml
dan mengakumulasikan kumpulan karakter yang terlihat beberapa kali ganjil di setiap awalan yang tidak kosong.Daftar ini diperiksa untuk duplikat dengan membuatnya menjadi kumpulan pemahaman dan melihat apakah panjangnya lebih kecil dari itu
s
, yang berarti bahwa beberapa pengulangan runtuh. Jika demikian, pengulangan berarti bahwa dalam porsi yangs
terlihat di antara saat-saat itu setiap karakter menemukan angka genap, membuat string tidak terhubung dengan baik. Python tidak mengizinkan set himpunan menjadi tidak dapat pecah, jadi set batin dikonversi ke string sebagai gantinya.Set
b
diinisialisasi sebagai argumen opsional, dan berhasil dimodifikasi dalam lingkup fungsi. Saya khawatir ini akan membuat fungsi tersebut tidak dapat digunakan kembali, tetapi tampaknya untuk mengatur ulang antar berjalan.Untuk pembatasan sumber, karakter yang tidak berpasangan dimasukkan ke dalam komentar di bagian akhir. Menulis
for(c)in l
daripadafor c in l
membatalkan paren tambahan secara gratis. Kami menempatkanid
ke dalam set awalb
, yang tidak berbahaya karena dapat dimulai sebagai set apa pun, tetapi set kosong tidak dapat ditulis{}
karena Python akan membuat kamus kosong. Karena surat-surati
dan did
antara mereka yang membutuhkan pasangan, kita dapat menempatkan fungsinya diid
sana.Perhatikan bahwa output kode meniadakan boolean, sehingga kode itu akan memberikan
False
dirinya sendiri dengan benar .sumber
Python 2 , 74 byte
Cobalah online!
Iterasi melalui string, melacak
P
set karakter yang dilihat dalam jumlah ganjil sejauh ini. Daftard
menyimpan semua nilai masa laluP
, dan jika melihat saat iniP
sudah dalamd
, ini berarti bahwa dalam karakter yang terlihat sejak saat itu, setiap karakter telah muncul beberapa kali genap. Jika demikian, periksa apakah kami telah melalui seluruh input: jika ada, terima karena seluruh string dipasangkan seperti yang diharapkan, dan jika tidak, tolak.Sekarang tentang batasan sumber. Karakter yang membutuhkan pasangan dimasukkan ke berbagai tempat yang tidak berbahaya, yang digarisbawahi di bawah ini:
The
f<s
mengevaluasi ke0
saat memasangkan offf
, mengambil keuntungan dari nama fungsi juga menjadif
sehingga didefinisikan (pada saat fungsi ini dipanggil.) Yang0^0
menyerap sebuah^
simbol.The
0
dalamP={0}
sangat disayangkan: Python{}
mengevaluasi ke dict kosong daripada himpunan kosong seperti yang kita inginkan, dan di sini kita dapat dimasukkan ke dalam setiap elemen non-karakter dan itu akan menjadi berbahaya. Saya tidak melihat ada cadangan untuk dimasukkan, dan telah dimasukkan0
dan digandakanbmn0
, biaya 2 byte. Perhatikan bahwa argumen awal dievaluasi ketika fungsi didefinisikan, sehingga variabel yang kita definisikan sendiri tidak dapat dimasukkan ke sini.sumber
Perl 6 , 76 byte
Cobalah online!
A Apapun lambda yang mengembalikan Persimpangan Tidak Ada Persimpangan yang dapat didekati dengan nilai true / falsey. Saya akan merekomendasikan untuk tidak menghapus hasil
?
pengembalian yang boolify, jika tidak, output akan menjadi agak besar .Solusi ini sedikit lebih kompleks dari yang diperlukan, karena beberapa fungsi yang terlibat yang dibatalkan, misalnya
..
,all
,>>
,%%
dll Tanpa pembatasan sumber, ini bisa menjadi 43 bytes:Cobalah online!
Penjelasan:
sumber
Perl 5
-p
,94,86,78 byteouput 0 jika terhubung dengan baik 1 sebaliknya.
78 byte
86 byte
94 byte
Bagaimana itu bekerja
-p
dengan}{
trik akhir untuk menghasilkan$\
di akhirm-.+(?{
..})(?!)-
, untuk mengeksekusi kode pada semua substring yang tidak kosong (.+
cocok dengan seluruh string terlebih dahulu, dan setelah mengeksekusi kode antara(?{
..})
backtracks karena gagal paksa(?!)
$Q|=@q&grp,
sampah karena pembatasan sumber$\|=
integer bitwise atau assignment, jika hampir ada 1,$\
akan menjadi 1 (true), secara default itu kosong (false)$&eq$_
kasus di mana sbustring adalah seluruh string bitwise xored^
dengan "tidak ada kejadian karakter yang aneh"($g=$&)=~/./g
untuk menyalin substring yang cocok ke$g
(karena akan overwirtten setelah pertandingan regex berikutnya) dan mengembalikan array karakter substring./^/
sampah yang dievaluasi menjadi 1grep
1&(@m=$g=~/\Q$_/g),
untuk setiap karakter dalam substring mendapatkan array karakter dalam$g
pencocokan itu sendiri, array dalam skalar mengevaluasi ukurannya dangrep
menyaring pemburu dengan kejadian aneh1&x
setara denganx%2==1
sumber
Retina ,
15096 byteCobalah online! Tautan termasuk kasus uji, termasuk dirinya sendiri. Sunting: Memotong regex yang asli sedikit dengan bantuan dari @Deadcode, lalu kembali dengan agak kurang mewah untuk mempertahankan tata letak sumber. Penjelasan:
Menyatakan bahwa tidak
\3
ada substring yang cocok dengan batasan berikut.Menegaskan bahwa substring bukan keseluruhan string asli.
Tegaskan bahwa tidak ada karakter
\6
yang:Untuk melewati batasan tata letak sumber, saya mengganti
((((
dengan(?:(^?(?:(
dan((
dengan(|(
. Saya masih memiliki satu kendala sumber))
tersisa dan karakter!()1<{}
tersisa, jadi saya mengubah+
ke dalam{1,}
dan memasukkan yang tidak berguna(?!,<)?
untuk mengkonsumsi sisanya.sumber
C # (Visual C # Interactive Compiler) ,
208206200198 byteCobalah online!
-2 byte terima kasih kepada @KevinCruijssen!
Akhirnya mendapatkannya di bawah 200, jadi saya mungkin bermain golf untuk saat ini :) Saya akhirnya membuat TIO kedua untuk menguji hal-hal berdasarkan jawaban sebelumnya.
Cobalah online!
Hal-hal yang membuat tugas ini rumit:
==
tidak diizinkan++
tidak diizinkanAll()
Fungsi Linq tidak diizinkanKode yang dikomentari di bawah ini:
sumber
Python 2 , 108 byte
Cobalah online!
-2 Terima kasih kepada Ørjan Johansen .
sumber
Brachylog , 16 byte
Cobalah online!
Mencetak
false.
untuk contoh yang benar dantrue.
untuk contoh yang salah. Versi TIO terlalu lambat untuk ditangani sendiri, tetapi jelas terkait dengan baik karena string dengan karakter unik diulang dua kali.Penjelasan
sumber
05AB1E ,
2220 byteOutput
1
jika string terhubung dengan baik, dan0
jika string tidak terhubung dengan baik.Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
Program dasar adalah
ŒsKεsS¢ÈP}à
( 11 byte ), yang menghasilkan0
jika terhubung dengan baik dan1
jika tidak terhubung dengan baik. TrailingÈ
(is_even) adalah semi no-op yang membalikkan output, jadi1
untuk string yang terhubung dengan baik dan0
untuk string yang tidak terhubung dengan baik. Bagian lain adalah no-ops untuk mematuhi aturan tantangan.sumber