11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Given your last comment, is it okay if we always return a list with the digits? \$\endgroup\$ – Greg Martin Jan 13 '17 at 2:12
  • \$\begingroup\$ Yes, That's a reasonable way to give output, as long as the numbers are correct \$\endgroup\$ – Ando Bando Jan 13 '17 at 2:13
  • 1
    \$\begingroup\$ I'm getting 100 -> 10035 rather than 100 -> 10033, can you verify? \$\endgroup\$ – Greg Martin Jan 13 '17 at 2:26
  • \$\begingroup\$ @GregMartin 10035 seems right. I did my calculations by pen and not program and hence made a computation error. I guess we have computers for a reasom \$\endgroup\$ – Ando Bando Jan 13 '17 at 2:28
  • 1
    \$\begingroup\$ Maybe duplicate? codegolf.stackexchange.com/questions/11735/… \$\endgroup\$ – G B Jan 13 '17 at 12:52
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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 *)
\$\endgroup\$
  • \$\begingroup\$ Nice use of y___,z_:0 to increase the length of the list! \$\endgroup\$ – Greg Martin Jan 13 '17 at 3:05
  • 2
    \$\begingroup\$ @GregMartin JungHwan Min used it in a similar problem yesterday. \$\endgroup\$ – ngenisis Jan 13 '17 at 3:14
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Pyth - 14 bytes

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

e.f.A.eghkbjZT

Test Suite.

\$\endgroup\$
  • 2
    \$\begingroup\$ Does this work on the input 2018967, where the last digit equals 10? \$\endgroup\$ – Greg Martin Jan 13 '17 at 2:36
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.