Otrzymujesz zestaw instrukcji logicznych. Twoim wyzwaniem jest usunięcie tych, które są sprzeczne z innymi, ale w optymalny sposób (tj. Usunięcie minimalnej liczby instrukcji).

Wyzwanie

Napisz program lub funkcję, która pobiera jako listę listę instrukcji, usuwa minimalną liczbę instrukcji, tak aby istniało rozwiązanie, i wypisuje resztę.

Logika

Instrukcje składają się ze zmiennych A-Z i operatorów między nimi.

Istnieje 5 operatorów : -(nie), v(lub), ^(i), ->(jeśli) i <->(iff).

Tabela prawdy:

A | B | -A | AvB | A^B | A->B | A<->B
0 | 0 |  1 |  0  |  0  |   1  |   1
0 | 1 |  1 |  1  |  0  |   1  |   0
1 | 0 |  0 |  1  |  0  |   0  |   0
1 | 1 |  0 |  1  |  1  |   1  |   1

Operatory te można łączyć z nawiasami ():

A | B | -(AvB) | Av(-A) | A^(-A) | (AvB)->(-B)
0 | 0 |    1   |    1   |    0   |      1
0 | 1 |    0   |    1   |    0   |      0
1 | 0 |    0   |    1   |    0   |      1
1 | 1 |    0   |    1   |    0   |      0

Systemy logiczne składają się z 1 lub więcej instrukcji .

Rozwiązanie do układu logicznego jest stan, w którym wszystkie wypowiedzi są jednocześnie prawdziwe.

Przykłady układów logicznych:

AvB
-(A<->B)
(AvB)->(-B)

Jedynym rozwiązaniem jest A = 1, B = 0.

A^B
-(B<->A)

Ten nie ma rozwiązania ; bez połączenia Ai Boba stwierdzenia są prawdziwe.

Wejście

Otrzymasz zestaw instrukcji jako danych wejściowych. Można to zrobić za pomocą argumentów STDIN lub funkcji, sformatowanych jako tablica (w wygodnym formacie) lub ciąg znaków oddzielony znakiem nowej linii lub znak odstępu.

Oświadczenia będą miały następującą formę (w prawie ABNF ):

statement        = variable / operation
operation        = not-operation / binary-operation
not-operation    = "-" operand
binary-operation = operand binary-operator operand
operand          = variable / "(" operation ")"
variable         = "A"-"Z"
binary-operator  = "v" / "^" / "->" / "<->"

Przykładowe instrukcje:

A
Av(-B)
(A<->(Q^C))v((-B)vH)

Wynik

Musisz zwrócić (ewentualnie) zredukowany zestaw instrukcji w dokładnie takiej formie, w jakiej je otrzymałeś. Ponownie, lista może być sformatowana jako tablica ciągów znaków lub ciąg znaków oddzielony znakiem nowej linii lub znak odstępu.

Zasady

• Zawsze powinieneś usunąć minimalną liczbę instrukcji. Jeśli istnieje wiele możliwych rozwiązań, wypisz jedno z nich.
• Możesz założyć, że dane wejściowe zawsze zawierają co najmniej 1 instrukcję i że żadna instrukcja nie jest powtarzana w danych wejściowych.
• Nie można zakładać, że dane wyjściowe zawsze zawierają instrukcję. (patrz przykłady)
• Korzystanie ze standardowych luk jest sprzeczne z prawidłową odpowiedzią i jedną z nich należy usunąć.
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

Przykłady

Wejście:

A^(-A)

Wynik:

(nothing)

Wejście:

A^B A<->(-B) A<->B

Wynik:

A^B A<->B

Wejście:

["AvB","A^B"]

Wynik:

["AvB","A^B"]

Rubinowy, 299 298 283 279 bajtów

class Object;def * o;!self|o;end;def s;w=join.gsub(/\W/,"").chars.uniq;n=w.size;(0..2**n).any?{|i|n.times{|j|eval(w[j]+"=#{i[j]>0}")};all?{|e|eval([%w[<-> ==],%w[-> *],%w[- !],%w[^ &],%w[v |]].inject(e){|x,i|x.gsub(*i)})}}?self:combination(size-1).map(&:s).max_by(&:size);end;end

• Oczekuje tablicy wyrażeń.
• Jeśli zamierzasz go uruchomić, ustaw $ VERBOSE = zero od wewnątrz rubinu, aby nie wyświetlało się wiele ostrzeżeń o przedefiniowaniu stałych.
• Zauważ, że tak naprawdę ustawia również zmienną „v”, ale to nie robi różnicy.
• Używa wartości prawdy, ponieważ mają już wszystkie wymagane operatory, z wyjątkiem implikacji. Niestety Ruby nie ma klasy boolowskiej, więc musimy wstawić małpę Obiekt, aby uzyskać implikację :)
• Mogłoby to być krótsze, gdybyśmy po prostu ustawili WSZYSTKIE zmienne pisane dużymi literami, ale wtedy uruchomienie zajmie dużo czasu. Prawdopodobnie powinien mieć zastrzeżenie w pytaniu na ten temat.

Nie golfowany:

class Object
  def * o 
    !self|o
  end 
end

def sat? exs 
  #exs: an array of expressions
  s=[%w[<-> ==], %w[-> *], "-!", "^&", %w[v ||]]

  w=exs.join.gsub(/\W/,"").chars.uniq #variable names
  n=w.size
  if (0...2**n).any? {|i|
    n.times do |vi|
      eval("#{w[vi]}=#{i[vi]==1}")
    end 
    exs.all?{|ex|eval(s.inject(ex){|x,i|x.gsub(i[0],i[1])})}
  }
    exs
  else
    exs.combination(exs.size-1).map{|sm|sat?(sm)}.max_by(&:size)
  end
end

Python 3, 431 bajtów

W tej chwili niezbyt golfa, ale myślę, że rzuciłbym piłkę z odpowiedzią. Spróbuj tutaj , g()to główna funkcja.

import re,itertools as H
def g(i):
 y=re.sub(r'\W','',''.join(set(i)).upper());l=i.split()
 def e(s):
  def f(a):
   for v,w in a:exec(v+'='+w)
   return eval(re.sub('[^A-Z()]+',lambda x:{'v':' or ','^':'*','<->':'==','->':'<=','-':'not '}[x.group()],s))
  return[c for c in H.product("01",repeat=len(y))if f(zip(y,c))]
 for n in range(len(l),-1,-1):
  for q in H.combinations(l,n):
   if e('('+')^('.join(q)+')'):return' '.join(q)