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 ₁ , k ₂ , ..., k _m , genera el residuo del coeficiente multinomial:

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

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 ₁ , k ₂ , ..., 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:

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:

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

code-golf math combinatorics 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

9

Jalea , 4 bytes

S=|/

Pruébalo en línea!

Pruebe si la suma es igual a bit-or-sum (ie a+b+c == a|b|c).

Monja permeable
fuente

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

4

Python 2 , 37 bytes

lambda l:sum(l)==reduce(int.__or__,l)

Pruébalo en línea!

Otro puerto del algoritmo de pizzapants184 ...

Erik el Outgolfer
fuente

3

Limpio , 38 bytes

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

Pruébalo en línea!

Otro puerto más.

Οurous
fuente

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

Mostrar fragmento de código

let f =

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

console.log(f([2, 0, 1]))                                                       // Truthy
console.log(f([5,4,3,2,1]))                                                     // Falsey
console.log(f([1,2,4,8,16]))                                                    // Truthy
console.log(f([7,16,76]))                                                       // Falsey
console.log(f([7,16,1000]))                                                     // Truthy
console.log(f([545, 1044, 266, 2240]))                                          // Truthy
console.log(f([1282, 2068, 137, 584]))                                          // Falsey
console.log(f([274728976, 546308480, 67272744, 135004166, 16790592, 33636865])) // Truthy
console.log(f([134285315, 33849872, 553780288, 544928, 4202764, 345243648]))    // Falsey

Expandir fragmento

Alt. versión, 38 bytes

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

Casos de prueba

Mostrar fragmento de código

let f =

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

console.log(f([2, 0, 1]))                                                       // Truthy
console.log(f([5,4,3,2,1]))                                                     // Falsey
console.log(f([1,2,4,8,16]))                                                    // Truthy
console.log(f([7,16,76]))                                                       // Falsey
console.log(f([7,16,1000]))                                                     // Truthy
console.log(f([545, 1044, 266, 2240]))                                          // Truthy
console.log(f([1282, 2068, 137, 584]))                                          // Falsey
console.log(f([274728976, 546308480, 67272744, 135004166, 16790592, 33636865])) // Truthy
console.log(f([134285315, 33849872, 553780288, 544928, 4202764, 345243648]))    // Falsey

Expandir fragmento

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

Pyth , 6 bytes

qsQ.|F

Banco de pruebas.

Sr. Xcoder
fuente

1

Casco , 5 bytes

§=ΣFv

Pruébalo en línea!

Sr. Xcoder
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

1

Wolfram Language (Mathematica) , 15 bytes

Tr@#==BitOr@@#&

Pruébalo en línea!

alephalpha
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

0

Triangularidad , 31 bytes.

...)...
..IEu..
.)IE...
"|"JE=.

Pruébalo en línea!

Solución alternativa, 31 bytes.

...)...
..IED..
.us"|".
JE=....

Pruébalo en línea!

Sr. Xcoder
fuente

Mod 2 coeficientes multinomiales

Tarea

Puntuación

Ejemplos:

Casos de prueba:

Respuestas:

Jalea , 4 bytes

Python 3 2, 55 43 42 bytes

Python 2 , 37 bytes

Limpio , 38 bytes

Japt, 6 bytes

JavaScript (ES6), 37 35 34 bytes

Casos de prueba

Alt. versión, 38 bytes

Casos de prueba

Haskell , 38 bytes

Java 8, 53 bytes

Pyth , 6 bytes

Casco , 5 bytes

Perl 6 , 15 bytes

Expandido:

rojo , 78 bytes

Cómo funciona:

Wolfram Language (Mathematica) , 15 bytes

Lote, 73 bytes

J , 10 bytes

¿Cómo funciona?

Alternativa directa

J , 12 bytes

¿Cómo funciona?

Triangularidad , 31 bytes.

Solución alternativa, 31 bytes.