Gerrymandering z bramkami logicznymi

16

Funkcja większości jest funkcją logiczną, która pobiera trzy dane logiczne i zwraca najczęściej. Na przykład jeśli maj(x,y,z)jest funkcją większości i Toznacza prawdę, a Ffałsz, to:

maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F

To pytanie dotyczy pisania funkcji boolowskich jako kompozycji funkcji większościowych. Przykład 5-arylowej kompozycji funkcji większościowych to (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Ta funkcja zwraca następujące dane wyjściowe dla tych przykładowych wektorów wejściowych:

(T,T,F,F,F) => maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) => maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) => maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) => maj(F,F,maj(F,T,T)) = maj(F,F,T) = F

Zadanie

Napisz program, który wprowadza dodatnią liczbę całkowitą n oraz listę długości n wektorów boolean i wypisuje drzewo bramek większości, które zwraca wartość true dla wszystkich podanych wektorów, jeśli to możliwe. Funkcja może zwracać wartość true lub false w wektorach, które nie znajdują się na liście ograniczeń.

  • Lista wektorów może być wprowadzana w dowolnym formacie. Jeśli wolisz, zamiast wprowadzania wektora, możesz wprowadzić listę prawdziwych pozycji w wektorze. Na przykład, [TTF,TFT,FTT]lub [[T,T,F],[T,F,T],[F,T,T]]lub [[1,2],[1,3],[2,3]](lista prawdziwych pozycji) są w porządku.

  • Dane wyjściowe mogą być dowolnym poprawnym formatem drzewa. Na przykład,maj(maj(x1,x2,x3),x4,x5) działa. Prawdopodobnie będziesz chciał użyć pojedynczych liczb jako stand-ins dla zmiennych, jak w [[1,2,3],4,5]. Na przykład polerowanie wsteczne 123m45mjest również w porządku.

  • Jeśli żadna funkcja nie działa, twój program powinien wygenerować błąd lub wygenerować wartość falsey.

  • Jeśli działa wiele funkcji, Twój program może zwrócić dowolną z nich. Funkcja nie musi być uproszczona. Na przykład maj(x1,x1,x2)lubx1 są równoważne.

Punktacja

To jest kod golfowy: wygrywa najkrótsze rozwiązanie w bajtach.

Przypadki testowe:

Zauważ, że istnieje wiele możliwych danych wyjściowych dla każdego z tych przypadków, dlatego powinieneś napisać skrypt sprawdzający, który konwertuje dane wyjściowe na funkcję i sprawdź, czy funkcja zwraca wartość true dla każdego z określonych wektorów wejściowych.

Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent

Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)

Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent

Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent

Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error

Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options

Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options 

Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others

Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others

Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
kaptur
źródło
„Skład 5-arytowy funkcji większości jest (x1, x2, x3, x4, x5) => maj (x1, x2, maj (x3, x4, x5))” jak? Jaka powinna być odpowiedź, jeśli x1 = x2 = F; x3 = x4 = x5 = T; ?
tsh
Dodam tabelę prawdy.
Hood
1
Co oznacza wynik 1?
Mhmd
2
Sugerowany tytuł: Gerrymandering z bramkami logicznymi
Robert Fraser
1
@trichoplax Nie, dane wyjściowe dla wszystkich pozostałych wektorów mogą być dowolne. Będę aktualizować, aby to wyraźnie.
Hood

Odpowiedzi:

2

JavaScript (ES6), 260 bajtów

Pobiera dane wejściowe jako tablicę tablic booleanów. Zwraca drzewo bramek 1-indeksowanej większości lub zgłasza błąd rekurencji (1), jeśli nie ma rozwiązania.

Główna funkcja f () rekurencyjnie próbuje znaleźć rozwiązanie, wywołując solver F () i zwiększając maksymalny poziom zagnieżdżenia m przy każdej iteracji.

(1) po długim czasie i przy założeniu nieskończonej pamięci

f=(a,m)=>(F=(a,d,I=a[i=0].map(_=>++i),g=(a,b)=>b[1]?b.reduce((s,i)=>s+g(a,i),0)>1:a[b-1])=>I.find(i=>a.every(a=>g(a,i)))||d&&(I.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(b=>r=b.length==3&&F(a.map(a=>[...a,g(a,b)]),d-1,[...I,b]))&&r))(a,m)||f(a,-~m)

Próbny

Przykład

Poniżej znajduje się tabela sprawdzania poprawności rozwiązania znalezionego dla ostatniego przypadku testowego wersji demonstracyjnej.

12345 | [5,[1,2,4],[3,4,[1,2,3]]]
------+-------------------------------------------------------------
TTTFF | [F,[T,T,F],[T,F,[T,T,T]]] --> [F,T,[T,F,T]] -> [F,T,T] --> T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --> [F,T,[F,T,T]] -> [F,T,T] --> T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --> [T,T,[F,F,T]] -> [T,T,F] --> T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --> [T,F,[T,T,F]] -> [T,F,T] --> T
Arnauld
źródło
Istnieje skuteczne rozwiązanie, które, mam nadzieję, znajdzie ktoś. Tymczasem wydaje mi się, że działa
Hood
2

Mathematica, 121 bajtów

Anonimowa funkcja, która bierze swój drugi argument jako listę list prawdziwych pozycji w wektorze wartości logicznych.

f[n_][s_]:=If[n<3,(Intersection@@s)[[1]],{#/. 2->1,#2/.{2->1,3->2},#3}&@@(1+f[n-1]/@(s-1/.{{0->1},{1->2,0->1},{0->2}}))]

Sformatowane nieco ładniej:

f[n_][s_] := If[n < 3, (Intersection @@s)[[1]],
   {# /. 2 -> 1, #2 /. {2 -> 1, 3 -> 2}, #3} & @@ 
    (1 + f[n - 1] /@ (s - 1 /. {{0 -> 1}, {1 -> 2, 0 -> 1}, {0 -> 2}}))]

Jeśli jest mniej niż trzy zmienne, przecinaj wektory ograniczenia, aby sprawdzić, czy we wszystkich ograniczeniach występuje wspólna „prawda”. Jeśli istnieje, to funkcja stała (x_1, x_2) -> x_i działa, w przeciwnym razie jest to niemożliwe (i zgłasza błąd, próbując pobrać pierwszy element z pustej listy).

W przeciwnym razie zastąp f1=f(x1,x1,x2,x3,,xn1) , f2=f(x1,x2,x2,x3,,xn1) oraz f3=f(x1,x2,x1,x3,,xn1)) , rozwiąż rekurencyjnie każdy z nich, a następnie ustawf=maj(f1(x1,x3,x4,,xn),f2(x1,x2,x4,,xn),f2(x2,x3,x4,,xn)) .

Wyjaśnienie:

Jest to algorytm rekurencyjny, który ogranicza problem znalezienia rozwiązania problemu zmiennej n do znalezienia trzech rozwiązań problemów zmiennej n1 . Kluczem obserwacja sprawia, że tej pracy jest to, że dla f jedna z funkcji szukamy mamy: f(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,),f(x3,x2,x3,))

W pierwszej pozycji wymieniliśmy x2 ox1 , w drugim położeniux3 zx2 , w trzeciej pozycjix1 zx3 .

Gdy poznasz tę tożsamość, algorytm jest jasny: gdy istnieją dwie lub mniej zmiennych, problem jest trywialny. W przeciwnym razie rekurencyjnie rozwiąż trzy problemy reprezentowania f(x1,x1,x3,x4,,xn) , f(x1,x2,x2,x4,,xn) i f(x3,x2,x3,x4,,xn))i weź większość z nich.

Dlaczego to prawda? Cóż, funkcja większości spełnia dwie właściwości:

  1. Jest „komplementarny”. To znaczy, jeśli !x jest negacja x , a maj(!x,!y,!z)=!maj(x,y,z) . W konsekwencji każda funkcja, którą możemy zbudować z funkcji większości, jest komplementarna.

  2. Jest monotoniczny. To znaczy, maj(x,y,False)maj(x,y,True) . Ogólnie rzecz biorąc, jeśli powiemy, że FalseTrue i powiedzmy (x1,,xn)(y1,,yn) jeślixiyi dla wszystkichi , to mówię, że funkcjaf jest monotoniczna jeśli(x1,xn)(y1,,yn) implikujef(x1,xn)f(y1,,yn). Skład funkcji monotonicznych jest monotoniczny, więc każda funkcja, którą możemy zbudować z funkcji większości, jest monotoniczna.

Okazuje się, że uzupełniające się funkcje monotoniczne są dokładnie klasą funkcji, które można zbudować z bram większości.

ff(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,x4,,xn),f(x3,x2,x3,x4,,xn))

Let's set f1(x1,x2,x3,,xn)=f(x1,x1,x3,x4,,xn), f2(x1,,xn)=f(x1,x2,x2,x4,,xn) and f3(x1,,xn)=f(x3,x2,x3,x4,,xn). To show that f=maj(f1,f2,f3), we need to show that for any input, at least two of f1, f2, and f3 are equal to f. We divide up into cases based on the values of x1, x2 and x3. If x1=x2=x3 then f1=f2=f3=f.

Suppose not all of x1, x2, and x3 are the same. By permuting the variables of f, we can assume that x1=x2 and x3 is different and because f is complementary, it suffices to deal with the case x1=x2=False and x3=True. In this case, (x1,x1,x3)=(False,False,True)=(x1,x2,x3), (x1,x2,x2)=(False,False,False)(x1,x2,x3) and (x3,x2,x3)=(True,False,True)(x1,x2,x3). By monotonicity we deduce that f2f1=ff3. If f=False then f2False implies f2=False=f and if f=True then f3True implies f3=True. Thus, at least two of f1, f2, and f3 are equal to f in all cases so f=maj(f1,f2,f3).

Hood
źródło