В этом задании вам будет предложено реализовать любую функцию (или полную программу), которая выполняет два свойства. Эти свойства:
Ваша функция должна быть инъективной (обратимой) функцией от полиномов с неотрицательными целочисленными коэффициентами до неотрицательных целых чисел. Это означает, что никакие два неравных входа не могут быть сопоставлены с одинаковым выходом.
Ваша функция должна сохранить общее количество битов от своего входа до выхода. Это означает, что если вы посчитаете 1 бит каждого коэффициента полинома, их сумма должна быть такой же, как число 1 бит в двоичном представлении выходных данных. Например
9
,1001
в двоичном коде, поэтому он имеет 21
бита.
IO
Целый неотрицательный многочлен такой же, как бесконечный список неотрицательных целых чисел, так что после определенной точки все целые числа равны нулю. Таким образом, полиномы могут быть представлены либо бесконечными списками (хотя это, вероятно, нежелательно), либо конечными списками с неявными нулями после конца списка.
Основное различие между полиномами и конечными списками заключается в том, что добавление нуля в конец списка изменит список:
При добавлении нуля в конец многочлена не изменяется его значение:
Таким образом, если ваша функция принимает конечный список, представляющий многочлен в качестве входных данных, добавление нуля не должно изменить его результат.
При представлении полиномов в виде списков вы можете представлять их либо с первой, либо с последней записью, представляющей постоянный член. Например, у вас может быть одна из следующих возможностей:
В первом случае добавление нулей в конец списка не должно изменить результат; во втором случае, добавляя нули к передней части списка не должно изменить результат.
Конечно, если ваш язык поддерживает многочлены, вы можете использовать их в качестве входных данных.
Вывод должен быть неотрицательным целочисленным выводом через любые стандартные методы.
Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.
[]
или[0]
правильный вход?Ответы:
Желе , 8 байт
Попробуйте онлайн!
Левый обратный, 5 байтов
Попробуйте онлайн!
Как это устроено
источник
Wolfram Language (Mathematica) ,
3620 байтПопробуйте онлайн!
Принимает полином f (x) в качестве входных данных. Оценивает y * f (y), где y = 2 ^ (f (2)!). К сожалению, это означает, что результаты становятся довольно большими.
Оценка y * f (y) сохранит число 1-битов всякий раз, когда y на степень 2 больше любого коэффициента, что верно для значения, выбранного выше. Мы выбираем y = 2 ^ (f (2)!), Чтобы сделать результат инъективным:
источник
Wolfram Language (Mathematica) , 61 байт
Попробуйте онлайн!
Два положительных целых числа могут быть сопоставлены с одним положительным целым числом. Позвольте
a, b
быть два натуральных числа. Тогдаa, b -> (2a - 1) 2^(b-1)
это биекция из NxN в N.Эта функция находит положение всех
1
битов на входе (с места 1) и применяет к каждой позиции только инъективный вариант приведенной выше карты. Затем каждое полученное число возводится в степень двух, и все числа складываются вместе (что нормально, поскольку мы применили инъективное отображение NxN -> N).Например:
Обратная функция (124 байта)
Вот обратная функция для проверки на инъективность.
Попробуйте онлайн!
источник
Python 2 ,
118117114103100 байт100 байтов от Джонатана Фреха:
Попробуйте онлайн!
103 байта с возможностью игры в гольф 1
Попробуйте онлайн!
-15 байт благодаря Джонатану Фреху
Он создает число, которое сначала содержит биты «on», а затем унарное представление массива, интерпретируемое как троичное число.
Троичное число создается путем преобразования чисел в двоичные строки (
0bNNN
), а затем заменыb
на2
.1 Я мог бы сэкономить 14 байтов, преобразовав его в число с основанием 12, но TIO не хватило памяти, поэтому я решил использовать это.
источник
05AB1E , 14 байтов
Попробуйте онлайн!
Дает те же результаты, что и раствор Денниса Желе, но методика немного отличается.
Как?
Давайте попробуем ввод
[1, 2, 3]
:источник
Python 2 , 74 байта
Попробуйте онлайн!
источник
JavaScript 6,
9683 байтавыводит двоичное выражение
источник
replace(/0|2/g,0)
Кажется, тоже работает, но сложнее декодироватьx=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/2/g,'0'.repeat(t))
. Чувствую себя хорошо, но не могу доказать