Kompresowanie formuł boolowskich

17

Składnia

~nie
/\i
\/czy
tprawdziwe
ffałszywe
P, Q, FISHitp: zmienne

(Operatory są podane w kolejności pierwszeństwa)

Wprowadzenie

Niektóre formuły logiczne można zmienić na różne formy, aby je skrócić. Na przykład formuła

~(~P /\ ~Q)

można zmienić na krótszą formę

P\/Q

podczas gdy formuła

P \/ ~P

można zmienić na krótszą formę

t

Wyzwanie

W tym wyzwaniem, które są wymagane, aby napisać program, który mając każdy logiczna formuły przy użyciu tylko /\, \/, ~, t, f, nawiasów zmiennych logicznych (w wielkie litery), a spacje, wyjścia najkrótszej formy (ponieważ nie może być więcej niż jedna najkrótsza forma ) w znakach tego wyrażenia, które jest równoważne dla wszystkich przypisań zmiennych. Najkrótszy kod (w dowolnym języku) wygrywa. I / O można wykonać w dowolny rozsądny sposób.

Ponieważ odpowiedzi są trudne do zweryfikowania, pomocne byłoby (ale nie jest to wymagane) podanie krótkiego wyjaśnienia, jak działa kod.

Lily Chung
źródło
W sekcji „Wyzwanie” nie wspominasz o żadnych białych znakach, ale twoje przykłady je mają. Czy powinienem sobie z nimi poradzić?
Victor Stafusa,
4
Myślę, że Florent ma na myśli to, że jest to trudny problem do rozwiązania, nie mówiąc już o grze w golfa. Parser będzie musiał między innymi ustalić, czy dwie dowolne formuły mają takie same warunki prawdy. Zmniejszenie p ^ ~ p jest dość łatwe, jeśli p jest atomowe, ale co z ((A ^ B) v (A ^ C)) ^ ~ (A ^ (BvC))? Myślę, że to fajny problem i jestem ciekawy odpowiedzi. Ale jeśli potrzebujesz krótkich rozwiązań, problem może być bardziej sprzyjający grze w golfa przez A. za pomocą notacji przedrostkowej i B. dostarczenia listy wymaganych redukcji.
dfernig
1
Mam ważne (gra w golfa) rozwiązanie w ponad 5000 znaków. To niedorzeczne ... Składa się z tokenizera, parsera AST, przepisarki AST i generatora wyrażeń.
Florent,
1
Mathematica może to zrobić w jednym wywołaniu funkcji ( BooleanMinimize)
Florent
1
Dla przypomnienia mam teraz 498-znakowe rozwiązanie, którego suma to sha256sum b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a. Właściwy kod opublikuję później, ponieważ nie chcę stłumić kreatywności.
Lily Chung

Odpowiedzi:

2

No tak, zapomniałem opublikować moją odpowiedź. Wykorzystuje dokładnie to samo podejście, którego używa odpowiedź KSab , ale drukuje tylko najkrótsze prawidłowe wyrażenie.

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)

Zauważ, że hash I obliczane wcześniej obejmował nowej linii spływu i było zanim ja grałem def e(x): returnnae=lambda x:

Lily Chung
źródło
1

Python 616

Nie jest szczególnie wydajny, ale działa w rozsądnym czasie dla danych wejściowych, których wyniki mają około 5 lub 6 znaków. Aby sprawdzić ciąg znaków, aby sprawdzić, czy pasuje, przechodzi przez każdą możliwą kombinację wartości prawda / fałsz dla wszystkich zmiennych i upewnia się, że każda z nich się zgadza. Za pomocą tego sprawdza każdy możliwy ciąg znaków złożony z odpowiednich znaków (nawet niekoniecznie poprawny pod względem składniowym).

W rzeczywistości wydrukuje każde równoważne wyrażenie (każdego rozmiaru) i tak naprawdę nigdy się nie zakończy.

Kod:

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

Wejście / Ouput:

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

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

> (P \/ Q) /\ P
P
(P)
...
KSab
źródło