Die meisten Computer speichern Ganzzahlen in Binärform, geben sie jedoch in Dezimalform aus. Die Dezimalzahl ist jedoch nur eine Darstellung, die wir einfach als zweckmäßig empfinden.

Diese Herausforderung besteht darin, Code zu schreiben, um einen ganzzahligen Wert in Shortlex Decimal auszugeben .

Was ist das?
http://en.wikipedia.org/wiki/Shortlex_order

Shortlex verwendet die Länge der Ziffernfolge als primären Wertekennzeichner. Die Sequenz, beginnend mit einer leeren Zeichenfolge, die Null darstellt, lautet ...

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

(Denken Sie an Excel-Spalten, aber verwenden Sie nur die Dezimalstellen.)

Schreiben Sie ein Programm oder eine Funktion, die eine Ganzzahl akzeptiert und eine Zeichenfolge zurückgibt, die der oben beschriebenen Darstellung dieser Ganzzahl in Form einer kurzen Dezimalzahl entspricht.

Testwerte:

0 → "" (leere Zeichenfolge)
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 in der FireFox-Konsole

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

Ausgabe

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

Wie habe ich darüber nachgedacht?

Bei einer festgelegten Anzahl von Ziffern steigt die Ausgabesequenz einfach an, sodass zwischen Eingabe und Ausgabe ein festes Delta besteht. Guck mal:

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

Aber die führenden Nullen sind schwierig zu verwalten, also habe ich einen Standardtrick, füge eine erste Ziffer hinzu und arbeite modulo (dh schneide die erste Ziffer in der Ausgabe ab). Dann -1-> +9, -11 -> +89, -111 -> +889 und so weiter.
Letzter Schritt: Es ist mir egal, wie hoch die erste Ziffer ist, daher muss nicht überprüft werden, ob die Eingangsnummer <oder> 111 ist ... (ehrlich gesagt, ich habe dies durch Ausprobieren herausgefunden.)

Prüfung

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

Es funktioniert nur für Werte unter 256, da Marbelous eine 8-Bit-Sprache ist.

Wie es funktioniert

Marbelous ist eine 2D-Sprache mit Werten, die durch 8-Bit-Murmeln dargestellt werden, die bei jedem Tick um eine Zelle nach unten fallen, es sei denn, ein Gerät verhindert, dass sie nach unten fallen. Dieses Marbelous-Programm besteht aus 3 Tafeln; Fangen wir mit dem einfachsten an:

:O
}0
+Z
+C
{0

:Oist der Name der Karte (um genau zu sein, O ist der Name und: sagt dem Interpretierten, dass diese Zeile ein Name ist. Wenn Sie einer Karte einen Namen geben, können andere Karten darauf }0zugreifen. Dies ist ein Eingabegerät Argument dieser Funktion: Diese Zelle wird durch einen Eingabemurmel (Wert) ersetzt, wenn die Funktion aufgerufen wird. +ZFügt jedem Marmor, der darüber läuft, 35 hinzu und lässt ihn fallen. +CFührt dasselbe aus, fügt jedoch nur 12 hinzu. Ist {0eine Ausgabezelle Wenn eine Kugel diese Zelle erreicht, wird die Funktion beendet und der Wert in diesem Ausgabegerät zurückgegeben.

Alles in allem nimmt dieses Board einen Wert an und addiert dann 47 dazu. Für uns bedeutet dies, dass jede einstellige Zahl in den ASCII-Code der Ziffer -1 umgewandelt wird (dies funktioniert natürlich auch für 10).

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

Dieses Board sieht etwas komplizierter aus. Sie sollten sich :Ials Name der Karte identifizieren können und einige Eingabe- und Ausgabegeräte entdeckt haben. Sie werden feststellen, dass wir zwei verschiedene Eingabegeräte haben }0und }1. Dies bedeutet, dass diese Funktion 2 Eingänge akzeptiert. Sie werden auch feststellen, dass es zwei Instanzen des }1Geräts gibt. Beim Aufrufen der Funktion enthalten beide Zellen denselben Wert. Das }0Eingabegerät befindet sich direkt über einem \/Gerät, dies wirkt wie ein Mülleimer und entfernt jeglichen Marmor, der darauf fällt, sofort.

Werfen wir einen Blick darauf, was mit einem der Murmeln passiert, die von den }1Eingabegeräten auf die Tafel gelegt werden:

}1
=9 &1
&0
{>

Es wird beim ersten Tick runterfallen und das =9Gerät treffen . Dies vergleicht den Wert der Murmel mit 9 und lässt die Murmel fallen, wenn die Anweisung =9mit through bewertet wird. Wenn nicht, wird der Marmor nach rechts gedrückt. &0und &1sind Synchronisierer. Sie halten sich an Murmeln fest, die auf sie fallen, bis auch alle anderen &nSynchronisierer gefüllt sind. Wie zu erwarten ist, wird dies bedingt ein anderes Verhalten auf einem anderen Teil der Platine auslösen.

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

Wenn ich Ihnen sage, dass ++es sich um einen Inkrementor handelt, sollten Sie bereits in der Lage sein, zu bestimmen, mit welchen Synchronisierungen die verschiedenen Synchronisierungen gefüllt werden. Die linke Seite &1enthält den Eingabewert }1+ 1, die &0nächste 0 ( 00ein hexadezimal dargestelltes Sprachliteral). Die zweite &1enthält den Wert 1 und die rechte &0wird mit einem gefüllt F7, der 9 von einem Wert abzieht, da die Addition in Marbelous modulo 256 ist.

// ist eine Ablenkvorrichtung, die jeglichen Marmor nach links drückt, anstatt ihn fallen zu lassen.

Wenn Sie dies alles zusammenfassen, erhalten Sie Folgendes: Wenn der Marmor in }19 ist, werden die &0Synchronisierer gefüllt. Dies bewirkt, dass der Wert 0 in den {0Ausgang und F7(oder -9) in den {1Ausgang fällt . Wenn }1nicht 9, {0wird mit }1+ 1 gefüllt und {0enthält 1. Es gibt auch ein {>Gerät, dies ist ein spezieller Ausgang, der eine Kugel neben einer Tafel anstelle darunter ausgibt. Dies wird mit gefüllt, }1wenn es gleich 9 ist.

@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, jetzt zum Großen. Dieses Board hat keinen expliziten Namen, da es das Hauptboard der Datei ist. Der implizite Name lautet Mb. Sie sollten in der Lage sein, einige Zellen zu erkennen. Es gibt ein Eingabegerät, einige Sprachliterale ( 00und FF). Es gibt einige Synchronisierer und einen Deflektor. Lassen Sie uns Schritt für Schritt durch diese.

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

Der Eingabewert (die Befehlszeileneingabe, da dies die Hauptplatine ist) beginnt also in der zweiten Zelle von oben, wo er }0sich befindet. Es fällt herunter und erreicht das >0Gerät, bei dem es sich um ein anderes Vergleichsgerät handelt. Jeder Marmor, der größer als 0 ist, fällt durch, jeder andere Marmor wird nach rechts gedrückt. (Da Marbelous-Variablen ohne Vorzeichen sind, wird nur genau 0 nach rechts verschoben.) Dieser Nullwert-Marmor trifft dann das @6Gerät. Dies ist ein Portal und transportiert den Marmor zu einem anderen entsprechenden Portal, in diesem Fall direkt darüber. Die 0-Kugel erreicht dann den &0Synchronisierer und löst einige Dinge an anderer Stelle aus.

Wenn der Marmor nicht 0 ist, fällt er nach unten, wird durch \\Treffer nach rechts abgelenkt, --wodurch er um eins verringert wird, und fällt dann auf /\einen Kloner. Dieses Gerät nimmt eine Murmel und gibt eine Kopie davon rechts und eine links aus. Der linke wird nach oben zum anderen geführt, @0wo der Marmor dieselbe Sequenz erneut durchläuft. Der linke wird woanders hingebracht. Dadurch erhalten wir eine Schleife, die die Befehlszeileneingabe einmal pro Schleife dekrementiert und bei jeder Schleife ein bestimmtes Verhalten auslöst, bis sie 0 erreicht. Anschließend wird ein anderes Verhalten ausgelöst.

Lassen Sie uns einen Blick darauf werfen, was mit dem Marmor passiert, der in @4jede Schleife geschoben wird.

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

Es gibt hier 3 Sprachliterale ( FF), die sofort in Portale fallen. Diese Portale führen sie zu drei der IIGeräte. IIbezieht sich auf das Board, das :Iwir weiter unten in der Datei definiert haben. Da :Ies zwei verschiedene Eingabegeräte gibt, muss die Darstellung auf einer anderen Karte 2 Zellen breit sein. Da 6 Zellen enthalten sind II, haben wir 3 Instanzen dieser Funktion auf dem Board.

Die FF(oder 256 oder -1, wenn Sie wollen) Murmeln sitzen in den Eingabezellen der :IFunktion und warten, bis genügend Eingabemurmeln vorhanden sind, um die Funktion zu starten (dh eine weitere). Hier kommt das @4Portal ins Spiel. Dort fällt in jeder Schleife eine Kopie der dekrementierten Kommandozeilen-Eingabe durch. Dies wird das :IBoard ganz links auslösen . Anfänglich mit den Werten 256 (oder -1) und unabhängig von der Eingabe in der Befehlszeile mit -1. Die linke Murmel wird in die }0Geräte der :ITafel und die rechte in die Murmel gelegt }1. Wenn Sie sich erinnern, was dieses Board getan hat, können Sie feststellen, welches Ergebnis dies hat. Es gibt eine inkrementierte Version des rechten Eingangs auf dem linken Ausgang aus (und verwandelt eine 9 in eine 0, nicht in eine 10) und gibt entweder 1 oder -9 auf der rechten Seite aus.

Der inkrementierte Wert wird von einem Portal direkt in die rechte Eingabezelle zurückgeführt, und der Wert auf der rechten Seite fällt in einen Synchronizer. Wenn ein Synchronisierer bereits eine Kugel in der Hand hält, kollidieren die beiden Kugeln. Kollidierende Murmeln werden modulo 256 addiert. Die Werte in den Synchronisierern bewirken also Folgendes: Sie beginnen leer, drehen sich dann zu 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 und dann zu 1 wieder (da 247 Modulo 256 hinzugefügt wird).

Sie können sich auch daran erinnern, dass eine Murmel nach rechts ausgegeben wird, wenn der Eingabewert auf 0 zurückspringt. Da die :IKarten direkt nebeneinander liegen, wird die Karte einmal nach rechts getriggert. Dies füllt die drei Synchronisierer mit Werten, die um eins höher sind, als sie sein sollten, um eine kurze Darstellung der Befehlszeileneingabe zu sein, bis diese auf 0 zurückgeschleift ist.

Sie können sich auch daran erinnern, dass die :OFunktion einen Wert in den ASCII-Wert der Ziffer umwandelt, die den Wert -1 darstellt. Die Ausgabe dieser OOZellen fällt dann von der Platine, wodurch die entsprechenden ASCII-Zeichen an STDOUT ausgegeben werden.

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

Was passiert also, wenn die Befehlszeileneingabemurmel 0 erreicht und diese &0Synchronisierer füllt ? Nun, ein paar Murmeln mit dem Wert 0 fallen nach unten und lösen die drei Synchronisierungen aus, die die Ziffern (+ 1) der Shortlex-Zahl unten auf der Platine enthalten. &3wird zuerst ausgelöst, da es die höchstwertige Ziffer enthält, &2gefolgt von &1. Dieser Marmor wird dann zum anderen @5Gerät teleportiert, bevor er schließlich auf die !!Zelle trifft , die das Board terminiert.

CJam, 14 11 Bytes

l40f-Ab)s1>

Probieren Sie es online aus.

Wie es funktioniert

Dieser Ansatz basiert stark auf der Antwort von edc65 (mit seiner ausdrücklichen Erlaubnis ):

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

Beispiellauf

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

Keine Zeichenersetzung, nur Arithmetik.

Ungolfed:

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

Ich habe keinen guten Grund, warum die Rekursion funktioniert. Ich passe dieses Muster einfach an die Werteliste an. Wenn Sie jeweils n-1in geändert haben n, erhalten Sie die reguläre Stellendarstellung.

Beim Golfen ~-nberechne ich n-1mit höherer Priorität als /10oder %10und spare dabei Parens. Das n*'_'ist nur, um die leere Zeichenkette zu erzeugen, wenn n=0und jede andere Zeichenkette anders. Das '_'kann zu diesem Zweck eine beliebige Zeichenfolge sein.

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}

Definiert eine Funktion, die wie folgt aufgerufen werden soll f[42]. Hier ist die grobe Aufteilung des Algorithmus:

• Treat 0getrennt.
• Subtrahiere Potenzen von 10, bis die nächste Potenz von 10 nicht mehr in die Zahl passt.
• Verwandle die Zahl in eine Zeichenkette, die links mit Nullen aufgefüllt ist.

Dank für die Idee, einen Formatstring zu verwenden, geht an Falko!

Alternativ können Sie den Ansatz von edc65 verwenden:

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

Das sind 45 Bytes und ich beziehe es nur ein, weil ich ihn nicht damit besiege. ;)

Haskell, 67 Bytes

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

Diese Lösung addiert im Grunde genommen die angegebene Anzahl von Malen in Kurzschreibweise.

Verwendung:

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

CJam, 16 Bytes

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

Probieren Sie es online aus. Benötigt mindestens O (n) Zeit und Speicher. Überlassen Sie daher 100501 dem Offline-Interpreter.

Wie es funktioniert

Die Grundidee hinter diesem Ansatz besteht darin, mindestens N Shortlex-Dezimalstellen in ihrer natürlichen Reihenfolge zu berechnen und alle außer der N-ten zu verwerfen. Nicht sehr effizient, aber kurz.

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

Beispiellauf

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

Port of @ edc65's clevere Antwort mit den Verbesserungen von @ Dennis :

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

Ausgabe:

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

Vorherige Antwort:

Bash + Coreutils, 71 54 Bytes

Hier ist ein etwas anderer Weg, um es zu tun:

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

• jot gibt ansteigende hexadezimale Ganzzahlen aus
• tr konvertiert dies in (0,1, ..., 8,9, b, ... f, 0a, 00,01, ..., 99,9b, ..., ff, 0aa, ..., 000 , ...)
• grep filtert einfach alle Zeilen, die Ziffern enthalten (0,1, ..., 8,9,00, ..., 99,000 ....)
• sed löscht alle bis auf die n-te Zeile
• STDERR wird in eine Wegwerfdatei '-' umgeleitet, so dass wir einfach die leere Zeichenfolge erhalten, wenn 0 übergeben wird (sed Zeilennummern beginnen bei 1, also Fehler, wenn 0 übergeben wird).
• Da wir Zahlen mit herausfiltern grep, müssen wir mehr Ganzzahlen zur Basis 11 mit seq/ dcals der eingegebenen Zahl generieren . Das Wiederholen der Ziffern von n ist mehr als ausreichend.

Beachten Sie, dass, sobald die Shortlex-Zahl gedruckt ist, seqweiterhin Zahlen bis zu erzeugt werden $1$1, die sich insbesondere bei größeren Eingaben verlangsamen - O (n²), denke ich. Wir können den seqVorgang beschleunigen, indem wir das Programm unmittelbar nach dem Drucken beenden. Dies kostet 7 Byte:

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

In der Frage gibt es keine Geschwindigkeitsanforderung, daher gehe ich für meine Hauptantwort auf die kürzere Version.

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)

Alternativer Ansatz (gleiche Länge):

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

Python 3, 107 Zeichen

Das hat nicht gewonnen, aber ich fand es klug:

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]

Ich definiere einen Generator für die gesamte Sequenz in 64 Zeichen. Leider muss ich einige Verzerrungen durchgehen, um das n-te Element des Generators zu erhalten ... wenn ich es nur könnte S=lambda n:G()[n].

Pyth , 12

Eine weitere Portierung der Antwort von @ edc65, wer ist der klare Gewinner (IMO):

t`+hQv*l`Q\8

Testpaket (Dank an @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"

Erläuterung:

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 Bytes

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

Port of @ edc65's erstaunliche JavaScript (ES6) Antwort , da ich bezweifle, dass es in Java auf arithmetische Weise kürzer gemacht werden kann.

Probieren Sie es hier aus.

Haskell , 57 Bytes

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

Probieren Sie es online!

Erstellt eine unendliche Liste von Shortlex-Zahlen und indiziert diese für die Antwort. g nKonstruiert die n-te "Generation" von Zahlen, indem die nächste Ziffer vor jeder der Zahlen der vorherigen Generation vorangestellt wird.

05AB1E , 7 Bytes

Verwendet edc65's , um 8 Tricks zu ersetzen

8sg×+>¦

Probieren Sie es online!

Erläuterung

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

Excel, 37 Bytes

Verwenden Sie den @ edc65-Ansatz:

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

Gelee , 5 Bytes

ḃ⁵ịØD

Probieren Sie es online!

Ich bin sehr neu bei Jelly. Wenn Sie dies verbessern können, kommentieren Sie dies bitte!

Erläuterung:

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

(Nach dem obigen Kommentar von res ist das Problem gleichbedeutend damit, die Zahl in die bijektive Basis 10 umzuwandeln.)