Większość komputerów zapisuje liczby całkowite w postaci binarnej, ale wypisuje je w postaci dziesiętnej. Jednak dziesiętny jest tylko jedną reprezentacją, akurat zdarza się, że jest to wygodne.
Wyzwanie polega na napisaniu kodu do wyprowadzenia wartości całkowitej w postaci dziesiętnej shortlex .
Co to jest?
http://en.wikipedia.org/wiki/Shortlex_order
Shortlex przyjmuje długość ciągu cyfr jako główny znacznik wartości. Sekwencja, zaczynająca się od pustego ciągu reprezentującego zero, jest ...
ε,0,1,...,8,9,00,01,...98,99,000,001,...,998,999,0000,...
(Pomyśl o kolumnach Excela, ale używając tylko cyfr dziesiętnych).
Napisz program lub funkcję, która akceptuje liczbę całkowitą i zwraca ciąg odpowiadający reprezentacji tej liczby całkowitej w formacie shortlex-decimal, jak opisano powyżej.
Wartości testowe:
0 → „” (pusty ciąg znaków)
1 → „0”
10 → „9”
11 → „00”
42 → „31”
100 → „89”
800 → „689”
1060 → „949”
10270 → „9159”
100501 → „89390”
19, 20, 21, 22
w mapach dziesiętnych do08, 09, 10, 11
krótkich. Dlatego użyłem tego mylić100 -> 89
!Odpowiedzi:
JavaScript (ES6) 42
74Przetestuj w konsoli FireFox
Wynik
Jak o tym pomyślałem?
Biorąc pod uwagę stałą liczbę cyfr, sekwencja wyjściowa jest po prostu rosnąca, więc istnieje stała delta między wejściem a wyjściem. Spójrz:
Ale wiodącymi zerami są trudne do zarządzania, więc mam standardową sztuczkę, dodaję pierwszą cyfrę i działaj modulo (to znaczy wytnij pierwszą cyfrę na wyjściu). Następnie -1-> +9, -11 -> +89, -111 -> +889 i tak dalej.
Ostatni krok: nie dbam o to, jaka jest pierwsza cyfra, więc nie trzeba sprawdzać, czy numer wejściowy to <lub> niż 111 ... (szczerze mówiąc, znalazłem to metodą prób i błędów)
Test
źródło
n-~(n+'')
zamiast po prostun-~n
?(n+'').replace(...)
, zamień działa na ciągi, a nie na liczby.Cudowny
177173170Działa tylko dla wartości poniżej 256, ponieważ Marbelous jest językiem 8-bitowym.
Jak to działa
Marbelous to język 2D z wartościami reprezentowanymi przez 8-bitowe kulki, które spadają po jednej komórce na każdym tiku, chyba że jakieś urządzenie zapobiega ich upadkowi. Ten program Marbelous składa się z 3 plansz; zacznijmy od najłatwiejszego:
:O
to nazwa tablicy (a dokładniej, O to nazwa i: mówi interpretowanemu, że ta linia jest nazwą. Nadając tablicom nazwę, inne tablice mogą na nich wywoływać,}0
jest urządzeniem wejściowym, można to postrzegać jako argument tej funkcji. Ta komórka zostanie zastąpiona przez marmur wejściowy (wartość), gdy funkcja zostanie wywołana.+Z
dodaje 35 do każdego marmuru, który przechodzi nad nim i pozwala mu spaść.+C
robi to samo, ale tylko dodaje 12.{0
jest komórką wyjściową , gdy marmur dotrze do tej komórki, funkcja wyjdzie i zwróci wartość w tym urządzeniu wyjściowym.Tak więc razem ta tablica przyjmuje jedną wartość, a następnie dodaje do niej 47. Dla nas oznacza to, że zamienia każdą pojedynczą cyfrę w kod ascii cyfry -1 (będzie to oczywiście działało również dla 10).
Ta tablica wygląda na nieco bardziej skomplikowaną. Powinieneś być w stanie zidentyfikować się
:I
jako nazwa płyty i zauważyłeś niektóre urządzenia wejściowe i wyjściowe. Zauważysz, że mamy dwa różne urządzenia wejściowe}0
i}1
. Oznacza to, że ta funkcja przyjmuje 2 wejścia. Zauważysz również, że istnieją dwa wystąpienia}1
urządzenia. Po wywołaniu funkcji obie te komórki będą zawierały tę samą wartość. Urządzenie}0
wejściowe znajduje się bezpośrednio nad\/
urządzeniem, działa jak kosz na śmieci i natychmiast usuwa marmur, który na niego spadnie.Rzućmy okiem na to, co dzieje się z jedną z kul umieszczonych na płycie przez
}1
urządzenia wejściowe:Upadnie przy pierwszym tiku i uderzy w
=9
urządzenie. Porównuje to wartość marmuru do 9 i pozwala, aby marmur wypadł, jeśli oświadczenie=9
oceni to. Marmur zostaje przesunięty w prawo, jeśli nie.&0
i&1
są synchronizatorami. Trzymają kulki, które na nie spadają, dopóki wszystkie inne&n
synchronizatory również nie zostaną wypełnione. Jak można się spodziewać, warunkowo spowoduje to inne zachowanie w innej części planszy.Jeśli powiem ci, że
++
to inkrementor, powinieneś już być w stanie powiedzieć, czym zostaną wypełnione różne synchronizatory. Lewa strona&1
będzie zawierała wartość wejściową}1
+ 1, a&0
obok niej będzie 0 (00
literał językowy, reprezentowany w systemie szesnastkowym). Drugi&1
będzie zawierał wartość 1, a prawy&0
zostanie wypełnionyF7
znakiem, który odejmuje 9 od wartości, ponieważ dodawanie w Marbelous jest modulo 256.//
jest urządzeniem odchylającym, które popycha każdy marmur w lewo zamiast upuszczać.Połączenie tego wszystkiego daje ci to: jeśli marmur
}1
ma 9,&0
synchronizatory się zapełniają. Spowoduje to, że wartość 0 spadnie na{0
wyjście iF7
(lub -9) na{1
wyjście. Jeśli}1
nie jest 9,{0
zostanie wypełnione}1
+ 1 i{0
będzie zawierało 1. Istnieje również{>
urządzenie, jest to specjalne wyjście, które wyrzuca marmur obok płyty zamiast pod nią. Zostanie to wypełnione}1
jeśli będzie równe 9.Dobra, teraz duża. Ta tablica nie ma wyraźnej nazwy, ponieważ jest główną płytą pliku. Jego domyślna nazwa to
Mb
. Powinieneś być w stanie rozpoznać niektóre komórki. Istnieje urządzenie wejściowe, niektóre literały językowe (00
iFF
). Istnieje kilka synchronizatorów i deflektor. przejdźmy krok po kroku przez ten kawałek.Tak więc wartość wejściowa (wejście wiersza poleceń, ponieważ jest to płyta główna) zaczyna się od drugiej komórki od góry, gdzie
}0
się znajduje. Opadnie i dosięgnie>0
urządzenia, które jest kolejnym urządzeniem porównawczym. każdy marmur większy niż 0 wpada, każdy inny marmur zostaje popchnięty w prawo. (ponieważ zmienne Marbelous są niepodpisane, tylko dokładnie 0 zostanie przesunięte w prawo). Ten marmur o zerowej wartości trafi następnie@6
urządzenie. To jest portal, który przenosi marmur do innego odpowiedniego portalu, w tym przypadku tuż nad nim. Marmur 0 dotrze wtedy do&0
synchronizatora i wyzwoli niektóre rzeczy w innym miejscu.Jeśli marmur nie jest równy 0, upada, zostaje odbity w prawo przez
\\
uderzenia,--
które zmniejsza go o jeden, a następnie spada na/\
klonera. To urządzenie bierze marmur i wysyła jedną jego kopię w prawo, a drugą w lewo. Lewy zostanie przeniesiony w górę do drugiego,@0
gdzie marmur ponownie przejdzie tę samą sekwencję. Lewy zostanie zabrany gdzie indziej. To daje nam pętlę, która zmniejsza wartość wiersza poleceń raz na pętlę i wyzwala pewne zachowanie w każdej pętli, aż osiągnie 0. Następnie wyzwala inne zachowanie.Zobaczmy, co dzieje się z marmurem wciskanym w
@4
każdą pętlę.Są tutaj 3 literały językowe (
FF
), które natychmiast popadną w portale. Portale te zabiorą je do trzechII
urządzeń.II
odnosi się do tablicy,:I
którą zdefiniowaliśmy w dalszej części pliku. Ponieważ:I
ma 2 różne urządzenia wejściowe, jego reprezentacja na innej płycie musi mieć szerokość 2 komórek. Ponieważ mamy 6 komórek zawierającychII
, kamera informuje, że mamy 3 instancje tej funkcji na płycie.FF
(Lub 256 lub -1 jeśli będzie) marmury zasiądzie w komórkach wejściowych:I
funkcji czekając aż istnieją wystarczająco marmurowe wejście STO uruchomić funkcję (jeden bardziej, że jest). Tam właśnie@4
wchodzi portal. Kopia zmniejszonego wejścia wiersza poleceń przepływa tam przez każdą pętlę. Spowoduje to uruchomienie lewej:I
planszy. Początkowo z wartościami 256 (lub -1) i bez względu na wejście wiersza poleceń było -1. Lewy marmur zostanie umieszczony w}0
urządzeniach:I
planszy, a prawy do}1
. Jeśli przypomnisz sobie, co zrobiła ta tablica, będziesz w stanie powiedzieć, jaki to ma wynik. Wyprowadzi zwiększoną wersję prawego wejścia na lewym wyjściu (i zamienia 9 w 0, a nie 10) i wyprowadza albo 1 albo -9 po prawej.Zwiększona wartość zostanie przeniesiona z powrotem do właściwej komórki wejściowej przez portal, a wartość po prawej stronie spadnie do synchronizatora. Jeśli synchronizator już trzyma marmur, dwie kulki zderzą się. Kolumny zderzające są dodawane razem modulo 256. Tak więc wartości w synchronizatorach wykonają następujące czynności: Zaczynają puste, a następnie zmieniają się na 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a następnie na 1 ponownie (od 247 dodaje się modulo 256).
Możesz również pamiętać, że marmur zostaje wyprowadzony w prawo, gdy wartość wejściowa zapętla się z powrotem do 0. Ponieważ
:I
plansze znajdują się obok siebie, thsi raz aktywuje tablicę po prawej stronie. Spowoduje to wypełnienie trzech synchronizatorów wartościami, które są o jeden wyższe niż powinny być, aby były krótką reprezentacją wejścia wiersza poleceń, do czasu zapętlenia do 0.Możesz także pamiętać, że
:O
funkcja przekształca wartość w wartość ascii cyfry reprezentującej wartość -1. Wyjście tychOO
komórek spadnie następnie z płyty, co drukuje odpowiadające im znaki ascii do STDOUT.Więc co się stanie, gdy marmur wiersza poleceń osiągnie 0 i wypełni te
&0
synchronizatory? Cóż, kilka kul o wartości 0 spada i wyzwala trzy synchronizatory, które trzymają cyfry (+ 1) numeru shortlex na dole planszy.&3
jest uruchamiany jako pierwszy, ponieważ zawiera najbardziej znaczącą cyfrę, a następnie&2
następuje&1
. Ten marmur zostaje następnie teleportowany do drugiego@5
urządzenia, zanim ostatecznie trafi do!!
komórki, która kończy planszę.źródło
CJam,
1411 bajtówWypróbuj online.
Jak to działa
To podejście jest w dużej mierze oparte na odpowiedzi edc65 (za jego wyraźnym pozwoleniem ):
Przykładowy przebieg
źródło
Python 2 (38)
(43)Brak zamiany postaci, tylko arytmetyka.
Nie golfowany:
Nie mam dobrego powodu, dla którego rekurencja działa, po prostu dopasowuję ten wzorzec do listy wartości. Jeśli zmienisz każdy
n-1
z nichn
, otrzymasz regularną reprezentację cyfr.Do gry w golfa używam
~-n
komputerówn-1
z wyższym priorytetem niż/10
lub%10
, oszczędzając na parens. Jestn*'_'
to po prostu wytworzenie pustego łańcucha,n=0
a także dowolnego innego łańcucha. W'_'
tym celu może być dowolny ciąg.źródło
Rubinowy,
7068666457 bajtówDefiniuje funkcję, która ma być wywoływana jak
f[42]
. Oto przybliżony podział algorytmu:0
osobno.Kredyty za pomysł użycia ciągu formatu przejdź do Falko!
Alternatywnie, stosując podejście edc65:
To 45 bajtów i tylko to uwzględniam, ponieważ nie biję go tym. ;)
źródło
Haskell, 67 bajtów
to rozwiązanie w zasadzie dodaje 1 określoną liczbę razy, w skrócie notacji.
stosowanie:
źródło
CJam, 16 bajtów
Wypróbuj online. Wymaga co najmniej O (n) czasu i pamięci, więc pozostaw 100501 tłumaczowi offline ...
Jak to działa
Podstawową ideą tego podejścia jest obliczenie co najmniej N miejsc dziesiętnych w ich naturalnym porządku i odrzucenie wszystkich oprócz N-tego. Niezbyt wydajny, ale krótki.
Przykładowy przebieg
źródło
Bash + coreutils, 27 bajtów
Port sprytnej odpowiedzi @ edc65 , z ulepszeniami @ Dennis :
Wynik:
Poprzednia odpowiedź:
Bash + coreutils,
7154 bajtówOto nieco inny sposób na zrobienie tego:
jot
generuje zwiększenie liczb całkowitych szesnastkowychtr
konwertuje to na (0,1, ..., 8,9, b, ... f, 0a, 00,01, ..., 99,9b, ..., ff, 0aa, ..., 000 , ...)grep
po prostu filtruje wszystkie wiersze zawierające cyfry, aby dać (0,1, ..., 8,9,00, ..., 99 000 ....)sed
usuwa wszystko oprócz n-tej liniised
zlicza numery linii zaczynające się od 1, więc błędy, jeśli 0 zostanie przekazane)grep
, musimy wygenerować więcej bazowych liczb całkowitych 11 zseq
/dc
niż liczbą wejściową. Powtarzanie cyfr n jest więcej niż wystarczające.Zauważ, że po wydrukowaniu numeru shortlex
seq
generuje liczby aż do$1$1
, co zwalnia szczególnie dla większych liczb wejściowych - O (n²), tak myślę. Możemy przyspieszyć, kończącseq
pracę natychmiast po wydrukowaniu, kosztem 7 bajtów:Pytanie nie wymaga prędkości, więc wybieram krótszą wersję dla mojej głównej odpowiedzi.
źródło
s='jot -w%x $1$1|tr 0-9a a0-9|grep -P ^\\d+$|sed $1!d 2>-'; echo ${#s}
. Podejrzewam, że możesz używać Pythona do mierzenia długości łańcucha, który traktuje „\\” jako jeden znak.$a
wydaje się niepotrzebna;cut -b2-<<<$[$1-~${1//?/8}]
powinien działać dobrze.Python 2 -
84, 7066Alternatywne podejście (ta sama długość):
źródło
Python 3, 107 znaków
Nie skończyło się to wygraną, ale pomyślałem, że to sprytne:
Generator dla całej sekwencji definiuję w 64 znakach. Niestety muszę przejść przez kilka skręceń, aby uzyskać n-ty element generatora ... gdybym tylko mógł
S=lambda n:G()[n]
.źródło
Pyt , 12
Kolejny port odpowiedzi @ edc65, który jest wyraźnym zwycięzcą (IMO):
Pakiet testowy (dzięki @DigitalTrauama):
Wyjaśnienie:
źródło
[8, 8, 9] -> 889
). Jak to robisz?jk
zamieni twoją listę w ciąg iv
przekształci ją w liczbę całkowitą.vjk[8 8 9]
[2 -1] -> 19
i[1 11] -> 21
.Java 8, 60 bajtów
Port niesamowitej odpowiedzi JavaScript (ES6) @ edc65 , ponieważ wątpię, że można to zrobić w języku Java w sposób arytmetyczny krótszy.
Wypróbuj tutaj.
źródło
Haskell , 57 bajtów
Wypróbuj online!
Konstruuje nieskończoną listę liczb krótkich i indeksuje w niej odpowiedź.
g n
konstruuje n-tą „generację” liczb, przygotowując kolejną cyfrę przed każdą z liczb z poprzedniej generacji.źródło
05AB1E , 7 bajtów
Wykorzystuje edc65's replace przez 8 trick
Wypróbuj online!
Wyjaśnienie
źródło
Excel, 37 bajtów
Korzystanie z podejścia @ edc65:
źródło
Galaretka , 5 bajtów
Wypróbuj online!
Jestem bardzo nowy w Jelly, więc jeśli możesz to poprawić, proszę o komentarz!
Wyjaśnienie:
(Zgodnie z powyższym komentarzem res problem polega na konwersji liczby na bazę bijective 10)
źródło