La plupart des ordinateurs stockent des entiers en binaire, mais les affichent en décimal. Cependant, le nombre décimal n'est qu'une représentation, il se trouve que c'est pratique.

Ce défi consiste à écrire du code pour sortir une valeur entière en décimal shortlex .

Qu'est-ce que c'est?
http://en.wikipedia.org/wiki/Shortlex_order

Shortlex prend la longueur de la séquence de chiffres comme signifiant principal de la valeur. La séquence, à partir d'une chaîne vide représentant zéro, est ...

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

(Pensez aux colonnes Excel, mais en utilisant uniquement les chiffres décimaux.)

Écrivez un programme ou une fonction qui accepte un entier et renvoie une chaîne correspondant à la représentation décimal-décimal de cet entier comme décrit ci-dessus.

Valeurs de test:

0 → "" (chaîne vide)
1 → "0"
10 → "9"
11 → "00"
42 → "31"
100 → "89"
800 → "689"
1060 → "949"
10270 → "9159"
100501 → "89390"

JavaScript (ES6) 42 74

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

Test dans la console FireFox

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

Production

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

Comment ai-je pensé à ça?

Étant donné un nombre fixe de chiffres, la séquence de sortie est simplement ascendante, il y a donc un delta fixe entre l'entrée et la sortie. Regarde:

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

Mais les 0 principaux sont difficiles à gérer, j'ai donc une astuce standard, ajouter un premier chiffre et travailler modulo (c'est-à-dire couper le premier chiffre en sortie). Ensuite -1-> +9, -11 -> +89, -111 -> +889 et ainsi de suite.
Dernière étape: peu m'importe le premier chiffre, il n'est donc pas nécessaire de vérifier si le numéro d'entrée est <ou> supérieur à 111 ... (honnêtement, j'ai trouvé cela par essais et erreurs)

Tester

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>

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

Il ne fonctionne que pour les valeurs inférieures à 256 car Marbelous est un langage 8 bits.

Comment ça fonctionne

Marbelous est un langage 2D avec des valeurs représentées par des billes 8 bits qui tombent d'une cellule à chaque tick à moins qu'un appareil ne les empêche de tomber. Ce programme Marbelous se compose de 3 planches; Commençons par le plus simple:

:O
}0
+Z
+C
{0

:Oest le nom de la carte (pour être précis, O est le nom et: indique à l'interprété que cette ligne est un nom. En donnant un nom aux cartes, d'autres cartes peuvent les appeler }0est un périphérique d'entrée, cela peut être vu comme un argument de cette fonction. Cette cellule sera remplacée par une bille d'entrée (valeur) lorsque la fonction sera appelée. +Zajoute 35 à toute bille qui la traverse et la laisse passer. +Cfait de même mais n'ajoute que 12. {0est une cellule de sortie , lorsqu'un marbre atteint cette cellule, la fonction se termine et renvoie la valeur dans ce périphérique de sortie.

Donc, tous ensemble, ce tableau prend une valeur, puis en ajoute 47. Pour nous, cela signifie qu'il transforme n'importe quel nombre à un seul chiffre en code ascii du chiffre -1 (cela fonctionnera bien sûr également pour 10).

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

Cette carte semble un peu plus compliquée. Vous devriez pouvoir identifier:I le nom de la carte et avoir repéré certains périphériques d'entrée et de sortie. Vous remarquerez que nous avons deux périphériques d'entrée différents, }0et }1. Cela signifie que cette fonction prend 2 entrées. Vous remarquerez également qu'il existe deux instances de l' }1appareil. Lors de l'appel de la fonction, ces deux cellules contiendront la même valeur. Le }0périphérique d'entrée est directement au-dessus d'un \/périphérique, cela agit comme une poubelle et élimine immédiatement toute bille qui tombe dessus.

Jetons un œil à ce qui arrive à l'une des billes mises dans le tableau par les }1périphériques d'entrée:

}1
=9 &1
&0
{>

Il tombera sur le premier tick et frappera l' =9appareil. Cela compare la valeur de la bille à 9 et laisse la bille tomber si l'instruction est =9évaluée à travers. Le marbre est poussé vers la droite sinon. &0et&1 sont des synchroniseurs. Ils s'accrochent aux billes qui tombent sur eux jusqu'à ce que tous les autres &nsynchroniseurs soient également remplis. Comme vous pouvez vous y attendre, cela déclenchera conditionnellement un comportement différent sur une autre partie de la carte.

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

Si je vous dis qu'il ++s'agit d'un incrémenteur, vous devriez déjà être en mesure de dire de quoi les différents synchroniseurs seront remplis. La gauche &1contiendra la valeur d'entrée }1+ 1, la &0suivante contiendra 0 ( 00est un littéral de langue, représenté en hexadécimal). La deuxième&1 contiendra la valeur 1 et la droite sera &0remplie d'un F7, ce qui soustrait 9 d'une valeur puisque l'addition dans Marbelous est le modulo 256.

// est un dispositif déflecteur qui pousse n'importe quelle bille vers la gauche au lieu de la laisser tomber.

Mettre tout cela ensemble vous donne ceci: si le marbre }1est à 9, les &0synchroniseurs se remplissent. Cela entraînera la valeur 0 à tomber dans la {0sortie et F7(ou -9) dans la {1sortie. Si ce }1n'est pas 9, {0sera rempli de }1+ 1 et {0contiendra 1. Il y a aussi un {>appareil, c'est une sortie spéciale qui sort une bille à côté d'une planche au lieu d'en dessous. Cela sera rempli de}1 s'il est égal à 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

D'accord, maintenant pour le grand. Cette carte n'a pas de nom explicite, car il s'agit de la carte principale du fichier. Son nom implicite est Mb. Vous devriez pouvoir reconnaître certaines cellules. Il existe un périphérique d'entrée, certains littéraux de langue ( 00et FF). Il y a des synchroniseurs et un déflecteur. permet de parcourir ce morceau par morceau.

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

Ainsi, la valeur d'entrée (l'entrée de ligne de commande car il s'agit de la carte principale) commence à la deuxième cellule du haut où }0se trouve. Il tombera et atteindra l' >0appareil, qui est un autre appareil de comparaison. tout marbre supérieur à 0 tombe à travers, tout autre marbre est poussé vers la droite. (puisque les variables Marbelous ne sont pas signées, seulement exactement 0 sera poussé vers la droite). Ce marbre de valeur nulle frappera alors le@6 appareil. Il s'agit d'un portail et transporte le marbre vers un autre portail correspondant, dans ce cas juste au-dessus. La bille 0 atteindra alors le &0synchroniseur et déclenchera certaines choses ailleurs.

Si la bille n'est pas 0, elle tombe, est déviée vers la droite par des \\coups --qui la décrémentent d'un, puis tombe sur /\un cloneur. Cet appareil prend une bille et en sort une copie à droite et une à gauche. Celui de gauche sera amené vers le haut de l'autre@0 où le marbre passera à nouveau par la même séquence. Celui de gauche sera pris ailleurs. Cela nous donne une boucle, qui décrémente l'entrée de ligne de commande une fois par boucle et déclenche un comportement sur chaque boucle jusqu'à ce qu'il atteigne 0. Il déclenche ensuite un autre comportement.

Voyons ce qui se passe avec le marbre poussé dans @4chaque boucle.

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

Il y a 3 littéraux de langue ici ( FF), qui tomberont immédiatement dans les portails. Ces portails les amèneront à trois des IIappareils. IIfait référence au tableau que :Inous avons défini plus loin dans le fichier. Puisqu'il :Ia 2 périphériques d'entrée distincts, sa représentation sur une autre carte doit avoir 2 cellules de large. Puisque nous avons 6 cellules contenantII , nous pouvons dire que nous avons 3 instances de cette fonction sur la carte.

Les FFbilles (ou 256 ou -1 si vous voulez) resteront dans les cellules d'entrée de la :Ifonction en attendant jusqu'à ce qu'il y ait suffisamment de billes d' entrée pour démarrer la fonction (une de plus). C'est là que le @4portail entre en jeu. Une copie de l'entrée de ligne de commande décrémentée passe par là sur chaque boucle. Cela déclenchera la :Icarte la plus à gauche . Initialement avec les valeurs 256 (ou -1) et quelle que soit l'entrée de ligne de commande était -1. Le marbre gauche sera placé dans les }0appareils de la :Iplanche et celui de droite dans le }1. Si vous vous souvenez de ce que cette carte a fait, vous pourrez dire quel résultat cela a. Il produira une version incrémentée de l'entrée droite sur la sortie gauche (et il transforme un 9 en 0, pas 10) et sort soit 1 ou -9 sur la droite.

La valeur incrémentée sera reprise directement dans la cellule d'entrée de droite par un portail, et la valeur de droite tombe dans un synchroniseur. Si un synchroniseur contient déjà une bille, les deux billes entreront en collision. Les billes en collision sont ajoutées ensemble modulo 256. Les valeurs dans les synchroniseurs feront donc le suivi: elles commencent vide, puis passent à 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, puis à 1 à nouveau (puisque 247 s'ajoute modulo 256).

Vous vous souvenez peut-être également qu'une bille est sortie vers la droite lorsque la valeur d'entrée revient à 0. Comme les :Icartes sont côte à côte, thsi déclenchera la carte vers la droite une fois. Cela remplira les trois synchroniseurs avec des valeurs plus élevées qu'elles ne devraient l'être pour être une représentation en shortlex de l'entrée de ligne de commande, au moment où celle-ci est bouclée à 0.

Vous vous souvenez peut-être également que la :Ofonction transforme une valeur en valeur ascii du chiffre qui représente la valeur -1. La sortie de ces OOcellules tombera alors de la carte, qui imprime leurs caractères ascii correspondants sur STDOUT.

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

Alors, que se passe-t-il lorsque la bille d'entrée de ligne de commande atteint 0 et remplit les &0synchroniseurs? eh bien, quelques billes de valeur 0 tombent et déclenchent les trois synchroniseurs qui contiennent les chiffres (+ 1) du numéro de shortlex au bas de la planche. &3est déclenché en premier, car il contient le chiffre le plus significatif, puis vient &2ensuite &1. Cette bille est ensuite téléportée vers l'autre @5appareil avant de finalement toucher la !!cellule, ce qui met fin à la planche.

CJam, 14 11 octets

l40f-Ab)s1>

Essayez-le en ligne.

Comment ça fonctionne

Cette approche est fortement basée sur la réponse d'edc65 (avec sa permission explicite ):

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

Exemple d'exécution

$ 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

Python 2 (38) (43)

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

Pas de substitution de caractères, juste de l'arithmétique.

Non golfé:

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

Je n'ai pas de bonne raison pour laquelle la récursivité fonctionne, j'adapte simplement ce modèle à la liste de valeurs. Si vous changez chacun n-1en n, vous obtiendrez la représentation numérique régulière.

Pour le golf, j'utilise ~-npour calculer n-1avec une priorité plus élevée que /10ou %10, en économisant sur les parens. Le n*'_'est juste de produire la chaîne vide quand n=0et toute autre chaîne sinon. Le '_'peut être n'importe quelle chaîne à cet effet.

Rubis, 70 68 66 64 57 octets

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

Définit une fonction à appeler comme f[42]. Voici la répartition approximative de l'algorithme:

• Traitez 0séparément.
• Soustrayez les pouvoirs de 10 jusqu'à ce que le prochain pouvoir de 10 ne rentre plus dans le nombre.
• Transformez le nombre en une chaîne rembourrée avec des zéros sur la gauche.

Les crédits pour l'idée d'utiliser une chaîne de format vont à Falko!

Alternativement, en utilisant l'approche d'edc65:

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

C'est 45 octets et je ne fais que l'inclure, car je ne le bat pas avec. ;)

Haskell, 67 octets

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

cette solution ajoute fondamentalement 1 le nombre de fois donné, en notation shortlex.

usage:

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

CJam, 16 octets

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

Essayez-le en ligne. Nécessite au moins O (n) de temps et de mémoire, alors laissez 100501 à l'interprète hors ligne ...

Comment ça fonctionne

L'idée de base derrière cette approche est de calculer au moins N décimales shortlex dans leur ordre naturel et de rejeter tout sauf le Nième. Pas très efficace, mais bref.

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

Exemple d'exécution

$ 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

Bash + coreutils, 27 octets

Port de la réponse intelligente de @ edc65 , avec les améliorations de @ Dennis :

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

Production:

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

Réponse précédente:

Bash + coreutils, 71 54 octets

Voici une façon légèrement différente de le faire:

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

• jot affiche des nombres hexadécimaux croissants
• tr convertit ceci en (0,1, ..., 8,9, b, ... f, 0a, 00,01, ..., 99,9b, ..., ff, 0aa, ..., 000 , ...)
• grep filtre simplement toutes les lignes contenant des chiffres à donner (0,1, ..., 8,9,00, ..., 99,000 ....)
• sed supprime tout sauf la nième ligne
• STDERR est redirigé vers un fichier jetable '-' afin que nous obtenions simplement la chaîne vide lorsque 0 est passé (sed compte les numéros de ligne commençant à 1, donc des erreurs si 0 est passé)
• Parce que nous filtrons les nombres avec grep, nous devons générer plus d'entiers de base 11 avec seq/ dcque le nombre d'entrée. La répétition des chiffres de n est plus que suffisante.

Notez qu'une fois que le nombre de shortlex est imprimé, seqcontinue de générer des nombres jusqu'à $1$1, ce qui ralentit surtout pour les plus grands nombres d'entrée - O (n²), je pense. Nous pouvons accélérer en ayant la seqsortie immédiatement après l'impression au prix de 7 octets:

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

Il n'y a aucune exigence de vitesse dans la question, donc je vais utiliser la version courte pour ma réponse principale.

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)

Approche alternative (même longueur):

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

Python 3, 107 caractères

Cela n'a pas fini par gagner mais j'ai pensé que c'était intelligent:

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]

Je définis un générateur pour toute la séquence en 64 caractères. Malheureusement, je dois passer par quelques contorsions pour obtenir le nième élément du générateur ... si seulement je pouvais le faire S=lambda n:G()[n].

Pyth , 12

Un autre port de la réponse de @ edc65, qui est le gagnant clair (IMO):

t`+hQv*l`Q\8

Pack de test (Merci à @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"

Explication:

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

Java 8, 60 octets

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

Port de la réponse JavaScript (ES6) étonnante de @ edc65 , car je doute que cela puisse être fait plus court de manière arithmétique en Java.

Essayez-le ici.

Haskell , 57 octets

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

Essayez-le en ligne!

Construit une liste infinie de nombres shortlex et indexe dedans pour la réponse. g nconstruit la nième "génération" de nombres en ajoutant le chiffre suivant devant chacun des nombres de la génération précédente.

05AB1E , 7 octets

Utilise le remplacement d' edc65 par 8 astuces

8sg×+>¦

Essayez-le en ligne!

Explication

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

Excel, 37 octets

En utilisant l'approche de @ edc65:

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

Gelée , 5 octets

ḃ⁵ịØD

Essayez-le en ligne!

Je suis très nouveau sur Jelly, donc si vous pouvez améliorer cela, veuillez commenter!

Explication:

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

(Selon le commentaire de res ci-dessus, le problème est équivalent à convertir le nombre en base bijective 10)