Mod 2 coeficientes multinomiales

14

quintopia ha publicado aquí un desafío para calcular coeficientes multinomiales (parte del texto aquí se copia desde allí). Hay un algoritmo divertido para calcular coeficientes multinomiales mod 2.

Dada una lista de números, k 1 , k 2 , ..., k m , genera el residuo del coeficiente multinomial:

ingrese la descripción de la imagen aquí

mod 2. reducido El siguiente algoritmo hace esto de manera eficiente: para cada k i , calcule la expansión binaria de k i , es decir, encuentre un ij tal que cada a ij sea ​​1 o 0 y

ingrese la descripción de la imagen aquí

Si hay alguna j tal que a rj = a sj = 1 para r ≠ s, entonces el coeficiente multinomial mod 2 asociado es 0, de lo contrario el coeficiente multinomial mod 2 es 1.

Tarea

Escriba un programa o función que tome m números, k 1 , k 2 , ..., k m , y genere o devuelva el coeficiente multinomial correspondiente. Opcionalmente, su programa puede tomar m como argumento adicional si es necesario.

  • Estos números pueden ingresarse en cualquier formato que le guste, por ejemplo, agrupados en listas o codificados en unario, o cualquier otra cosa, siempre que su código realice el cálculo real del coeficiente multinomial, y no el proceso de codificación.

  • La salida puede ser cualquier valor verdadero si el coeficiente multinomial es impar y cualquier valor falsey si el coeficiente multinomial es par.

  • No están permitidos los elementos integrados diseñados para calcular el coeficiente multinomial.

  • Se aplican lagunas estándar.

Puntuación

Este es el código de golf: la solución más corta en bytes gana.

Ejemplos:

Para encontrar el coeficiente multinomial de 7, 16 y 1000, expandimos binariamente cada uno de ellos:

ingrese la descripción de la imagen aquí

Como ninguna columna tiene más de un 1, el coeficiente multinomial es impar y, por lo tanto, deberíamos generar algo verdadero.

Para encontrar el coeficiente multinomial de 7, 16 y 76, expandimos binariamente cada uno de ellos:

ingrese la descripción de la imagen aquí

Dado que 76 y 7 tienen un 4 en su expansión binaria, el coeficiente multinomial es par y, por lo tanto, arrojamos un valor de falsey.

Casos de prueba:

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
capucha
fuente
1
Bienvenido a PPCG! Bonito primer post!
Rɪᴋᴇʀ
Creo que varios idiomas ==para la igualdad podrían haber salvado un byte si se permitiera cambiar la verdad y la falsey.
Ørjan Johansen
@ ØrjanJohansen Eso suena bien.
Hood

Respuestas:

7

Python 3 2, 55 43 42 bytes

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

-12 bytes del Sr. Xcoder

-1 byte de Rod

Pruébalo en línea!

Explicación: Comprueba si la suma de los números es igual a los bits o a los números.

pizzapants184
fuente
43 bytes:lambda l:sum(l)==eval("|".join(map(str,l)))
Sr. Xcoder
Puede alcanzar 42 bytes cambiando a python2
Rod
2

Japt, 6 bytes

Otro puerto de soluciones de pizzapants184 y Leaky Nun.

x ¶Ur|

Pruébalo

Lanudo
fuente
Técnicamente, pizzapants184 respondió 14 segundos antes que yo ...
Leaky Nun
2

JavaScript (ES6), 37 35 34 bytes

Guardado 2 bytes gracias a @ Mr.Xcoder
Guardado 1 byte gracias a @ETHproductions

Comparar la suma con el OR bit a bit (como lo hicieron pizzapants184 y Leaky Nun ) es 1 3 4 bytes más corto que mi enfoque inicial:

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

Casos de prueba


Alt. versión, 38 bytes

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

Casos de prueba

Arnauld
fuente
Técnicamente, pizzapants184 respondió 14 segundos antes que yo ...
Leaky Nun
-1 byte:a=>(q=c=>eval(a.join(c)))`|`==q`+`;
ETHproductions
@ETHproductions ¡Agradable! Esto funciona bien en Node.js. ¿Pero lograste que funcionara en un navegador?
Arnauld
Me funciona bien en Firefox 57. ¿Recibes un error o simplemente no funciona correctamente?
ETHproductions
@ETHproductions En realidad, sí funciona. Lo que ocurre a fallar en repl.it .
Arnauld
2

Haskell , 38 bytes

(==).sum<*>foldl1 xores una función anónima que devuelve a Bool. Usar como ((==).sum<*>foldl1 xor) [2,0,1].

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

Pruébalo en línea!

  • Prácticamente el mismo truco de pizzapants184 y Leaky Nun que todo el mundo usa, excepto que con los nombres de los operadores Haskell ahorra un byte para usar (bit a bit) en xorlugar de (.|.)(bit a bit o).

  • (==).sum<*>foldl1 xores una versión sin puntos de \l->sum l==foldl1 xor l.

Ørjan Johansen
fuente
2

Java 8, 53 bytes

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

Puerto de la respuesta Jelly de @LeakyNun .

Explicación:

Pruébalo aquí.

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
fuente
1

Perl 6 , 15 bytes

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

Pruébalo

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
fuente
1

rojo , 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]

Cómo funciona:

Sin golf:

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

Pruébalo en línea!

Galen Ivanov
fuente
0

Lote, 73 bytes

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

Salidas 1para la verdad, nada para la falsedad. Otro puerto obvio de pizzapants184 / algoritmo de Leaky Nun.

Neil
fuente
0

J , 10 bytes

+/=+./&.#:

Otro puerto más de soluciones para pizzapants184 y Leaky Nun.

¿Cómo funciona?

+/.&.#: - Convierta los números a binario, aplique bit a bit o a las potencias de dos y vuelva a convertir de binario a decimal

+/ - reducir la entrada por adición

= - ¿son iguales los anteriores?

Pruébalo en línea!

Alternativa directa

J , 12 bytes

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

¿Cómo funciona?

+/@#: - convierte cada número a binario y encuentra la suma de cada potencia de 2

>./ - encuentra el máximo

2>- ¿es menos de 2? -> verdad

Pruébalo en línea!

Galen Ivanov
fuente