Stellen Sie sich einen Pfad vor, der aus <und besteht >und in einem endet @, z
><>@
Ein Wanderer beginnt in der Zelle ganz links. Er wird den Pfad wie folgt durchlaufen:
- Wenn der Wanderer in einer
@Zelle ist, hat er das Ziel erreicht und ist fertig. - Befindet sich der Walker in einer
>Zelle, verschiebt sich der gesamte Pfad zyklisch einen Schritt nach rechts und nimmt den Walker mit . - Befindet sich der Walker in einer
<Zelle, verschiebt sich der gesamte Pfad zyklisch um einen Schritt nach links und nimmt den Walker mit . - Danach macht der Läufer einen einzelnen Schritt. Wenn er sich an einem Ende des Pfades befindet, bewegt er sich vom Ende weg. Andernfalls bewegt er sich weiter in die Richtung, in die er sich beim letzten Schritt bewegt hat (ohne Berücksichtigung der Drehung) und geht zunächst nach rechts.
Lassen Sie uns das obige Beispiel durcharbeiten. Die Position des Wanderers ist markiert mit ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
Der Walker besuchte dabei 6 Zellen (einschließlich der Startzelle sowie der @und zählte jede Zelle so oft, wie sie besucht wurde).
Hier ein kleines Beispiel, bei dem der Läufer durch eine Drehung über die Kanten transportiert wird:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
Diesmal besuchte der Wanderer 3 Zellen.
Wir können dies leicht in eine ganzzahlige Folge umwandeln:
- Sie erhalten eine positive ganze Zahl N , z
9. - Sie berechnen die binäre Darstellung dieser ganzen Zahl, z
1001. - Dann biegen Sie
1in>und0in<und fügen Sie ein@:><<>@. - Wir assoziieren mit N die Anzahl der vom Wanderer besuchten Zellen in der auf diese Weise konstruierten Anzahl.
Die ersten Elemente der resultierenden Sequenz sind:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Das mag recht willkürlich erscheinen, aber die resultierende Sequenz hat tatsächlich eine Menge Struktur:
Als Referenz finden Sie die ersten 2048 Nummern der Sequenz in diesem Pastebin .
Die Herausforderung
Sie haben es erraten: Sie müssen die obige Sequenz berechnen. Sie können dies auf drei Arten tun:
- Sie können eine unendliche Folge erzeugen (solange der Speicher dies zulässt), indem Sie entweder fortlaufend Werte ausgeben (durch nicht numerische Zeichen getrennt) oder indem Sie einen unendlichen Generator in Sprachen verwenden, die diese unterstützen. Wenn Sie einen unendlichen Datenstrom nach STDOUT drucken, müssen Sie die Zahlen nicht einzeln drucken, sondern müssen sicherstellen, dass jede Zahl nach einer begrenzten Zeitspanne (und in der angegebenen Reihenfolge) gedruckt wird. Wenn Sie diese Option verwenden, sollten Sie keine Eingaben vornehmen.
- Sie können eine ganze Zahl N als Eingabe nehmen und den N- ten Term der Sequenz erzeugen .
- Sie können eine ganze Zahl nehmen N als Eingabe und produziert alles auf bis die N - te Glied der Folge, entweder als Liste oder String ein eindeutiges Trennzeichen verwenden.
Da ich Sprachen, die nicht einfach zwischen Basen konvertieren können, nicht bestrafen möchte, können Sie anstelle der Ganzzahl N die Binärdarstellung von N verwenden 0und dabei 1wie gewohnt s und s (als Liste oder Zeichenfolge) mit den meisten verwenden -signifikantes Bit zuerst.
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.
Es gelten die Standardregeln für Code-Golf .
Hintergrund
Dies berechnet tatsächlich die Anzahl der "Ticks", die ein einfacher Interpreter meiner esoterischen Programmiersprache Labyrinth benötigen würde, um den "Pfad" als Quellcode zu interpretieren. In diesem Fall ist der "Walker" einfach der Befehlszeiger (der eine Position und eine Richtung hat), der @Befehl beendet das Programm <und >sind Quellcode-Änderungsbefehle.
Antworten:
Gelee , 10 Bytes
Diese Funktion akzeptiert eine einzelne Ganzzahl in Form der Liste ihrer Binärziffern als Eingabe.
Der Algorithmus entspricht dem von @ Agawa001 .
Probieren Sie es online! oder generieren Sie die ersten 2048 Zahlen .
Hintergrund
Zählen Sie die Positionen unter dem Pfad von 0 bis L auf und geben Sie insgesamt L + 1 Positionen an. L entspricht der Anzahl der Binärziffern der Zahl N , die den Pfad codiert. Mit dieser Notation, beginnen die Wanderer an Position 0 , um das Ziel in der Position L .
Mit jedem Schritt des Läufers kommt er dem Ziel einen Schritt näher (in die Richtung, in die er gerade geht). Außerdem erhöht oder verringert er mit jedem Schaltschritt, abhängig davon, ob er mit oder gegen die Schaltrichtung geht, seine Position um 2 Modulo L + 1 oder bleibt in der aktuellen Position.
Um die Richtung zu ändern, muss er auf Position L - 1 (mit Blick auf L ) oder Position 1 (mit Blick auf 0 ) landen und wird dann in seine Richtung verschoben. Der nächste Schritt bringt ihn in die entgegengesetzte Richtung zurück.
Wenn L gerade ist, ist L - 1 ungerade, so dass er nicht direkt von seiner Ausgangsposition zu L - 1 vorrücken kann . Der einzige Weg, um es zu erreichen, besteht darin, durch L zu gehen , auf 0 gebracht zu werden und den nächsten Schritt zu machen, um auf 1 zu landen , und dann nach rechts vorzurücken. Dies erfordert das Vorrücken von 2L- Positionen, was in nicht weniger als L- Schritten erfolgen kann.
Nachdem er L- Schritte gemacht hat, ohne die Richtung zu ändern, hat er das Ziel erreicht. Wenn Sie eine für die Startzelle hinzufügen, erhalten Sie in diesem Fall insgesamt L + 1 besuchte Zellen.
Wenn L ungerade ist, ist L - 1 gerade, so dass er diese Position durch zweimaliges Verschieben (L - 1) nach rechts erreichen kann. Wenn die Position L - 1 zu diesem Zeitpunkt unter einer 1 liegt , wird er in die Position L versetzt , dreht sich um und tritt auf die Position L - 1 (nach links zeigend).
Dies kann passieren oder auch nicht, bevor er sein Ziel erreicht hat. Daher sind zwei Fälle zu analysieren:
Wenn in der binären Erweiterung von N weniger als (L + 1) / 2 Vorkommen von 1 vorkommen , reichen L- Schritte nicht aus, um die Richtung zu ändern. Da diese L- Schritte den Wanderer zu seinem Ziel führen und eine für die Startzelle hinzufügen, erhalten wir in diesem Fall insgesamt L + 1 besuchte Zellen.
Wenn mindestens (L + 1) / 2 Vorkommen von 1 in der binären Expansion von N vorhanden sind , erfordert das Vorrücken zum ((L + 1) / 2) -ten Vorkommen I Schritte, wobei I die Anfangsposition dieses Vorkommens ist von 1 .
So nach der Einnahme I Schritte wird die Gehhilfe in Position L - 1 , mit Blick nach links. Um die Richtung erneut zu ändern, müsste er nach links auf Position 1 gehen . Da jedoch wie im geraden Fall (L - 1) - 1 ungerade ist, ist es erforderlich, durch 0 zu gehen und nicht weniger als L Schritte zu machen.
Da die anfängliche Entfernung zum Ziel in der linken Richtung 1 beträgt , befindet sich der Wanderer nach dem Ausführen von I- Schritten in einer Entfernung von I + 1 vom Ziel, nachdem er die Richtung geändert hat. Da I <L ist, ist I + 1 ≤ L , und die nächsten I + 1- Schritte bringen ihn zum Ziel.
Dies ergibt insgesamt I + I + 1 = 2I + 1 ausgeführte Schritte. Wenn Sie eine für die Startzelle hinzufügen , erhalten Sie in diesem Fall insgesamt 2I + 1 + 1 = 2 (I + 1) besuchte Zellen.
Wie es funktioniert
quelle
Matlab (Punktzahl = 230, n = inf)
infSie ein, wenn Sie auf unendlich bleiben möchten).h=1000000000000000000000000000000000000000000000000000;w(h,h+1), um dies sicherzustellen.Der Algorithmus folgt einem mathematischen Ansatz, den ich später erläutern werde, und bestätigt Martins Referenzliste basierend auf diesem Programm:
Da der Algorithmus 2048 erste Testfälle überprüft, gehe ich blindlings davon aus, dass dies für jeden Testfall der Fall ist. Daher funktioniert mein Algorithmus in Bezug auf einige Eigenschaften, die ich in diesem Prozess entdeckt habe, ohne den Schmerz des Verschiebens und Bewegens des Zeigers:
1- Wenn die doppelte Anzahl von Einsen bei der binären Übersetzung die Länge der Sequenz nicht überschreitet
L, ist die AusgabeL+12- Wenn die Sequenzlänge gerade ist und die vorherige Bedingung nicht festgelegt ist, ist die Ausgabe gleich
L+13 - Andernfalls ist die Ausgabe doppelt so hoch wie der
L/2Index 1.quelle
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, was nur ein einzelnes Element der Sequenz ergibt.Python,
122119113110108107103 BytesÜbernimmt die Eingabe als Liste von Binärziffern. Hilfsfunktion zum Testen:
Wir danken Lynn für die Ersparnis von 7 Bytes.
quelle
p-d-1in[-2,w]ein Byte gespart.d*=2*(1!=d-p>~w)-1ändern, werden vier weitere gespeichert! ° v °Python 2, 99 Bytes
Python-Portierung von Agawa001s brillanter Antwort.
Lesbare Version:
quelle
MATL,
31, 25 BytesDies ist nur eine MATL-Version des Agawa001-Algorithmus, außer dass er eine Ganzzahleingabe N akzeptiert und den N-ten Term in der Sequenz zurückgibt. Es war schwierig, mit allen Elementen im Stapel Schritt zu halten! Ich musste auf eine Zwischenablage zurückgreifen, um nicht verrückt zu werden. Sie können es online ausprobieren!
Kann zu einer Schleife gemacht werden, indem die ersten N Terme
:"@vor und]Dnach dem Code hinzugefügt werden .Danke an Luis Mendo für das Speichern von 6 ganzen Bytes!
quelle
Julia 0.4, 4̷4̷ 42 Bytes
Diese Funktion akzeptiert eine einzelne Ganzzahl in Form der Liste ihrer Binärziffern als Eingabe.
Der Algorithmus entspricht dem von @ Agawa001 und meiner Gelee-Antwort .
Probieren Sie es online!
Wie es funktioniert
find(x)Gibt die 1-basierten Indizes aller Nicht-Null-Elemente von x zurück . Wir versuchen, über den Index k / 2 auf das resultierende Array zuzugreifen und bei Erfolg k mit dem doppelten ausgewählten Index zu überschreiben .Dies schlägt nur dann fehl, wenn eine der folgenden Bedingungen erfüllt ist:
k / 2 ist ein nicht integraler Schwimmer, also und InexactError ausgelöst .
Das Index-Array hat weniger als k / 2 Elemente, also a BoundsError ausgelöst .
In beiden Fällen schlägt das Überschreiben von k fehl, sodass der ursprüngliche Wert zurückgegeben wird.
quelle
JavaScript (ES6), 65 Byte
Akzeptiert eine Binärzeichenfolge. Verwendet den Bounce-Check aus den verschiedenen anderen Antworten.
quelle
Python 2, 74 Bytes
Diese Funktion akzeptiert eine einzelne Ganzzahl in Form der Liste ihrer Binärziffern als Eingabe.
Der Algorithmus entspricht dem von @ Agawa001 und meiner Gelee-Antwort .
Teste es auf Ideone .
Wie es funktioniert
nextversucht, die erste Ganzzahl 2i zu finden, für diek==2*sum(x[:i])true zurückgegeben wird. Da i Elementex[:i]enthält , ergibt dies den 1-basierten Index der (k / 2) -ten 1 .nextschlägt fehl, wenn k / 2 nicht ganzzahlig ist oder wenn x weniger als k / 2 Einsen enthält. In diesem Fall wird der Standardwert k zurückgegeben.quelle
> <> 63 Bytes
Von dem Moment an, als ich das Beispielmuster in dieser Herausforderung sah, wusste ich, welche Sprache ich verwenden sollte :)
Verwenden von N , um den N- ten Term zu erhalten.
Es wird angenommen, dass die Eingabe im Stapel binär ist. Anstatt den Läufer zu bewegen, beruht diese Lösung hauptsächlich darauf, das Band unter dem Läufer zu bewegen.
Probieren Sie es online!
quelle