Boolesche Formeln komprimieren

16

Syntax

~nicht
/\und
\/oder
twahr
ffalsch
P, Q, FISH, etc: Variablen

(Die Operatoren werden in der Rangfolge angegeben.)

Einführung

Einige Boolesche Formeln können in andere Formen geändert werden, um sie zu verkürzen. Zum Beispiel die Formel

~(~P /\ ~Q)

kann in die kürzere Form geändert werden

P\/Q

während die Formel

P \/ ~P

kann in die kürzere Form geändert werden

t

Herausforderung

In dieser Herausforderung sind Sie verpflichtet , ein Programm zu schreiben , dass, da jede Boolesche Formel nur /\, \/, ~, t, f, Klammern, boolean Variablen (in Großbuchstaben) und Leerzeichen, gibt eine kürzeste Form (da es mehr sein kann als eine kürzeste Form ) in Zeichen des Ausdrucks, der für alle Zuweisungen der Variablen äquivalent ist. Der kürzeste Code (in einer beliebigen Sprache) gewinnt. I / O kann auf jede vernünftige Weise erfolgen.

Da sich die Antworten nur schwer überprüfen lassen, ist es hilfreich (aber nicht erforderlich), eine kurze Erläuterung der Funktionsweise des Codes beizufügen.

Lily Chung
quelle
In Ihrem Abschnitt "Herausforderung" erwähnen Sie keine Leerzeichen, aber Ihre Beispiele haben sie. Soll ich damit umgehen?
Victor Stafusa
4
Ich denke, Florents Punkt ist, dass es ein schwieriges Problem ist, es im Allgemeinen zu lösen, geschweige denn Golf zu spielen. Unter anderem muss der Parser feststellen können, ob zwei beliebige Formeln die gleichen Wahrheitsbedingungen haben. Die Reduktion von p ^ ~ p ist einfach genug, wenn p atomar ist, aber wie wäre es mit ((A ^ B) v (A ^ C)) ^ ~ (A ^ (BvC))? Ich halte es für ein cooles Problem und bin gespannt auf einige Antworten. Wenn Sie jedoch kurze Lösungen wünschen, könnte das Problem durch A. mit Präfixnotation und B. mit einer Liste der erforderlichen Reduktionen für das Golfen förderlicher gemacht werden.
dfernig
1
Ich habe eine gültige (Golf-) Lösung mit mehr als 5000 Zeichen. Das ist lächerlich ... Es besteht aus einem Tokenizer, einem AST-Parser, einem AST-Rewriter und einem Ausdrucksgenerator.
Florent
1
Mathematica kann es in einem Funktionsaufruf ( BooleanMinimize) tun
Florent
1
Für die Aufzeichnung habe ich jetzt eine 498-Zeichen-Lösung, deren sha256sum ist b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a. Ich werde den eigentlichen Code zu einem späteren Zeitpunkt veröffentlichen, da ich die Kreativität nicht unterdrücken möchte.
Lily Chung

Antworten:

2

Oh richtig, ich habe vergessen, meine Antwort jemals wirklich zu posten. Es verwendet im Wesentlichen denselben Ansatz wie die Antwort von KSab , gibt jedoch nur den kürzesten gültigen Ausdruck aus.

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)

Beachten Sie, dass der Hash, den ich zuvor berechnet habe, die abschließende Newline enthielt, bevor ich Golf gespielt def e(x): returnhabee=lambda x:

Lily Chung
quelle
1

Python 616

Nicht besonders effizient, arbeitet aber in angemessener Zeit für Eingaben, deren Ergebnisse etwa 5 oder 6 Zeichen betragen. Um eine Zeichenfolge auf Übereinstimmung zu prüfen, durchläuft sie alle möglichen Kombinationen von Wahr- und Falschwerten für alle Variablen und stellt sicher, dass alle übereinstimmen. Damit prüft es jeden möglichen String, der aus den relevanten Zeichen besteht (nicht einmal notwendigerweise ein syntaktisch korrekter).

Tatsächlich wird jeder äquivalente Ausdruck (in jeder Größe) gedruckt und wird nie beendet.

Code:

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

Eingabe / Ausgabe:

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

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

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