Die Collatz-Sequenz ausgehend von einer positiven ganzen Zahl n wird folgendermaßen definiert:
- wenn n gerade ist, dann dividiere es durch 2 (
n' = n / 2
) - Wenn n ungerade ist, multipliziere es mit 3 und addiere 1 (
n' = 3n + 1
)
Wiederholen Sie die obige Iteration, bis n 1 erreicht.
Es ist nicht bekannt (es ist ein großes ungelöstes Problem in der Zahlentheorie), ob die Sequenz schließlich die Zahl 1 erreicht, unabhängig davon, welche positive ganze Zahl anfänglich gewählt wird.
Eine Zwei-Zähler-Maschine (2CM) ist eine Maschine, die mit zwei Registern ausgestattet ist, die einen nicht negativen ganzzahligen Wert enthalten können und mit dem folgenden Befehlssatz programmiert werden können:
INCX increase the value of register X
INCY increase the value of register Y
JMP n jump to instruction n
DJZX n if register X is zero jump to instruction n,
otherwise decrement its value
DJZY n if register Y is zero jump to instruction n,
otherwise decrement its value
HALT halt (and accept)
PRINTX print the content of register X
Ein 2CM-Programm ist einfach eine Folge von Anweisungen. Beispielsweise kopiert das folgende Programm einfach den Inhalt von Register X in Register Y:
cp: DJZX end
INCY
JMP cp
end: HALT
Beachten Sie, dass ein 2CM Turing Complete ist (dh es kann jede berechenbare Funktion mit einer geeigneten Eingabecodierung berechnen, dies ist hier jedoch irrelevant). Beachten Sie auch, dass sich der Befehlssatz ein wenig von dem im Wikipedia-Artikel unterscheidet.
Die Herausforderung
Schreiben Sie das kürzeste 2CM-Programm, das die Collatz-Sequenz bis zu 1 berechnet und druckt und anhält (das Register X enthält anfänglich den Startwert n
und das Register Y enthält anfänglich 0). Beachten Sie, dass die Länge eines 2CM-Programms der Anzahl der verwendeten Anweisungen entspricht (nicht der Länge des Textes).
Wenn beispielsweise von X = 3 aus gestartet wird, muss 3 10 5 16 8 4 2 1
Folgendes gedruckt werden: und HALT.
Sie können also Ihre Lieblingssprache verwenden, um einen 2CM-Simulator / Interpreter zu erstellen. Der endgültige (kürzeste) Code, den Sie in die Antwort eingeben, muss jedoch in der 2CM-Sprache vorliegen .
quelle
Antworten:
18 Anweisungen
Ich war ein bisschen enttäuscht, dass ich spät vor Ort ankam, da die minimalistische Natur des Problems und die Sprache dort (scheinbar) nur einen allgemeinen Ansatz für eine gute Antwort liefern. Ich bekam ziemlich schnell eine Antwort mit 19 Anweisungen, aber ich hatte nicht das Gefühl, dass sie genug auf den Tisch brachte, um sie zu veröffentlichen. Aber nach langem Kopfkratzen kam meine Erfahrung mit der Hacky-Z80-Montage zum Tragen und ich fand einen Weg, eine Anweisung zu speichern, indem ich einen Codeblock für einen Zweck wiederverwendete, für den er nicht gedacht war!
quelle
SCORE: 21
Hier ist mein Versuch:
main
: drucktX
und springt zufinish
(wennX==1
).divisibility
: unterscheidet, obX%2==0
oderX%2==1
. KopiertX
auchY
und machtX==0
. Springt entweder zuisDivisible
(wennX%2==0
) oderisNotDivisible
(wennX%2==1
).isDivisible
: Schleife verwendet, wennY%2==0
. Bei jeder AbnahmeY
um 2 erhöht sie sichX
um 1. WennY==0
, springt zumain
.isNotDivisible
: verwendet wennY%2==1
. Es erhöht sichX
um 1.notDivLoop
: Schleife verwendet, wennY%2==1
. Bei jeder VerringerungY
um 1 erhöht sie sichX
um 3. WannY==0
springt zumain
.finish
: hält anMit 3 geliefert (unter Verwendung des von @orlp bereitgestellten Interpreters) ergibt sich Folgendes:
quelle
19 Anweisungen
Ich habe meinen eigenen Dolmetscher geschrieben, weil ich so Lust habe. Hier ist meine Lösung für meinen eigenen Dolmetscher:
Und so sieht es mit einer Syntax aus, die mit dem anderen Interpreter kompatibel ist:
quelle
19 Anweisungen
Sie können es mit meinem Dolmetscher ausführen .
quelle