Mod 2 Coeficientes multinomiais

14

A quintopia postou aqui um desafio para calcular coeficientes multinomiais (parte do texto aqui é copiado de lá). Existe um algoritmo divertido para calcular coeficientes multinomiais mod 2.

Dada uma lista de números, k 1 , k 2 , ..., k m , gera o resíduo do coeficiente multinomial:

insira a descrição da imagem aqui

mod reduzida 2. O seguinte algoritmo faz isso de forma eficiente: para cada k i , calcular a expansão binária de k i , isto é, encontrar um ij tal que cada um ij é 1 ou 0 e

insira a descrição da imagem aqui

Se não houver qualquer j de tal modo que um RJ = a sj = 1 para R ≠ s, em seguida, a associada modificação 2 coeficiente multinominal é 0, caso contrário, a modificação 2 é um coeficiente multinominal.

Tarefa

Escreva um programa ou função que pegue m números, k 1 , k 2 , ..., k m e emita ou retorne o coeficiente multinomial correspondente. Seu programa pode opcionalmente considerar m como argumento adicional, se necessário.

  • Esses números podem ser inseridos em qualquer formato que você queira, por exemplo, agrupado em listas ou codificado em unário ou qualquer outra coisa, desde que a computação real do coeficiente multinomial seja realizada pelo seu código, e não pelo processo de codificação.

  • A saída pode ser qualquer valor verdadeiro se o coeficiente multinomial for ímpar e qualquer valor falsey se o coeficiente multinomial for par.

  • Built-ins projetados para calcular o coeficiente multinomial não são permitidos.

  • Aplicam-se brechas padrão.

Pontuação

Este é o código golf: A solução mais curta em bytes vence.

Exemplos:

Para encontrar o coeficiente multinomial de 7, 16 e 1000, expandimos binariamente cada um deles:

insira a descrição da imagem aqui

Como nenhuma coluna possui mais de um 1, o coeficiente multinomial é ímpar e, portanto, devemos produzir algo de verdade.

Para encontrar o coeficiente multinomial de 7, 16 e 76, expandimos binariamente cada um deles:

insira a descrição da imagem aqui

Como 76 e 7 têm 4 em sua expansão binária, o coeficiente multinomial é uniforme e, portanto, produzimos um valor de falsey.

Casos de teste:

Input: [2, 0, 1]
Output: Truthy

Input: [5,4,3,2,1]
Output: Falsey

Input: [1,2,4,8,16]
Output: Truthy

Input: [7,16,76]
Output: Falsey

Input: [7,16,1000]
Output: Truthy

Input: [545, 1044, 266, 2240]
Output: Truthy

Input: [1282, 2068, 137, 584]
Output: Falsey

Input: [274728976, 546308480, 67272744, 135004166, 16790592, 33636865]
Output: Truthy

Input: [134285315, 33849872, 553780288, 544928, 4202764, 345243648]
Output: Falsey
de capuz
fonte
1
Bem-vindo ao PPCG! Bom primeiro post!
Rɪᴋᴇʀ
Eu acho que vários idiomas com ==igualdade poderiam ter economizado um byte se truthy e falsey pudessem ser invertidos.
Ørjan Johansen
@ ØrjanJohansen Isso soa bem.
Hood

Respostas:

7

Python 3 2, 55 43 42 bytes

lambda l:sum(l)==eval(`l`.replace(*',|'))

-12 bytes do Sr. Xcoder

-1 byte de Rod

Experimente online!

Explicação: Verifica se a soma dos números é igual ao bit a bit - ou dos números.

pizzapants184
fonte
43 bytes:lambda l:sum(l)==eval("|".join(map(str,l)))
Sr. Xcoder
Você pode chegar a 42 bytes mudar para python2
Rod
3

Limpo , 38 bytes

import StdEnv
?l=sum l==foldr(bitor)0l

Experimente online!

Mais um porto.

Furioso
fonte
2

Japonês, 6 bytes

Outro porto de soluções pizzapants184 e Leaky Nun.

x ¶Ur|

Teste-o

Shaggy
fonte
Tecnicamente, pizzapants184 respondeu 14 segundos mais cedo do que eu ...
Leaky Nun
2

JavaScript (ES6), 37 35 34 bytes

Economizou 2 bytes graças a @ Mr.Xcoder
Economizou 1 byte graças a @ETHproductions

A comparação da soma com o OR bit a bit (como pizzapants184 e Leaky Nun fizeram) é 1 3 4 bytes menor que minha abordagem inicial:

a=>(q=c=>eval(a.join(c)))`|`==q`+`

Casos de teste


Alt. versão, 38 bytes

a=>!a.some((x,i)=>a.some(y=>i--&&x&y))

Casos de teste

Arnauld
fonte
Tecnicamente, pizzapants184 respondeu 14 segundos mais cedo do que eu ...
Leaky Nun
-1 byte:a=>(q=c=>eval(a.join(c)))`|`==q`+`;
ETHproductions
@ETHproductions Nice! Isso funciona bem no Node.js. Mas você conseguiu fazê-lo funcionar em um navegador?
Arnauld
Funciona bem para mim no Firefox 57. Você está recebendo um erro ou simplesmente não está funcionando corretamente?
ETHproductions
@ETHproductions Na verdade, sim, funciona. Ela só acontece a falhar em repl.it .
Arnauld
2

Haskell , 38 bytes

(==).sum<*>foldl1 xoré uma função anônima retornando a Bool. Use como ((==).sum<*>foldl1 xor) [2,0,1].

import Data.Bits
(==).sum<*>foldl1 xor

Experimente online!

  • Praticamente o mesmo truque de pizzapants184 e Leaky Nun que todo mundo usa, exceto que, com o nome do operador Haskell, ele economiza um byte para usar (bit a bit) em xorvez de (.|.)(bit a bit ou).

  • (==).sum<*>foldl1 xoré uma versão sem pontos do \l->sum l==foldl1 xor l.

Ørjan Johansen
fonte
2

Java 8, 53 bytes

a->{int i=0,j=0;for(int x:a){i+=x;j|=x;}return i==j;}

Porto da resposta da @LeakyNun 's Jelly .

Explicação:

Experimente aqui.

a->{             // Method with integer-array parameter and boolean return-type
  int i=0,j=0;   //  Two integers, both starting at 0
  for(int x:a){  //  Loop over the array
    i+=x;        //   Add them to the first integer
    j|=x;}       //   And bitwise-OR it with the second integer
  return i==j;}  //  Return if both integers are the same after the loop
Kevin Cruijssen
fonte
1

Perl 6 , 15 bytes

{.sum==[+|] $_}

Teste-o

Expandido:

{  # bare block lambda with implicit parameter 「$_」

    .sum  # the sum of 「$_」 (implicit method call)

  ==

    [+|]  # reduce using &infix:«+|» (numeric binary or)

      $_  # the input
}
Brad Gilbert b2gills
fonte
1

Vermelho , 78 bytes

f: func[x][b: :to-binary t: 0 s: b 0 foreach n x[t: t + n s: s or b n]s = b t]

Como funciona:

Ungolfed:

Red []
f: func [x][         -  a function taking a block as an argument
    b: :to-binary    -  an alias for the to-binary function
    t: 0             -  set the sum of the numbers to 0
    s: b 0           -  set the "or" total to binary 0
    foreach n x[     -  for each number in the block
        t: t + n     -  add it to the sum
        s: s or b n  -  bitwise or of its binary representation with the total
    ]
    s = b t          - are the sum (binary) and the "or" total equal?
]

Experimente online!

Galen Ivanov
fonte
0

Lote, 73 bytes

@set/as=o=0
@for %%i in (%*)do @set/as+=%%i,o^|=%%i
@if %s%==%o% echo 1

Saídas 1para verdade, nada para falsidade. Outro exemplo óbvio do algoritmo de pizzapants184 / Leaky Nun.

Neil
fonte
0

J , 10 bytes

+/=+./&.#:

Mais um porto de soluções pizzapants184 e Leaky Nun.

Como funciona?

+/.&.#: - converta os números em binário, aplique bit a bit ou na potência de dois e converta novamente de binário em decimal

+/ - reduza a entrada adicionando

= - os acima são iguais?

Experimente online!

Alternativa direta

J , 12 bytes

2>[:>./+/@#:

Como funciona?

+/@#: - converta cada número em binário e encontre a soma de cada potência de 2

>./ - encontre o máximo

2>- é inferior a 2? -> verdade

Experimente online!

Galen Ivanov
fonte