Löse diese uHerbert-Herausforderung

8

TL; DR : Lösen Sie diese besondere Herausforderung, eine Robotersimulation, indem Sie auf alle weißen Pads treten und die grauen Pads meiden. Sie können beliebig oft auf ein weißes Feld treten, solange Sie mindestens einmal auf jedes weiße Feld treten. Lösungen in Sprachen wie Befunge mit einem 2D-Anweisungszeiger würden ebenfalls akzeptiert, aber H wird mit dem uHerbert- Programm geliefert und die Sprachspezifikationen sind unten angegeben. Sie benötigen das uHerbert-Programm nicht, um dies zu lösen, aber es erleichtert die Überprüfung Ihrer Lösung erheblich.

So sieht das Level aus. Dies ist ein 25x25-Gitter von Zellen, in dem der Roboter und jedes weiße und graue Pad eine Zelle belegen. Der Roboter zeigt zunächst nach oben.

Geben Sie hier die Bildbeschreibung ein

Hintergrund zu uHerbert

Herbert ist eine Robotersimulation, die ich 2008 zum ersten Mal bei der Online-Programmier-Challenge des IGF (Independent Games Festival) kennengelernt habe. Lange Zeit war ich enttäuscht, dass ich die Herausforderungen nach dem eigentlichen Wettbewerb nicht ausprobieren konnte. Zum Glück muss jemand anderes meine Gedanken gelesen und dieses kleine Dandy-Programm codiert haben: uHerbert (alias mu-Herbert oder micro-Herbert).

H (Sprachspezifikationen)

Das Programm ist eine Robotersimulation, fungiert aber auch als Interpreter für die Programmiersprache H, die nur dazu dient, den Roboter zu bewegen.

Es gibt drei Anweisungen:

  • S: Der Roboter tritt eine Zelle vor
  • L: Der Roboter dreht sich um 90 Grad nach links
  • R: Der Roboter dreht sich um 90 Grad nach rechts

Es stehen Ihnen drei Standardprogrammierfunktionen zur Verfügung: Funktionen, Parameter und Rekursion. Es werden zwei verschiedene Parametertypen unterstützt.

Numerische Parameter

g(A):sslg(A-1)

Hier ist g eine Funktion mit einem numerischen Parameter. Dies ist der Kesselplattencode. Anschließend können Sie Ihr eigentliches Programm schreiben, indem Sie Ihre Funktion aufrufen und ein Argument übergeben:

g(4)

Dies würde Ihre Funktion viermal aufrufen und die Rekursion wird automatisch beendet, wenn Ihr Parameter Aeinen Wert von Null erreicht:

g(4) = sslg(4-1) = sslg(3) = sslsslg(2) = sslsslsslg(1) = sslsslsslssl

Funktionsparameter

Sie können auch Funktionsparameter verwenden, die im Grunde nur Anweisungen wiedergeben, die Sie übergeben:

f(A):rAlA

Wenn Sie diese Funktion aufrufen und Anweisungen übergeben, wird Folgendes ausgewertet:

f(ss) = rsslss
f(sslssr) = rsslssrlsslssr

Andere Syntax

Funktionen können mehr als einen Parameter haben, und sie können auch beide Typen haben. Sie könnten alternativ keine Parameter haben. Folgendes sind ebenfalls gültige Funktionen:

j:ssss
k(A,B):Ajjjk(A,B-1)

Wie Sie sehen können, nimmt die Funktion j keine Parameter an, und die Funktion k nimmt beide Arten von Parametern an. A ist ein Funktionsparameter und B ist ein numerischer Parameter, wie oben beschrieben.

Unendliche Rekursion

Eine unendliche Rekursion ist ebenfalls zulässig, kann jedoch nur einmal eingeleitet werden und wird effektiv beendet, wenn Sie auf das letzte weiße Pad treten (ohne auf graue Pads getreten zu sein):

m:sslssrm

Zustand lösen

Das Ziel ist es, den Roboter dazu zu bringen, auf alle weißen Pads zu treten und zu vermeiden, auf eines der grauen Pads zu treten. Weiße Pads können beliebig oft betreten werden, solange jeder mindestens einmal betreten wird. Der Roboter kann auf jeden Punkt im Gitter treten, den er erreichen kann (einige Ebenen haben Sperrwände, und in dieser Ebene wirken die grauen Pads als Barriere).

Das zuvor gezeigte Puzzle ist auf der obigen Site unter level_pack2.zip verfügbar und heißt level3.txt . Sowohl das uHerbert-Programm als auch das Level Pack sind ab heute über den obigen Link verfügbar (die Site wurde archiviert, aber die Archivierungs-Engine hostet sie weiterhin), sie sind jedoch für eine Lösung nicht erforderlich.

Ich würde gerne die kürzest mögliche Lösung gemäß Code Golf sehen. Lösungen in anderen Sprachen als H werden nicht als gültig akzeptiert. (Es wäre sicherlich interessant, eine Beispiellösung in einer Sprache wie Befunge zu sehen, in der sich der Anweisungszeiger auf einem 2D-Gitter bewegt, aber gemäß der Golfbewertung mit Atomcode können nur H-Anweisungen eine genaue Bewertung erhalten. Der Anweisungszeiger könnte als behandelt werden Zum Beispiel die Position des Roboters.) Eine gültige Lösung ist eine, bei der der Roboter auf alle weißen Pads tritt (jeweils mindestens einmal) und nicht auf graue Pads tritt. Das Betreten anderer Teile des Gitters ist in Ordnung, aber in diesem speziellen Puzzle können Sie dies nicht tun, ohne auf ein graues Pad zu treten. Die Startposition des Roboters kann nicht geändert werden.

Ich sollte auch beachten, dass Lösungen, die zu einer nicht benachbarten Zelle springen, nicht akzeptiert werden. Dies ist für den Roboter in der Simulation nicht möglich und würde keine gültige Lösung darstellen. H erlaubt das sowieso nicht. Eine gültige Lösung muss also aus einzelnen Schritten bestehen. Für jede Zelle im Raster gibt es nur vier benachbarte Zellen: die orthogonalen dazu (oben, unten sowie links und rechts). Dies würde natürlich diagonale Schritte nicht zulassen, aber da Sie nur in 90-Grad-Schritten drehen können, sind diagonale Schritte nicht einmal möglich.

Wenn der Roboter eine Anweisung erhält, die erfordert, dass er sich in eine Barriere oder außerhalb des Gitters bewegt, ist das Ergebnis im Grunde "derp" - der Roboter trifft die Wand und bleibt dort, wo er ist, und der Anweisungszeiger bewegt sich zur nächsten Anweisung (der Anweisung wird grundsätzlich übersprungen).

Hinweis zur Lösungsgröße

Wenn Sie diese Ebene im Programm öffnen, werden Sie feststellen, dass es anscheinend möglich ist, in 13 Bytes zu lösen. Ich bin total verblüfft darüber, wie das möglich ist, und bin gespannt, wie nahe andere dem kommen können. Meine kürzeste Lösung ist 30 Byte in H. Wenn jemand möchte, dass ich sie poste, werde ich es tun, aber ich würde gerne andere Lösungen sehen, bevor ich meine poste. Das Programm gibt Ihnen auch eine Punktzahl, aber die Punktzahl ist für diese Frage irrelevant. Lösungen jeglicher Punktzahl werden akzeptiert.

Es scheint, dass das uHerbert-Programm keine Klammern oder Doppelpunkte als Teil Ihres Programms zählt (Sie werden dies sehen, wenn es Ihre Bytes hochzählt). Für die Zwecke dieser Frage zählen Klammern und Doppelpunkte in der Sprache H nicht als Bytes für Ihre Lösung, da sie in erster Linie Trennzeichen sind und eher rein syntaktischer als semantischer Natur sind.

Tim
quelle

Antworten:

6

H, 13 Bytes

a:ssr
b:sasaaab
b

Demo

Animation

Anders Kaseorg
quelle
Klug. Ich erinnere mich, dass ich dieses Rätsel beim ersten Posten durchgesehen habe, aber ich habe diese Lösung nicht gefunden.
Draco18s vertraut SE nicht mehr
Ausgezeichnete Arbeit. Dies ist eindeutig die beabsichtigte Lösung.
Tim