A função majoritária é uma função booleana que recebe três entradas booleanas e retorna a mais comum. Por exemplo, se maj(x,y,z)
é a função majoritária e T
denota verdadeiro e F
denota falso, então:
maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F
Esta questão diz respeito à escrita de funções booleanas como composições das funções majoritárias. Um exemplo de uma composição de 5 árias de funções majoritárias é (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))
. Esta função retorna a seguinte saída nesses vetores de entrada de amostra:
(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
Tarefa
Escreva um programa que insira um número inteiro positivo n e uma lista de vetores de comprimento n de booleanos e produza uma árvore de portas majoritárias que retorne true em todos os vetores fornecidos, se possível. A função pode retornar verdadeiro ou falso em vetores que não estão na lista de restrições.
A lista de vetores pode ser inserida em qualquer formato que você desejar. Se preferir, em vez de inserir o vetor, você pode inserir a lista de posições verdadeiras no vetor. Por exemplo,
[TTF,TFT,FTT]
ou[[T,T,F],[T,F,T],[F,T,T]]
ou[[1,2],[1,3],[2,3]]
(lista de posições verdadeiras) estão bem.A saída pode ser qualquer formato de árvore válido. Por exemplo,
maj(maj(x1,x2,x3),x4,x5)
funciona. Você provavelmente desejará usar números únicos como substitutos para variáveis, como em[[1,2,3],4,5]
. O polimento reverso123m45m
também é bom, por exemplo.Se não houver nenhuma função que funcione, seu programa deve gerar um erro ou gerar um valor falsey.
Se houver várias funções que funcionem, seu programa poderá retornar qualquer uma delas. A função não precisa ser simplificada. Por exemplo,
maj(x1,x1,x2)
oux1
são equivalentes.
Pontuação
Este é o código golf: A solução mais curta em bytes vence.
Casos de teste:
Observe que existem muitas saídas possíveis para cada um desses casos, portanto, você deve escrever um script verificador que converta sua saída em uma função e verifique se sua função retorna verdadeira em cada um dos vetores de entrada especificados.
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]]]]]
Respostas:
JavaScript (ES6), 260 bytes
Recebe entrada como uma matriz de matrizes de booleanos. Retorna uma árvore de portas majoritárias 1 indexadas ou gera um erro de recursão (1) se não houver solução.
A função principal f () tenta recursivamente encontrar uma solução chamando o solucionador F () e aumentando o nível máximo de aninhamento m a cada iteração.
(1) depois de muito tempo, e assumindo memória infinita
Demo
Mostrar snippet de código
Exemplo
Abaixo está uma tabela de validação da solução encontrada para o último caso de teste da demonstração.
fonte
Mathematica, 121 bytes
Uma função anônima que usa seu segundo argumento como uma lista das listas de posições verdadeiras no vetor de booleanos.
Formatado um pouco melhor:
Explicação:
Por que isso é verdade? Bem, a função majoritária satisfaz duas propriedades:
Acontece que funções monotônicas complementares são exatamente a classe de funções que podem ser construídas a partir dos portões majoritários.
Suppose not all ofx1 , 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 f2≤f1=f≤f3 . If f=False then f2≤False implies f2=False=f and if f=True then f3≥True 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) .
fonte