Converting Numbers to a "Not quite place-value system"

Question

Lets create a system of numbers where the biggest digit in the nth place value (counting from right to left) of a number length m is always equal to m - n + 1. To give an example the largest 5 digit number expressible in this system is written 12345. Apart from the number of digits available to be used in a particular place being restricted, all other incrementation is standard. Namely when a digit is to surpass its digit limit we add one to the next digit.

Here is how counting would be represented in this system:

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

Your task is to write a function that takes a standard base 10 number and converts it to my numbering system.

Shorter code is preferable. Bonne Chance!

**If you need digits after 9 (you should) you can choose to use letters, or you can you return a 2 digit number as an element of a list.

Test Cases

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

Last case may be incredibly slow to run depending on how you implemented. You don't need to run it if it takes too long or uses too much memory. However note that there exist ways to have it run quickly and using little memory.

Answer 1

Mathematica, 64 bytes

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

Unnamed function taking a positive integer argument and returning a list of integers.

Join[{{1}},Array[Range,#-1,3]-1] returns the nested list { {1}, {0,1,2}, {0,1,2,3}, ..., {0,1,...,#} }. Then Tuples returns the (sorted) set of all tuples whose first element lies in {1}, whose second element lies in {0,1,2}, and so on; these are the #-digit numbers in this numbering system. Join@@Array[...,#] returns an array of all the numbers in this numbering system with at most # digits, and Part[...,#] extracts the #th such number.

This is hopelessly slow! It runs fine for the input up to 9. For larger input, test it by replacing the end ,#],#]& with ,Ceiling[0.9Log[#]]],#]&; this puts a more realistic cap on the number of digits necessary to go far enough in the numbering system to find the one we want.

Answer 2

Mathematica, 93 bytes

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

Pure function with first argument #. If a nonnegative integer is given, it will output the correct list of digits (even handles 0 correctly!).

Explanation

Nest[f,expr,n] gives the result of applying f to expr n times. In this case, expr is the list {0} and n is the input integer #. The function f is complicated:

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

Answer 3

Perl 6, 38 bytes

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

Takes a positive integer, and outputs a list of integers representing the digits.

Explanation:

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

Answer 4

Pyth - 14 bytes

Simply returns the nth value that fits the "less than place value pattern".

e.f.A.eghkbjZT

Test Suite.

Answer 5

Haskell, 65 bytes

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

i increases numbers in the number system with the digits in reversed order. iterate creates the infinite list of all these numbers starting with zero which is represented by []. Then all that is left to do is take (!!) the demanded number and reverse it.

The last line is a function, not a function definition, so it can not appear as is in a source code file. Instead, only put the other lines in the source code and use the last line at the interpreter (or bind the function to a name by prepending f= to the last line).

Example use:

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

(8 bytes could be saved if [5,3,0,0,1] were an allowed representation of the result.)

Answer 6

Haskell, 49 bytes

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

The first line is an auxiliary definition, and the second evaluates to a function. It takes an integer and returns a list of integers. Try it online!

Explanation

I define x as the infinite list of representations mentioned in the challenge text; the main function just decrements its argument and indexes into x. The first line works like this:

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.

You see that x is defined in terms of itself, but Haskell is lazy, so this is not an issue.