Seitennummerierung im xkcd-Stil

65

Randall Munroes Buch "xkcd, Band 0" verwendet ein ziemlich ungerades Zahlensystem für die Seitenzahlen. Die ersten Seitenzahlen sind

1, 2, 10, 11, 12, 20, 100, 101, 102, 110, 111, 112, 120, 200, 1000, 1001, ...

Das sieht ein bisschen wie ternär aus, aber beachte, dass er von 20direkt nach 100, von 120nach 200und von 200nach überspringt 1000. Eine Möglichkeit , diese Sequenz zu definieren , ist zu sagen dass es alle ternären Zahlen aufzählt , die höchstens ein enthalten 2und nicht 1danach 2. Sie finden dies auf OEIS in Eintrag A169683 . Dieses Zahlensystem ist als Binärverschiebung bekannt .

Ihre Aufgabe ist es, die Darstellung einer bestimmten positiven ganzen Zahl Nin diesem Zahlensystem zu finden.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Die Ausgabe kann eine Zeichenfolge, eine Zahl mit einer Dezimaldarstellung sein, die der binären Neigungsdarstellung entspricht, oder eine Liste von Ziffern (als Ganzzahlen oder Zeichen / Zeichenfolgen). Sie dürfen keine führenden Nullen zurückgeben.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Unterhaltsame Tatsache: Dieses Zahlensystem hat tatsächlich einige Vorteile. Wenn Sie eine Zahl erhöhen, ändern Sie immer höchstens zwei benachbarte Ziffern - Sie müssen die Änderung nie durch die gesamte Zahl führen. Mit der richtigen Darstellung, die das Inkrementieren in O (1) ermöglicht.

Testfälle

1 => 1
2 => 2
3 => 10
6 => 20
7 => 100
50 => 11011
100 => 110020
200 => 1100110
1000 => 111110120
10000 => 1001110001012
100000 => 1100001101010020
1000000 => 1111010000100100100
1048576 => 10000000000000000001

1000000000000000000 => 11011110000010110110101100111010011101100100000000000001102

Ich werde der kürzesten Antwort eine Prämie geben, die den letzten Testfall (und jede andere Eingabe von ähnlicher Größe, also denken Sie nicht daran, sie hart zu codieren) in weniger als einer Sekunde lösen kann.

Bestenlisten

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihre Punktzahl verbessern, können Sie alte Punkte in der Überschrift behalten, indem Sie sie durchstreichen. Zum Beispiel:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 51517</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Martin Ender
quelle
32
Ich habe das Buch seit dem Erscheinen und habe die Seitennummerierung nie bemerkt.
Alex A.
2
@AlexA. Ich habe es auf meinem Kindle, wo Sie keine interessante Seitennummerierung machen können.
LegionMammal978
21
@ LegionMammal978: Tragisch.
Alex A.
1
@ SuperJedi224 Konsens scheint nein zu sein , also tut mir leid (ich würde eine Ausnahme vom Konsens machen, wenn dies die einzige Art von Eingabe wäre, die Ihre Sprache verarbeiten könnte, aber das scheint nicht der Fall zu sein).
Martin Ender
4
Das erinnert mich daran, wie ich gezählt habe, als ich 3 Jahre alt war. Ich überlegte: "Es gibt keine zehnundfünfzig, also muss nach neunundzwanzig zweihundert sein." Ich habe meinen Fehler erst erkannt, als ich den Unterschied zwischen 59->60und 109->110mit der zusätzlichen 0 gesehen habe.
Cyoce

Antworten:

12

Pyth, 17 Bytes

Ljb3ye.f!-P-yZ01Q

Das ist etwas lächerlich langsam - O(output^log_2(3)). Es ist exponentiell in der Länge der Eingabe, aber nicht doppelt exponentiell, wie einige der Antworten auf der Seite. Einige Ideen aus der Antwort von @ Dennis hier .

Demonstration.

Dabei wird die .fFunktion "Schleife bis n Übereinstimmungen gefunden wurden" von Pyth verwendet.

isaacg
quelle
32

CJam, 24 23 22 21 19 Bytes

ri_)2b,,W%{2\#(md}/

Dies ist ein O (log n) -Ansatz, bei dem n die Eingabe ist, mit der der letzte Testfall sofort abgeschlossen wird. Es konvertiert n direkt in einen binären Versatz, indem es modular durch die Werte der Ziffer 1 dividiert wird .

Dieser Code endet mit einem Fehler, der mit dem Java-Interpreter an STDERR gesendet wird. Dies ist gemäß dem Meta-Konsens zulässig .

Wenn Sie diesen Code im CJam-Interpreter ausprobieren , ignorieren Sie einfach alles außer der letzten Ausgabezeile.

Der Fehler kann auf Kosten von 2 Bytes eliminiert werden, indem das Voranstellen 2>zu W%.

Vielen Dank an @ MartinBüttner fürs Abschlagen eines Bytes.

Hintergrund

Die binäre Schrägdarstellung a k ... a 0 entspricht der ganzen Zahl n = (2 k + 1 -1) a k + ... + (2 1 -1) a 0 .

Da sowohl (2 k & supmin; ¹) + ... + (2 1 & supmin; ¹) = 2 k + 1 - (k + 2) als auch (2 k & supmin; ¹) + ... + 2 (2 j & supmin; ¹) = 2 k + 1 - (2 j + 1 - 2 j + k + 1) sind kleiner als 2 k + 1 -1 , die Werte von a k bis a 0 können durch sukzessive modulare Division durch 2 k + 1 -1 wiederhergestellt werden , 2 k & supmin ; ¹ usw.

Zunächst müssen wir den Wert von 2 k + 1 -1 ermitteln . Da n höchstens 2 ist (2 k + 1 -1) , muss die ganze Zahl n + 1 genau kleiner als 2 k + 2 sein .

Wenn man also den ganzzahligen Teil des binären Logarithmus von n + 1 nimmt, erhält man k + 1 .

Schließlich beobachtet man , dass die ganze Zahl n + 1 hat ⌊log 2 (n + 1) ⌋ Ziffern in der Basis 2.

Wie es funktioniert

ri    e# Read an integer N from STDIN.
2b,   e# Push the number of binary digits of N + 1, i.e, K + 2 = log(N + 1) + 1.
,W%   e# Push the range [K+1 ... 0].
{     e# For each J in the range:
  2\# e#   J -> 2**J
  (   e#     -> 2**J - 1
  md  e#   Perform modular division of the integer on the stack (initially N)
      e#   by 2**J - 1: N, 2**J - 1 -> N/(2**J - 1), N%(2**J - 1)
}/    e#

In den letzten beiden Iterationen führen wir eine modulare Division durch 1 und 0 durch . Der erste drückt eine unerwünschte 0 auf den Stapel. Die letzten Versuche ausführen zu 0 0 md, die beide unerwünschte knallt 0 s aus dem Stapel, verlässt sofort statt irgendetwas drängen und Dumps den Stapel zu STDOUT.

Dennis
quelle
28

Python 2, 67 Bytes

def f(n):x=len(bin(n+1))-3;y=2**x-1;return n and n/y*10**~-x+f(n%y)

Scheint für die gegebenen Testfälle zu funktionieren. Wenn ich das richtig verstanden habe, sollte es ungefähr O(place values set in output)so sein , also macht es den letzten Fall mit Leichtigkeit.

Rufen Sie gerne an f(100). Gibt eine Dezimaldarstellung zurück, die der binären Abweichung entspricht.

Python 3, 65 Bytes

def g(n,x=1):*a,b=n>x*2and g(n,x-~x)or[n];return a+[b//x,b%x][:x]

Etwas weniger effizient, aber immer noch logarithmisch, so dass der letzte Fall fast augenblicklich ist.

Rufen Sie gerne an g(100). Gibt eine Liste mit Ziffern zurück.

Sp3000
quelle
ist 2andin 3 kompilieren? Ich bin in 2 und 2and2wirft einen Syntaxfehler
TankorSmash
3
@TankorSmash 2and2würde nicht funktionieren, da es als 2 and2- try analysiert würde 2and 2, was funktionieren sollte, wenn Ihre Python-Version neu genug ist (getestet in Python 2.7.10)
Sp3000
Oh schön, du hast recht. Sogar auf 2.7.3 funktioniert es.
TankorSmash
12

CJam, 22 21 20 Bytes

ri_me,3fb{0-W<1-!},=

Dies ist ein O ( en n) -Ansatz, bei dem n die Eingabe ist. Es listet die erste ⌊e n nicht negativen ganzen Zahlen in der Basis 3, eliminiert diejenigen, haben 2 s oder 1 s nach den ersten 2 (falls vorhanden) und wählt den n + 1 - te .

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

ri    e# Read an integer N from STDIN.
_me,  e# Push [0 ... floor(exp(N))-1].
3fb   e# Replace each integer in the range by the array of its digits in base 3.
{     e# Filter; for each array A:
  0-  e#   Remove all 0's.
  W<  e#   Remove the last element.
  1-  e#   Remove all 1's.
  !   e#   Logical NOT. Pushes 1 iff the array is empty.
},    e#   If ! pushed 1, keep the array.
=     e# Select the (N+1)th element of the filtered array.
Dennis
quelle
9

Pyth, 20 Bytes

Jt^2hslhQ#p/=%QJ=/J2

Läuft in O (log (input ())), deutlich unter einer Sekunde für den letzten Testfall. Basiert auf einer Lauf-bis-Fehler-Schleife. Keine nachgestellte Newline.

Demonstration.

Erläuterung:

Jt^2hslhQ#p/=%QJ=/J2
                        Implicit: Q is the input.
      lhQ                          log(Q+1,2)
     slhQ                    floor(log(Q+1,2))
    hslhQ                    floor(log(Q+1,2))+1
  ^2hslhQ                 2^(floor(log(Q+1,2))+1)
 t^2hslhQ                 2^(floor(log(Q+1,2))+1)-1
Jt^2hslhQ               J=2^(floor(log(Q+1,2))+1)-1
         #              until an error is thrown:
            =%QJ        Q=Q%J
                =/J2    J=J/2
           /            The value Q/J, with the new values of Q and J.
          p             print that charcter, with no trailing newline.

J wird auf den Wert der Position der kleinsten Binärziffer initialisiert, die größer als die Eingabe ist. Dann machen wir jedes Mal, wenn wir die Schleife durchlaufen, Folgendes:

  • Entfernen Sie jede Wertziffer Jvon Qmit =%QJ. Wenn beispielsweise , Q=10und J=7, Qwird 3, der der binären skew Wechsel von 110zu 10. Dies hat in der ersten Iteration keine Auswirkung.
  • Mit Jzum nächstkleineren binären Basiswert wechseln =/J2. Dies wird platt Division durch 2, Wechsel J=7zu J=3, zum Beispiel. Da dies geschieht, bevor die erste Ziffer ausgegeben wird, Jwird eine Ziffer höher als erforderlich initialisiert.
  • Finden Sie den tatsächlichen Ziffernwert mit /QJ(effektiv).
  • Drucken Sie diesen Wert mit p, anstatt mit Pyths Standarddruck, um die nachgestellte Newline zu vermeiden.

Diese Schleife wird wiederholt, bis sie JNull wird. An diesem Punkt wird ein Fehler durch Teilen durch Null ausgelöst, und die Schleife wird beendet.

isaacg
quelle
8

ES6, 105 Bytes

f=n=>{for(o=0;n--;c?o+=Math.pow(3,s.length-c):o++)s=t(o),c=s.search(2)+1;return t(o);},t=a=>a.toString(3)

Verwendung ist: f(1048576)=> "10000000000000000001"

Testen Sie das letzte Argument auf eigene Gefahr. Ich habe nach 5 Sekunden aufgegeben.

Und hübscher Druck mit Kommentaren!

f=n=>{ //define function f with input of n (iteration)
    for(o=0; //define o (output value in decimal)
        n--; //decrement n (goes towards falsy 0) each loop until 0
        c?o+=Math.pow(3,s.length-c):o++) //if search finds a 2, increment output by 3^place (basically moves the 2 to the left and sets the place to 0), else ++
        s=t(o), //convert output to base 3      
        c=s.search(2)+1; //find the location of 2, +1, so a not-found becomes falsy 0.
    return t(o); //return the output in base 3
},

t=a=>a.toString(3);  //convert input a to base 3
Kompass
quelle
5
Übrigens sind unbenannte Funktionen durchaus akzeptabel, Sie brauchen sie also nicht f=.
Martin Ender,
2
-16 bytes:f=n=>{for(o=0;~n--;o+=c?Math.pow(3,s.length+c):1)s=o.toString(3),c=~s.search(2);return s}
nderscore
@nderscore Ziemlich cool: D
Compass
1
-7 Bytes bei Verwendung von ES7: Ersetzen Math.pow(3,s.length+c)durch 3**(s.length+c).
Gustavo Rodrigues
3
@GustavoRodrigues Ich habe noch nicht einmal ES6 gelernt! @ _ @
Compass
7

Netzhaut, 55 Bytes

^
0a
(+`12(.*a)1
20$1
0?2(.*a)1
10$1
0a1
1a
)`1a1
2a
a
<empty line>

Nimmt unäre Eingaben auf.

Jede Zeile sollte in eine eigene Datei gehen, aber Sie können den Code als eine Datei mit dem -sFlag ausführen . Z.B:

> echo 11111|retina -s skew
12

Methode: Führt die Inkrementierung einer Zeichenfolge aus, beginnend mit der Zeichenfolge 0.

Wir verwenden die folgenden Inkrementierungsregeln:

  • wenn enthält 2: ^2 -> ^12; 02 -> 12;12 -> 20
  • wenn nicht enthalten 2: 0$ -> 1$;1$ -> 2$

(Es kann höchstens einen 2in der Zeichenfolge geben; ^und $markiert den Anfang und das Ende der Zeichenfolge in den Regeln.)

Weitere Informationen zu Retina.

randomra
quelle
7

Java, 154, 148

n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;}

Diese Antwort hat die Form einer einzelnen anonymen Funktion, die ein ganzzahliges Argument annimmt und die Antwort als Zeichenfolge zurückgibt. Im Folgenden finden Sie eine vollständige Klasse zum Testen dieser Lösung.

import java.util.function.Function;
public class Skew {
    public static void main(String[] args){
        Function<Integer,String> skew = n->{String s="0";for(;n-->0;)s=s.contains("2")?s.replaceAll("(^|0)2","10").replace("12","20"):s.replaceAll("1$","2").replaceAll("0$","1");return s;};

        for(String s:args){
            System.out.println(skew.apply(Integer.parseInt(s)));
        }
    }
}
Ankh-Morpork
quelle
5

Bash + Coreutils, 52

dc -e3o0[r1+prdx]dx|grep -v 2.\*[12]|sed -n $1{p\;q}

Dies ist ein Brute-Forcer, daher ist es für größere Zahlen eher langsam.

Ausgabe:

$ ./xkcdnum.sh 1000
111110120
$ 
Digitales Trauma
quelle
5

Java, 337 335 253 246 244 Bytes

Eine Methode, die den Index als "" aufnimmt longund das Ergebnis als Zeichenfolge zurückgibt

Verwendet a longfür den Index, kann also theoretisch den letzten Testfall behandeln, aber ich würde es wirklich nicht vorschlagen.

String f(long i){List<Long>l=new ArrayList<>();l.add(0L);for(;i-->0;){int j=l.indexOf(2);if(j!=-1){l.set(j,0L);if(j==0){l.add(0,1L);}else{l.set(j-1,l.get(j-1)+1);}}else{j=l.size()-1;l.set(j,l.get(j)+1);}}String s="";for(long q:l)s+=q;return s;}
SuperJedi224
quelle
4
Sie können dies erheblich verkürzen, indem Sie eine Funktion anstelle eines vollständigen Programms definieren (und die Eingabe als Argument anstelle eines Scanners verwenden).
Geobits
2
Sie brauchen keine geschweiften Klammern in der if(j == 0) Anweisung (vier Bytes). Sie müssen nicht deklarieren k; Sie können nur noch jeinmal verwenden (vier weitere). Sie können generische Typinferenz (in Java 7) in Ihrer List-Deklaration ( new ArrayList<>();) verwenden (weitere 4)
durron597
4

Haskell, 73 72

Danke an @nimi für 1 Byte!

Diese Lösung wird kein Kopfgeld gewinnen, die letzten paar Tests dauern übermäßig lange, aber ich denke, ich habe es ziemlich gut gespielt.

i(2:b)=1:0:b
i[b]=[b+1]
i(b:2:c)=b+1:0:c
i(b:c)=b:i c
s=(iterate i[0]!!)

Diese Lösung ist ein eher naiver Ansatz, bei dem die Binärzahl ndes Versatzes durch 0- maliges Inkrementieren berechnet wird n.

Ankh-Morpork
quelle
4

CJam, 24 Bytes

Q{0\+2a/())+a\+0a*}ri*si

Dies ist ein O (n log n) -Ansatz, bei dem n die Eingabe ist. Es beginnt mit der binären Neigungsdarstellung von 0 und inkrementiert die entsprechende Ganzzahl n- mal.

Probieren Sie es online im CJam-Interpreter aus .

Hintergrund

Das Inkrementieren einer Zahl in der Binärdatei kann in zwei einfachen Schritten erfolgen:

  1. Ersetzen Sie eine eventuelle 2 durch eine 0 .

  2. Wenn eine 2 ersetzt wurde, erhöhen Sie die Ziffer nach links.

    Andernfalls erhöhen Sie die letzte Ziffer.

Wie es funktioniert

Q     e# Push an empty array.
{     e# Define an anonymous function:
  0\+ e#   Prepend a 0 to the array.
  2a/ e#   Split the array at 2's.
  (   e#   Shift out the first chunk of this array.
  )   e#   Pop the last digit.
  )+  e#   Increment it and append it to the array.
  a\+ e#   Prepend the chunk to the array of chunks.
  0a* e#   Join the chunks, using [0] as separator.
      e#   If there was a 2, it will get replaced with a 0. Otherewise, there's
      e#   only one chunk and joining the array dumps the chunk on the stack.
}     e#
ri*   e# Call the function int(input()) times.
si    e# Cast to string, then to integer. This eliminates leading 0's.
Dennis
quelle
4

VBA, 209 147 142 Bytes

Sub p(k)
For i=1To k
a=StrReverse(q)
If Left(Replace(a,"0",""),1)=2Then:q=q-2*10^(InStr(a,2)-1)+10^InStr(a,2):Else:q=q+1
Next
msgbox q
End Sub

Meine Mathematik ist ineffizient und mein Golfen könnte Arbeit gebrauchen. Aber es ist mein erster Versuch bei PoG und ich dachte, ich würde es versuchen. Eine Art Brute-Force-Weg.

Es zählt nur um 1, es sei denn, die letzte Ziffer ist eine 2, dann geht es um 2 zurück und springt um 10 vorwärts.

Dies funktioniert bei 65534 nicht mehr, da VBA darauf besteht, die Ausgabe in wissenschaftlicher Notation zu geben, aber die Logik sollte für noch höhere Zahlen gut funktionieren

VBA ist nicht sehr golffreundlich, aber nicht oft vertreten, und ich denke, es kann Java in der Länge schlagen.

Edit1: Vielen Dank, Manu, dass du 62 Bytes gespart hast

Edit2: Vertauschte debug.printfür msgboxals Ausgabe. 5 Bytes gespeichert

JimmyJazzx
quelle
1
Sie können die Klammern von entfernen Debug.Print (q). Sie können auch den größten Teil des Leerzeichens entfernen (der Editor setzt sie zurück, sie sind jedoch nicht erforderlich). Sie müssen nicht deklarieren k as Long, schreiben Sie einfach k. Es wird eine Variable vom Typ Variant sein und der Code wird weiterhin funktionieren. Mit diesen Tipps sollten Sie auf ~ 165 Bytes reduzieren.
CommonGuy
Noch ein paar Gedanken: Sie können das erste und letzte Argument von weglassen InStr, sie sind optional. Trim()ist nicht notwendig, da Sie kein Leerzeichen haben. Bei richtiger Anwendung komme ich auf 147 Bytes .
CommonGuy
1
Vielen Dank für die Hilfe Manu, eine kurze Frage, Ausgabe sollte die Standardausgabe sein. Ich bin mir nicht sicher, was das in VBA sein würde. debug.print qwäre die Standardausgabe? msgbox qist kürzer, scheint aber wieder nicht ganz die Standardausgabe zu sein. Sheet1.cells(1,1)Scheint wie die typische Ausgabe, geht aber davon aus, dass sie in Excel ausgeführt wird. Ich bin mir nur nicht ganz sicher, wie streng Code-Golf mit solchen Dingen ist.
JimmyJazzx
Herzlichen Glückwunsch, du hast die Java-Antwort geschlagen;) Ich weiß es auch nicht ... Benutze einfach MsgBox, wenn sich jemand beschwert, kannst du es trotzdem zurück ändern.
CommonGuy
4

Javascript ES6, 99 86 78 76 72 Zeichen

f=n=>{for(s="1";--n;s=s.replace(/.?2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 76 chars:
f=n=>{for(s="1";--n;s=s.replace(/02|12|2|.$/,m=>[1,2,10][+m]||20));return s}

// Old version, 86 chars:
f=n=>{for(s="1";--n;s=s.replace(/(02|12|2|.$)/,m=>[1,2,10,,,,,,,,,,20][+m]));return s}

// Old version, 99 chars:
f=n=>{for(s="1";--n;s=s.replace(/(^2|02|12|20|.$)/,m=>({0:1,1:2,2:10,12:20,20:100}[+m])));return s}

Prüfung:

;[1,2,3,6,7,50,100,200,1000,10000,100000,1000000,1048576].map(f) == "1,2,10,20,100,11011,110020,1100110,111110120,1001110001012,1100001101010020,1111010000100100100,10000000000000000001"

Unterhaltsame Tatsache: Dieses Zahlensystem hat tatsächlich einige Vorteile. Wenn Sie eine Zahl erhöhen, ändern Sie immer höchstens zwei benachbarte Ziffern - Sie müssen die Änderung nie durch die gesamte Zahl führen. Mit der richtigen Darstellung, die das Inkrementieren in O (1) ermöglicht.

Danke für die Tatsache - es ist die Basis meiner Lösung :)

Qwertiy
quelle
Wie könnte ich unnötige Klammern im Regex lassen? o_O
Qwertiy
3

Oktave, 107 101 Bytes

Sollte O (log n) sein, wenn ich das richtig finde ...

function r=s(n)r="";for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)x=idivide(n,a);r=[r x+48];n-=x*a;end;end

Pretty-Print:

function r=s(n)
  r="";
  for(a=2.^(uint64(fix(log2(n+1))):-1:1)-1)
    x=idivide(n,a);
    r=[r x+48];
    n-=x*a;
  end
end

Ich war bei der Bewältigung der letzten Herausforderung etwas verlegen, da Octave standardmäßig alles als Gleitkommazahlen behandelt und ich nicht die erforderliche Genauigkeit hatte, um die letzte zu berechnen. Ich habe das umgangen, indem ich wertvolle Bytes ausgegeben habe, um alles zu einer vorzeichenlosen Ganzzahl zu machen. Das Ergebnis des letzten war zu groß, um als Zahl behandelt zu werden, daher ist das Ergebnis eine Zeichenfolge.

Ausgabe (Ich 1e18 - 1gebe an, um zu zeigen, dass ich das genau kann, und der letzte Satz von Ausgaben zeigt, wie lange es dauert, diesen Wert zu berechnen):

octave:83> s(uint64(1e18))
ans = 11011110000010110110101100111010011101100100000000000001102

octave:84> s(uint64(1e18)-1)
ans = 11011110000010110110101100111010011101100100000000000001101

octave:85> tic();s(uint64(1e18)-1);toc()
Elapsed time is 0.0270021 seconds.
dcsohl
quelle
3

T-SQL, 221 189 177 Bytes

BEARBEITEN: Die Originalversionen dieses Codes erzeugten für einige Zahlen eine falsche Ausgabe. Dies wurde korrigiert.

Fügen Sie bei jeder Abfrage hier einfach die zu berechnende Zahl vor dem ersten Komma hinzu.

Jeder weiß, dass T-SQL die beste Golfsprache ist. Hier ist eine Version, die sogar den letzten Testfall berechnet. Auf der Maschine, auf der ich es getestet habe, lief es in weniger als einer Sekunde. Ich wäre gespannt, wie es für alle anderen läuft.

DECLARE @ BIGINT=,@T VARCHAR(MAX)='';WITH M AS(SELECT CAST(2AS BIGINT)I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T += STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Und hier ist es wieder, aber lesbar:

DECLARE 
    @ BIGINT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        CAST(2 AS BIGINT) I

    UNION ALL

    SELECT I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T

Wenn ich nur ints verwende, kann dies mit 157 Bytes etwas kürzer sein:

DECLARE @ INT=,@T VARCHAR(MAX)='';WITH M AS(SELECT 2I UNION ALL SELECT I*2FROM M WHERE I<@)SELECT @T+=STR(@/(I-1),1),@%=(I-1)FROM M ORDER BY I DESC SELECT @T

Und noch einmal besser lesbar:

DECLARE 
    @ INT=,
    @T VARCHAR(MAX)='';

WITH M AS
(
    SELECT
        2I

    UNION ALL

    SELECT 
        I * 2
    FROM M
    WHERE I < @
)

SELECT 
    @T+=STR(@/(I-1),1),
    @%=(I-1)
FROM M 
ORDER BY I DESC

SELECT @T
PenutReaper
quelle
Denken @Sie daran, ist ein gültiger Bezeichner in SQL und Sie können höchstwahrscheinlich davonkommen, Char(8000) was immer noch billiger als nvarchar (max) ist. Sie können auch konvertieren , charanstatt varchar, oder verwenden Sie die strFunktion.
Michael B
@MichaelB Oh, ich dachte, ich hätte @mich benutzt , doof . Der CHAR(8000)Rat ist ziemlich gut, ich werde das versuchen. Ich scheine immer die Existenz des STR()Dankes für die Heads-Ups zu vergessen .
PenutReaper
hilft eigentlich nicht. Sie können jedoch den Teil nach dem CTE in :: umschreiben, der select @t=concat(@t,@/i)kleiner sein sollte. Benötigt allerdings sql2012.
Michael B
@ MichaelB ah. CONCATIch bin auf 2008. Also kann ich es jetzt nicht testen, ohne eine SQL-Geige zu benutzen. Guter Anruf.
PenutReaper
3

Turing Machine Code, 333 293 Bytes

Ich verwende eine Kodierung, wie sie hier verwendet wird .

Diese Maschine verwendet 9 Zustände und 11 Farben.

Wenn eine Binäreingabe zulässig ist, kann diese auf nur 4 Farben reduziert werden, wodurch einige zehn Bytes eingespart werden.

0 _ _ l 1
0 * * r 0
1 9 8 l 2 
1 8 7 l 2
1 7 6 l 2
1 6 5 l 2
1 5 4 l 2
1 4 3 l 2
1 3 2 l 2
1 2 1 l 2
1 1 0 l 2
1 0 9 l 1
1 _ _ r 8
2 _ _ l 3
2 * * l 2
3 _ 1 r 4
3 * * l 5
4 _ _ r 0
4 * * r 4
5 * * l 5
5 _ _ r 6
6 _ _ l 7
6 2 0 l 7
6 * * r 6
7 _ 1 r 4
7 0 1 r 4
7 1 2 r 4
8 _ _ * halt
8 * _ r 8

Wenn der obige Link nicht funktioniert (manchmal funktioniert er für mich, manchmal kann die Seite nicht geladen werden), können Sie dies auch mit dieser Java-Implementierung testen .

SuperJedi224
quelle
2

Perl, 66 Bytes

Die Nummer muss über STDIN eingegeben werden.

$_=1;$c=<>;s/(.*)(.?)2(.*)/$1.$2+1 .$3.0/e||$_++while(--$c);print;
Frederick
quelle
Können Sie erklären, wie Ihre Lösung funktioniert? Ich sehe nicht , wie Sie brauchen (.?)in $2da (.*)in $1gierig sein und zuerst diesen Charakter bekommen. Wird es jedoch entfernt, führt der Code nicht mehr zu den richtigen Ergebnissen! Das Finale braucht man übrigens nicht ;.
CJ Dennis
@CJDennis Danke für das gespeicherte Byte. Wie auch immer, die.? Kommt die Ziffer genau vor die beiden, es sei denn, es gibt keine Ziffer (z. B. 20). In Fällen wie 120 oder 10020 mögen die Regex-Gruppen Folgendes: () (1) 2 (0) und (10) (0) 2 (0). Dann wird die erste Gruppe einfach ignoriert, die zweite Gruppe (die nach Möglichkeit immer eine Ziffer oder leer ist) wird inkrementiert, und die dritte Gruppe (die immer aus Nullen besteht) wird ignoriert und eine Null hinzugefügt. Ich habe einfach den OEIS-Eintrag als Leitfaden für diesen regulären Ausdruck verwendet.
Frederick
Ich habe den Code unten zu 53 Bytes: $c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print. Ich hatte recht, das hat (.?)nie etwas eingefangen.
CJ Dennis
Kann auf $_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print50 Byte optimiert werden . .*Am Anfang oder Ende kann optimiert werden, wenn Sie es einfach durch den Originaltext ersetzen. Es gibt auch keinen Grund, die 0 am Ende hinzuzufügen, da das Original immer nur Nullen enthält $3.
Thraidh,
2

Pyth, 19 Bytes

m/=%Qtydtd^L2_SslhQ

Logarithmische Komplexität. Beendet leicht in der notwendigen Zeit. Ausgabe in Form einer Ziffernliste.

Vorführung .

isaacg
quelle
2

Perl, 84 70 67 Bytes

$n=<>;$d*=2while($d++<$n);$_.=int($n/$d)while($n%=$d--,$d/=2);print

Nicht sehr golfen, immer besser, aber es funktioniert sehr schnell!

Dennis 'Vorschlag bringt es auf 51 (50 Bytes + -p Schalter)

$d*=2while$d++<$_;$\.=$_/$d|0while$_%=$d--,$d/=2}{

Es muss so heißen, als ob " perl -p skew_binary.pl num_list.txtwhere" num_list.txteine einzelne Zeile mit der Nummer enthält, die darauf codiert werden soll.

CJ Dennis
quelle
@ Frederick wir sind am Rande unserer Plätze warten auf 2.
Robert Grant
@RobertGrant Er spielte seinen Kommentar von zwei Dingen zu einer Sache!
CJ Dennis
Zwei Dinge: 1. Verwenden Sie anstelle von $ ARGV [0] <> als Eingabe. Es werden Eingaben von stdin akzeptiert, sofern keine Dateien als Argumente vorhanden sind. 2. Verwenden Sie für solche ungeraden Zählschemata reguläre Ausdrücke. Anstatt ungerade Rechenoperationen auszuführen, können Sie Ziffern in einer Zahl ersetzen, als wäre es eine Zeichenfolge. Das Beste daran ist, dass Sie gleichzeitig mathematische Operationen (wie Inkremente) verwenden können, vorausgesetzt, es handelt sich um eine Zeichenfolge, die vollständig aus Ziffern besteht. Überprüfen Sie die Dokumentation für die Operatoren für reguläre Ausdrücke, da sie in so vielen Situationen sehr nützlich sein können.
Frederick
Entschuldigung, ich habe die Eingabetaste gedrückt und es wurde gespeichert, bevor ich den Kommentar beendet habe.
Frederick
@ Frederick sei nicht so bescheiden. Wir wissen was passiert ist!
Robert Grant
1

Mathematica, 65

Sollte ziemlich schnell genug sein, obwohl ich zugeben muss, dass ich vorher einen Blick auf die anderen Einsendungen geworfen habe.

f = (n = #;
     l = 0; 
     While[n > 0,
      m = Floor[Log2[1 + n]];
      l += 10^(m - 1);
      n -= 2^m - 1
     ]; l)&

Verwendungszweck:

f[1000000000000000000]

Ausgabe:

11011110000010110110101100111010011101100100000000000001102

Beginnt, MaxExtraPrecision-Fehlermeldungen irgendwo nach 10 ^ 228 auszugeben (für die das Ergebnis in 0,03 Sekunden auf meinem Computer berechnet wird).

Nachdem die MaxExtraPrecision-Grenze aufgehoben wurde, werden in einer Sekunde Zahlen bis zu 10 ^ 8000 verarbeitet.

Eingang:

Timing[Block[{$MaxExtraPrecision = Infinity}, f[10^8000]];]

Ausgabe:

{1.060807, Null}
Übereinstimmen
quelle
1

C 95 Bytes

void f(unsigned long i,int*b){for(unsigned long a=~0,m=0;a;a/=2,b+=!!m)m|=*b=i/a,i-=a**b;*b=3;}

Dies akzeptiert eine Ganzzahl und einen Puffer, in dem die Ziffern zurückgegeben werden. Die Ergebnisse werden in gespeichert bund mit value abgeschlossen 3(was in der Ausgabe nicht vorkommen kann). Wir müssen nicht mit der Eingabe von umgehen 0(da die Frage nur positive Ganzzahlen angibt), daher gibt es keine spezielle Schreibweise, um leere Ausgaben zu vermeiden.

Erweiterter Code

void f(unsigned long i,int*b)
{
    for (unsigned long a=~0, m=0;  a;  a/=2, b+=(m!=0)) {
        *b = i/a;               /* rounds down */
        i -= *b * a;
        m = m | *b;             /* m != 0 after leading zeros */
    }
    *b=3;                       /* add terminator */
}

Wir arbeiten durch sukzessive Subtraktion, beginnend mit der höchstwertigen Ziffer. Die einzige Schwierigkeit besteht darin, dass wir die Variable verwenden m, um das Drucken von führenden Nullen zu vermeiden. unsigned long longFalls gewünscht, kann eine natürliche Erweiterung auf Kosten von 10 Bytes vorgenommen werden.

Testprogramm

Übergeben Sie die zu konvertierenden Zahlen als Befehlsargumente. Es konvertiert den intArray-Puffer in eine druckbare Ziffernfolge. Die Laufzeit für die Eingabe beträgt weniger als eine Millisekunde 1000000000000000000.

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char**argv)
{
    while (*++argv) {
        unsigned long i = strtoul(*argv, NULL, 10);
        int result[1024];
        f(i,result);

        /* convert to string */
        char s[1024];
        {char*d=s;int*p=result;while(*p!=3)*d++=*p+++'0';*d=0;}
        printf("%lu = %s\n", i, s);
    }

    return EXIT_SUCCESS;
}

Testergebnisse

$ ./51517 $(seq 20)
1 = 1
2 = 2
3 = 10
4 = 11
5 = 12
6 = 20
7 = 100
8 = 101
9 = 102
10 = 110
11 = 111
12 = 112
13 = 120
14 = 200
15 = 1000
16 = 1001
17 = 1002
18 = 1010
19 = 1011
20 = 1012
Toby Speight
quelle
Ich denke, eine C ++ - Version ist ähnlich, kann aber auto a=~0ullfür einen kleinen Vorteil nutzen ...
Toby Speight
0

CoffeeScript, 92-69 Bytes

Basierend auf der Antwort und den Updates von Qwertiy :

f=(n)->s='1';(s=s.replace /(.?2|.$)/,(m)->[1,2,10][+m]||20)while--n;s

# older version, 92 bytes
f=(n)->s='1';(s=s.replace /(^2|02|12|20|.$)/,(m)->{0:1,1:2,2:10,12:20,20:100}[+m])while--n;s
rink.attendant.6
quelle
2
Das Konvertieren in eine andere Sprache ohne einfache Optimierung durch Entfernen unnötiger Klammern in der Regex erscheint mir nicht cool ...
Qwertiy
@Qwertiy Ich habe auf Ihre Antwort zur Verfügung gestellt Zuschreibung, und mit beiden der Antworten kann ich nicht die gleichen Ergebnisse ohne die Klammern in der Regex produzieren
rink.attendant.6
Das ganze Vorkommen wird ersetzt. Warum muss es in der Gruppe sein? Die JS-Version funktioniert in Firefox ohne Klammern.
Qwertiy
0

Japt , 31 Bytes

_r/?2|.$/g_÷C ç20 ª°Zs3}}gU['0]

Probieren Sie es online!

Fast direkter Port dieser JS-Lösung . Keine Ahnung, ob es einen besseren Weg gibt.

Ausgepackt und wie es funktioniert

X{Xr/?2|.$/gZ{Z÷C ç20 ||++Zs3}}gU['0]

X{     Declare a function...
Xr       Accept a string, replace the regex...
/?2|.$/g   /.?2|.$/   (g is needed to match *only once*, opposite of JS)
Z{       ...with the function... (matched string will be 0,1,2,02 or 12)
Z÷C        Implicitly cast the matched string into number, divide by 12
ç20        Repeat "20" that many times (discard fractions)
||         If the above results in "", use the next one instead
++Z        Increment the value
s3         Convert to base-3 string (so 0,1,2 becomes 1,2,10)
}}
gU['0] Repeatedly apply the function on "0", U (input) times
Bubbler
quelle
0

Stax , 16 Bytes

üxëàè£öΦGΩ│Je5█ò

Führen Sie es aus und debuggen Sie es

Ich bin mir nicht sicher, wie die Klasse für formale Komplexität genau lautet, aber sie ist schnell genug, um alle Testfälle auf diesem Computer in einer Zehntelsekunde durchzuführen.

Ausgepackt, ungolfed und kommentiert sieht es so aus. In diesem Programm enthält das x-Register ursprünglich die Eingabe.

z       push []
{       start block for while loop
 |X:2N  -log2(++x)
 {^}&   increment array at index (pad with 0s if necessary)
 xc:G-X unset high bit of x; write back to x register
w       while; loop until x is falsy (0)
$       convert to string

Führen Sie dieses aus

rekursiv
quelle