quintopia opublikowała tutaj wyzwanie obliczenia współczynników wielomianowych (stamtąd tekst tutaj jest kopiowany). Istnieje zabawny algorytm do obliczania współczynników wielomianowych mod 2.

Biorąc pod uwagę listę liczb, k ₁ , k ₂ , ..., k _m , wyprowadzamy pozostałość współczynnika wielomianowego:

ograniczonej mod 2. Poniższy algorytm robi to skutecznie: dla każdego k _I , obliczyć binarny ekspansję k _ja , to znaczy znaleźć się _ij tak, że każda _ij jest albo 1 albo 0 i

Jeżeli istnieje j, tak że _RJ = a _sj = 1 dla R ≠ s, asocjowany mod 2 wielomianu współczynnik wynosi 0, inaczej mod 2 wielomianu współczynnik wynosi 1.

Zadanie

Napisz program lub funkcję, która pobierze m liczb, k ₁ , k ₂ , ..., k _m , i wyświetli lub zwróci odpowiedni współczynnik wielomianowy. W razie potrzeby twój program może opcjonalnie potraktować m jako dodatkowy argument.

Liczby te mogą być wprowadzane w dowolnym formacie, który nam się podoba, na przykład pogrupowane w listy lub zakodowane jako jednoargumentowe lub cokolwiek innego, o ile kod oblicza rzeczywiste obliczenie współczynnika wielomianowego, a nie proces kodowania.
Wyjściem może być dowolna prawdziwa wartość, jeśli współczynnik wielomianowy jest nieparzysty, i dowolna wartość falsey, jeśli współczynnik wielomianowy jest parzysty.
Wbudowane funkcje obliczania współczynnika wielomianowego są niedozwolone.
Obowiązują standardowe luki.

Punktacja

Oto kod golfowy: wygrywa najkrótsze rozwiązanie w bajtach.

Przykłady:

Aby znaleźć wielomianowy współczynnik 7, 16 i 1000, binarnie rozwijamy każdy z nich:

Ponieważ żadna kolumna nie ma więcej niż jednego 1, współczynnik wielomianowy jest nieparzysty i dlatego powinniśmy otrzymać coś prawdziwego.

Aby znaleźć wielomianowy współczynnik 7, 16 i 76, binarnie rozwijamy każdy z nich:

Ponieważ zarówno 76, jak i 7 mają binarną ekspansję 4, współczynnik wielomianowy jest parzysty, więc otrzymujemy wartość falsey.

Przypadki testowe:

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

— kaptur
źródło

1

Witamy w PPCG! Miły pierwszy post!

— Rɪᴋᴇʀ

Myślę, że kilka języków ==dla równości mogłoby uratować bajt, gdyby prawda i Falsey mogły zostać odrzucone.

— Ørjan Johansen

@ ØrjanJohansen To brzmi dobrze.

— Hood

9

Galaretka , 4 bajty

S=|/

Wypróbuj online!

Sprawdź, czy suma jest równa bit-suma (tj a+b+c == a|b|c.).

— Leaky Nun
źródło

7

Python 3 2, 55 43 42 bajtów

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

-12 bajtów od pana Xcodera

-1 bajt z Rod

Wypróbuj online!

Objaśnienie: Sprawdza, czy suma liczb jest równa bitowej lub liczb.

— pizzapanty184
źródło

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

— Pan Xcoder,

Możesz osiągnąć 42 bajty przełączając się na python2

— Rod

4

Python 2 , 37 bajtów

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

Wypróbuj online!

Kolejny port algorytmu pizzapants184 ...

— Erik the Outgolfer
źródło

3

Czysty , 38 bajtów

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

Wypróbuj online!

Jeszcze inny port.

— Obrzydliwe
źródło

2

Japt, 6 bajtów

Kolejny port rozwiązań pizzapants184 i Leaky Nun.

x ¶Ur|

Sprawdź to

— Kudłaty
źródło

Technicznie rzecz biorąc, pizzapants184 odpowiedziały 14 sekund wcześniej niż ja ...

— Leaky Nun

2

JavaScript (ES6), 37 35 34 bajtów

Zapisano 2 bajty dzięki @ Mr.Xcoder
Zapisano 1 bajt dzięki @ETHproductions

Porównanie sumy z bitowym OR (jak zrobili to pizzapants184 i Leaky Nun ) jest o 1 3 4 bajty krótsze niż moje początkowe podejście:

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

Przypadki testowe

Pokaż fragment kodu

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. wersja, 38 bajtów

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

Przypadki testowe

Pokaż fragment kodu

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
źródło

Technicznie rzecz biorąc, pizzapants184 odpowiedziały 14 sekund wcześniej niż ja ...

— Leaky Nun

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

— ETHprodukcje

@ETHproductions Nice! Działa to dobrze w Node.js. Ale czy udało ci się uruchomić go w przeglądarce?

— Arnauld

Działa dobrze dla mnie w przeglądarce Firefox 57. Wystąpił błąd, czy po prostu nie działa poprawnie?

— ETHprodukcje

@ETHproductions Właściwie tak, to działa. To właśnie dzieje się zawieść na repl.it .

— Arnauld

2

Haskell , 38 bajtów

(==).sum<*>foldl1 xorjest anonimową funkcją zwracającą Bool. Użyj jako ((==).sum<*>foldl1 xor) [2,0,1].

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

Wypróbuj online!

Prawie ta sama sztuczka pizzapants184 i Leaky Nun, której wszyscy używają, z wyjątkiem tego, że przy nazwach operatorów Haskell oszczędza jeden bajt do użycia (bitowy) xorzamiast (.|.)(bitowy lub).
(==).sum<*>foldl1 xorjest pozbawioną punktów wersją \l->sum l==foldl1 xor l.

— Ørjan Johansen
źródło

2

Java 8, 53 bajty

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

Port odpowiedzi galaretki @LeakyNun .

Wyjaśnienie:

Wypróbuj tutaj.

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
źródło

1

Pyth , 6 bajtów

qsQ.|F

Pakiet testowy.

— Pan Xcoder
źródło

1

Łuska , 5 bajtów

§=ΣFv

Wypróbuj online!

— Pan Xcoder
źródło

1

Perl 6 , 15 bajtów

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

Sprawdź to

Rozszerzony:

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

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

  ==

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

      $_  # the input
}

— Brad Gilbert b2gills
źródło

1

Czerwony , 78 bajtów

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]

Jak to działa:

Nie golfowany:

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

Wypróbuj online!

— Galen Iwanow
źródło

1

Wolfram Language (Mathematica) , 15 bajtów

Tr@#==BitOr@@#&

Wypróbuj online!

— alephalpha
źródło

0

Partia, 73 bajty

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

Wyjścia 1dla prawdy, nic dla fałszu. Kolejny oczywisty port pizzapantów184 / algorytm Dziurawej Zakonnicy.

— Neil
źródło

0

J , 10 bajtów

+/=+./&.#:

Jeszcze jeden port rozwiązań pizzapantów184 i Dziurawej Zakonnicy.

Jak to działa?

+/.&.#: - zamień liczby na binarne, zastosuj bitowe lub potęgi dwóch i przekonwertuj z powrotem z binarnego na dziesiętny

+/ - zmniejszyć wkład przez dodanie

= - czy powyższe są równe?

Wypróbuj online!

Prosta alternatywa

J , 12 bajtów

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

Jak to działa?

+/@#: - zamień każdą liczbę na binarną i znajdź sumę każdej potęgi 2

>./ - znajdź maksimum

2>- czy to mniej niż 2? -> prawda

Wypróbuj online!

— Galen Iwanow
źródło

0

Trójkątność , 31 bajtów

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

Wypróbuj online!

Alternatywne rozwiązanie, 31 bajtów

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

Wypróbuj online!

— Pan Xcoder
źródło

Mod 2 Współczynniki wielomianowe

Zadanie

Punktacja

Przykłady:

Przypadki testowe:

Galaretka , 4 bajty

Python 3 2, 55 43 42 bajtów

Python 2 , 37 bajtów

Czysty , 38 bajtów

Japt, 6 bajtów

JavaScript (ES6), 37 35 34 bajtów

Przypadki testowe

Alt. wersja, 38 bajtów

Przypadki testowe

Haskell , 38 bajtów

Java 8, 53 bajty

Pyth , 6 bajtów

Łuska , 5 bajtów

Perl 6 , 15 bajtów

Rozszerzony:

Czerwony , 78 bajtów

Jak to działa:

Wolfram Language (Mathematica) , 15 bajtów

Partia, 73 bajty

J , 10 bajtów

Jak to działa?

Prosta alternatywa

J , 12 bajtów

Jak to działa?

Trójkątność , 31 bajtów

Alternatywne rozwiązanie, 31 bajtów