What's that number in Shortlex?

Question

Most computers store integers in binary, but output them in decimal. However, decimal is just one representation, we just happen to find it convenient.

This challenge is to write some code to output an integer value in shortlex decimal.

What's that?
http://en.wikipedia.org/wiki/Shortlex_order

Shortlex takes the length of the sequence of digits as the primary signifier of value. The sequence, starting from an empty string representing zero, is...

ε,0,1,...,8,9,00,01,...98,99,000,001,...,998,999,0000,...

(Think of Excel columns, but using only the decimal digits.)

Write a program or function that accepts an integer and returns a string corresponding to the shortlex-decimal representation of that integer as described above.

Test values:

0 → "" (Empty string)
1 → "0"
10 → "9"
11 → "00"
42 → "31"
100 → "89"
800 → "689"
1060 → "949"
10270 → "9159"
100501 → "89390"

Answer 1

JavaScript (ES6) 42 74

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

Test in FireFox console

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

Output

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

How did I think of this?

Given a fixed number of digits, the output sequence is simply ascending, so there is a fixed delta between input and output. Have a look:

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

But the leading 0s are difficult to manage, so I have a standard trick, add a first digit and work modulo (that is, cut the first digit in output). Then -1-> +9, -11 -> +89, -111 -> +889 and so on.
Last step: I don't care what the first digit is, so there is no need to check if the iinput number is < or > than 111... (honestly I found this by trial and error)

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>

Answer 2

Marbelous 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

It works for only for values under 256 since Marbelous is an 8 bit language.

How it works

Marbelous is a 2D language with values represented by 8 bit marbles that fall down one cell on each tick unless some device prevents them from falling down. This Marbelous program consists of 3 boards; let's start with the easiest one:

:O
}0
+Z
+C
{0

:O is the name of the board (to be precise, O is the name and : tells the interpreted that this line is a name. By giving boards a name, other boards can call on them }0 is an input device, this can be seen as an argument of this function. This cell will get replaced by an input marble (value) when the function gets called. +Z adds 35 to any marble that passes over it and lets it fall through. +C does the same but only adds 12. {0 is an output cell, when a marble reaches this cell, the function will exit and return the value in this output device.

So all together, this board takes one value and then adds 47 to it. For us this means it turns any single digit number into the ascii code of the digit -1 (this will of course also work for 10).

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

This board is looking a bit more complicated. You should be able to identify :I as the name of the board and have spotted some input and output devices. You'll notice that we have two different input devices, }0 and }1. This means this function takes 2 inputs. You'll also notice that there are two instances of the }1 device. Upon calling the function, both of these cells will contain the same value. The }0 input device is directly above a \/ device, this acts as a trashcan and removes any marble that falls upon it immediately.

Let's have a look at what happens to one of the marbles put into the board by the }1 input devices:

}1
=9 &1
&0
{>

It will fall down on the first tick and hit the =9 device. This compares the value oif the marble to 9 and lets the marble fall through if the statement =9 evaluates to through. The marble gets pushed to the right if not. &0and &1 are synchronizers. They hold on to marbles that fall onto them until all other &nsynchronizers are filled as well. As you can expect, this will conditionally trigger different behaviour on some other part of the board.

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

If I tell you that ++ is an incrementor, you should already be able to tell what the different synchronizers will be filled with. The left &1 will contain the input value }1 + 1, the &0 next to it will contain 0 (00 is a language literal, represented in hexadecimal). The second &1 will contain the value 1 and the right &0 gets filled with an F7, which subtracts 9 from a value since addition in Marbelous is modulo 256.

// is a deflector device, which pushes any marble to the left instead of letting it fall down.

Putting this all together gives you this: if the marble in }1 is 9, the &0 synchronizers get filled. This will cause the value 0 to fall into the {0 output and F7 (or -9) into the {1 output. If }1 is not 9, {0 will be filled with }1 + 1 and {0 will contain 1. There is also a {> device, this is a special output that outputs a marble next to a board in stead of underneath it. This will get filled with }1 if it equals 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

Okay, now for the big one. This board does not have an explicit name, since it is the main board of the file. Its implicit name is Mb. You should be able to recognize some cells. There is an input device, some language literals (00 and FF). There are some synchronizers and there's a deflector. lets step through this piece by piece.

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

So the input value (the command line input since this is the main board) starts at the second cell from the top where }0 is located. It will fall down and reach the >0 device, which is another comparison device. any marble larger than 0 falls through, any other marble gets pushed to the right. (since Marbelous variables are unsigned, only exactly 0 will get pushed to the right). This zero value marble will then hit the @6 device. This is a portal and transports the marble to another corresponding portal, in this case right above it. The 0 marble will then reach the &0 synchronizer and trigger some things elsewhere.

If the marble is not 0, it falls down, gets deflected to the right by \\ hits -- which decrements it by one and then falls onto /\, a cloner. This device takes a marble and outputs one copy of it to the right and one to the left. The left one will be taken upwards to the other @0 where the marble will go through the same sequence again. The left one will be taken elsewhere. This gives us a loop, which decrements the command line input once per loop and triggers some behaviour on every loop until it reaches 0. It then triggers some other behaviour.

Let's have a look at what happens with the marble pushed into @4 on each loop.

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

There are 3 language literals here (FF), which will immediately fall into portals. These portals will take them to three of the II devices. II refers to the board :I we defined further down the file. Since :I has 2 distinct input devices, it's representation on another board must be 2 cells wide. Since we have 6 cells containing II, we cam tell we have 3 instances of this function on the board.

The FF (or 256 or -1 if you will) marbles will sit in the input cells of the :I function waiting untill there are enough input marble sto start the function (one more that is). That's where the @4 portal comes in. A copy of the decremented command line input falls through there on each loop. This will trigger the leftmost :I board. Initialy with the values 256 (or -1) and whatever the command line input was -1. The left marble will be put into the }0 devices of the :I board and the right one into the }1. If you recall what this board did, you'll be able to tell what result this has. It will output an incremented version of the right input on the left output (and it turns a 9 into a 0, not 10) and outputs either 1 or -9 on the right.

The incremented value will be taken right back to the right input cell by a portal, and the value on the right falls into a synchronizer. If a synchronizer is already holding a marble, the two marbles will collide. Colliding marbles get added together modulo 256. So the values in the synchroizers will do the folowing: They start out empty, then turn to 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and then to 1 again (since 247 gets added modulo 256).

You also might remember that a marble gets output to the right when the input value loops back to 0. Since the :I boards are right next to each other, thsi will trigger the board to the right once. This will fill the three synchronizers with values that are one higher than they should be to be a shortlex representation of the command line input, by the time this has looped down to 0.

You might also remember that the :O function turns a value into the ascii value of the digit that represents the value -1. The output of these OO cells will then fall off the board, which prints their corresponding ascii chars to STDOUT.

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

So what happens when the command line input marble reaches 0 and fills that &0 synchronizers? well, a few 0 value marbles fall down and trigger the three synchronizers that are holding the digits (+ 1) of the shortlex number at the bottom of the board. &3 gets triggered first, since it contain the most significant digit, then comes &2 followed by &1. This marble then gets teleported to the other @5 device before eventually hitting the !! cell, which terminates the board.

Answer 3

CJam, 14 11 bytes

l40f-Ab)s1>

Try it online.

How it works

This approach is heavily based on edc65's answer (with his explicit permission):

" 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>

Example run

$ 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

Answer 4

Python 2 (38) (43)

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

No character substitution, just arithmetic.

Ungolfed:

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

I don't have a good reason why the recursion works, I just fit this pattern to the list of values. If you changed each n-1 to n, you'd get the regular digit representation.

For golfing, I use ~-n to compute n-1 with higher precedence than /10 or %10, saving on parens. The n*'_' is just to produce the empty string when n=0 and any other string otherwise. The '_' can be any string for this purpose.

Answer 5

Ruby, 70 68 66 64 57 bytes

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

Defines a function to be called like f[42]. Here is the rough breakdown of the algorithm:

• Treat 0 separately.
• Subtract powers of 10 until the next power of 10 doesn't fit into the number any more.
• Turn the number into a string padded with zeroes on the left.

Credits for the idea of using a format string go to Falko!

---

Alternatively, using edc65's approach:

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

That's 45 bytes and I'm only including it, because I'm not beating him with it. ;)

Answer 6

Haskell, 67 bytes

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

this solution basically adds 1 the given number of times, in shortlex notation.

usage:

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

Answer 7

CJam, 16 bytes

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

Try it online. Requires at least O(n) time and memory, so leave 100501 to the offline interpreter...

How it works

The basic idea behind this approach is to compute at least N shortlex decimals in their natural order and discard all but the Nth. Not very efficient, but short.

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.                                       ";

Example run

$ 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

Answer 8

Bash+coreutils, 27 bytes

Port of @edc65's clever answer, with @Dennis's improvements:

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

Output:

$ 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"
$ 

---

Previous answer:

Bash+coreutils, 71 54 bytes

Here's a slightly different way to do it:

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

• jot outputs increasing hexadecimal integers
• tr converts this to (0,1,...,8,9,b,...f,0a,00,01,...,99,9b,...,ff,0aa,...,000,...)
• grep simply filters all lines containing digits to give (0,1,...,8,9,00,...,99,000....)
• sed deletes all but the nth line
• STDERR is redirected to a throwaway file '-' so that we simply get the empty string when 0 is passed in (sed counts line numbers starting at 1, so errors if 0 is passed)
• Because we are filtering numbers out with grep, we need to generate more base 11 integers with seq/dc than the input number. Repeating the digits of n is more than sufficient.

Note that once the shortlex number is printed, seq continues generating numbers up to $1$1, which slow especially for larger input numbers - O(n²), I think. We can speed up by having the seq quit immediately after printing at the cost of 7 bytes:

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

There is no speed requirement in the question, so I'm going with the shorter version for my main answer.

Answer 9

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)

Alternative approach (same length):

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

Answer 10

Python 3, 107 characters

This didn't end up winning but I thought it was clever:

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]

I define a generator for the entire sequence in 64 characters. Unfortunately, I have to go through some contortions to get the nth element of the generator... if only I could do S=lambda n:G()[n].

Answer 11

Pyth, 12

Another port of @edc65's answer, who is the clear winner (IMO):

t`+hQv*l`Q\8

Test package (Thanks to @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"

Explanation:

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

Answer 12

Java 8, 60 bytes

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

Port of @edc65's amazing JavaScript (ES6) answer, since I doubt it can be done shorter in an arithmetic way in Java.

Try it here.

Answer 13

Haskell, 57 bytes

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

Try it online!

Constructs an infinite list of shortlex numbers and indexes into it for the answer. g n constructs the nth "generation" of numbers by prepending the next digit in front of each of the numbers in the previous generation.

Answer 14

05AB1E, 7 bytes

Uses edc65's replace by 8 trick

8sg×+>¦

Try it online!

Explanation

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

Answer 15

Jelly, 5 bytes

ḃ⁵ịØD

Try it online!

I'm very new to Jelly, so if you can improve this, please comment!

Explanation:

ḃ⁵ịØ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)

(According to r.e.s.'s comment above, the problem is equivalent to convert the number to bijective base 10)

Answer 16

Excel, 37 bytes

Using @edc65's approach:

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