pengantar
Misi Anda dalam hidup itu sederhana: Buktikan orang salah di internet!
Untuk melakukan ini, Anda biasanya hati-hati menganalisis pernyataan mereka dan menunjukkan kontradiksi di dalamnya.
Sudah waktunya untuk mengotomatisasi ini, tetapi karena kita malas, kami ingin membuktikan orang salah dengan upaya yang paling sedikit (baca: kode terpendek) yang mungkin.
Spesifikasi
Memasukkan
Masukan Anda akan menjadi rumus dalam bentuk normal konjungtif . Untuk format, Anda dapat menggunakan format di bawah ini atau menentukan sendiri, berdasarkan kebutuhan bahasa Anda (Anda tidak dapat menyandikan lebih banyak dalam format daripada CNF murni sekalipun). Kasing uji (di sini) disediakan dalam format di bawah ini (meskipun tidak akan terlalu sulit membuat sendiri).
Input Anda akan berupa daftar daftar variabel (Anda juga dapat membacanya sebagai string / memerlukan string). Input adalah rumus dalam bentuk normal konjungtif (CNF) yang ditulis sebagai satu set klausa, masing-masing menjadi daftar dua daftar. Daftar pertama dalam klausa mengkodekan literal positif (variabel), daftar kedua mengkodekan literal negatif (dinegasikan) (variabel). Setiap variabel dalam klausa adalah OR'ed bersama dan semua klausa adalah AND'ed bersama.
Untuk membuatnya lebih jelas: [[[A,B],[C]],[[C,A],[B]],[[B],[A]]]
dapat dibaca sebagai:
(A OR B OR (NOT C)) AND (C OR A OR (NOT B)) AND (B OR (NOT A))
Keluaran
Outputnya adalah boolean, misalnya nilai kebenaran atau nilai palsu.
Melakukan apa?
Sederhana: Periksa apakah rumus yang diberikan sudah memuaskan, misalnya apakah ada beberapa penugasan benar dan salah untuk semua variabel sehingga keseluruhan rumus menghasilkan "benar". Output Anda akan "benar" jika rumusnya memuaskan dan "salah" jika tidak.
Fun-Fact: Ini adalah masalah NP-complete dalam kasus umum.
Catatan: Membuat tabel kebenaran dan memeriksa apakah entri yang dihasilkan benar, diizinkan.
Kasus sudut
Jika Anda mendapatkan daftar level 3 kosong, maka tidak ada variabel (positif / negatif) dalam klausa itu - input yang valid.
Anda dapat membiarkan case sudut lainnya tidak terdefinisi jika Anda mau.
Anda juga dapat mengembalikan true pada formula kosong (daftar level 1) dan false pada klausa kosong (daftar level 2).
Yang menang?
Ini adalah kode-golf sehingga jawaban tersingkat dalam byte menang!
Aturan standar berlaku tentu saja.
Kasus uji
[[[P],[Q,R]],[[Q,R],[P]],[[Q],[P,R]]] -> true
[[[],[P]],[[S],[]],[[R],[P]],[[U],[Q]],[[X],[R]],[[Q],[S]],[[],[P,U]],[[W],[Q,U]]] -> true
[[[],[P,Q]],[[Q,P],[]],[[P],[Q]],[[Q],[P]]] -> false
[[[P],[]],[[],[P,S]],[[P,T],[]],[[Q],[R]],[[],[R,S]],[[],[P,Q,R]],[[],[P]]] -> false
optional behavior (not mandatory, may be left undefined):
[] -> true (empty formula)
[[]] -> false (empty clause)
[[[],[]]] -> false (empty clause)
(A OR B OR (NOT C)) AND (C OR A OR (NOT B)) AND (B OR (NOT A))
?{{P,Q},{P,!Q},{!P,Q},{!P,!Q}}
(tidak dalam urutan ini) yang dapat dengan mudah ditampilkan adalah sebuah kontradiksi. Untuk 4): Ini adalah kontradiksi sepele karena ituP AND ... AND (NOT P)
jelas tidak pernah benar untuk nilai P.Jawaban:
Mathematica, 12 byte
Nah, ada built-in ...
Format input adalah
And[Or[a, b, Not[c], Not[d]], Or[...], ...]
. Ini tidak bekerja dengan benar untuk sub-ekspresi kosong, karenaOr[]
iniFalse
danAnd[]
adalahTrue
.Sebagai catatan, solusi yang menerima format berbasis daftar dari tantangan dan melakukan konversi itu sendiri adalah 44 byte, tetapi OP mengklarifikasi dalam komentar bahwa format apa pun baik-baik saja asalkan tidak menyandikan informasi tambahan:
sumber
S a t i s f i a b l e Q
akan menyelesaikan masalah. Baru kemudian, pemahaman membaca mengetuk pintu ...Haskell,
203200 byteTantangan ini layak mendapat jawaban tidak-built-in, jadi begini saja. Cobalah di ideone . Algoritma hanya mencoba semua tugas variabel dan memeriksa apakah salah satu dari mereka memenuhi formula.
Input dalam bentuk
[([],["P","Q"]),(["Q","P"],[]),(["P"],["Q"]),(["Q"],["P"])]
, meskipun alih-alih string, setiap tipe dengan kesetaraan akan berfungsi.Kode tidak dikunci:
sumber
JavaScript 6, 69B
Pemakaian:
sumber