The majority function is a boolean function which takes three boolean inputs and returns the most common. For instance if maj(x,y,z)
is the majority function and T
denotes true and F
denotes false then:
maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F
This question concerns writing boolean functions as compositions of majority functions. An example of a 5-ary composition of majority functions is (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))
. This function returns the following output on these sample input vectors:
(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
Task
Write a program which inputs a positive integer n and a list of length n vectors of booleans and outputs a tree of majority gates that returns true on all of the given vectors if possible. The function may return either true or false on vectors not in the list of constraints.
The list of vectors may be input in any format you like. If you prefer, instead of inputting the vector, you may input the list of true positions in the vector. So for instance,
[TTF,TFT,FTT]
or[[T,T,F],[T,F,T],[F,T,T]]
or[[1,2],[1,3],[2,3]]
(list of true positions) are all fine.Output can be any valid tree format. For instance,
maj(maj(x1,x2,x3),x4,x5)
works. You will probably want to use single numbers as stand-ins for variables, as in[[1,2,3],4,5]
. Reverse polish123m45m
is also okay, for instance.If there is no function that works, your program should generate an error or output a falsey value.
If there are multiple functions that work, your program can return any of them. The function does not need to be simplified. For instance,
maj(x1,x1,x2)
orx1
are equivalent.
Scoring
This is code golf: Shortest solution in bytes wins.
Test cases:
Note that there are many possible outputs for each of these cases, so you should write a checker script that converts your output to a function and check that your function returns true on each of the specified input vectors.
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]]]]]