quintopia telah memposting di sini sebuah tantangan untuk menghitung koefisien multinomial (beberapa teks di sini disalin dari sana). Ada algoritma yang menyenangkan untuk menghitung koefisien multinomial mod 2.

Mengingat daftar nomor, k ₁ , k ₂ , ..., k _m , output residu dari koefisien multinomial:

berkurang mod 2. Berikut algoritma hal ini efisien: untuk setiap k _i , menghitung ekspansi biner k _i , yaitu, menemukan sebuah _ij sehingga setiap a _ij adalah 1 atau 0 dan

Jika ada j sehingga a _rj = a _sj = 1 untuk r ≠ s, maka koefisien multinomial mod 2 yang terkait adalah 0, jika tidak, koefisien multinomial mod 2 adalah 1.

Tugas

Menulis sebuah program atau fungsi yang mengambil m nomor, k ₁ , k ₂ , ..., k _m , dan output atau hasil koefisien multinomial yang sesuai. Program Anda secara opsional dapat menganggap m sebagai argumen tambahan jika perlu.

Angka-angka ini dapat dimasukkan dalam format apa pun yang disukai, misalnya dikelompokkan ke dalam daftar atau disandikan di unary, atau apa pun, selama perhitungan aktual dari koefisien multinomial dilakukan oleh kode Anda, dan bukan proses pengkodean.
Output dapat berupa nilai kebenaran jika koefisien multinomialnya ganjil dan nilai falsey apa pun jika koefisien multinomial genap.
Built-in yang dirancang untuk menghitung koefisien multinomial tidak diperbolehkan.
Celah standar berlaku.

Mencetak gol

Ini adalah kode golf: Solusi terpendek dalam byte yang menang.

Contoh:

Untuk menemukan koefisien multinomial 7, 16, dan 1000, kami biner mengembangkan masing-masing:

Karena tidak ada kolom yang memiliki lebih dari satu 1, koefisien multinomialnya aneh, dan karenanya kita harus menampilkan sesuatu yang benar.

Untuk menemukan koefisien multinomial dari 7, 16, dan 76, kami biner mengembangkan masing-masing:

Karena keduanya 76 dan 7 memiliki 4 dalam ekspansi biner mereka, koefisien multinomial genap dan jadi kami menghasilkan nilai falsey.

Kasus uji:

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 jilbab
sumber

1

Selamat datang di PPCG! Posting pertama yang bagus!

R

Saya pikir beberapa bahasa dengan ==kesetaraan bisa menyelamatkan satu byte jika kebenaran dan falsey dibiarkan terbalik.

Ørjan Johansen

@ ØrjanJohansen Kedengarannya bagus.

Hood

9

Jelly , 4 byte

S=|/

Cobalah online!

Uji apakah jumlahnya sama dengan bitwise-atau-jumlah (yaitu a+b+c == a|b|c).

Biarawati Bocor
sumber

7

Python 3 2, 55 43 42 byte

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

-12 byte dari Mr. Xcoder

-1 byte dari Rod

Cobalah online!

Penjelasan: Memeriksa apakah jumlah angka sama dengan bitwise-atau angka.

pizzapants184
sumber

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

Tn. Xcoder

Anda dapat mencapai 42 byte yang beralih ke python2

Rod

4

Python 2 , 37 byte

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

Cobalah online!

Port lain dari algoritme pizzapants184 ...

Erik the Outgolfer
sumber

3

Bersih , 38 byte

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

Cobalah online!

Namun pelabuhan lain.

Suram
sumber

2

Japt, 6 byte

Port lain dari solusi pizzapants184 & Leaky Nun.

x ¶Ur|

Menguji

Shaggy
sumber

Secara teknis, pizzapants184 menjawab 14 detik lebih awal dari saya ...

Leaky Nun

2

JavaScript (ES6), 37 35 34 byte

Disimpan 2 byte berkat @ Mr.Xcoder
Disimpan 1 byte berkat @ETHproduksi

Membandingkan jumlah dengan bitwise OR (seperti pizzapants184 dan Leaky Nun lakukan) adalah 1 3 4 byte lebih pendek daripada pendekatan awal saya:

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

Uji kasus

Tampilkan cuplikan kode

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. versi, 38 byte

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

Uji kasus

Tampilkan cuplikan kode

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
sumber

Secara teknis, pizzapants184 menjawab 14 detik lebih awal dari saya ...

Leaky Nun

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

ETHproduksi

@ EHProduk Bagus! Ini berfungsi dengan baik di Node.js. Tetapi apakah Anda berhasil membuatnya bekerja di browser?

Arnauld

Bekerja dengan baik untuk saya di Firefox 57. Apakah Anda mendapatkan kesalahan atau tidak berfungsi dengan benar?

ETHproduksi

@ ETHproductions Sebenarnya, ya itu berhasil. Itu hanya terjadi gagal pada repl.it .

Arnauld

2

Haskell , 38 byte

(==).sum<*>foldl1 xoradalah fungsi anonim mengembalikan a Bool. Gunakan sebagai ((==).sum<*>foldl1 xor) [2,0,1].

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

Cobalah online!

Trik yang hampir sama oleh pizzapants184 dan Leaky Nun yang digunakan semua orang, kecuali bahwa dengan nama operator Haskell menghemat satu byte untuk menggunakan (bitwise) xoralih-alih (.|.)(bitwise atau).
(==).sum<*>foldl1 xoradalah versi point-free dari \l->sum l==foldl1 xor l.

Ørjan Johansen
sumber

2

Java 8, 53 byte

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

Port dari jawaban Jelly @ LeakyNun .

Penjelasan:

Coba di sini.

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
sumber

1

Pyth , 6 byte

qsQ.|F

Test Suite.

Tuan Xcoder
sumber

1

Sekam , 5 byte

§=ΣFv

Cobalah online!

Tuan Xcoder
sumber

1

Perl 6 , 15 byte

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

Menguji

Diperluas:

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

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

  ==

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

      $_  # the input
}

Brad Gilbert b2gills
sumber

1

Merah , 78 byte

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]

Bagaimana itu bekerja:

Tidak Disatukan:

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

Cobalah online!

Galen Ivanov
sumber

1

Bahasa Wolfram (Mathematica) , 15 byte

Tr@#==BitOr@@#&

Cobalah online!

alephalpha
sumber

0

Batch, 73 byte

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

Keluaran 1untuk kebenaran, tidak ada yang palsu. Port lain yang jelas dari algoritme pizzapants184 / Leaky Nun.

Neil
sumber

0

J , 10 byte

+/=+./&.#:

Namun port lain dari solusi pizzapants184 & Leaky Nun.

Bagaimana itu bekerja?

+/.&.#: - Mengonversi angka menjadi biner, menerapkan bitwise atau ke pangkat dua dan mengkonversi kembali dari biner ke desimal

+/ - kurangi input dengan penambahan

= - apakah di atas sama?

Cobalah online!

Alternatif langsung

J , 12 byte

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

Bagaimana itu bekerja?

+/@#: - Konversi setiap angka menjadi biner dan temukan jumlah masing-masing kekuatan 2

>./ - temukan yang maksimal

2>- apakah kurang dari 2? -> benar

Cobalah online!

Galen Ivanov
sumber

0

Triangularity , 31 byte

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

Cobalah online!

Solusi alternatif, 31 byte

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

Cobalah online!

Tuan Xcoder
sumber

Mod 2 Koefisien multinomial

Tugas

Mencetak gol

Contoh:

Kasus uji:

Jawaban:

Jelly , 4 byte

Python 3 2, 55 43 42 byte

Python 2 , 37 byte

Bersih , 38 byte

Japt, 6 byte

JavaScript (ES6), 37 35 34 byte

Uji kasus

Alt. versi, 38 byte

Uji kasus

Haskell , 38 byte

Java 8, 53 byte

Pyth , 6 byte

Sekam , 5 byte

Perl 6 , 15 byte

Diperluas:

Merah , 78 byte

Bagaimana itu bekerja:

Bahasa Wolfram (Mathematica) , 15 byte

Batch, 73 byte

J , 10 byte

Bagaimana itu bekerja?

Alternatif langsung

J , 12 byte

Bagaimana itu bekerja?

Triangularity , 31 byte

Solusi alternatif, 31 byte