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 20
direkt nach 100
, von 120
nach 200
und von 200
nach ü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 2
und nicht 1
danach 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 N
in 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 N
ist 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>
quelle
59->60
und109->110
mit der zusätzlichen 0 gesehen habe.Antworten:
Pyth, 17 Bytes
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
.f
Funktion "Schleife bis n Übereinstimmungen gefunden wurden" von Pyth verwendet.quelle
CJam,
2423222119 BytesDies 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>
zuW%
.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
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.quelle
Python 2, 67 Bytes
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
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.quelle
2and
in 3 kompilieren? Ich bin in 2 und2and2
wirft einen Syntaxfehler2and2
würde nicht funktionieren, da es als2 and2
- try analysiert würde2and 2
, was funktionieren sollte, wenn Ihre Python-Version neu genug ist (getestet in Python 2.7.10)CJam,
222120 BytesDies 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
quelle
Pyth, 20 Bytes
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:
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:
J
vonQ
mit=%QJ
. Wenn beispielsweise ,Q=10
undJ=7
,Q
wird3
, der der binären skew Wechsel von110
zu10
. Dies hat in der ersten Iteration keine Auswirkung.J
zum nächstkleineren binären Basiswert wechseln=/J2
. Dies wird platt Division durch 2, WechselJ=7
zuJ=3
, zum Beispiel. Da dies geschieht, bevor die erste Ziffer ausgegeben wird,J
wird eine Ziffer höher als erforderlich initialisiert./QJ
(effektiv).p
, anstatt mit Pyths Standarddruck, um die nachgestellte Newline zu vermeiden.Diese Schleife wird wiederholt, bis sie
J
Null wird. An diesem Punkt wird ein Fehler durch Teilen durch Null ausgelöst, und die Schleife wird beendet.quelle
ES6, 105 Bytes
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!
quelle
f=
.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}
Math.pow(3,s.length+c)
durch3**(s.length+c)
.Netzhaut, 55 Bytes
Nimmt unäre Eingaben auf.
Jede Zeile sollte in eine eigene Datei gehen, aber Sie können den Code als eine Datei mit dem
-s
Flag ausführen . Z.B:Methode: Führt die Inkrementierung einer Zeichenfolge aus, beginnend mit der Zeichenfolge
0
.Wir verwenden die folgenden Inkrementierungsregeln:
2
:^2 -> ^12
;02 -> 12
;12 -> 20
2
:0$ -> 1$
;1$ -> 2$
(Es kann höchstens einen
2
in der Zeichenfolge geben;^
und$
markiert den Anfang und das Ende der Zeichenfolge in den Regeln.)Weitere Informationen zu Retina.
quelle
Java,
154,148Diese 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.
quelle
Bash + Coreutils, 52
Dies ist ein Brute-Forcer, daher ist es für größere Zahlen eher langsam.
Ausgabe:
quelle
Java,
337335253246244 BytesEine Methode, die den Index als "" aufnimmt
long
und das Ergebnis als Zeichenfolge zurückgibtVerwendet a
long
für den Index, kann also theoretisch den letzten Testfall behandeln, aber ich würde es wirklich nicht vorschlagen.quelle
if(j == 0)
Anweisung (vier Bytes). Sie müssen nicht deklarierenk
; Sie können nur nochj
einmal verwenden (vier weitere). Sie können generische Typinferenz (in Java 7) in Ihrer List-Deklaration (new ArrayList<>();
) verwenden (weitere 4)Haskell,
7372Danke 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.
Diese Lösung ist ein eher naiver Ansatz, bei dem die Binärzahl
n
des Versatzes durch 0- maliges Inkrementieren berechnet wirdn
.quelle
CJam, 24 Bytes
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:
Ersetzen Sie eine eventuelle 2 durch eine 0 .
Wenn eine 2 ersetzt wurde, erhöhen Sie die Ziffer nach links.
Andernfalls erhöhen Sie die letzte Ziffer.
Wie es funktioniert
quelle
VBA,
209147142 BytesMeine 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.print
fürmsgbox
als Ausgabe. 5 Bytes gespeichertquelle
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 deklarierenk as Long
, schreiben Sie einfachk
. Es wird eine Variable vom Typ Variant sein und der Code wird weiterhin funktionieren. Mit diesen Tipps sollten Sie auf ~ 165 Bytes reduzieren.InStr
, sie sind optional.Trim()
ist nicht notwendig, da Sie kein Leerzeichen haben. Bei richtiger Anwendung komme ich auf 147 Bytes .debug.print q
wäre die Standardausgabe?msgbox q
ist 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.MsgBox
, wenn sich jemand beschwert, kannst du es trotzdem zurück ändern.Javascript ES6,
9986787672 ZeichenPrüfung:
Danke für die Tatsache - es ist die Basis meiner Lösung :)
quelle
Oktave,
107101 BytesSollte O (log n) sein, wenn ich das richtig finde ...
Pretty-Print:
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 - 1
gebe an, um zu zeigen, dass ich das genau kann, und der letzte Satz von Ausgaben zeigt, wie lange es dauert, diesen Wert zu berechnen):quelle
T-SQL,
221189177 BytesBEARBEITEN: 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.
Und hier ist es wieder, aber lesbar:
Wenn ich nur ints verwende, kann dies mit 157 Bytes etwas kürzer sein:
Und noch einmal besser lesbar:
quelle
@
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 ,char
anstattvarchar
, oder verwenden Sie diestr
Funktion.@
mich benutzt , doof . DerCHAR(8000)
Rat ist ziemlich gut, ich werde das versuchen. Ich scheine immer die Existenz desSTR()
Dankes für die Heads-Ups zu vergessen .select @t=concat(@t,@/i)
kleiner sein sollte. Benötigt allerdings sql2012.CONCAT
Ich bin auf 2008. Also kann ich es jetzt nicht testen, ohne eine SQL-Geige zu benutzen. Guter Anruf.Turing Machine Code,
333293 BytesIch 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.
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 .
quelle
Perl, 66 Bytes
Die Nummer muss über STDIN eingegeben werden.
quelle
(.?)
in$2
da(.*)
in$1
gierig 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;
.$c=<>;s/(.*)2(.*)/$1+1 .$2.0/e||$_++while($c--);print
. Ich hatte recht, das hat(.?)
nie etwas eingefangen.$_=1;$c=<>;s/(.?)2/1+$1.0/e||$_++while(--$c);print
50 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
.Pyth, 19 Bytes
Logarithmische Komplexität. Beendet leicht in der notwendigen Zeit. Ausgabe in Form einer Ziffernliste.
Vorführung .
quelle
Perl,
847067 BytesNicht sehr golfen,immer besser, aber es funktioniert sehr schnell!Dennis 'Vorschlag bringt es auf 51 (50 Bytes + -p Schalter)
Es muss so heißen, als ob "
perl -p skew_binary.pl num_list.txt
where"num_list.txt
eine einzelne Zeile mit der Nummer enthält, die darauf codiert werden soll.quelle
Mathematica, 65
Sollte ziemlich schnell genug sein, obwohl ich zugeben muss, dass ich vorher einen Blick auf die anderen Einsendungen geworfen habe.
Verwendungszweck:
Ausgabe:
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:
Ausgabe:
quelle
C 95 Bytes
Dies akzeptiert eine Ganzzahl und einen Puffer, in dem die Ziffern zurückgegeben werden. Die Ergebnisse werden in gespeichert
b
und mit value abgeschlossen3
(was in der Ausgabe nicht vorkommen kann). Wir müssen nicht mit der Eingabe von umgehen0
(da die Frage nur positive Ganzzahlen angibt), daher gibt es keine spezielle Schreibweise, um leere Ausgaben zu vermeiden.Erweiterter Code
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 long
Falls 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
int
Array-Puffer in eine druckbare Ziffernfolge. Die Laufzeit für die Eingabe beträgt weniger als eine Millisekunde1000000000000000000
.Testergebnisse
quelle
auto a=~0ull
für einen kleinen Vorteil nutzen ...JavaScript (Node.js) , 40 Byte
Probieren Sie es online!
Diese Lösung funktioniert nicht im letzten Testfall. Es verursacht nur einen Stapelüberlauf.
quelle
CoffeeScript,
92-69BytesBasierend auf der Antwort und den Updates von Qwertiy :
quelle
Japt , 31 Bytes
Probieren Sie es online!
Fast direkter Port dieser JS-Lösung . Keine Ahnung, ob es einen besseren Weg gibt.
Ausgepackt und wie es funktioniert
quelle
Stax , 16 Bytes
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.
Führen Sie dieses aus
quelle