Бинарный отель Гильберта

18

В этом задании вам будет предложено реализовать любую функцию (или полную программу), которая выполняет два свойства. Эти свойства:

  • Ваша функция должна быть инъективной (обратимой) функцией от полиномов с неотрицательными целочисленными коэффициентами до неотрицательных целых чисел. Это означает, что никакие два неравных входа не могут быть сопоставлены с одинаковым выходом.

  • Ваша функция должна сохранить общее количество битов от своего входа до выхода. Это означает, что если вы посчитаете 1 бит каждого коэффициента полинома, их сумма должна быть такой же, как число 1 бит в двоичном представлении выходных данных. Например 9, 1001в двоичном коде, поэтому он имеет 2 1бита.


IO

Целый неотрицательный многочлен такой же, как бесконечный список неотрицательных целых чисел, так что после определенной точки все целые числа равны нулю. Таким образом, полиномы могут быть представлены либо бесконечными списками (хотя это, вероятно, нежелательно), либо конечными списками с неявными нулями после конца списка.

Основное различие между полиномами и конечными списками заключается в том, что добавление нуля в конец списка изменит список:

Списки

При добавлении нуля в конец многочлена не изменяется его значение:

Многочлены

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

При представлении полиномов в виде списков вы можете представлять их либо с первой, либо с последней записью, представляющей постоянный член. Например, у вас может быть одна из следующих возможностей:

Вперед или назад

В первом случае добавление нулей в конец списка не должно изменить результат; во втором случае, добавляя нули к передней части списка не должно изменить результат.

Конечно, если ваш язык поддерживает многочлены, вы можете использовать их в качестве входных данных.

Вывод должен быть неотрицательным целочисленным выводом через любые стандартные методы.


Это поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.

Мастер пшеницы
источник
Это []или [0]правильный вход?
JungHwan Мин
1
@JungHwanMin Да, оба они, они нулевой полином.
Пшеничный волшебник
Я знаю, что вы хотите поставить 1, чтобы разделить нули, но некоторые способы могут работать и казаться не очень хорошими ...
l4m2
1
@ l4m2 Извините, но я не понимаю ни одного из ваших комментариев. Насколько ваш вопрос идет, ведущие нули на что? Полином, коэффициенты? Я не уверен, что вы подразумеваете под "нулями не написано".
Wheat Wizard
1
Действительно ли изображения необходимы (то есть они не могут быть представлены с использованием форматированного текста) ??? Потому что люди, не имеющие возможности видеть изображения, не могут увидеть вашу проблему в полном объеме.
Mindwin

Ответы:

6

Желе , 8 байт

BFṢḄæ«ÆẸ

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

Левый обратный, 5 байтов

Bċ0ÆE

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

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

BFṢḄæ«ÆẸ  Main link. Argument: A (array)

B         Binary; convert each integer in A to base 2.
 F        Flatten; concatenate the resulting binary arrays.
  Ṣ       Sort the resulting bit array.
   Ḅ      Convert from base 2 to integer, yielding an integer x with as much set
          bits as there are set bits in A.
      ÆẸ  Unexponents; convert A = [a1, a2, ...] to y = (p1**a1 + p2**a2 + ...),
          where pn is the n-th prime number.
          By the fundamental theorem of arithmetic, the resulting integer is unique
          for each array A without trailing zeroes.
    æ«    Bitshift left; compute x * 2**y.
Деннис
источник
6

Wolfram Language (Mathematica) , 36 20 байт

x#/.x->2^(#/.x->2)!&

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

Принимает полином f (x) в качестве входных данных. Оценивает y * f (y), где y = 2 ^ (f (2)!). К сожалению, это означает, что результаты становятся довольно большими.

Оценка y * f (y) сохранит число 1-битов всякий раз, когда y на степень 2 больше любого коэффициента, что верно для значения, выбранного выше. Мы выбираем y = 2 ^ (f (2)!), Чтобы сделать результат инъективным:

  • Два разных входа с одинаковым значением y будут давать разные выходы, потому что мы по сути читаем два разных числа в базе y.
  • Если мы фиксируем k = f (2) и, следовательно, y, наименьшее значение y * f (y) достигается, когда входной сигнал является постоянным полиномом, равным k, и наибольшее значение достигается, когда входной сигнал является полиномом, дающим основание. -2 расширение к. В первом случае y * f (y) = 2 ^ (k!) * K, а во втором случае y * f (y) <2 ^ (k! * Ceil (lg k)), что меньше чем 2 ^ ((k + 1)!) * (k + 1).
  • В результате для двух полиномов f и g с f (2) <g (2) целое число, которое мы получаем из f, будет меньше, чем целое число, которое мы получаем из g.
Миша лавров
источник
5

Wolfram Language (Mathematica) , 61 байт

Tr[2^((2#2-1)2^#)&@@@Position[Reverse/@#~IntegerDigits~2,1]]&

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

Два положительных целых числа могут быть сопоставлены с одним положительным целым числом. Позвольте a, bбыть два натуральных числа. Тогда a, b -> (2a - 1) 2^(b-1)это биекция из NxN в N.

Эта функция находит положение всех 1битов на входе (с места 1) и применяет к каждой позиции только инъективный вариант приведенной выше карты. Затем каждое полученное число возводится в степень двух, и все числа складываются вместе (что нормально, поскольку мы применили инъективное отображение NxN -> N).

Например:

{1, 2, 3}
{{1}, {1, 0}, {1, 1}}             (* Convert to binary *)
{{1}, {0, 1}, {1, 1}}             (* Reverse each *)
{{1, 1}, {2, 2}, {3, 1}, {3, 2}}  (* Position of 1s *)
{2, 12, 8, 24}                    (* Inject to N *)
{4, 4096, 256, 16777216}          (* Raise to the power of 2 *)
16781572                          (* Add *)

Обратная функция (124 байта)

##+#&~Fold~#&@*Reverse/@Normal@SparseArray[{Log2[j=#~BitAnd~-#],(#/j+1)/2}->1&@@@(Reverse[#~IntegerDigits~2]~Position~1-1)]&

Вот обратная функция для проверки на инъективность.

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

Юнг Хван Мин
источник
5

Python 2 , 118 117 114 103 100 байт

100 байтов от Джонатана Фреха:

a=input()
while a[0]<1:a.pop(0)
y="".join("2"+bin(v)[2:]for v in a)
print~-2**y.count("1")<<int(y,3)

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

103 байта с возможностью игры в гольф 1

a=input()
while a[0]<1:a.pop(0)
x="".join(map(bin,a))
print~-(1<<x.count("1"))<<int(x.replace(*"b2"),3)

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

-15 байт благодаря Джонатану Фреху

Он создает число, которое сначала содержит биты «on», а затем унарное представление массива, интерпретируемое как троичное число.

Троичное число создается путем преобразования чисел в двоичные строки ( 0bNNN), а затем замены bна 2.

1 Я мог бы сэкономить 14 байтов, преобразовав его в число с основанием 12, но TIO не хватило памяти, поэтому я решил использовать это.

fergusq
источник
@JonathanFrech Спасибо большое :)
fergusq
1

05AB1E , 14 байтов

gÅpImPoIbS{2β*

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

Дает те же результаты, что и раствор Денниса Желе, но методика немного отличается.

Как?

Давайте попробуем ввод [1, 2, 3]:

gÅpImPoIbS{2β* | Full program.
               | STACK: [[1, 2, 3]]
               |
g              | Push the length.
               | STACK: [3]
 Åp            | Generate the first N primes.
               | STACK: [[2, 3, 5]]
   Im          | Push the input, and apply pairwise exponentiation.
               | STACK: [2, 9, 125]
     P         | Push the product.
               | STACK: 2250
      o        | Push 2 ** N.
               | STACK: 2 ** 2250 (way too large)
       Ib      | Push the input and convert to binary.
               | STACK: [2 ** 2250, ['1', '10', '11']].
         S{    | Sort all the characters.
               | STACK: [2 ** 2250, ['0', '1', '1', '1', '1']]
           2β  | Convert from binary.
               | STACK: [2 ** 2250, 15]
             * | Multiplication.
               | STACK: [2 ** 2250 * 15]
               | Implicitly print the top of the stack (2 ** 2250 * 15).
Мистер Xcoder
источник
0

JavaScript 6, 96 83 байта

x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/0|2/g,'')+'0'.repeat(t)

выводит двоичное выражение

([1,2]) => 3*2^21210(Decimal)
([0,1,2]) => 3*2^21210
([1,2,0]) => 3*2^2121020
([1,2,3,4]) => 31*2^212102112100(Threotically)
l4m2
источник
ноль приведет к пустой строке, представляющей ноль
l4m2
replace(/0|2/g,0)Кажется, тоже работает, но сложнее декодировать
l4m2
Не уверен насчет x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/2/g,'0'.repeat(t)). Чувствую себя хорошо, но не могу доказать
l4m2