14
\$\begingroup\$

quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2.

Given a list of numbers, k1, k2, ... ,km, output the residue of the multinomial coefficient:

enter image description here

reduced mod 2. The following algorithm does this efficiently: for each ki, compute the binary expansion of ki, that is, find aij such that each aij is either 1 or 0 and

enter image description here

If there is any j such that arj = asj = 1 for r ≠ s, then the associated mod 2 multinomial coefficient is 0, otherwise the mod 2 multinomial coefficient is 1.

Task

Write a program or function which takes m numbers, k1, k2, ... ,km, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take m as an additional argument if need be.

  • These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else, as long as the actual computation of the multinomial coefficient is performed by your code, and not the encoding process.

  • Output can be any truthy value if the multinomial coefficient is odd and any falsey value if the multinomial coefficient is even.

  • Built-ins designed to compute the multinomial coefficient are not allowed.

  • Standard loopholes apply.

Scoring

This is code golf: Shortest solution in bytes wins.

Examples:

To find the multinomial coefficient of 7, 16, and 1000, we binary expand each of them:

enter image description here

Since no column has more than one 1, the multinomial coefficient is odd, and hence we should output something truthy.

To find the multinomial coefficient of 7, 16, and 76, we binary expand each of them:

enter image description here

Since both 76 and 7 have a 4 in their binary expansion, the multinomial coefficient is even and so we output a falsey value.

Test cases:

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! Nice first post! \$\endgroup\$ – Rɪᴋᴇʀ Jan 17 '18 at 20:57
  • \$\begingroup\$ I think several languages with == for equality could have saved a byte if truthy and falsey were allowed to be flipped. \$\endgroup\$ – Ørjan Johansen Jan 18 '18 at 8:44
  • \$\begingroup\$ @ØrjanJohansen That sounds fine. \$\endgroup\$ – Hood Jan 19 '18 at 4:59

16 Answers 16

9
\$\begingroup\$

Jelly, 4 bytes

S=|/

Try it online!

Test whether the sum is equal to the bitwise-or-sum (i.e. a+b+c == a|b|c).

\$\endgroup\$
7
\$\begingroup\$

Python 3 2, 55 43 42 bytes

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

-12 bytes from Mr. Xcoder

-1 byte from Rod

Try it online!

Explanation: Checks if the sum of the numbers is equal to the bitwise-or of the numbers.

\$\endgroup\$
  • \$\begingroup\$ 43 bytes: lambda l:sum(l)==eval("|".join(map(str,l))) \$\endgroup\$ – Mr. Xcoder Jan 17 '18 at 21:04
  • \$\begingroup\$ You can reach 42 bytes switching to python2 \$\endgroup\$ – Rod Jan 18 '18 at 9:57
4
\$\begingroup\$

Python 2, 37 bytes

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

Try it online!

Another port of pizzapants184's algorithm...

\$\endgroup\$
3
\$\begingroup\$

Clean, 38 bytes

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

Try it online!

Yet another port.

\$\endgroup\$
2
\$\begingroup\$

Japt, 6 bytes

Another port of pizzapants184's & Leaky Nun's solutions.

x ¶Ur|

Test it

\$\endgroup\$
  • \$\begingroup\$ Technically, pizzapants184 answered 14 seconds earlier than me... \$\endgroup\$ – Leaky Nun Jan 17 '18 at 21:16
2
\$\begingroup\$

JavaScript (ES6), 37 35 34 bytes

Saved 2 bytes thanks to @Mr.Xcoder
Saved 1 byte thanks to @ETHproductions

Comparing the sum with the bitwise OR (like pizzapants184 and Leaky Nun did) is 1 3 4 bytes shorter than my initial approach:

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

Test cases

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


Alt. version, 38 bytes

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

Test cases

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

\$\endgroup\$
  • \$\begingroup\$ Technically, pizzapants184 answered 14 seconds earlier than me... \$\endgroup\$ – Leaky Nun Jan 17 '18 at 21:16
  • \$\begingroup\$ -1 byte: a=>(q=c=>eval(a.join(c)))`|`==q`+`; \$\endgroup\$ – ETHproductions Jan 17 '18 at 21:36
  • \$\begingroup\$ @ETHproductions Nice! This works fine in Node.js. But did you manage to have it working in a browser? \$\endgroup\$ – Arnauld Jan 17 '18 at 21:43
  • \$\begingroup\$ Works fine for me in Firefox 57. Are you getting an error or is it just not working properly? \$\endgroup\$ – ETHproductions Jan 17 '18 at 22:12
  • \$\begingroup\$ @ETHproductions Actually, yes it does work. It just happens to fail on repl.it. \$\endgroup\$ – Arnauld Jan 17 '18 at 22:22
2
\$\begingroup\$

Haskell, 38 bytes

(==).sum<*>foldl1 xor is an anonymous function returning a Bool. Use as ((==).sum<*>foldl1 xor) [2,0,1].

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

Try it online!

  • Pretty much the same trick by pizzapants184 and Leaky Nun that everyone uses, except that with Haskell operator names it saves one byte to use (bitwise) xor instead of (.|.) (bitwise or).

  • (==).sum<*>foldl1 xor is a point-free version of \l->sum l==foldl1 xor l.

\$\endgroup\$
2
\$\begingroup\$

Java 8, 53 bytes

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

Port of @LeakyNun's Jelly answer.

Explanation:

Try it here.

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
\$\endgroup\$
1
\$\begingroup\$

Pyth, 6 bytes

qsQ.|F

Test Suite.

\$\endgroup\$
1
\$\begingroup\$

Husk, 5 bytes

§=ΣFv

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 15 bytes

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

Test it

Expanded:

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

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

  ==

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

      $_  # the input
}
\$\endgroup\$
1
\$\begingroup\$

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

How it works:

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 15 bytes

Tr@#==BitOr@@#&

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Batch, 73 bytes

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

Outputs 1 for truthy, nothing for falsy. Another obvious port of pizzapants184/Leaky Nun's algorithm.

\$\endgroup\$
0
\$\begingroup\$

J, 10 bytes

+/=+./&.#:

Yet another port of pizzapants184's & Leaky Nun's solutions.

How it works?

+/.&.#: - convert the numbers to binary, apply bitwise or to the powers of two and convert back from binary to decimal

+/ - reduce the input by addition

= - are the above equal?

Try it online!

Straightforward alternative

J, 12 bytes

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

How it works?

+/@#: - convert each number to binary and find the sum of each power of 2

>./ - find the maximum

2> - is it less than 2? -> truthy

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Triangularity, 31 bytes

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

Try it online!

Alternate solution, 31 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.