Podano dodatnią liczbę całkowitą n > 2
. Konwertujemy go na tablicę w następujący sposób:
- Jeśli jest równy,
2
zwróć pustą tablicę - W przeciwnym razie utwórz tablicę wszystkich
n
czynników pierwszych posortowanych rosnąco, następnie każdy element zamień jego indeksem w sekwencji liczb pierwszych i na koniec przekonwertuj każdy element na tablicę
Na przykład pozwala przekonwertować liczbę 46
na tablicę. Po pierwsze, przekonwertuj go na tablicę jego głównych czynników:
[2, 23]
Numer 23
jest 9
th prime, więc zastąpić 2
z pustej tablicy i 23
z [9]
. Tablica staje się teraz:
[[], [9]]
Najważniejsze czynniki 9
to, 3
a 3
więc:
[[], [3, 3]]
Zrób to samo dla obu 3
:
[[], [[2], [2]]]
I w końcu:
[[], [[[]], [[]]]]
Teraz, aby go zakodować, po prostu zamieniamy każdy otwarty nawias na 1
i każdy zamykający na 0
, następnie usuwamy wszystkie zera końcowe i upuszczamy jeden 1
z końca. To jest nasz numer binarny. Korzystając z powyższego przykładu:
[ ] [ [ [ ] ] [ [ ] ] ]
| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V
1 0 1 1 1 0 0 1 1 0 0 0
Teraz po prostu upuść trzy ostatnie zera i ostatnie 1
. Liczba staje 10111001
się 185
dziesiętna. To jest oczekiwany wynik. Zauważ, że w tablicy do konwersji binarnej nawiasy główne tablicy nie są uwzględnione.
Wkład
Dodatnia liczba całkowita n
większa niż 2
.
Wydajność
Zakodowana liczba całkowita n
.
Zasady i format IO
- Obowiązują standardowe zasady.
- Dane wejściowe mogą być ciągiem lub liczbą (ale w przypadku ciągu musi być w bazie 10).
- Dane wyjściowe mogą być ciągiem lub liczbą (ale w przypadku ciągu musi być w bazie 10).
- To jest golf golfowy , wygrywa najkrótsza odpowiedź w bajtach!
Przypadki testowe
Więcej przypadków testowych na żądanie.
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478
2
ponieważ przedłożenie nie jest wymagane do jego obsługi.Odpowiedzi:
Łuska ,
3531302926252422201915 bajtów-7 bajtów dzięki @Zgarb!
Zaoszczędź dodatkowe 4 bajty, pośrednio, dzięki Zgarb
Wypróbuj online!
Wyjaśnienie
źródło
φ
fixpoint lambda!`:0:1
może być`Jḋ2
.Galaretka ,
22 2019 bajtów-1 dzięki Erikowi Outgolfer (zera ogona z obu stron
t
, a nie z prawejœr
)Łącze monadyczne przyjmujące liczbę całkowitą większą niż 2 i zwracającą liczbę całkowitą większą niż 0 (2 zwróciłoby 0 zgodnie z oryginalną specyfikacją).
Wypróbuj online!
W jaki sposób?
To prawie dokładnie odwzorowuje podany opis, tylko z pewną porządkową manipulacją w celu utworzenia tablicy binarnej ...
źródło
Python 2 ,
212177 bajtówWypróbuj online!
Brak wbudowanych liczb pierwszych naprawdę boli liczbę bajtów, i przekracza limit czasu dla TIO z większymi liczbami pierwszymi. Zastosowania XNOR „s czek pierwszości.
Python 2 + gmpy2 , 175 bajtów
Wypróbuj online!
Ta wersja nie przekracza limitów czasu dla większych przypadków testowych (tj. 10000 - 10008).
źródło
Mathematica,
125119 bajtówStosuje nieco inne podejście; konwertuje indeksy pierwsze na
{1, index, 0}
i 2 na{1, 0}
.Wypróbuj na Wolfram Sandbox
Stosowanie:
źródło
Galaretka , 35 bajtów
Wypróbuj online!
źródło
J,
747366 bajtówWypróbuj online!
To prawdziwy bałagan, który z pewnością wymaga dalszej gry w golfa (np. Usunięcia wyraźnej definicji funkcji). Myślę, że boks, który robiłem, jest szczególnie tym, co przywołuje liczbę bajtów, ponieważ tak naprawdę nie wiem, co tam robię (było wiele prób i błędów). Ponadto jestem całkiem pewien, że są pewne wbudowane elementy, o których zapominam (np. Czuję, że
_2,~_1,
prawdopodobnie mają wbudowane).Wyjaśnienie (bez golfa)
Preambuła
Usiądźcie wygodnie, bo to nie będzie krótkie wyjaśnienie. Jak na ironię, zwięzły język został sparowany z osobą pełną.
Podzielę to na kilka funkcji
encode
koduje liczbę całkowitą za pomocą _1 i _2 zamiast [i]convert
konwertuje listę _1 i _2 na listę 1 i 0drop
upuszcza ostatni 1 i końcowe zeradecode
konwertuje z listy binarnej na liczbęPrzejdę przez przykładowe wezwanie na 46, które jest wyrażone w formacie bez golfa
Kodować
Tutaj jest wiele do wyjaśnienia.
Zauważ, że wyraźna definicja funkcji
3 : '[function]'
ocenia funkcję tak, jakby znajdowała się na REPL, z odpowiednim argumentem zastępującym każde wystąpieniey
(oznacza to, że mogę uniknąć konieczności używania caps ([:
), atops (@
) i ats (@:
) kosztem kilka bajtów).Oto, jak to wygląda dla każdej kolejnej iteracji na wejściu 46
Ta funkcja korzysta z funkcji negative (
::
) w celu zagnieżdżenia wartości w „nawiasach” (stosowane tutaj nawiasy to -1 i -2). Zasadniczo, za każdym razem, gdy rozkładamy na czynniki pierwsze i przekształcamy w indeksy liczb pierwszych, _1 jest dodawane, a _2 jest dołączane, które działają jak nawiasy. Gdy funkcja jest wywoływana na tych elementach, po prostu zwraca je takimi, jakimi są, ponieważq:
wystąpi błąd przy próbie faktoryzacji liczby ujemnej. Jest to także szczęście, żeq:
ma nie błąd na próby na czynniki 1 i zamiast zwraca pustą tablicę (w razie potrzeby).Konwertować
Konwersja jest znacznie prostsza. Po prostu usuwa wszystkie boks, a także pierwszy element, a następnie konwertuje wszystko na 1 i 0 (po prostu dodając 2)
Upuszczać
Spowoduje to odwrócenie listy, znalezienie pierwszej, a następnie upuszczenie wszystkich wartości do tej, a następnie ponowne odwrócenie listy.
Rozszyfrować
Dekodowanie to wbudowana funkcja,
#.
która pobiera listę 1 i 0 i konwertuje ją na liczbę binarną.źródło
Retina ,
244227225 bajtówWypróbuj online!
Jest to proste podejście oparte na algorytmie przedstawionym w pytaniu. Generowanie indeksu podstawowego ma złożoność wykładniczą, więc przekroczy limit czasu dla większych danych wejściowych
Wyjaśnienie:
źródło
Haskell ,
162160155 bajtówWypróbuj online!
Wyjaśnienie:
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
definiuje nieskończoną listę krotek liczb pierwszych i ich indeksów:[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...]
.Funkcja
(%)
pobiera tę listęr
i liczbęn
i konwertuje liczbę na odwróconą reprezentację tablicy czynników. Odbywa się to krok po kroku,r
dopóki nie znajdziemy liczby pierwszej, która dzielin
. My wtedy rekurencyjnie określić reprezentację wskaźnik ten główny i ująć ją w0
i1
a poprzedzić reprezentacjin
podzielony przez to prime.W przypadku
n=46
, to otrzymuje się liście[0,0,0,1,1,0,0,1,1,1,0,1]
, z których następnie wiodącymi zerami (snd.span(<1)
) i następne1
(tail
) są odrzucane. Następnie lista jest przekształcany na liczbę dziesiętną od elementu mnożenie listę potęgi dwójki i sumowanie otrzymanej listy:sum.zipWith((*).(2^))[0..]
.źródło
JavaScript, 289 bajtów
Bajty to suma kodu JavaScript bez podziałów wierszy po przecinkach (które są wstawiane tylko w celu lepszego formatowania i czytelności) (256 bajtów) oraz dodatkowe znaki dla przełącznika wiersza poleceń, które są wymagane przy korzystaniu z Chrome (33 bajty).
I dłuższa, lepiej czytelna wersja:
Kilka krótkich wyjaśnień:
f
jest czysto funkcjonalnym algorytmem faktoryzacji typu tail-recursive.c
zlicza, w którym miejscu występujer
liczba pierwszap
w sekwencji liczb pierwszych i zwraca albo[]
(jeślip=2
ir=1
) albo rozkłada na czynniki pierwsze i procesyr
za pomocą rekurencji.h
jest małą funkcją pomocniczą, która niestety jest niezbędna, ponieważmap
wywołuje dostarczoną funkcję znumberOfCurrentElement
drugim iwholeArray
trzecim argumentem, zastępując w ten sposób wartości domyślne podane,c
jeśli przekażemy tę funkcję bezpośrednio (zajęło mi to trochę czasu, aby dostać się po tej pułapce; zastąpienieh
jej definicją byłoby kilka bajtów dłuższe).s
przekształca wygenerowaną tablicę w ciąg. Używamyblank
zamiast0
, abyśmy mogli używaćtrim()
wo
.o
to funkcja, która ma zostać wywołana z wartością wejściowąi
zwracającą dane wyjściowe. Generuje reprezentację ciągu binarnego wymaganą przez specyfikację i konwertuje ją na (dziesiętną) liczbę.Edycja: Chrome należy uruchomić za pomocą,
chrome --js-flags="--harmony-tailcalls"
aby umożliwić optymalizację rekurencji ogona (patrz https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html ). Wymaga to również użycia trybu ścisłego.Poniższy test pokazuje, że obliczenia są nieco wolne dla niektórych wartości (najdłuższy to ponad sześć sekund
10007
na moim komputerze). Co ciekawe, bez optymalizacji rekurencji obliczeń obliczenia są znacznie szybsze (około 5), gdy nie ma przepełnienia stosu.źródło
tinylisp , 209 bajtów
Ostatni wiersz to nienazwana funkcja, która oblicza określone kodowanie. Wypróbuj online!
Wersja do gry w golfa
Oto kod, który miałem przed rozpoczęciem gry w golfa:
źródło
05AB1E , 18 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło