Przekształcanie liczb w „Niezupełnie system wartości miejsca”

11

Stwórzmy system liczb, w którym największa cyfra w n-tym miejscu wartości (licząc od prawej do lewej) o długości liczby m jest zawsze równa m - n + 1. Na przykład największa 5-cyfrowa liczba wyrażalna w tym systemie jest napisany 12345. Poza liczbą cyfr dostępnych do użycia w określonym miejscu, które jest ograniczone, wszystkie inne przyrosty są standardowe. Mianowicie, gdy cyfra ma przekroczyć limit cyfr, dodajemy ją do następnej cyfry.

Oto jak liczenie byłoby reprezentowane w tym systemie:

1; 10; 11; 12; 100; 101; 102; 103; 110; 111; 112; 113; 120; 121; 122; 123; 1000; 1001 ...

Twoim zadaniem jest napisanie funkcji, która pobierze standardową liczbę podstawową 10 i przekształci ją w mój system numeracji.

Preferowany jest krótszy kod. Bonne Chance!

** Jeśli potrzebujesz cyfr po 9 (powinieneś), możesz użyć liter lub możesz zwrócić 2-cyfrową liczbę jako element listy.

Przypadki testowe

10 -> 111
20 -> 1003
30 -> 1023
50 -> 1123
100 -> 10035
23116 -> 1234567
21977356 -> 123456789A

Ostatni przypadek może być niewiarygodnie powolny, w zależności od sposobu wdrożenia. Nie musisz go uruchamiać, jeśli trwa to zbyt długo lub zużywa zbyt dużo pamięci. Należy jednak pamiętać, że istnieją sposoby na szybkie uruchomienie i użycie niewielkiej ilości pamięci.

Ando Bando
źródło
Biorąc pod uwagę twój ostatni komentarz, czy jest w porządku, jeśli zawsze zwracamy listę z cyframi?
Greg Martin
Tak, to rozsądny sposób na uzyskanie danych wyjściowych, pod warunkiem, że liczby są prawidłowe
Ando Bando
1
Dostaję 100 -> 10035raczej 100 -> 10033, czy możesz to zweryfikować?
Greg Martin
@GregMartin 10035 wydaje się mieć rację. Wykonałem moje obliczenia za pomocą pióra, a nie programu i dlatego popełniłem błąd obliczeniowy. Wydaje mi się, że mamy komputery na poważnie
Ando Bando,

Odpowiedzi:

4

Mathematica, 64 bajty

Part[Join@@Array[Tuples@Join[{{1}},Array[Range,#-1,3]-1]&,#],#]&

Nienazwana funkcja przyjmująca dodatni argument liczby całkowitej i zwracająca listę liczb całkowitych.

Join[{{1}},Array[Range,#-1,3]-1]zwraca listę zagnieżdżoną { {1}, {0,1,2}, {0,1,2,3}, ..., {0,1,...,#} }. Następnie Tupleszwraca (posortowany) zestaw wszystkich krotek, w których znajduje się pierwszy element, w {1}których znajduje się drugi element {0,1,2}i tak dalej; są to #numery cyfrowe w tym systemie numeracji. Join@@Array[...,#]zwraca tablicę wszystkich liczb w tym systemie numeracji z najwyżej #cyframi i Part[...,#]wyodrębnia tę #liczbę.

To jest beznadziejnie powolne! Działa poprawnie do wejściowego aż do 9. W przypadku większych wejścia, test go zastępując koniec ,#],#]&z ,Ceiling[0.9Log[#]]],#]&; nakłada to bardziej realistyczny pułap na liczbę cyfr potrzebną do przejścia wystarczająco daleko w systemie numeracji, aby znaleźć tę, której chcemy.

Greg Martin
źródło
3

Mathematica, 93 bajty

Nest[#/.{x___,y_}:>{x,y+1}//.x:{y___,z_:0,w_,v___}/;w>Tr[1^x]-Tr[1^{v}]:>{y,z+1,0,v}&,{0},#]&

Czysta funkcja z pierwszym argumentem #. Jeśli podana jest nieujemna liczba całkowita, wyświetli ona prawidłową listę cyfr (nawet 0poprawnie się obsługuje !).

Wyjaśnienie

Nest[f,expr,n]daje wynik zastosowania fdo expr nczasów. W tym przypadku exprjest to lista {0}i nwejściowa liczba całkowita #. Funkcja fjest skomplikowana:

# (* Starting with the input # *)
 /. (* Apply the following rule *)
   {x___,y_} (* If you see a list of the form {x___,y} *)
            :> (* replace it with *)
              {x,y+1} (* this *)
                     //. (* Now apply the following rule repeatedly until nothing changes *)
                        x:{y___,z_:0,w_,v___} (* If you see a list x starting with a sequence y of 0 or more elements, 
                                                 followed by an optional element z (default value of 0),
                                                 followed by an element w,
                                                 followed by a sequence v of 0 or more elements *)
                                             /; (* such that *)
                                               w>Tr[1^x]-Tr[1^{v}] (* w is greater than the length of x minus the length of {v} *)
                                                                  :> (* replace it with *)
                                                                    {y,z+1,0,v}& (* this *)
ngenisis
źródło
Fajne zastosowanie w y___,z_:0celu zwiększenia długości listy!
Greg Martin
2
@GregMartin JungHwan Min użył go wczoraj w podobnym problemie .
ngenisis
3

Perl 6 , 38 bajtów

{map({|[X] 1,|map ^*,3..$_},1..*)[$_]}

Pobiera dodatnią liczbę całkowitą i wyświetla listę liczb całkowitych reprezentujących cyfry.

Wyjaśnienie:

{                                    }  # a lambda

 map({                    },1..*)       # for each number length from 0 to infinity,
                                        # offset by 1 to avoid a +1 in next step...

           1,|map ^*,3..$_              # generate the digit ranges, e.g.:
                                        #     length 0  ->  (1)  # bogus, but irrelevant
                                        #     length 1  ->  (1)
                                        #     length 2  ->  (1, 0..2)
                                        #     length 3  ->  (1, 0..2, 0..3)
                                        #     length 4  ->  (1, 0..2, 0..3, 0..4)

       [X]                              # take the cartesian product

      |                                 # slip the results into the outer sequence

                                 [$_]   # Index the sequence generated this way
smls
źródło
2

Pyth - 14 bajtów

Zwraca po prostu nthwartość pasującą do „wzorca wartości mniejszej niż miejsce”.

e.f.A.eghkbjZT

Pakiet testowy .

Maltysen
źródło
2
Czy działa to na wejściu 2018967, gdzie ostatnia cyfra wynosi 10?
Greg Martin
1

Haskell, 65 bajtów

i(x:r)|x>length r=0:i r|1<2=1+x:r
i[]=[1]
reverse.(iterate i[]!!)

izwiększa liczby w systemie liczbowym o cyfry w odwrotnej kolejności. iteratetworzy nieskończoną listę wszystkich tych liczb, zaczynając od zera, który jest reprezentowany przez []. Następnie pozostaje tylko wziąć !!żądaną liczbę i reverseto.

Ostatni wiersz jest funkcją, a nie definicją funkcji, więc nie może pojawić się tak, jak w pliku kodu źródłowego. Zamiast tego umieść tylko inne wiersze w kodzie źródłowym i użyj ostatniego wiersza w tłumaczu (lub powiąż funkcję z nazwą, przechodząc f=do ostatniego wiersza).

Przykładowe zastosowanie:

*Main> reverse.(iterate i[]!!) $ 100
[1,0,0,3,5]

(8 bajtów można by zapisać, gdyby [5,3,0,0,1]były dozwoloną reprezentacją wyniku).

Christian Sievers
źródło
1

Haskell, 49 bajtów

x=[1]:[n++[d]|n<-x,d<-[0..length n+1]]
(x!!).pred

Pierwszy wiersz jest definicją pomocniczą, a drugi stanowi funkcję. Pobiera liczbę całkowitą i zwraca listę liczb całkowitych. Wypróbuj online!

Wyjaśnienie

Definiuję xjako nieskończoną listę przedstawień wymienionych w tekście wyzwania; główna funkcja po prostu zmniejsza swój argument i indeksuje do x. Pierwszy wiersz działa w następujący sposób:

x=                     -- The list of lists x contains
 [1]:                  -- the list [1], followed by
 [n++[d]|              -- integer d appended to list n, where
  n<-x,                -- n is drawn from x, and
  d<-[0..length n+1]]  -- the new "digit" d is drawn from this range.

Widzisz, że xjest to zdefiniowane samo w sobie, ale Haskell jest leniwy, więc to nie jest problem.

Zgarb
źródło