Pertimbangkan tata bahasa lebih alfabet { 0
, 1
, ?
, :
} yang didefinisikan oleh aturan produksi
s →
0
┃1
┃0
?
s:
s ┃1
?
s:
s
Diberikan string yang dihasilkan dari s , parsing sebagai ekspresi di mana ?:
asosiatif-benar (misalnya, a?B?X:Y:c?d:e?f:g
berarti a?(B?X:Y):(c?d:(e?f:g))
) dan mengevaluasinya dengan semantik berikut:
eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)
Jika hasilnya 0 , hasilkan beberapa nilai tetap; jika output 1 , output nilai tetap berbeda. Tentukan nilai output yang Anda pilih (misalnya 0
/ 1
, atau False
/ True
) dalam jawaban Anda.
Uji kasus
0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0
Aturan
- Anda tidak boleh menggunakan bahasa bawaan yang menafsirkan string sebagai kode dalam beberapa bahasa pemrograman dan menjalankannya (seperti JavaScript / Perl / Ruby / Python
eval
). - Yang mengatakan, kode Anda sebenarnya tidak harus diuraikan dan kemudian mengevaluasi string input. Anda dapat mengambil pendekatan apa pun untuk mencapai hasil yang setara dan tidak melanggar aturan sebelumnya.
- Program Anda akan diperiksa
perl -le 'print eval<>'
. - Kode terpendek (dalam byte) menang.
S → T | T ? S : S
,T → 0 | 1
, menghilangkan kebutuhan untuk berbicara tentang associativity?Jawaban:
GolfScript, 21 byte
Ini menghasilkan
0
atau1
. Input diasumsikan memiliki satu trailing newline. Menggunakan~
(yang mengevaluasi string) akan menghemat byte:Ini didasarkan pada http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .
sumber
Retina , 23 byte
Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)
Penjelasan
Ini sebenarnya cukup sederhana. Input dikurangi ke hasil dengan berulang kali (
+
) mengevaluasi terner yang hanya mengandung literal. Untuk memastikan ini dilakukan dengan benar secara asosiatif, kami mencari kecocokan dari kanan ke kiri (r
) dan hanya mengganti kecocokan terakhir yang kami temukan (-1=
).Regex itu sendiri cocok
0\?.:
dan menghapusnya (hanya menyisakan barang setelah:
) atau1\?.:.
dan menggantinya dengan nilai setelah?
.sumber
1
pertandingan st bukan-1
st?Haskell,
106 101 100 9083 byteIni sangat bergantung pada kemampuan pencocokan pola pola Haskell. Pertama-tama, kita membalikkan string sehingga kita bisa mencari kejadian pertama
b:a?x
(yang biasanya dibaca sebagaix?a:b
) dan menggantinya dengan nilainya. Ini secara otomatis memberikan asosiasi yang tepat . Di sini kita menggunakanx:xs
pola. Inilah fungsif
yang dilakukan. Kemudian kami pada dasarnya berlakuf
untuk output itu berulang-ulang, sampai kami memiliki satu nomor (0 atau 1) yang tersisa.Terima kasih @ Lynn untuk 12 byte!
sumber
Brainfuck,
826463 byteOutputnya adalah
\xff
untuk0
dan\x00
untuk1
. Implementasi brainfuck harus memungkinkan untuk pergi ke kiri sel awal.Ini pada dasarnya menggunakan pendekatan yang sama dengan jawaban Python xsot , tetapi percabangannya mungkin lebih sulit untuk diikuti dibandingkan dengan pengiriman 82 byte awal saya:
(Untuk solusi ini, output adalah
\xfe
untuk0
dan\xff
untuk1
, dan kompatibilitas yang lebih luas dicapai ketika input berakhir dengan baris baru.)Jika Anda tidak dapat repot-repot menganalisis solusi xsot, idenya adalah ini: Lanjutkan dari kiri ke kanan. Jika Anda melihat
1?
maka dengan rakus buanglah. Jika Anda melihat0?
maka buang semuanya antara itu dan yang sesuai:
. Ketika?
tidak muncul sebagai karakter kedua, hentikan perulangan dan cetak karakter pertama dari string yang tersisa.Jadi, solusi 82-byte sebenarnya mencerminkan skema itu dengan cukup dekat. Loop dalam menangani
0?
, seperti loop dalam xsot. Beberapa perhatian diambil untuk memasuki loop utama tanpa memeriksa karakter input apa pun; yaitu, kami ingin memeriksa apakah karakter kedua?
hanya sekali di akhir loop utama, dan tidak juga di awal sebelum memasukkan loop utama.Solusi 63-byte pada dasarnya menggabungkan loop dalam dan luar menjadi satu, yang saya duga dimungkinkan karena kesamaan antara loop tersebut. Tata letak memori dalam loop utama dapat digambarkan sebagai:
di mana
[x]
berarti sel saat ini -s
dimulai sebagai nilai bukan nol boneka yang hanya menunjukkan kita masih mengulang, dan segera ditimpa dengan karakter input (baik0
atau1
). Thed
sel memegang (negatif) kedalaman dalam kasus kita berada di tengah-tengah0?
, sebaliknya0
. Thec
akan menjadi baik?
atau:
atau baris baru atau EOF.Setelah memperbarui
s
danc
, kami menangani0?
kasing dengan memperbarui yangd
sesuai dan menyesuaikan pointer, jika tidak kami menggunakan nilai saat inic
sebagai nilaid
dalam iterasi berikutnya, atau berhenti jika kami selesai.sumber
Python 2,
76747372 byteDengan input sebagai string literal yang harus dihindari
raw_
.Outputnya
0
atau1
diikuti oleh<built-in function id>
.sumber
3>>int(c)
`id`
trik ...! Bagus :)Python 2, 89 byte
Input diambil sebagai string literal.
sumber
Grime ,
3431 byteMencetak
1
untuk input yang benar dan0
yang salah. Cobalah online! Kasing uji terakhir sayangnya kehabisan memori pada TIO.Penjelasan
Asosiatif-kanan pada dasarnya berarti bahwa
a?b:c
,a
selalu0
atau1
tidak pernah, merupakan ekspresi yang lebih panjang. Saya hanya akan secara rekursif mendefinisikan pola yang cocok dengan ekspresi yang benar seperti itu, dan memeriksa input yang menentangnya. Ini juga tidak perlu untuk memeriksa bahwa setiap:
benar-benar a:
, jika?
s semua dicentang: ada jumlah?
s dan:
s yang sama dalam input, dan jika ada?
yang salah diklasifikasikan sebagai:
, yang sesuai:
akan gagal untuk mencocokkan, dan pencocokan Grime mesin akan mundur.sumber
Haskell,
79 71 70 62 6056 byteSunting: Terima kasih kepada @Zgarb selama 3 byte dan untuk @nimi selama 4 byte!
Ini pendekatan rekursif
yang agak menyalahgunakan aturan "beberapa nilai tetap". Sunting: Menyingkirkan tuple tidak hanya menghemat 8 byte, ia juga menghasilkan output yang lebih bagus:"0"
atau"1"
.Versi tidak disatukan:
Bagaimana cara kerjanya?
The
eval
Fungsi melintasi pohon implisit dari ekspresidan mengembalikan tuple formulir
(result, rest)
.Pola pertama
(x:'?':r1)
cocokx
dengan'1'
danr1
ke"0?0:1:0?1:0"
. Melamar secara rekursifeval
untukr1
mengevaluasi sub ekspresi0?0:1
dan pengembalian(0,":0?1:0")
. Mencocokkan ini dengan(a,':':r2)
hasil polaa=0
danr2=0?1:0
. Sub-formula ini juga dievaluasi secara rekursif sehinggab='0'
danr3=""
. Periksa apakahx
ini'1'
atau'0'
dan kembali baik(a, r3)
atau(b, r3)
.sumber
x>'0'
bekerja di tempatx=='1'
?':'
dengan_
.:
. Terima kasih lagi!if .. then .. else
denganlast$e s:[a:tail(e s)|x>'0']
.JavaScript (ES6), 53 byte
Pengembalian
0
atau1
untuk input yang valid; hang untuk input yang tidak valid. Penjelasan: karena membalikkan string adalah canggung dalam JavaScript, upaya 71-byte pertama saya berhasil dengan menggunakan lookahead negatif untuk?
yang akan mengganggu asosiatif:Karena ini agak lama saya bertanya-tanya apakah saya bisa memperbaiki masalah dengan memasukkan pengambilan keputusan ke dalam regexp. Ternyata, itu bukan kesuksesan langsung, karena juga butuh 71 byte:
Kemudian terpikir olehku bahwa
0?0:
dan0?1:
selalu tanpa usaha, tanpa memperhatikan asosiatif. Ini menyelamatkan saya hampir 25%.sumber
f=
. Saya belum memeriksa apakah jumlah byte Anda memperhitungkannya atau tidak.Perl, 32 + 1 (
-p
flag) = 33 bytePenghargaan penuh untuk @Mitch Swartch , karena solusinya 14 byte lebih pendek dari saya!
Terima kasih juga kepada @Neil yang menyarankan solusi 1 byte lebih lama dari Mitch.
Membutuhkan
-p
flag, juga-M5.010
atau-E
untuk menjalankan. Contohnya :Penjelasan : Ini pada dasarnya mengurangi blok
a?b:c
(mulai dari akhir untuk memastikan tidak ada yang?
mengikuti) menjadib
atauc
tergantung pada kebenarana
, berulang dan berulang sampai string hanya berisi1
atau0
.sumber
-
tidak diperhitungkan skor Anda? Hrm Menarik ... Jawaban bagus!perl -e '<code>'
dengan menggunakan sehinggap
hanya menambah biaya 1 byteperl -pe '<code>'
.?
, saya bisa memotong ini menjadi 34 byte dengan cara ini.s/.*\K(1\?(.)..|0\?..)/\2/&&redo
Python 3,
9369 byteInput adalah string sebagai daftar karakter, output dapat
"0"
atau"1"
Versi tidak disatukan:
Percobaan lain, tetapi dengan byte lebih banyak:
sumber
def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x
, dan untuk Python 3 dengan jarak edit kecil untuk Anda, adadef f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r
.SED,
75 74 68(40 +1 untuk -r) 41sumber
(.*)
dan menambahkan istilah penggantian tambahan.\3
bukan\2
. Anda juga dapat bergabung dengan garis;
untuk mendapatkan:;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t
.\3
jadi itu berarti saya tidak sengaja menyalin versi sebelumnya. Saya tahu tentang titik koma. Tapi yuck, mengapa Anda ingin menggunakan titik koma.Utilitas Bash + GNU, 42
Ide yang mirip dengan sebagian besar jawaban pencocokan pola lainnya.
Ideone .
sumber
0
kasing, yang menghemat 5 byte.