Definieren Sie die Funktion f (n) für eine positive ganze Zahl n wie folgt:
- n / 2 , wenn n gerade ist
- 3 * n + 1 , wenn n ungerade ist
Wenn Sie diese Funktion wiederholt auf n größer als 0 anwenden , scheint das Ergebnis immer auf 1 zu konvergieren (obwohl dies noch niemand beweisen konnte). Diese Eigenschaft wird als Collatz-Vermutung bezeichnet .
Definieren Sie die Stoppzeit einer Ganzzahl als die Häufigkeit, mit der Sie die Collatz-Funktion f durchlaufen müssen, bevor sie 1 erreicht. Hier sind die Stoppzeiten der ersten 15 Ganzzahlen:
1 0
2 1
3 7
4 2
5 5
6 8
7 16
8 3
9 19
10 6
11 14
12 9
13 9
14 17
15 17
Nennen wir einen beliebigen Satz von Nummern mit denselben Haltezeiten wie die Cousins von Collatz . Zum Beispiel sind 5 und 32 Cousins von Collatz mit einer Haltezeit von 5.
Ihre Aufgabe: Schreiben Sie ein Programm oder eine Funktion, die eine nicht negative Ganzzahl verwendet und die Menge der Collatz-Cousins generiert, deren Stoppzeit dieser Ganzzahl entspricht.
Eingang
Eine nichtnegative Ganzzahl S, angegeben über STDIN, ARGV oder Funktionsargument.
Ausgabe
Eine Liste aller Zahlen , deren Stoppzeit ist S, sortiert in aufsteigender Reihenfolge. Die Liste kann von Ihrem Programm ausgegeben oder von Ihrer Funktion zurückgegeben oder ausgegeben werden. Das Ausgabeformat ist flexibel: Durch Leerzeichen oder Zeilenumbrüche getrennt oder jedes Standard-Listenformat Ihrer Sprache ist in Ordnung, solange die Zahlen leicht voneinander zu unterscheiden sind.
Bedarf
Ihre Einreichung muss für S ≤ 30 korrekte Ergebnisse liefern. Sie sollte in Sekunden oder Minuten und nicht in Stunden oder Tagen abgeschlossen sein.
Beispiele
0 -> 1
1 -> 2
5 -> 5, 32
9 -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768
Hier ist eine Zusammenfassung der Ausgabe für S = 30 .
Das ist Code-Golf : Das kürzeste Programm in Bytes gewinnt. Viel Glück!
Antworten:
Pyth,
262421 BytesDieser Code läuft sofort für
S=30
. Probieren Sie es aus: DemonstrationVielen Dank an @isaacg für das Speichern von 5 Bytes.
Erläuterung
Mein Code beginnt mit
1
und macht die Collatz-Funktion rückgängig. Es ordnet alle Nummernd
desS-1
Schritts2*d
und zu(d-1)/3
. Der letzte ist jedoch nicht immer gültig.quelle
-F
.- ... 1
die Summe innerhalb des Reduzierers umrunden, muss der Reduzierer.u
weder ein noch das-F
Äußere sein. Speichert 2 Zeichen.q4%d6
entspricht!%hhd6
, aber 1 Zeichen kürzer.Mathematica,
989289 BytesDiese Lösung löst
S = 30
sofort:Dies ist eine unbenannte Funktion, die
S
als einzigen Parameter eine Liste der Cousins von Collatz zurückgibt.Der Algorithmus ist eine einfache Breitensuche. Die Collatz-Cousins für eine bestimmte
S
Zahl sind alle Ganzzahlen, die von den Collatz-Cousins für eineS-1
Via2*n
oder ungerade Zahlen, die über eine Via erreicht werden können, erreicht werden können(n-1)/3
. Wir müssen auch sicherstellen, dass wir nur die Ganzzahlen produzieren, die zum ersten Mal nachS
Schritten erreicht wurden, also behalten wir alle vorherigen Cousins im Augep
und entfernen diese aus dem Ergebnis. Da wir das sowieso tun, können wir ein paar Bytes sparen, indem wir die Schritte aller vorherigen Cousins (nicht nur die vonS-1
) berechnen , um ein paar Bytes zu sparen (das macht es etwas langsamer, aber nicht merklich für die erforderlichenS
).Hier ist eine etwas besser lesbare Version:
quelle
Python 2,
8683757371 BytesRufen Sie gerne an
f(30)
.n = 30
ist ziemlich augenblicklich.(Vielen Dank an @DLosc für die Idee, dass
k
es sich um eine Zahl statt um eine Liste von Cousins handelt, und ein paar Bytes. Vielen Dank an @isaacg für das Löschen~-
.)Diese Variante ist viel kürzer, dauert aber aufgrund der exponentiellen Verzweigung leider zu lange:
quelle
f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]
. Es ist weniger effizient mit den Funktionsaufrufen, tut es abern = 30
in weniger als einer Sekunde.f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
~-
ist unnötig, weil Sie die Ganzzahldivision verwenden.CJam,
2926 BytesDank geht an @isaacg für seine Idee, Einsen nach jeder Iteration zu entfernen, wodurch mir zwei Bytes direkt und ein weiteres indirekt erspart wurden.
Probieren Sie es online im CJam-Interpreter aus (sollte in weniger als einer Sekunde beendet sein).
Wie es funktioniert
quelle
CJam, 35 Bytes
Erklärung folgt in Kürze. Dies ist eine viel schnellere Version als der "ziemlich direkte" Ansatz (siehe im Bearbeitungsverlauf).
Probieren Sie es hier online aus,
N = 30
was in Sekundenschnelle in der Online-Version und sofort im Java Compiler ausgeführt wirdquelle
It should finish in seconds or minutes, not hours or days.
S=15
funktioniert nicht.Java 8, 123
Bei
x
30 dauert das Programm 15 Minuten und 29 Sekunden.Erweitert
quelle
javac 1.7.0_79
Ubuntu gab es viele Syntaxfehler.i > 1 && ++n <= x
(Sie können auch ablegenn++
) scheint für nur 5 weitere Zeichen noch schneller zu sein ... für mich ungefähr 3 Minuten für S = 30. Das wird sicher unter einer Minute rasiert, wenn ich.parallel()
auch, aber da dies Code-Golf ist ...Python 2, 118 Bytes
Nun, ich dachte mir, dass ich nicht die beste Python-Punktzahl erreichen würde, wenn ich die Lösung von @ Sp3000 gesehen hätte. Aber es sah nach einem lustigen kleinen Problem aus, deshalb wollte ich trotzdem eine unabhängige Lösung ausprobieren:
Das Gleiche vor dem Entfernen von Leerzeichen:
Dies ist eine sehr direkte Implementierung einer breiten ersten Suche. In jedem Schritt haben wir die Menge mit der Stoppzeit
k
und leiten die Menge mit der Stoppzeit ab,k + 1
indem wir die möglichen Vorgänger für jeden Wertt
in der Menge aus Schritt hinzufügenk
:2 * t
ist immer ein möglicher Vorgänger.t
geschrieben werden kann als3 * u + 1
, wou
eine ungerade Zahl ist1
,u
ist das auch ein Vorgänger.N = 30
Auf meinem MacBook Pro dauert die Ausführung etwa 0,02 Sekunden .quelle
s.add(x)
ist das beim Golfen unnötig, da man es in der Regels|={x}
stattdessen machen kann. Verwenden Sie~-x
statt(x+1)
spart auch in Klammern. Aber sonst gute Arbeit :)s.add()
da sie zu einer Aufgabe wird und nicht mehr Teil des Ausdrucks ist. Es funktioniert für den ersten. Diefor
auf Zählern basierenden Schleifen sind immer auch ziemlich ausführlich. Ich dachte, ich könnte es mit einerwhile
Schlaufe verkürzen , aber es stellte sich heraus, dass es genauso lang war.for
Schleife, da Sie die Eingabe nicht auf andere Weise verwenden, können Sie dies wahrscheinlich auch tunexec"..."*input()
:)PHP 5.4+, 178 Bytes
Die Funktion
Test & Ausgabe
S (30) läuft in 0,24 Sekunden * und gibt 732 Elemente zurück. Ein paar sind
* Um Bytes zu sparen, musste ich
ksort
undarray_keys
bei jedem Schritt hinzufügen . Die einzige andere Wahl , die ich war , hatte eine kleine Wrapper - Funktion, dass Anrufec()
und dann Anrufearray_keys
undksort
auf dem Ergebnis einmal. Da die Zeit aber noch recht knapp ist, habe ich beschlossen, den Performance-Hit für eine niedrige Byteanzahl zu halten. Ohne die richtige Sortierung und Verarbeitung beträgt die Zeit für S (30) durchschnittlich 0,07 Sekunden .Wenn jemand clevere Möglichkeiten hat, die ordnungsgemäße Verarbeitung nur einmal ohne zu viele zusätzliche Bytes zu erreichen, lassen Sie es mich bitte wissen! (Ich speichere meine Zahlen als Array-Schlüssel, daher die Verwendung von
array_keys
undksort
)quelle
C Sprache
quelle
{}
Knopf drücken, um Ihren Code zu formatieren, was ich für Sie getan habe. Aber wie Alex sagt, füge bitte den Sprachnamen (C?) Hinzu und probiere es mit Golf :) Aber willkommen!f
verhält sich nicht richtig. Mits=5
bekomme ich eine Reihe von falschen Ergebnissen.if (r == s)return true;
sollte seinreturn (r==s)
, daf
nichts Bedeutungsvolles zurückkommt, wenn(r < s)
. Außerdem glaube ich , Sie erklären sollteni
inf
solong
, da es ziemlich schnell für einige Werte überlaufen wird.return (r==s);