Comprimir fórmulas booleanas

17

Sintaxis

~No
/\y
\/o
tverdaderos
ffalsos
P, Q, FISH, etc: Variables

(Los operadores se dan en orden de precedencia)

Introducción

Algunas fórmulas booleanas se pueden cambiar a diferentes formas para acortarlas. Por ejemplo, la fórmula

~(~P /\ ~Q)

se puede cambiar a la forma más corta

P\/Q

mientras que la fórmula

P \/ ~P

se puede cambiar a la forma más corta

t

Desafío

En este desafío, se le requiere para escribir un programa que, dado cualquier fórmula booleana utilizando únicamente /\, \/, ~, t, f, paréntesis variables booleanas (en mayúsculas), y un espacio en blanco, da salida a una forma más corta (ya que puede haber más de una forma más corta ) en caracteres de esa expresión que es equivalente para todas las asignaciones de las variables. El código más corto (en cualquier idioma) gana. La E / S se puede hacer de cualquier manera razonable.

Además, dado que las respuestas son difíciles de verificar, sería útil (pero no es obligatorio) incluir una breve explicación de cómo funciona el código.

Lily Chung
fuente
En su sección "Desafío" no menciona ningún espacio en blanco, pero sus ejemplos los tienen. ¿Debería manejarlos?
Victor Stafusa
44
Creo que el punto de Florent es que es un problema difícil de resolver en general, y mucho menos para el golf. Entre otras cosas, el analizador deberá poder determinar si dos fórmulas arbitrarias tienen las mismas condiciones de verdad. Reducir p ^ ~ p es bastante fácil si p es atómico, pero ¿qué tal ((A ^ B) v (A ^ C)) ^ ~ (A ^ (BvC))? Creo que es un problema genial y tengo curiosidad por ver algunas respuestas. Pero si desea soluciones cortas, el problema podría ser más propicio para el golf mediante A. utilizando la notación de prefijo y B. proporcionando una lista de las reducciones necesarias.
dfernig
1
Tengo una solución válida (golf) en más de 5000 caracteres. Esto es ridículo ... Está compuesto por un tokenizador, un analizador AST, un reescritor AST y un generador de expresiones.
Florent
1
Mathematica puede hacerlo en una llamada de función ( BooleanMinimize)
Florent
1
Para el registro, ahora tengo una solución de 498 caracteres, cuyo sha256sum es b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a. Publicaré el código real en una fecha posterior, ya que no quiero sofocar la creatividad.
Lily Chung

Respuestas:

2

Ah, claro, olvidé publicar mi respuesta. Utiliza esencialmente el mismo enfoque que utiliza la respuesta de KSab , pero imprime solo la expresión válida más corta.

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)

Tenga en cuenta que el hash computé anterior incluido el salto de línea final y era antes Jugamos al golf def e(x): returnae=lambda x:

Lily Chung
fuente
1

Python 616

No es particularmente eficiente, pero funciona en un tiempo razonable para entradas cuyos resultados son de alrededor de 5 o 6 caracteres. Para verificar una cadena para ver si coincide, recorre todas las combinaciones posibles de valores de verdad / falso para todas las variables y se asegura de que cada una esté de acuerdo. Con esto, verifica cada cadena posible compuesta por los caracteres relevantes (ni siquiera necesariamente uno sintácticamente correcto).

En realidad imprimirá cada expresión equivalente (de cada tamaño) y en realidad nunca termina.

Código:

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

Entrada / salida:

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

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

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