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”

JavaScript (ES6) 42 74

n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

Przetestuj w konsoli FireFox

;[0,1,10,11,42,100,800,1060,10270,100501]
.forEach(x => console.log(x +" -> '" + S(x) + "'"))

Wynik

0 -> ''
1 -> '0'
10 -> '9'
11 -> '00'
42 -> '31'
100 -> '89'
800 -> '689'
1060 -> '949'
10270 -> '9159'
100501 -> '89390'

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:

  1..10 -> 0..9 (delta -1)
 11..110 -> 00..99 (delta -11)
111..1110 -> 000..999 (delta -111) mmm there's a pattern here...

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

var F=
n=>(n-~(n+'').replace(/./g,8)+'').slice(1)

function update()
{
  var i=+I.value
  O.textContent = F(i)
}


update()

<input id=I value=99 type=number oninput='update()'><pre id=O></pre>

Cudowny 177 173 170

@0@6000000@5
}0&0&0&0&0
>0@6&3
\\--\/&2
@0/\@4\/&1!!
@4@1..@2@5@3
IIIIIIIIIIII
FF&1FF&2FF&3
@1OO@2OO@3OO
:I
}1..}10001F7
=9&1++..&1&0
&0}0&1&0{1{1
{>\/{0//
:O
}0
+Z
+C
{0

Dział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
}0
+Z
+C
{0

:Oto 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ć, }0jest 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. +Zdodaje 35 do każdego marmuru, który przechodzi nad nim i pozwala mu spaść. +Crobi to samo, ale tylko dodaje 12. {0jest 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).

:I
}1 .. }1 00 01 F7
=9 &1 ++ .. &1 &0
&0 }0 &1 &0 {1 {1
{> \/ {0 //

Ta tablica wygląda na nieco bardziej skomplikowaną. Powinieneś być w stanie zidentyfikować się :Ijako 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 }0i }1. Oznacza to, że ta funkcja przyjmuje 2 wejścia. Zauważysz również, że istnieją dwa wystąpienia }1urządzenia. Po wywołaniu funkcji obie te komórki będą zawierały tę samą wartość. Urządzenie }0wejś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 }1urządzenia wejściowe:

}1
=9 &1
&0
{>

Upadnie przy pierwszym tiku i uderzy w =9urzą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. &0i &1są synchronizatorami. Trzymają kulki, które na nie spadają, dopóki wszystkie inne &nsynchronizatory również nie zostaną wypełnione. Jak można się spodziewać, warunkowo spowoduje to inne zachowanie w innej części planszy.

}1 00 01 F7
++ .. &1 &0
&1 &0 {1 {1
{0 //

Jeśli powiem ci, że ++to inkrementor, powinieneś już być w stanie powiedzieć, czym zostaną wypełnione różne synchronizatory. Lewa strona &1będzie zawierała wartość wejściową }1+ 1, a &0obok niej będzie 0 (00 literał językowy, reprezentowany w systemie szesnastkowym). Drugi &1będzie zawierał wartość 1, a prawy &0zostanie wypełniony F7znakiem, 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 }1ma 9, &0synchronizatory się zapełniają. Spowoduje to, że wartość 0 spadnie na {0wyjście i F7(lub -9) na {1wyjście. Jeśli }1nie jest 9, {0zostanie wypełnione }1+ 1 i {0bę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.

@0 @6 00 00 00 @5
}0 &0 &0 &0 &0
>0 @6 &3
\\ -- \/ &2
@0 /\ @4 \/ &1 !!
@4 @1 .. @2 @5 @3
II II II II II II
FF &1 FF &2 FF &3
@1 OO @2 OO @3 OO

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 ( 00iFF ). Istnieje kilka synchronizatorów i deflektor. przejdźmy krok po kroku przez ten kawałek.

@0 @6
}0 &0
>0 @6
\\ --
@0 /\ @4

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 }0się znajduje. Opadnie i dosięgnie >0urzą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 &0synchronizatora 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, @0gdzie 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 @4każdą pętlę.

@4 @1 .. @2 @5 @3
II II II II II II
FF &1 FF &2 FF &3
@1 OO @2 OO @3 OO

Są tutaj 3 literały językowe ( FF), które natychmiast popadną w portale. Portale te zabiorą je do trzech IIurządzeń. IIodnosi się do tablicy, :Iktórą zdefiniowaliśmy w dalszej części pliku. Ponieważ :Ima 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 :Ifunkcji czekając aż istnieją wystarczająco marmurowe wejście STO uruchomić funkcję (jeden bardziej, że jest). Tam właśnie @4wchodzi portal. Kopia zmniejszonego wejścia wiersza poleceń przepływa tam przez każdą pętlę. Spowoduje to uruchomienie lewej :Iplanszy. 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 }0urządzeniach :Iplanszy, 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ż :Iplansze 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 :Ofunkcja przekształca wartość w wartość ascii cyfry reprezentującej wartość -1. Wyjście tych OOkomórek spadnie następnie z płyty, co drukuje odpowiadające im znaki ascii do STDOUT.

00 00 00 @5
&0 &0 &0
&3
\/ &2
   \/ &1 !!
      @5

Więc co się stanie, gdy marmur wiersza poleceń osiągnie 0 i wypełni te &0synchronizatory? Cóż, kilka kul o wartości 0 spada i wyzwala trzy synchronizatory, które trzymają cyfry (+ 1) numeru shortlex na dole planszy. &3jest uruchamiany jako pierwszy, ponieważ zawiera najbardziej znaczącą cyfrę, a następnie &2następuje &1. Ten marmur zostaje następnie teleportowany do drugiego @5urządzenia, zanim ostatecznie trafi do !!komórki, która kończy planszę.

CJam, 14 11 bajtów

l40f-Ab)s1>

Wypróbuj online.

Jak to działa

To podejście jest w dużej mierze oparte na odpowiedzi edc65 (za jego wyraźnym pozwoleniem ):

" Read a line L from STDIN. ";

l

" edc65's answer now forms an integer N by replacing each digit in L by an 8 and computes
  L - ~N = L + N + 1. Instead of adding L and N, we subtract 40 from each char code of L.
  Since the char code of the digit `D` is `D + 48`, this basically adds 8 to each digit.  ";

40f-

" Turn the resulting array into an integer by considering its elements a base 10 number.
  This is implemented as A ↦ A[-1] + 10 * A[-2] + 100 * A[-3] + ⋅⋅⋅, so it won't choke
  on digits greater than the base.                                                        ";

Ab

" Increment the integer on the stack to complete the calculation of L + N + 1.            ";

)

" Push the integers string representation and discard its first character.                ";

s1>

Przykładowy przebieg

$ for i in 0 1 10 11 42 100 800 1060 10270 100501
> do echo $i: $(cjam <(echo 'l40f-Ab)s1>') <<< $i)
> done
0:
1: 0
10: 9
11: 00
42: 31
100: 89
800: 689
1060: 949
10270: 9159
100501: 89390

Python 2 (38) (43)

f=lambda n:n*'_'and f(~-n/10)+`~-n%10`

Brak zamiany postaci, tylko arytmetyka.

Nie golfowany:

def f(n):
    if n==0: return ''
    else: return f((n-1)//10) + str((n-1)%10)

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-1z nich n, otrzymasz regularną reprezentację cyfr.

Do gry w golfa używam ~-nkomputerów n-1z wyższym priorytetem niż /10lub %10, oszczędzając na parens. Jest n*'_'to po prostu wytworzenie pustego łańcucha, n=0a także dowolnego innego łańcucha. W '_'tym celu może być dowolny ciąg.

Rubinowy, 70 68 66 64 57 bajtów

f=->n{i=-1;n-=10**i while n>=10**i+=1;i<1?'':"%0#{i}d"%n}

Definiuje funkcję, która ma być wywoływana jak f[42]. Oto przybliżony podział algorytmu:

• Traktować 0osobno.
• Odejmij moce 10, aż następna moc 10 nie będzie już pasować do liczby.
• Zamień liczbę na ciąg znaków wypełniony zerami po lewej stronie.

Kredyty za pomysł użycia ciągu formatu przejdź do Falko!

Alternatywnie, stosując podejście edc65:

f=->n{"#{n-~n.to_s.tr('^.',?8).to_i}"[1..-1]}

To 45 bajtów i tylko to uwzględniam, ponieważ nie biję go tym. ;)

Haskell, 67 bajtów

n('9':x)='0':n x
n(c:x)=succ c:x
n""="0"
f x=reverse$iterate n""!!x

to rozwiązanie w zasadzie dodaje 1 określoną liczbę razy, w skrócie notacji.

stosowanie:

>f 9
"8"
>f 100
"89"

CJam, 16 bajtów

li_)9*,{`1>}%_&=

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.

li                " Read an integer N from STDIN.                                   ";
  _)9*            " Push M := (N + 1) * 9.                                          ";
      ,           " Push A := [ 0 1 ... M - 1 ].                                    ";
       {   }%     " For each I ∊ A:                                                 ";
       {`1>}%     " Push its string representation and discard the first character. ";
             _&   " Remove duplicates from the resulting array.                     ";
               =  " Retrieve the Nth element.                                       ";

Przykładowy przebieg

$ for i in 0 1 10 11 42 100 800 1060 10270 100501
> do echo $i: $(cjam <(echo 'li_)9*,{`1>}%_&=') <<< $i)
> done
0:
1: 0
10: 9
11: 00
42: 31
100: 89
800: 689
1060: 949
10270: 9159
100501: 89390

Bash + coreutils, 27 bajtów

Port sprytnej odpowiedzi @ edc65 , z ulepszeniami @ Dennis :

cut -b2-<<<$[$1-~${1//?/8}]

Wynik:

$ for n in 0 1 10 11 42 100 110 111 800 1060 1110 1111 10270 100501; do echo "./shortlex.sh $n = \"$(./shortlex.sh $n)\""; done
./shortlex.sh 0 = ""
./shortlex.sh 1 = "0"
./shortlex.sh 10 = "9"
./shortlex.sh 11 = "00"
./shortlex.sh 42 = "31"
./shortlex.sh 100 = "89"
./shortlex.sh 110 = "99"
./shortlex.sh 111 = "000"
./shortlex.sh 800 = "689"
./shortlex.sh 1060 = "949"
./shortlex.sh 1110 = "999"
./shortlex.sh 1111 = "0000"
./shortlex.sh 10270 = "9159"
./shortlex.sh 100501 = "89390"
$ 

Poprzednia odpowiedź:

Bash + coreutils, 71 54 bajtów

Oto nieco inny sposób na zrobienie tego:

jot -w%x $1$1|tr 0-9a a0-9|grep -P ^\\d+$|sed $1!d 2>-

• jot generuje zwiększenie liczb całkowitych szesnastkowych
• tr 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 linii
• STDERR jest przekierowywany do pliku jednorazowego użytku „-”, dzięki czemu otrzymujemy pusty ciąg znaków, gdy zostanie przekazane 0 (sed zlicza numery linii zaczynające się od 1, więc błędy, jeśli 0 zostanie przekazane)
• Ponieważ odfiltrowujemy liczby za pomocą grep, musimy wygenerować więcej bazowych liczb całkowitych 11 z seq/ dcniż liczbą wejściową. Powtarzanie cyfr n jest więcej niż wystarczające.

Zauważ, że po wydrukowaniu numeru shortlex seqgeneruje 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ąc seqpracę natychmiast po wydrukowaniu, kosztem 7 bajtów:

jot -w%x $1$1|tr 0-9a a0-9|grep -P ^\\d+$|sed -n $1{p\;q} 2>-

Pytanie nie wymaga prędkości, więc wybieram krótszą wersję dla mojej głównej odpowiedzi.

Python 2 - 84, 70 66

n=input()
i=0
while n>=10**i:n-=10**i;i+=1
print"%%0%dd"%i%n*(i>0)

Alternatywne podejście (ta sama długość):

n=input()
k=len(`9*(n+1)/10`)
print"%%0%dd"%k%(n-int('1'*k))*(n>0)

Python 3, 107 znaków

Nie skończyło się to wygraną, ale pomyślałem, że to sprytne:

def G():yield'';yield from(r+c for r in G()for c in'0123456789')
S=lambda n:list(zip(range(n+1),G()))[n][1]

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].

Pyt , 12

Kolejny port odpowiedzi @ edc65, który jest wyraźnym zwycięzcą (IMO):

t`+hQv*l`Q\8

Pakiet testowy (dzięki @DigitalTrauama):

$ for n in 0 1 10 11 42 100 110 111 800 1060 1110 1111 10270 100501; do echo "shortlex.pyth $n = \"$(pyth programs/shortlex.pyth <<< $n)\""; done
shortlex.pyth 0 = ""
shortlex.pyth 1 = "0"
shortlex.pyth 10 = "9"
shortlex.pyth 11 = "00"
shortlex.pyth 42 = "31"
shortlex.pyth 100 = "89"
shortlex.pyth 110 = "99"
shortlex.pyth 111 = "000"
shortlex.pyth 800 = "689"
shortlex.pyth 1060 = "949"
shortlex.pyth 1110 = "999"
shortlex.pyth 1111 = "0000"
shortlex.pyth 10270 = "9159"
shortlex.pyth 100501 = "89390"

Wyjaśnienie:

Q = eval(input())             Implicit.
t`                            All but the first digit of
  +hQ                         Q+1 + 
   v                          eval(
    *l`Q                      len(repr(Q)) * 
     \8                       "8"

Java 8, 60 bajtów

n->(n-~new Long((n+"").replaceAll(".","8"))+"").substring(1)

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.

Haskell , 57 bajtów

((g=<<[0..])!!)
g 0=[""]
g n=[c:s|c<-['0'..'9'],s<-g$n-1]

Wypróbuj online!

Konstruuje nieskończoną listę liczb krótkich i indeksuje w niej odpowiedź. g nkonstruuje n-tą „generację” liczb, przygotowując kolejną cyfrę przed każdą z liczb z poprzedniej generacji.

05AB1E , 7 bajtów

Wykorzystuje edc65's replace przez 8 trick

8sg×+>¦

Wypróbuj online!

Wyjaśnienie

8          # push 8
 sg×       # repeat it len(input) times
    +      # add to input
     >     # increment
      ¦    # discard the first digit

Excel, 37 bajtów

Korzystanie z podejścia @ edc65:

=REPLACE(REPT(8,LEN(A1))+A1+1,1,1,"")

Galaretka , 5 bajtów

ḃ⁵ịØD

Wypróbuj online!

Jestem bardzo nowy w Jelly, więc jeśli możesz to poprawić, proszę o komentarz!

Wyjaśnienie:

ḃ⁵ịØD   Main link.
ḃ       Convert to bijective base ...
 ⁵      10.
  ị     Each number (1 - 10) is converted to the character at its index in the string...
   ØD   “0123456789” (digits)

(Zgodnie z powyższym komentarzem res problem polega na konwersji liczby na bazę bijective 10)