Eine Drehung einer Saite erfolgt durch Aufteilen einer Saite in zwei Teile und Umkehren ihrer Reihenfolge, beispielsweise "world! Hello,"eine Drehung von "Hello, world!". Es ist möglich, Programme zu erstellen, die gedreht werden können, um ein anderes, aber immer noch gültiges Programm zu bilden. Betrachten Sie dieses Beispiel in Python:
print ")import sys; sys.stdout.write("
Es kann gedreht werden, um zu formen
import sys; sys.stdout.write("print ")
Welches ist selbst ein gültiges Python-Programm.
Ihre Herausforderung besteht darin, ein Programm zu schreiben, das eine Drehung von sich selbst ausgibt, die beim Ausführen das ursprüngliche Programm ausgibt. Bonuspunkte für jeden Eintrag mit einer Zykluslänge von mehr als zwei!
Dies ist Code Golf, die genaue Punktzahl ist: (Länge des Codes) / (Zykluslänge - 1).
EDIT: Wir haben einen Gewinner (es sei denn, jemand anderes kann eine Punktzahl von 4 schlagen)! Es würde mich immer noch sehr interessieren, ob es sich um Konkurrenten handelt oder nicht.
quelle
Antworten:
APL (158 Zeichen, Punktzahl = 4)
Ich verwende hier Dyalog APL. Die Anzahl der Zyklen kann um eins erhöht werden, indem
0am Ende des Ausdrucks und am Ende der Zeichenfolge (vor''') (0 gefolgt von einem Leerzeichen) hinzugefügt wird . Die Zykluslänge ist(# 0's) + 1und die Länge des Ausdrucks ist150 + 4*(cycle length)). Angenommen, wir fügen für immer Nullen hinzu, dann ist die PunktzahlLimit[(150 + 4*n)/(n - 1), n -> Infinity] = 4, wondie Zykluslänge ist.Hier ist ein Beispiel mit Zykluslänge = 6:
192 Zeichen, Punktzahl = 2
Abhängig von der Implementierung kann ein Fehler auftreten, wenn die der Zeichenfolge vorangestellte Ganzzahl zu groß ist. Theoretisch können wir jedoch einen Zyklus hinzufügen, indem wir zwei Zeichen hinzufügen - a
1am Ende der Zeichenfolge (vor''') und a1am Ende der gesamten Zeile.200 Zeichen, Punktzahl = 1
Meine APL-Implementierung verfügt standardmäßig nicht über Ganzzahlen mit unbegrenzter Genauigkeit. Daher wird die Ganzzahl in einen Gleitkommawert konvertiert, wenn sie zu groß wird, was zu einer falschen Ausgabe führt. Das ist also das heikelste, aber theoretisch (entweder von Hand oder mit einem anderen APL-Interpreter) sollte es eine Punktzahl von 1 haben. Fügen Sie einfach
1am Ende des Ausdrucks ein hinzu, und Sie erhalten einen weiteren Zyklus.Übersicht (mit kürzerem Quine)
Ich werde einen Überblick über die erste Version geben, da ich denke, dass es wahrscheinlich am einfachsten ist, sie zu verstehen. Bevor wir diese Version jedoch in Angriff nehmen, betrachten wir eine einfache Quine in APL :
Ich habe festgestellt, dass eine der besten Möglichkeiten zum Verständnis einiger APL-Ausdrücke darin besteht, die Ausgabe in der Kaskade der Operatoren / Funktionen zu betrachten. Alle Operatoren und Funktionen in APL sind rechtsassoziativ und haben die gleiche Priorität. Hier also von rechts nach links:
'''1⌽22⍴11⍴''': Dies ist nur ein String-Literal (eine Liste von Zeichen).''ist die APL-Methode, um einfache Anführungszeichen zu umgehen. Ausgang:'1⌽22⍴11⍴'.11⍴'''1⌽22⍴11⍴''': Hier formen wir⍴den String um ( ), damit er lang ist11. Da die Länge der Zeichenfolge unter 11 liegt, wird sie wiederholt (dh sie5⍴'abc'würde nachgeben'abcab'). Ausgang:'1⌽22⍴11⍴''. Also haben wir jetzt zwei Anführungszeichen am Ende - wir kommen irgendwohin!22⍴11⍴'''1⌽22⍴11⍴''': In ähnlicher Weise gestalten wir jetzt unsere vorherige Ausgabe so um, dass sie lang ist22. Ausgang:'1⌽22⍴11⍴'''1⌽22⍴11⍴''. Wir sind fast da - wir müssen nur das erste einfache Anführungszeichen ans Ende setzen.1⌽22⍴11⍴'''1⌽22⍴11⍴''': Hier drehen wir (⌽) die Liste der Zeichen um1. Dadurch wird das erste Zeichen der Zeichenfolge an das Ende verschoben. Als weiteres Beispiel wird2⌽'abcdef'zurückgegeben'cdefab'. Ausgang:1⌽22⍴11⍴'''1⌽22⍴11⍴'''.Das rotierende Quin
Diese kurze Quine ist die Hauptgrundlage für unsere rotierende Quine. Schauen wir uns in diesem Sinne unsere Quine an:
{ ... }definiert eine unbenannte Funktion, in der wir die Arbeit erledigen werden. Beachten Sie, dass Funktionen in APL ein rechtes Argument (bezeichnet mit⍵) und ein optionales linkes Argument (bezeichnet mit⍺(think infix)) enthalten. Wir möchten mit dieser Funktion sowohl unseren Quine-String als auch etwas füttern, das uns dabei hilft, eine beliebige Anzahl von Zyklen zu erstellen. Um es uns (und allen, die Zyklen hinzufügen möchten) einfacher zu machen, machen wir den Quine-String zum linken Argument. Das richtige Argument ist also, wo wir unsere Liste der Zyklen ablegen. Zwei oder mehr durch ein Leerzeichen getrennte Elemente erstellen eine Liste. In diesem Beispiel haben wir also eine Liste mit zwei Elementen, bestehend aus a1und a0.Wir können sehen, dass die Funktion der Quine von früher ähnelt. Wir haben die gleiche
...⌽...⍴...⍴...Form von vor. Das ist gut so - wir verstehen zumindest so viel! Lassen Sie sich tiefer in die Ellipsen, beginnend mit allem , was nach dem letzten⍴:⊃,/(~^/¨⍺=0)/⍺.⍺=0In diesem Fall wird eine Liste mit der gleichen Form wie zurückgegeben⍺, wobei jedes Element in⍺durch ein,1wenn es gleich ist0, und ein, wenn nicht, ersetzt wird0. Dies wird rekursiv durchgeführt. Wenn wir also eine Liste mit einer Liste mit Zeichen haben, werden die einzelnen Zeichen gegen 0 getestet und Sie erhalten eine Liste mit einer Liste mit Binärwerten zurück.⍺sich also nur um unsere Zeichenfolge handelt, erhalten wir eine Liste mit Nullen zurück. Andernfalls sind unserem linken Argument einige Nullen vorangestellt (z. B.0 0 0 'quinestring'), sodass es sich um eine Liste handelt, die aus Nullen und einer anderen Liste, unserer Zeichenfolge, besteht. Dann sieht unsere Ausgabe so aus1 1 1 <sub-list of zeros>.^/¨⍺=0: Wir wenden die abgeleitete Funktion^/, die (/) unter Verwendung der logischen AND (^) - Funktion reduziert , auf jedes (¨) - Element von an⍺=0. Dies soll die Unterliste der Nullen abflachen, so dass wir den Quine-String als einen Binärwert betrachten können. In Anbetracht des vorherigen Beispiels wäre die Ausgabe1 1 1 0.~: Wir binären NICHT jeden der Werte von vor (z0 0 0 1. B. Rückkehr ).(~^/¨⍺=0)/⍺: Für jedes Element in⍺replizieren wir/es so oft, wie das entsprechende Element im linken Argument es angibt. Dies eliminiert alle Nullen und lässt uns nur mit unserer Quine-Saite zurück.⊃,/Es sind einige Formalitäten erforderlich, um sicherzustellen, dass wir eine reduzierte Liste von Zeichen erhalten, indem wir das Ergebnis mit der Verkettungsfunktion (,) reduzieren . Wenn die Eingabe bereits eine abgeflachte Liste ist (dh das linke Argument für unsere Hauptfunktion ist nur die Zeichenfolge), erhalten wir eine Liste mit 1 Elementen, die diese Liste enthält. In dem anderen Fall, wenn wir eine Liste haben, die aus einer Unterliste für den String besteht, erhalten wir dasselbe zurück (eine Liste mit einer Unterliste). Wir entpacken dann this (⊃) und geben uns nur das erste Element der Liste (dh die Unterliste der Zeichen). Dies mag unnötig erscheinen, aber sonst würden wir versuchen, eine Liste mit 1 Elementen umzugestalten!Als nächstes betrachten wir die Länge, die für die erste Umformung in Klammern angegeben wurde:
⍺,⍵: Wir verketten das richtige Argument mit dem ersten Argument⊃,/⍺,⍵: Wie zuvor - Reduzieren Sie die Liste.+/0=⊃,/⍺,⍵: Addieren Sie die Anzahl der Nullen in der Liste, indem Sie (/) mit der+Funktion addition ( ) reduzieren .2×+/0=⊃,/⍺,⍵: Multipliziere diese Zahl mit zwei.z←2×+/0=⊃,/⍺,⍵: Zuweisen (←) das Ergebnis in einer Variablenz. Um es noch einmal zusammenzufassen:zsich jetzt die doppelte Anzahl von Nullen sowohl im linken als auch im rechten Argument gefunden wird.77+z←2×+/0=⊃,/⍺,⍵: Wir fügen dann hinzu77für die Zeichen in der Quine-Zeichenfolge hinzu und ignorieren alles nach dem Leerzeichen1. Wie im ersten Quine-Beispiel addieren wir 1 zur Länge des Strings, um ein weiteres einfaches Anführungszeichen zu erhalten.'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''Das Argument für die folgende Umformung ist einfach und spiegelt die kurze Quine wider (2-fache Länge für die erste Umformung). Unsere Ausgabe ist jetzt:
Nun zum letzten Schritt, in dem wir berechnen, um wie viel die Ausgabezeichenfolge gedreht werden soll:
0(und ein anderes) Leerzeichen an den Anfang bewegt, möchten wir es um weitere 3 Zeichen zurückdrehen.+/+/¨⍺=0: Addiere die Anzahl der Nullen im linken Argument. Die erste (von rechts)+/¨summiert die Anzahl der Elemente (dh eine Unterliste oder nur eine Ganzzahl) und die zweite+/ergibt die Summe dieser resultierenden Liste.5+2×+/+/¨⍺=0: Multiplizieren Sie mit zwei (um auch die Leerzeichen zu drehen) und addieren Sie 5 (das Ergebnis, das wir zuvor gefunden haben).-um den Fall zu behandeln, wenn wir das Ende unseres Zyklus erreicht haben:(3+z)×^/⍵: UND alle Elemente im richtigen Argument zusammen, um zu sehen, ob wir unser Ende erreicht haben (1), und multiplizieren Sie das mit3+z.Und wir sind fertig!
quelle
⍴Operators (?). Ich denke, ich muss das Ganze noch ein paar Mal durchlesen, bevor ich es vollständig verdaue!GolfScript, 10046/9999 ≈ 1.0047 (asymptotische Punktzahl 1)
OK, ich werde versuchen, den APL-Eintrag von DC so zu übertreffen :
Der obige Code ist nicht der eigentliche Quine - ich war der Meinung, dass das Posten eines 10-KB-Einzeilers keine sehr gute Idee wäre. Wenn Sie den obigen Code einmal ausführen, wird das eigentliche GolfScript-Programm mit 10046 Zeichen generiert, das, wenn es wie in der Frage angegeben iteriert wird, 9999 Umdrehungen von sich selbst und schließlich von sich selbst generiert.
Die Länge des Zyklus (und des Programms) kann durch Ändern der Konstante angepasst werden
9999. Der Kürze halber werde ich zeigen, wie die iterierte Ausgabe aussieht, wenn die Konstante auf Folgendes reduziert wird9:Wenn die Konstante
9999erhöht wird, tendiert das Verhältnis der Programmlänge und der Zykluslänge (minus eins) zu eins. Ich bin mir ziemlich sicher, dass diese Lösung nicht zu übertreffen ist, zumindest nicht asymptotisch. ;-)Wie funktioniert es?
GolfScript ist eine ziemlich einfache Sprache, in der Quines geschrieben werden können, da im Grunde genommen jede beliebige Zahl als Quine fungiert: Beispielsweise gibt das GolfScript-Programm
12345- Sie haben es erraten - aus12345. Wenn Sie mehrere Quines verketten, wird in der Regel ein Quine erstellt. So könnte ich eine einfache Zahl wie11111...111als sich wiederholenden Teil meiner zyklischen Quine verwenden.Um die Quine tatsächlich zum Radfahren zu bringen, müssen wir jedoch eine nicht triviale "Nutzlast" tragen und ausführen. Die einfachste GolfScript-Quine, die ich mir vorstellen kann, ist die folgende:
Mein Plan war es also, einem Quine eine sich wiederholende numerische Konstante voranzustellen und eine Nutzlast zu verwenden, die eine Ziffer von der Zahl abschneidet und sie an das Ende des Programms verschiebt. Wenn das Programm feststellt, dass sich keine numerische Konstante davor befindet (in diesem Fall ist der Wert auf dem Stapel eine leere Zeichenfolge, sofern keine Eingabe erfolgt), wird stattdessen eine numerische Konstante fester Länge vorangestellt selbst.
Es gibt jedoch eine zusätzliche Falte - beim "Herumlaufen" muss die Nutzlast auch die Ausgabe der Zahl nach sich selbst unterdrücken . Wenn ein GolfScript-Programm beendet wird, werden normalerweise alle Werte auf dem Stapel automatisch gedruckt, was hier ein Problem darstellen würde.
Es hat sich jedoch herausgestellt, dass es eine (AFAIK-) undokumentierte Möglichkeit gibt, dies zu vermeiden: Der Interpreter ruft tatsächlich die vordefinierte Funktion
putsauf, um den Druckvorgang durchzuführen. Wenn Sie diese Funktion also als No-Op definieren, wird die automatische Ausgabe unterdrückt. Dies bedeutet natürlich auch, dass wir uns zuerst anrufenputsmüssen, um den Teil des Stapels zu drucken, den wir drucken möchten .Der endgültige Code sieht ziemlich chaotisch aus (auch für GolfScript), aber zumindest funktioniert es. Ich vermute, es gibt einige clevere Möglichkeiten, die ich noch nicht in Betracht gezogen habe, um ein paar Zeichen von der Nutzlast zu entfernen, aber bei dieser Version habe ich mich hauptsächlich auf die asymptotische Bewertung konzentriert.
quelle
puts{}:puts, obwohl ich ein Argument dafür sehen konnte,{print}:putsdass ein Zeilenumbruch in der Ausgabe bedeuten würde, dass es nicht ausschließlich Radfahren ist.]puts{}:putswird für den Wrap-Around von{STUFF}.~111111111bis benötigt111111111{STUFF}.~, sonst1wächst die Anzahl der s am Ende des Programms immer weiter. (Das{}scheint jedoch unnötig zu sein; anscheinend erlaubt der GolfScript-Interpreter die Zuweisung von einem leeren Stapel.)HTML, minus unendlich (fast)
-2
AA-10
AAAAAAAAAAUnd so weiter ... Wenn jemand sagt, dass es betrügt, können wir darüber streiten, aber ich habe ein fragliches Loch gefunden :)
Ich vermute, jeder versteht, dass Code keine Schleifen hat, die längste Schleife ist
0und wenn man die Programmlänge berücksichtigt, istnscoren / (0 - 1)oder-n, ich kann ein Programm schreiben, das einenpositive ganze Zahl hat, aber es ist nutzlos, weil jeder es versteht.quelle