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.

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:

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)
...