Inspiriert von http://xkcd.com/710/ ist hier ein Code Golf dafür.
Die Herausforderung
Bei einer positiven Ganzzahl größer als 0 drucken Sie die Hagelkornsequenz für diese Zahl aus.
Die Hagelkörner-Sequenz
Siehe Wikipedia für weitere Details.
- Wenn die Zahl gerade ist, teilen Sie sie durch zwei.
- Wenn die Zahl ungerade ist, verdreifachen Sie sie und fügen Sie eine hinzu.
Wiederholen Sie dies mit der erzeugten Zahl, bis es 1 erreicht. (Wenn es nach 1 fortgesetzt wird, wird es in einer Endlosschleife von 1 -> 4 -> 2 -> 1...
)
Manchmal ist Code der beste Weg, um dies zu erklären. Hier sind einige aus Wikipedia
function collatz(n)
show n
if n > 1
if n is odd
call collatz(3n + 1)
else
call collatz(n / 2)
Dieser Code funktioniert, aber ich füge eine zusätzliche Herausforderung hinzu. Das Programm darf nicht anfällig für Stapelüberläufe sein . Es muss also entweder Iteration oder Schwanzrekursion verwendet werden.
Außerdem Bonuspunkte, wenn es große Zahlen berechnen kann und die Sprache es noch nicht implementiert hat. (oder wenn Sie die Unterstützung großer Zahlen mit Ganzzahlen fester Länge erneut implementieren)
Testfall
Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Außerdem muss der Code Golf vollständige Benutzereingaben und -ausgaben enthalten.
Antworten:
x86-Assembly, 1337 Zeichen
quelle
int 23h
.Befunge
quelle
LOLCODE: 406 CHARAKTERZ
TESTD UNDR JUSTIN J. MEZAS INTERPRETR . KTHXBYE!
quelle
Python -
95645146 charErzeugt offensichtlich keinen Stapelüberlauf.
quelle
input
macht keineeval
.n=input()*2
Perl
Ich habe mich entschlossen, ein wenig wettbewerbswidrig zu sein und zu zeigen, wie Sie ein solches Problem normalerweise in Perl codieren würden.
Es gibt auch einen 46 (insgesamt) Char Code-Golf-Eintrag am Ende.
Diese ersten drei Beispiele beginnen alle mit diesem Header.
Einfache rekursive Version
Einfache iterative Version
Optimierte iterative Version
Jetzt werde ich zeigen, wie Sie dieses letzte Beispiel mit einer Version von Perl vor v5.10.0 machen würden
Benchmark
Zunächst einmal wird das IO immer der langsame Teil sein. Wenn Sie sie also tatsächlich so wie sie sind verglichen haben, sollten Sie mit jedem ungefähr die gleiche Geschwindigkeit erreichen.
Um diese dann zu testen, öffnete ich ein Dateihandle für
/dev/null
($null
) und bearbeitete jedes,say $n
um es stattdessen zu lesensay {$null} $n
. Dies soll die Abhängigkeit von IO verringern.Nach zehnmaliger Ausführung finden Sie hier eine repräsentative Beispielausgabe:
Endlich ein echter Code-Golf-Eintrag:
46 Zeichen insgesamt
Wenn Sie den Startwert nicht drucken müssen, können Sie 5 weitere Zeichen entfernen.
41 Zeichen insgesamt
31 Zeichen für den eigentlichen Codeteil, aber der Code funktioniert ohne den
-n
Schalter nicht. Also beziehe ich das gesamte Beispiel in meine Zählung ein.quelle
$i + 1
ist immer zusätzlich (Antwort auf den Blogeintrag). Auch mitSub::Call::Recur
ist auch eine Optimierung. Sonst würde ich verwenden@_=$n;goto &Collatz
. (Es ist 10-20% langsamer, wenn Siestate @next
zumy @next
Haskell, 62 Zeichen
637683,86,97,137Benutzereingabe, gedruckte Ausgabe, verwendet konstanten Speicher und Stapel, arbeitet mit beliebig großen ganzen Zahlen.
Ein Beispiellauf dieses Codes mit einer 80-stelligen Anzahl aller Einsen (!) Als Eingabe macht ziemlich viel Spaß.
Original, nur Funktionsversion:
Haskell 51 Zeichen
Wen braucht das @ & ^ # überhaupt Bedingungen?
(Bearbeiten: Ich war "schlau" und habe Fix verwendet. Ohne diesen Code ist der Code auf 54 Zeichen gesunken. Bearbeiten2: Durch Ausklammern auf 51 gesunken.
f()
)quelle
c 1=[1];c n=n:(c$div(n
mod2*(5*n+2)+n)2)
- 41 Zeichen wird die Tatsache verwendet, dass dies k * (3n + 1) + (1-k) * n / 2 ist, wobei k = n mod 2Golfscript: 20 Zeichen
Dies entspricht
quelle
21
durch~
wird das Programm veranlassen, eine Nummer von stdin zu verwenden(eval):1:in
initialize ': undefinierte Methodeleftparen' for nil:NilClass (NoMethodError)
beim Ersetzen21
durch~
.echo 21 | ruby golfscript.rb collatz.gs
bc 41 Zeichen
Ich denke, diese Art von Problemen
bc
wurde erfunden für:Prüfung:
Richtiger Code:
bc
behandelt Zahlen mit bis zuINT_MAX
ZiffernBearbeiten: Der Wikipedia-Artikel erwähnt, dass diese Vermutung auf alle Werte bis zu 20x2 58 (ca. 5.76e18 ) überprüft wurde . Dieses Programm:
testet 2 20.000 +1 (ca. 3.98e6.020 ) in 68 Sekunden, 144.404 Zyklen.
quelle
cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc
bc
Perl: 31 Zeichen
Bearbeitet, um 2 unnötige Leerzeichen zu entfernen.
Bearbeitet, um 1 unnötigen Speicherplatz zu entfernen.
quelle
MS Excel, 35 Zeichen
Entnommen direkt aus Wikipedia :
Es dauerte nur 111 Mal, die Formel zu kopieren / einzufügen, um das Ergebnis für eine Startnummer von 1000 zu erhalten .;)
quelle
C: 64 Zeichen
Mit Unterstützung für große Ganzzahlen: 431 (notwendige) Zeichen
Hinweis : Entfernen Sie nicht
#include <stdlib.h>
ohne Prototyping von malloc / realloc, da dies auf 64-Bit-Plattformen nicht sicher ist (64-Bit-void * wird in 32-Bit-int konvertiert).Dieser wurde noch nicht intensiv getestet. Es könnte auch eine Verkürzung gebrauchen.
Vorherige Versionen:
(12 Zeichen entfernt, da niemand dem Ausgabeformat folgt ...: |)
quelle
Eine andere Assembler-Version. Dieser ist nicht auf 32-Bit-Zahlen beschränkt, sondern kann Zahlen bis zu 10 65534 verarbeiten, obwohl das von MS-DOS verwendete ".com" -Format auf 80-stellige Zahlen beschränkt ist. Geschrieben für A86 Assembler und erfordert eine Win-XP DOS-Box zum Ausführen. Zusammengesetzt zu 180 Bytes:
quelle
dc - 24 Zeichen
2528dc
ist ein gutes Werkzeug für diese Sequenz:Auch 24 Zeichen nach der Formel aus dem Golfscript- Eintrag:
57 Zeichen , um die Spezifikationen zu erfüllen:
quelle
Schema: 72
Dies verwendet eine Rekursion, aber die Aufrufe sind endrekursiv, sodass ich denke, dass sie für die Iteration optimiert werden. In einigen schnellen Tests konnte ich keine Nummer finden, für die der Stapel ohnehin überläuft. Nur zum Beispiel:
(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 53987098123749825298309837432974329852309857807
... läuft gut. [das ist alles eine Zahl - ich habe sie gerade gebrochen, damit sie auf den Bildschirm passt.]
quelle
Mathematica, 45
50Zeichenquelle
OddQ[#]
mitOddQ@#
1 Zeichen zu speichern.c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]
Ruby, 50 Zeichen, kein Stapelüberlauf
Grundsätzlich ein direkter Rip von Makapufs Python-Lösung :
Ruby, 45 Zeichen, wird überlaufen
Grundsätzlich ein direkter Rip des in der Frage angegebenen Codes:
quelle
n.odd??
nicht definiert. Dies ist auch anfällig für Stapelüberläufe mit großen Zahlen.p n=[n/2,n*3+1][n%2]
quelle
Python 45 Char
Rasierte einen Saibling von Makapufs Antwort.
quelle
TI-BASIC
Nicht der kürzeste, aber ein neuartiger Ansatz. Sicherlich bei großen Sequenzen erheblich langsamer, aber es sollte nicht überlaufen.
quelle
Haskell: 50
quelle
c 1=[1];c n=n:(c$[n
div2,3*n+1]!!(n
mod2))
, 44 ZeichenNicht die kürzeste, aber eine elegante Clojure-Lösung
quelle
C #: 216 Zeichen
in langer Form:
Neue Version, akzeptiert eine Nummer als Eingabe über die Befehlszeile, keine Eingabevalidierung.
173154 Zeichen.in langer Form:
Ich kann ein paar Zeichen rasieren, indem ich die Idee in dieser Antwort abreiße , eine for-Schleife anstelle einer Weile zu verwenden. 150 Zeichen.
quelle
Ruby, 43 Zeichen
Bignum unterstützt, mit Stapelüberlaufanfälligkeit:
... und 50 Zeichen, Bignum unterstützt, ohne Stapelüberlauf:
Ein großes Lob an Jordanien. Ich wusste nicht über 'p' als Ersatz für Puts.
quelle
nroff 1
Laufen Sie mit
nroff -U hail.g
1. Groff-Version
quelle
groff -U hail.g
und du bekommst PostScript! :-)Scala + Scalaz
Und in Aktion:
Scala 2.8
Dies schließt auch die nachfolgende 1 ein.
Mit folgendem impliziten
dies kann auf verkürzt werden
Bearbeiten - 58 Zeichen (einschließlich Eingabe und Ausgabe, jedoch ohne Anfangsnummer)
Könnte um 2 reduziert werden, wenn Sie keine Zeilenumbrüche benötigen ...
quelle
F #, 90 Zeichen
Wenn Sie F # nicht interaktiv verwenden, um das Ergebnis anzuzeigen, werden 102 Zeichen angezeigt:
quelle
Common Lisp, 141 Zeichen:
Testlauf:
quelle
Das Programm von Jerry Coffin hat eine Ganzzahl über dem Fluss. Versuchen Sie Folgendes:
getestet mit
Die Zahl von weniger als 100 Millionen mit der längsten Gesamtstoppzeit beträgt 63.728.127 mit 949 Schritten.
Die Zahl von weniger als 1 Milliarde mit der längsten Gesamtstoppzeit beträgt 670.617.279 mit 986 Schritten.
quelle
unsigned long long
.Ruby, 43, erfüllt möglicherweise die E / A-Anforderungen
Laufen Sie mit
ruby -n hail
quelle
C #: 659 Zeichen mit BigInteger-Unterstützung
Ungolfed
quelle