Quintopia опубликовала здесь задачу по вычислению многочленных коэффициентов (часть текста здесь скопирована оттуда). Есть забавный алгоритм для вычисления коэффициентов многочлена mod 2.

Учитывая список чисел, k ₁ , k ₂ , ..., k _m , выведите остаток множителя:

приведенного по модулю 2. Следующий алгоритм делает это эффективно: для каждого к _я , вычислить двоичное разложение к _я , то есть, найти в _Ij таким образом, что каждая _IJ либо 1 , либо 0 и

Если существует такое j, что a _rj = a _sj = 1 для r ≠ s, то ассоциированный полиномиальный коэффициент mod 2 равен 0, в противном случае полиномиальный коэффициент mod 2 равен 1.

задача

Напишите программу или функцию, которая принимает m чисел, k ₁ , k ₂ , ..., k _m , и выводит или возвращает соответствующий коэффициент многочлена. Ваша программа может дополнительно принять m в качестве дополнительного аргумента, если это необходимо.

Эти числа могут быть введены в любом понравившемся формате, например, сгруппированы в списки или закодированы в унарном виде, или что-либо еще, при условии, что фактическое вычисление коэффициента многочлена выполняется вашим кодом, а не процессом кодирования.
Вывод может быть любым истинным значением, если коэффициент многочлена нечетен, и любым значением Ложь, если коэффициент многочлена четен.
Встроенные модули, предназначенные для вычисления коэффициента многочлена, не допускаются.
Применяются стандартные лазейки.

счет

Это код гольф: выигрывает самое короткое решение в байтах.

Примеры:

Чтобы найти мультиномиальный коэффициент 7, 16 и 1000, мы двоично расширяем каждый из них:

Поскольку ни один столбец не имеет более одного 1, коэффициент многочлена нечетен, и поэтому мы должны вывести что-то правдивое.

Чтобы найти коэффициент многочлена 7, 16 и 76, мы двоично разлагаем каждый из них:

Так как 76 и 7 имеют 4 в двоичном разложении, коэффициент многочлена является четным, и поэтому мы выводим значение Фолси.

Тестовые случаи:

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 капот
источник

1

Добро пожаловать в PPCG! Хороший первый пост!

августа

Я думаю, что несколько языков с ==равенством могли бы спасти байт, если бы истину и фальшивость можно было перевернуть.

Орджан Йохансен

@ ØrjanJohansen Звучит хорошо.

Капот

9

Желе , 4 байта

S=|/

Попробуйте онлайн!

Проверьте, равна ли сумма побитовой сумме (т.е. a+b+c == a|b|c).

Дрянная Монахиня
источник

7

Python 3 2, 55 43 42 байта

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

-12 байт от мистера Xcoder

-1 байт от стержня

Попробуйте онлайн!

Объяснение: Проверяет, равна ли сумма чисел битовой или чисел.

pizzapants184
источник

43 байта:lambda l:sum(l)==eval("|".join(map(str,l)))

г-н Xcoder

Вы можете достигнуть 42 байтов, переключаясь на python2

Род

4

Python 2 , 37 байт

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

Попробуйте онлайн!

Еще один порт алгоритма pizzapants184 ...

Эрик Outgolfer
источник

3

Чисто , 38 байт

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

Попробуйте онлайн!

Еще один порт.

Οurous
источник

2

Japt, 6 байт

Еще один порт с решениями pizzapants184 и Leaky Nun.

x ¶Ur|

Проверь это

мохнатый
источник

Технически, pizzapants184 ответили на 14 секунд раньше меня ...

Leaky Nun

2

JavaScript (ES6), 37 35 34 байта

Сохранено 2 байта благодаря @ Mr.Xcoder
Сохранено 1 байт благодаря @ETHproductions

Сравнение суммы с побитовым ИЛИ (как сделали pizzapants184 и Leaky Nun ) на 1 3 4 байта короче, чем мой первоначальный подход:

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

Контрольные примеры

Показать фрагмент кода

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

Развернуть фрагмент

Чередующийся версия, 38 байт

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

Контрольные примеры

Показать фрагмент кода

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

Развернуть фрагмент

Arnauld
источник

Технически, pizzapants184 ответили на 14 секунд раньше меня ...

Leaky Nun

-1 байт:a=>(q=c=>eval(a.join(c)))`|`==q`+`;

ETHproductions

@ETHproductions Отлично! Это прекрасно работает в Node.js. Но вам удалось заставить его работать в браузере?

Арно

У меня отлично работает в Firefox 57. Вы получаете сообщение об ошибке или оно просто не работает должным образом?

ETHproductions

@ETHproductions На самом деле, да, это работает. Это просто происходит сбой на repl.it .

Арно

2

Haskell , 38 байт

(==).sum<*>foldl1 xorявляется анонимной функцией, возвращающей Bool. Используйте как ((==).sum<*>foldl1 xor) [2,0,1].

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

Попробуйте онлайн!

Практически тот же трюк от pizzapants184 и Leaky Nun, который используют все, за исключением того, что с именами операторов Haskell он сохраняет один байт для использования (побитовый) xorвместо(.|.) (побитовый или).
(==).sum<*>foldl1 xorэто бессмысленная версия \l->sum l==foldl1 xor l.

Орджан Йохансен
источник

2

Java 8, 53 байта

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

Порт ответа @LeakyNun 's Jelly .

Объяснение:

Попробуй это здесь.

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

Кевин Круйссен
источник

1

Pyth , 6 байт

qsQ.|F

Тестирование.

Мистер Xcoder
источник

1

Шелуха , 5 байт

§=ΣFv

Попробуйте онлайн!

Мистер Xcoder
источник

1

Perl 6 , 15 байт

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

Проверь это

Expanded:

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

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

  ==

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

      $_  # the input
}

Брэд Гилберт b2gills
источник

1

Красный , 78 байт

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]

Как это устроено:

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

Попробуйте онлайн!

Гален Иванов
источник

1

Wolfram Language (Mathematica) , 15 байтов

Tr@#==BitOr@@#&

Попробуйте онлайн!

alephalpha
источник

0

Пакетный, 73 байта

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

Выходы 1для правды, ничего для фальши. Еще один очевидный порт для пиццы 184 / Алгоритм Leaky Nun.

Нил
источник

0

J , 10 байт

+/=+./&.#:

Еще один порт с решениями для пиццерий184 и Leaky Nun.

Как это устроено?

+/.&.#: - преобразовать числа в двоичные числа, применить их поразрядно или к степеням двух и преобразовать обратно из двоичного числа в десятичное

+/ - уменьшить ввод путем сложения

= - равны ли выше?

Попробуйте онлайн!

Простая альтернатива

J , 12 байт

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

Как это устроено?

+/@#: - преобразовать каждое число в двоичное и найти сумму каждой степени 2

>./ - найти максимум

2>- это меньше, чем 2? -> правда

Попробуйте онлайн!

Гален Иванов
источник

0

Треугольность , 31 байт

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

Попробуйте онлайн!

Альтернативный раствор, 31 байт

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

Попробуйте онлайн!

Мистер Xcoder
источник

Мод 2 Полиномиальные коэффициенты

задача

счет

Примеры:

Тестовые случаи:

Ответы:

Желе , 4 байта

Python 3 2, 55 43 42 байта

Python 2 , 37 байт

Чисто , 38 байт

Japt, 6 байт

JavaScript (ES6), 37 35 34 байта

Контрольные примеры

Чередующийся версия, 38 байт

Контрольные примеры

Haskell , 38 байт

Java 8, 53 байта

Pyth , 6 байт

Шелуха , 5 байт

Perl 6 , 15 байт

Expanded:

Красный , 78 байт

Как это устроено:

Wolfram Language (Mathematica) , 15 байтов

Пакетный, 73 байта

J , 10 байт

Как это устроено?

Простая альтернатива

J , 12 байт

Как это устроено?

Треугольность , 31 байт

Альтернативный раствор, 31 байт