16

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 polish`123m45m`

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

or`x1`

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]]]]]
```

"5-ary composition of majority functions is (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))" how? What the answer should be if x1=x2=F; x3=x4=x5=T; ? – tsh – 2018-01-19T05:44:58.033

I will add a truth table. – Hood – 2018-01-19T05:45:24.663

@tsh Does my edit clarify what the function does? – Hood – 2018-01-19T05:52:24.173

maybe i misunderstood the question. seems fine – tsh – 2018-01-19T05:55:06.367

1What does an output of 1 mean? – Mhmd – 2018-01-19T10:21:18.157

2

Suggested title: Gerrymandering with logic gates

– Robert Fraser – 2018-01-19T16:32:54.2331 represents x1 so the function is projection onto the first element

`(x1,x2,x3) => x1`

. – Hood – 2018-01-19T16:33:05.053can

`Input: 6, [TTTFFF,FTFTTF,TFFTFT]`

return`[1, 2, 4]`

? I ask because you have listed other outputs for the other inputs – H.PWiz – 2018-01-19T17:37:21.833Yes, that's a valid output, sorry that was an oversight. – Hood – 2018-01-19T17:49:13.970

The longer solution I posted was just the one my solver found. – Hood – 2018-01-19T17:50:44.243

I'm assuming that in addition to returning true for all the specified vectors, the output should also return false for all other vectors? Worth making it explicit in the spec either way – trichoplax – 2018-10-14T18:40:45.677

1@trichoplax No, the output on all remaining vectors can be anything. I will update to make that explicit. – Hood – 2018-10-14T18:42:36.483