quintopia hat hier eine Herausforderung zur Berechnung multinomialer Koeffizienten veröffentlicht (ein Teil des Textes hier wird von dort kopiert). Es gibt einen unterhaltsamen Algorithmus zur Berechnung von Multinomialkoeffizienten mod 2.

Ausgehend von einer Liste von Zahlen, k ₁ , k ₂ , ..., k _m , wird der Rest des Multinomialkoeffizienten ausgegeben:

Der folgende Algorithmus führt dies effizient aus: Berechne für jedes k _i die binäre Expansion von k _i , _dh finde ein _ij, so dass jedes a _ij entweder 1 oder 0 ist und

Wenn es irgendein j gibt, so dass ein _rj = ein _sj = 1 für r ≠ s ist, dann ist der zugehörige multinomiale Koeffizient von mod 2 0, andernfalls ist der multinomiale Koeffizient von mod 2 1.

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die m Zahlen, k ₁ , k ₂ , ..., k _m , annimmt und den entsprechenden Multinomialkoeffizienten ausgibt oder zurückgibt. Ihr Programm kann gegebenenfalls m als zusätzliches Argument verwenden.

Diese Zahlen können in einem beliebigen Format eingegeben werden, zum Beispiel in Listen gruppiert oder in Unary oder irgendetwas anderem codiert, solange die eigentliche Berechnung des Multinomialkoeffizienten von Ihrem Code durchgeführt wird und nicht der Codierungsprozess.
Die Ausgabe kann ein beliebiger Wahrheitswert sein, wenn der Multinomialkoeffizient ungerade ist, und ein beliebiger Falschwert, wenn der Multinomialkoeffizient gerade ist.
Integrierte Funktionen zur Berechnung des Multinomialkoeffizienten sind nicht zulässig.
Es gelten Standardlücken.

Wertung

Das ist Codegolf: Kürzeste Lösung in Bytes gewinnt.

Beispiele:

Um den Multinomialkoeffizienten von 7, 16 und 1000 zu ermitteln, erweitern wir jeden von ihnen binär:

Da keine Spalte mehr als eine 1 hat, ist der Multinomialkoeffizient ungerade, und daher sollten wir etwas Wahres ausgeben.

Um den Multinomialkoeffizienten von 7, 16 und 76 zu ermitteln, erweitern wir jeden von ihnen binär:

Da sowohl 76 als auch 7 eine 4 in ihrer binären Expansion haben, ist der Multinomialkoeffizient gerade und wir geben einen Falsey-Wert aus.

Testfälle:

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 Kapuze
quelle

1

Willkommen bei PPCG! Schöner erster Beitrag!

17.

Ich denke, mehrere ==gleichberechtigte Sprachen hätten ein Byte sparen können, wenn Wahrheit und Falschheit umgedreht worden wären.

Ørjan Johansen

@ ØrjanJohansen Das hört sich gut an.

Hood

9

Gelee , 4 Bytes

S=|/

Probieren Sie es online!

Testen Sie, ob die Summe der bitweisen oder der Summe (dh a+b+c == a|b|c) entspricht.

Undichte Nonne
quelle

7

Python 3 2, 55 43 42 Bytes

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

-12 Bytes von Mr. Xcoder

-1 Byte von Rod

Probieren Sie es online!

Erläuterung: Überprüft, ob die Summe der Zahlen der bitweisen oder der Zahlen entspricht.

Pizzapants184
quelle

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

Mr. Xcoder

Sie können 42 Bytes erreichen , indem Sie auf python2

Rod

4

Python 2 , 37 Bytes

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

Probieren Sie es online!

Ein weiterer Port des Algorithmus von pizzapants184 ...

Erik der Outgolfer
quelle

3

Sauber , 38 Bytes

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

Probieren Sie es online!

Noch ein Hafen.

Οurous
quelle

2

Japt, 6 Bytes

Ein weiterer Port der Lösungen von pizzapants184 & Leaky Nun.

x ¶Ur|

Probier es aus

Zottelig
quelle

Technisch gesehen antwortete pizzapants184 14 Sekunden früher als ich ...

Leaky Nun

2

JavaScript (ES6), 37 35 34 Bytes

2 Bytes gespart dank @ Mr.Xcoder
gespeichert 1 Byte dank @ETHproductions gespeichert

Der Vergleich der Summe mit dem bitweisen OR (wie es pizzapants184 und Leaky Nun taten) ist 1 3 4 Bytes kürzer als mein ursprünglicher Ansatz:

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

Testfälle

Code-Snippet anzeigen

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

Erweitern Sie das Snippet

Alt. Version, 38 Bytes

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

Testfälle

Code-Snippet anzeigen

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

Erweitern Sie das Snippet

Arnauld
quelle

Technisch gesehen antwortete pizzapants184 14 Sekunden früher als ich ...

Leaky Nun

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

ETHproductions

@ETHproductions Schön! Dies funktioniert gut in Node.js. Aber haben Sie es geschafft, dass es in einem Browser funktioniert?

Arnauld

Funktioniert in Firefox 57 einwandfrei. Wird eine Fehlermeldung angezeigt oder funktioniert sie nur nicht richtig?

ETHproductions

@ETHproductions Eigentlich funktioniert es ja. Bei repl.it schlägt dies einfach fehl .

Arnauld

2

Haskell , 38 Bytes

(==).sum<*>foldl1 xorist eine anonyme Funktion, die a zurückgibt Bool. Verwenden Sie als ((==).sum<*>foldl1 xor) [2,0,1].

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

Probieren Sie es online!

Ziemlich derselbe Trick von pizzapants184 und Leaky Nun, den jeder verwendet, mit der Ausnahme, dass bei Haskell-Operatorenamen ein Byte für die Verwendung von (bitweise) xoranstelle von (.|.)(bitweise oder) gespart wird .
(==).sum<*>foldl1 xorist eine punktefreie Version von \l->sum l==foldl1 xor l.

Ørjan Johansen
quelle

2

Java 8, 53 Bytes

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

Port von @LeakyNuns Jelly Antwort .

Erläuterung:

Probieren Sie es hier aus.

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
quelle

1

Pyth , 6 Bytes

qsQ.|F

Test Suite.

Mr. Xcoder
quelle

1

Schale , 5 Bytes

§=ΣFv

Probieren Sie es online!

Mr. Xcoder
quelle

1

Perl 6 , 15 Bytes

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

Probier es aus

Erweitert:

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

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

  ==

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

      $_  # the input
}

Brad Gilbert b2gills
quelle

1

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

Wie es funktioniert:

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

Probieren Sie es online!

Galen Ivanov
quelle

1

Wolfram Language (Mathematica) , 15 Byte

Tr@#==BitOr@@#&

Probieren Sie es online!

Alephalpha
quelle

0

Batch, 73 Bytes

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

Ausgänge 1für Wahres, nichts für Falsches. Eine weitere offensichtliche Portierung des Algorithmus von pizzapants184 / Leaky Nun.

Neil
quelle

0

J 10 Bytes

+/=+./&.#:

Noch eine Portierung der Lösungen von pizzapants184 & Leaky Nun.

Wie es funktioniert?

+/.&.#: - wandle die Zahlen in Binärzahlen um, wende sie bitweise oder in Zweierpotenzen an und wandle sie von Binärzahlen in Dezimalzahlen um

+/ - Reduzieren Sie die Eingabe durch Addition

= - Sind die oben genannten gleich?

Probieren Sie es online!

Einfache Alternative

J , 12 Bytes

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

Wie es funktioniert?

+/@#: - Wandle jede Zahl in Binär um und finde die Summe jeder Potenz von 2

>./ - finde das Maximum

2>- ist es weniger als 2? -> wahr

Probieren Sie es online!

Galen Ivanov
quelle

0

Dreieckigkeit , 31 Bytes

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

Probieren Sie es online!

Alternative Lösung, 31 Byte

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

Probieren Sie es online!

Mr. Xcoder
quelle

Mod 2 Multinomialkoeffizienten

Aufgabe

Wertung

Beispiele:

Testfälle:

Antworten:

Gelee , 4 Bytes

Python 3 2, 55 43 42 Bytes

Python 2 , 37 Bytes

Sauber , 38 Bytes

Japt, 6 Bytes

JavaScript (ES6), 37 35 34 Bytes

Testfälle

Alt. Version, 38 Bytes

Testfälle

Haskell , 38 Bytes

Java 8, 53 Bytes

Pyth , 6 Bytes

Schale , 5 Bytes

Perl 6 , 15 Bytes

Erweitert:

Rot , 78 Bytes

Wie es funktioniert:

Wolfram Language (Mathematica) , 15 Byte

Batch, 73 Bytes

J 10 Bytes

Wie es funktioniert?

Einfache Alternative

J , 12 Bytes

Wie es funktioniert?

Dreieckigkeit , 31 Bytes

Alternative Lösung, 31 Byte