W tym wyzwaniu zostaniesz poproszony o wdrożenie dowolnej funkcji (lub pełnego programu), która spełnia dwie właściwości. Te właściwości to:

• Twoja funkcja musi być funkcją iniekcyjną (odwracalną) od wielomianów z nieujemnymi współczynnikami całkowitymi do nieujemnych liczb całkowitych. Oznacza to, że żadne dwa nierówne dane wejściowe nie mogą być odwzorowane na równą wydajność.

• Twoja funkcja musi zachować całkowitą liczbę „bitów” od wejścia do wyjścia. Oznacza to, że jeśli policzysz 1 bit każdego współczynnika wielomianu, ich suma powinna być taka sama jak liczba 1 bitów w binarnej reprezentacji wyniku. Na przykład 9jest 1001binarny, więc ma 2 1bity.

IO

Nieujemny wielomian liczb całkowitych jest taki sam, jak nieskończona lista liczb całkowitych nieujemnych, tak że po pewnym punkcie wszystkie liczby całkowite są zerowe. Tak więc wielomiany mogą być reprezentowane przez listy nieskończone (chociaż jest to prawdopodobnie niepożądane) lub przez listy skończone z niejawnymi zerami po końcu listy.

Kluczowa różnica między wielomianami a listami skończonymi polega na tym, że dodanie zera na końcu listy zmieni listę:

Dodanie zera na końcu wielomianu nie zmienia jego wartości:

Zatem jeśli twoja funkcja pobiera skończoną listę reprezentującą wielomian jako dane wejściowe, dodanie zera nie może zmienić jej wyniku.

Reprezentując wielomiany jako listy, możesz je reprezentować za pomocą pierwszego lub ostatniego wpisu reprezentującego stały termin. Na przykład możesz mieć jedną z następujących możliwości:

W pierwszym przypadku dodanie zer na końcu listy nie powinno zmienić wyniku; w drugim przypadku dodanie zer na początku listy nie powinno zmienić wyniku.

Oczywiście, jeśli twój język obsługuje wielomiany, możesz wziąć je jako dane wejściowe.

Wyjście powinno być nieujemną liczbą całkowitą za pomocą dowolnych standardowych metod.

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Galaretka , 8 bajtów

BFṢḄæ«ÆẸ

Wypróbuj online!

Lewy odwrotny, 5 bajtów

Bċ0ÆE

Wypróbuj online!

Jak to działa

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.

Wolfram Language (Mathematica) , 36 20 bajtów

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

Wypróbuj online!

Pobiera na wejściu wielomian f (x). Ocenia y * f (y), gdzie y = 2 ^ (f (2)!). Niestety oznacza to, że wyniki stają się dość duże.

Ocena y * f (y) zachowa liczbę 1-bitów, gdy y jest potęgą 2 większą niż jakikolwiek współczynnik, co jest prawdą dla wybranej powyżej wartości. Wybieramy y = 2 ^ (f (2)!), Aby wynik był iniekcyjny:

• Dwa różne dane wejściowe o tej samej wartości y dadzą różne dane wyjściowe, ponieważ zasadniczo czytamy dwie różne liczby w podstawie y.
• Jeżeli ustalimy k = f (2) i dlatego y, najmniejszą wartość y * f (y) osiąga się, gdy wejście jest stałym wielomianem równym k, a największą wartość osiąga się, gdy wejście jest wielomianem dającym podstawę -2 rozszerzenie k. W pierwszym przypadku y * f (y) = 2 ^ (k!) * K, aw drugim przypadku y * f (y) <2 ^ (k! * Ceil (lg k)), który jest mniejszy niż 2 ^ ((k + 1)!) * (k + 1).
• W rezultacie, dla dwóch wielomianów f i g przy f (2) <g (2), liczba całkowita, którą otrzymujemy z f, będzie mniejsza niż liczba całkowita, którą otrzymujemy z g.

Wolfram Language (Mathematica) , 61 bajtów

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

Wypróbuj online!

Dwie dodatnie liczby całkowite można zmapować na jedną dodatnią liczbę całkowitą. Niech a, bbędą dwie dodatnie liczby całkowite. Następnie a, b -> (2a - 1) 2^(b-1)następuje bijectcja z NxN do N.

Ta funkcja wyszukuje pozycję wszystkich 1bitów na wejściu (od miejsca 1s) i stosuje do tej pozycji wariant tylko do iniekcji powyższej mapy. Następnie każda wynikowa liczba jest podnoszona do potęgi dwóch, a wszystkie liczby są sumowane (co jest w porządku, ponieważ zastosowaliśmy iniekcyjną mapę NxN -> N).

Na przykład:

{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 *)

Funkcja odwrotna (124 bajty)

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

Oto funkcja odwrotna do testowania iniekcji.

Wypróbuj online!

Python 2 , 118 117 114 103 100 bajtów

100 bajtów Jonathana Frecha:

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)

Wypróbuj online!

103 bajty z możliwością gry w golfa ¹

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

Wypróbuj online!

-15 bajtów dzięki Jonathanowi Frechowi

Tworzy liczbę, która najpierw zawiera „on bity”, a następnie jednoargumentową reprezentację tablicy interpretowaną jako liczba trójnarodowa.

Liczba trójkowy jest utworzony przez konwersję do ciągów liczb binarnych ( 0bNNN), a następnie wymianie bz 2.

¹ Mógłbym zaoszczędzić 14 bajtów, zamieniając go na liczbę podstawową 12, ale TIO zabrakło pamięci, więc postanowiłem to wykorzystać.

05AB1E , 14 bajtów

gÅpImPoIbS{2β*

Wypróbuj online!

Daje takie same wyniki jak roztwór galaretki Dennisa, ale technika jest nieco inna.

W jaki sposób?

Wypróbujmy dane wejściowe [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).

Python 2 , 74 bajty

r='print 0';s='<<'
for n in input():r+=oct(n)[:0:-1];s+='0'+'1'*n
exec r+s

Wypróbuj online!

JavaScript 6, 96 83 bajtów

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

wyprowadza wyrażenie binarne

([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)