quintopia a publié ici un défi pour calculer les coefficients multinomiaux (une partie du texte ici est copiée à partir de là). Il existe un algorithme amusant pour calculer les coefficients multinomiaux mod 2.

Étant donné une liste de nombres, k ₁ , k ₂ , ..., k _m , sortent le résidu du coefficient multinomial:

mod réduit 2. L'algorithme suivant le fait efficacement: pour chaque k _i , calculer l'expansion binaire de k _i , c'est-à-dire trouver un _ij tel que chaque a _ij soit 1 ou 0 et

S'il existe un j tel que a _rj = a _sj = 1 pour r ≠ s, alors le coefficient multinomial mod 2 associé est 0, sinon le coefficient multinomial mod 2 est 1.

Tâche

Écrivez un programme ou une fonction qui prend m nombres, k ₁ , k ₂ , ..., k _m , et génère ou renvoie le coefficient multinomial correspondant. Votre programme peut éventuellement prendre m comme argument supplémentaire si nécessaire.

Ces nombres peuvent être entrés dans n'importe quel format souhaité, par exemple regroupés dans des listes ou codés en unaire, ou toute autre chose, tant que le calcul réel du coefficient multinomial est effectué par votre code, et non le processus de codage.
La sortie peut être toute valeur vraie si le coefficient multinomial est impair et toute valeur de falsey si le coefficient multinomial est pair.
Les éléments intégrés conçus pour calculer le coefficient multinomial ne sont pas autorisés.
Des échappatoires standard s'appliquent.

Notation

Voici le code golf: la solution la plus courte en octets gagne.

Exemples:

Pour trouver le coefficient multinomial de 7, 16 et 1000, nous développons binaire chacun d'eux:

Puisqu'aucune colonne n'a plus d'un 1, le coefficient multinomial est impair, et donc nous devrions produire quelque chose de vrai.

Pour trouver le coefficient multinomial de 7, 16 et 76, nous développons binaire chacun d'eux:

Puisque 76 et 7 ont un 4 dans leur expansion binaire, le coefficient multinomial est pair et nous produisons donc une valeur de falsey.

Cas de test:

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 capuche
la source

1

Bienvenue chez PPCG! Bon premier post!

Rɪᴋᴇʀ

Je pense que plusieurs langues avec ==pour l'égalité auraient pu sauver un octet si la vérité et le falsey avaient été autorisés à être inversés.

Ørjan Johansen

@ ØrjanJohansen Cela sonne bien.

Hood

9

Gelée , 4 octets

S=|/

Essayez-le en ligne!

Testez si la somme est égale au bit ou à la somme (ie a+b+c == a|b|c).

Leaky Nun
la source

7

Python 3 2, 55 43 42 octets

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

-12 octets de M. Xcoder

-1 octet de Rod

Essayez-le en ligne!

Explication: Vérifie si la somme des nombres est égale au bit ou des nombres.

pizzapants184
la source

43 octets:lambda l:sum(l)==eval("|".join(map(str,l)))

M. Xcoder

Vous pouvez atteindre 42 octets en passant à python2

Rod

4

Python 2 , 37 octets

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

Essayez-le en ligne!

Un autre port de l'algorithme de pizzapants184 ...

Erik le Outgolfer
la source

3

Nettoyer , 38 octets

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

Essayez-le en ligne!

Encore un autre port.

Οurous
la source

2

Japt, 6 octets

Un autre port des solutions de pizzapants184 et de Leaky Nun.

x ¶Ur|

Essaye-le

Hirsute
la source

Techniquement, pizzapants184 a répondu 14 secondes plus tôt que moi ...

Leaky Nun

2

JavaScript (ES6), 37 35 34 octets

Enregistré 2 octets grâce à @ Mr.Xcoder
Enregistré 1 octet grâce à @ETHproductions

La comparaison de la somme avec l'OR au niveau du bit (comme l'ont fait pizzapants184 et Leaky Nun ) est 1 3 4 octets plus courte que mon approche initiale:

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

Cas de test

Afficher l'extrait de code

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

Expand snippet

Alt. version, 38 octets

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

Cas de test

Afficher l'extrait de code

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

Expand snippet

Arnauld
la source

Techniquement, pizzapants184 a répondu 14 secondes plus tôt que moi ...

Leaky Nun

-1 octet:a=>(q=c=>eval(a.join(c)))`|`==q`+`;

ETHproductions

@ETHproductions Nice! Cela fonctionne bien dans Node.js. Mais avez-vous réussi à le faire fonctionner dans un navigateur?

Arnauld

Fonctionne bien pour moi dans Firefox 57. Obtenez-vous une erreur ou ne fonctionne-t-il pas correctement?

ETHproductions

@ETHproductions En fait, oui, cela fonctionne. Il arrive juste à échouer sur repl.it .

Arnauld

2

Haskell , 38 octets

(==).sum<*>foldl1 xorest une fonction anonyme renvoyant un fichier Bool. Utiliser comme ((==).sum<*>foldl1 xor) [2,0,1].

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

Essayez-le en ligne!

À peu près la même astuce de pizzapants184 et Leaky Nun que tout le monde utilise, sauf qu'avec les noms d'opérateurs Haskell, il enregistre un octet à utiliser (bit à bit) xorau lieu de (.|.)(bit à bit ou).
(==).sum<*>foldl1 xorest une version sans point de \l->sum l==foldl1 xor l.

Ørjan Johansen
la source

2

Java 8, 53 octets

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

Port de la réponse Jelly de @LeakyNun .

Explication:

Essayez-le ici.

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
la source

1

Pyth , 6 octets

qsQ.|F

Suite de tests.

M. Xcoder
la source

1

Husk , 5 octets

§=ΣFv

Essayez-le en ligne!

M. Xcoder
la source

1

Perl 6 , 15 octets

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

Essaye-le

Étendu:

{  # bare block lambda with implicit parameter ｢$_｣

    .sum  # the sum of ｢$_｣ (implicit method call)

  ==

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

      $_  # the input
}

Brad Gilbert b2gills
la source

1

Rouge , 78 octets

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]

Comment ça fonctionne:

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

Essayez-le en ligne!

Galen Ivanov
la source

1

Wolfram Language (Mathematica) , 15 octets

Tr@#==BitOr@@#&

Essayez-le en ligne!

alephalpha
la source

0

Lot, 73 octets

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

Sorties 1pour vérité, rien pour fausse. Un autre port évident de l'algorithme de pizzapants184 / Leaky Nun.

Neil
la source

0

J , 10 octets

+/=+./&.#:

Encore un autre port des solutions de pizzapants184 et de Leaky Nun.

Comment ça fonctionne?

+/.&.#: - convertir les nombres en binaire, appliquer au niveau du bit ou aux puissances de deux et reconvertir du binaire en décimal

+/ - réduire l'entrée par addition

= - les éléments ci-dessus sont-ils égaux?

Essayez-le en ligne!

Alternative simple

J , 12 octets

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

Comment ça fonctionne?

+/@#: - convertir chaque nombre en binaire et trouver la somme de chaque puissance de 2

>./ - trouver le maximum

2>- est-ce moins de 2? -> véridique

Essayez-le en ligne!

Galen Ivanov
la source

0

Triangularité , 31 octets

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

Essayez-le en ligne!

Solution alternative, 31 octets

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

Essayez-le en ligne!

M. Xcoder
la source

Mod 2 Coefficients multinomiaux

Tâche

Notation

Exemples:

Cas de test:

Réponses:

Gelée , 4 octets

Python 3 2, 55 43 42 octets

Python 2 , 37 octets

Nettoyer , 38 octets

Japt, 6 octets

JavaScript (ES6), 37 35 34 octets

Cas de test

Alt. version, 38 octets

Cas de test

Haskell , 38 octets

Java 8, 53 octets

Pyth , 6 octets

Husk , 5 octets

Perl 6 , 15 octets

Étendu:

Rouge , 78 octets

Comment ça fonctionne:

Wolfram Language (Mathematica) , 15 octets

Lot, 73 octets

J , 10 octets

Comment ça fonctionne?

Alternative simple

J , 12 octets

Comment ça fonctionne?

Triangularité , 31 octets

Solution alternative, 31 octets