Давайте создадим систему чисел, в которой наибольшая цифра в n-м значении (считая справа налево) длины числа m всегда равна m - n + 1. Чтобы привести пример наибольшего числа из 5 цифр, выражаемого в этой системе написано 12345. За исключением числа цифр, доступных для использования в определенном месте, все остальные приращения являются стандартными. А именно, когда цифра должна превысить свой предел, мы добавляем ее к следующей цифре.

Вот как будет представлен счет в этой системе:

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

Ваша задача - написать функцию, которая берет стандартный номер 10 и преобразует его в мою систему нумерации.

Более короткий код предпочтительнее. Бонн Шанс!

** Если вам нужны цифры после 9 (вы должны), вы можете использовать буквы или вы можете вернуть двузначное число в качестве элемента списка.

Тестовые случаи

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

Последний случай может быть невероятно медленным в зависимости от того, как вы реализовали. Вам не нужно запускать его, если он занимает слишком много времени или использует слишком много памяти. Тем не менее, обратите внимание, что существуют способы, чтобы он работал быстро и используя мало памяти.

Mathematica, 64 байта

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

Безымянная функция, принимающая положительный целочисленный аргумент и возвращающая список целых чисел.

Join[{{1}},Array[Range,#-1,3]-1]возвращает вложенный список { {1}, {0,1,2}, {0,1,2,3}, ..., {0,1,...,#} }. Затем Tuplesвозвращает (отсортированный) набор всех кортежей, в которых лежит первый элемент, в котором находится {1}второй элемент {0,1,2}и т. Д .; это #цифры -d в этой системе нумерации. Join@@Array[...,#]возвращает массив всех чисел в этой системе нумерации с не более чем #цифрами и Part[...,#]извлекает #такое число.

Это безнадежно медленно! Он работает нормально для ввода до 9. Для большего ввода проверьте его, заменив конец ,#],#]&на ,Ceiling[0.9Log[#]]],#]&; это позволяет более реалистично ограничить количество цифр, необходимое для того, чтобы перейти в систему нумерации достаточно далеко, чтобы найти ту, которая нам нужна.

Mathematica, 93 байта

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},#]&

Чистая функция с первым аргументом #. Если задано неотрицательное целое число, оно выведет правильный список цифр (даже обрабатывает 0правильно!).

объяснение

Nest[f,expr,n]дает результат применения fко expr nвремени. В данном случае exprэто список {0}и nвходное целое число #. Функция fсложная:

# (* 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 *)

Perl 6 , 38 байт

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

Принимает положительное целое число и выводит список целых чисел, представляющих цифры.

Объяснение:

{                                    }  # 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

Pyth - 14 байт

Просто возвращает nthзначение, которое соответствует «шаблону значений меньше места».

e.f.A.eghkbjZT

Тестовый пакет .

Haskell, 65 байт

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

iувеличивает числа в системе счисления с цифрами в обратном порядке. iterateсоздает бесконечный список всех этих чисел, начиная с нуля, который представлен []. Тогда все, что осталось сделать, это взять ( !!) требуемый номер и reverseего.

Последняя строка - это функция, а не определение функции, поэтому она не может отображаться как есть в файле исходного кода. Вместо этого поместите только другие строки в исходный код и используйте последнюю строку в интерпретаторе (или привяжите функцию к имени, добавив f=к последней строке).

Пример использования:

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

(8 байт можно было бы сохранить, если бы [5,3,0,0,1]было разрешено представление результата.)

Haskell, 49 байтов

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

Первая строка является вспомогательным определением, а вторая - функцией. Он принимает целое число и возвращает список целых чисел. Попробуйте онлайн!

объяснение

Я определяю xкак бесконечный список представлений, упомянутых в тексте запроса; основная функция просто уменьшает свой аргумент и индексирует в x. Первая строка работает так:

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.

Вы видите, что xэто определяется само по себе, но Haskell ленив, так что это не проблема.