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
9
jest1001
binarny, więc ma 21
bity.
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.
[]
albo[0]
ważny wejście?Odpowiedzi:
Galaretka , 8 bajtów
Wypróbuj online!
Lewy odwrotny, 5 bajtów
Wypróbuj online!
Jak to działa
źródło
Wolfram Language (Mathematica) ,
3620 bajtówWypró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:
źródło
Wolfram Language (Mathematica) , 61 bajtów
Wypróbuj online!
Dwie dodatnie liczby całkowite można zmapować na jedną dodatnią liczbę całkowitą. Niech
a, b
będą dwie dodatnie liczby całkowite. Następniea, b -> (2a - 1) 2^(b-1)
następuje bijectcja z NxN do N.Ta funkcja wyszukuje pozycję wszystkich
1
bitó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:
Funkcja odwrotna (124 bajty)
Oto funkcja odwrotna do testowania iniekcji.
Wypróbuj online!
źródło
Python 2 ,
118117114103100 bajtów100 bajtów Jonathana Frecha:
Wypróbuj online!
103 bajty z możliwością gry w golfa 1
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 wymianieb
z2
.1 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ć.
źródło
05AB1E , 14 bajtów
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]
:źródło
Python 2 , 74 bajty
Wypróbuj online!
źródło
JavaScript 6,
9683 bajtówwyprowadza wyrażenie binarne
źródło
replace(/0|2/g,0)
wydaje się również działać, ale trudniej dekodowaćx=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/2/g,'0'.repeat(t))
. Czuję się dobrze, ale nie mogę udowodnić