Mengompresi formula boolean

17

Sintaksis

~tidak
/\dan
\/atau
tbenar
fpalsu
P, Q, FISH, dll: variabel

(Operator diberikan dalam urutan prioritas)

pengantar

Beberapa formula boolean dapat diubah ke bentuk yang berbeda untuk membuatnya lebih pendek. Misalnya rumusnya

~(~P /\ ~Q)

dapat diubah ke bentuk yang lebih pendek

P\/Q

sedangkan formula

P \/ ~P

dapat diubah ke bentuk yang lebih pendek

t

Tantangan

Dalam tantangan ini, Anda diminta untuk menulis sebuah program yang, diberikan rumus boolean hanya menggunakan /\, \/, ~, t, f, kurung, variabel boolean (dalam huruf besar), dan spasi, output bentuk terpendek (karena mungkin ada lebih dari satu bentuk terpendek ) dalam karakter ekspresi yang setara untuk semua penugasan variabel. Kode terpendek (dalam bahasa apa pun) menang. I / O dapat dilakukan dengan cara yang masuk akal.

Juga, karena jawaban sulit untuk diverifikasi, akan sangat membantu (tetapi tidak diharuskan) untuk menyertakan penjelasan singkat tentang bagaimana kode bekerja.

Lily Chung
sumber
Di bagian "Tantangan" Anda, Anda tidak menyebutkan spasi putih, tetapi contoh Anda memilikinya. Haruskah saya menanganinya?
Victor Stafusa
4
Saya pikir poin Florent adalah bahwa itu adalah masalah yang sulit dipecahkan secara umum, apalagi untuk golf. Di antara hal-hal lain, parser harus dapat menentukan apakah dua formula arbitrer memiliki kondisi kebenaran yang sama. Mengurangi p ^ ~ p cukup mudah jika p adalah atom, tetapi bagaimana dengan ((A ^ B) v (A ^ C)) ^ ~ (A ^ (BvC))? Saya pikir ini adalah masalah yang keren dan saya ingin melihat beberapa tanggapan. Tetapi jika Anda menginginkan solusi pendek, masalahnya bisa menjadi lebih kondusif untuk bermain golf oleh A. menggunakan notasi awalan dan B. menyediakan daftar pengurangan yang diperlukan.
dfernig
1
Saya memiliki solusi (golf) yang valid dalam lebih dari 5000 karakter. Ini konyol ... Ini terdiri dari tokenizer, AST-parser, AST-rewriter dan generator ekspresi.
Florent
1
Mathematica dapat melakukannya dalam satu panggilan fungsi ( BooleanMinimize)
Florent
1
Sebagai catatan, saya memiliki solusi 498 karakter sekarang, yang sha256sum adalah b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a. Saya akan memposting kode aktual di kemudian hari, karena saya tidak ingin menahan kreativitas.
Lily Chung

Jawaban:

2

Oh benar, saya lupa pernah benar-benar memposting jawaban saya. Ini menggunakan pendekatan yang persis sama persis yang digunakan jawaban KSab , tetapi hanya mencetak ekspresi valid terpendek.

Python3, 493

e=lambda x:eval(x.replace('\\/','+').replace('/\\','%'),None,w)
class V(int):
 def __add__(s,o):return V(s|o)
 def __mod__(s,o):return V(s*o)
 def __invert__(s):return V(-s+1)
import re;from itertools import product as P;t=V(1);f=V(0);i=input();v=re.findall('[A-Z]+',i)
for k in range(1,len(i)):
 for m in P(''.join(v)+'~/\\tf',repeat=k):
  m=''.join(m)
  try:
   for d in P((V(0),V(1)),repeat=len(v)):
    w=dict(zip(v,d))
    if e(m)!=e(i):raise
  except:continue
  print(m);exit()
print(i)

Perhatikan bahwa hash saya dihitung sebelumnya termasuk baris baru Trailing dan sebelum aku golfed def e(x): returnkee=lambda x:

Lily Chung
sumber
1

Python 616

Tidak terlalu efisien, tetapi bekerja pada waktu yang wajar untuk input yang hasilnya sekitar 5 atau 6 karakter. Untuk memeriksa string untuk melihat apakah cocok, itu loop melalui setiap kemungkinan kombinasi nilai kebenaran / salah untuk semua variabel dan memastikan masing-masing setuju. Menggunakan ini memeriksa setiap string yang mungkin terdiri dari karakter yang relevan (bahkan tidak harus yang secara sintaksis benar).

Ini sebenarnya akan mencetak setiap ekspresi setara (dari setiap ukuran) dan tidak pernah benar-benar berakhir.

Kode:

c=['t','f'];o=['1 ','0 ']
def e(s,v):
 for k in v:s=s.replace(k,v[k])
 return eval(s)
def z(t,p='~/\\() '):
 w=[]
 if p=='':return[t]*(t not in['']+c)
 for s in t.split(p[0]):w.extend(z(s,p[1:]))
 w.sort(key=lambda v:-len(v));return w
def m(v):
 l=list('~\\/()')+v
 for s in l:yield s
 for r in m(v):
    for s in l:yield s+r
def n(x):
 if x<1:yield []
 else:
    for l in n(x-1):
     for b in o:yield[b]+l
t=raw_input();v=z(t)+c;l=len(v)
for s in m(v):
 g=1
 for y in n(l):
    y[-2:]=o;d=dict(zip(v+['/\\','\\/','~'],y+['and ','or ','not ']))
    try:
     if e(s,d)!=e(t,d):g=0
    except:g=0
 if g:print s

Input / Ouput:

> ~(~P /\ ~Q)
Q\/P
P\/Q
...

> P /\ ~P
f
~t
...

> (P \/ Q) /\ P
P
(P)
...
KSab
sumber