Schreiben Sie ein Programm oder eine Funktion, die drei Ganzzahlen, eine Breite w, eine Höhe hund eine Schrittzahl enthält s. Sie werden einen nicht-selbstschneidende zeichnen werden Irrfahrt s auf einem langen Schritte 5*wvon 5*hPixelbild , wo all 5 von 5 Pixelzelle entweder leer (reine beige) ist oder eine dieser zwölf einfachen „Rohre“:

Das Bild oben ist vergrößert, um Details anzuzeigen. Hier sind die Pfeifen in Originalgröße:

^{(Die grauen Linien dienen nur zur Trennung der Rohrtypen.)}

Die zufällige Wanderung ist ein einzelner durchgehender Rohrleitungspfad, der an einem Rohrleitungsendpunkt (einer der unteren vier Rohrleitungstypen) beginnt und an einem anderen Rohrleitungsendpunkt endet.

Beginnen Sie mit einem leeren wdurch hGitter und zufällig wählen Sie eine Zelle der Ausgangspunkt zu sein. Wählen Sie dann nach dem Zufallsprinzip eine der vier Richtungen, in die Sie starten möchten, und zeichnen Sie den entsprechenden Rohrendpunkt. Diese Startzelle markiert den ersten Schritt auf Ihrem Weg. Jedes Mal, wenn Sie eine neue Zelle zeichnen oder eine vorhandene Zelle überschreiben, wird dies als weiterer Schritt gewertet.

Wählen Sie nun wiederholt nach dem Zufallsprinzip, ob Sie nach rechts, links oder gerade gehen möchten, und zeichnen Sie die entsprechende Rohrzelle, wenn die gewählte Richtung gültig ist. Zurückverfolgen und erneut auswählen, wenn eine Richtung nicht gültig ist, bis der vollständige sSchrittpfad gebildet ist. Der Pfad sollte mit einem Pipe-Endpunkt enden, der sich je nach Verlauf des Pfades an einer beliebigen Stelle im Raster befinden kann.

Es ist sehr wichtig zu beachten, dass nur die beiden geraden Rohrzellen überschrieben werden können und nur die gerade Rohrzelle mit der entgegengesetzten Ausrichtung. Das Ergebnis ist eine Schnittzelle. Ansonsten müssen alle Rohre in leere Zellen gelegt werden.

Wenn eine Kreuzung gezeichnet wird, sollte der Teil des Pfades, der weiter von der Startzelle entfernt ist, oben gezeichnet werden.

Es liegt an Ihnen, ob das Gitter periodische Randbedingungen (PBC) aufweist oder nicht , dh ob ein Rohr, das aus einer Seite des Gitters austritt, auf der anderen Seite austritt. Ohne PBC gilt die Gittergrenze als Barriere, auf die Sie wie auf andere Rohre stoßen können.

Spezialfälle

• Wenn s0 ist , sollte keine Rohre gezogen werden , und die Ausgabe sollte leer sein 5*wdurch 5*hBildes (dh alle beige).

• Wann sist 1 ein einzelner Rohrstutzen

  (Tatsächliche Größe: )

  sollte an der zufällig ausgewählten Startzelle gezeichnet werden.

Andere Details

• Sie können davon ausgehen, dass dies shöchstens der w*hFall ist, damit ein Pfad immer möglich ist. (Obwohl längere Wege aufgrund von Kreuzungen möglich sind.)
• wund hwird immer positiv sein.
• Alle zufälligen Entscheidungen müssen einheitlich zufällig sein. Sie sollten zB nicht vermeiden, Schnittpunkte zu erstellen, wenn dies möglich ist, auch wenn dies das Problem erleichtert. Pseudozufallszahlengeneratoren sind zulässig.
• Anstelle von Schwarz, Blau und Beige können drei beliebige visuell unterschiedliche Farben verwendet werden.
• Ihre Ausgabebilder können so vergrößert werden, dass sie wirklich 5*w*kaus 5*h*kPixeln bestehen, bei denen kes sich um eine positive Ganzzahl handelt. (Es wird empfohlen, die von Ihnen veröffentlichten Beispiele zu vergrößern, auch wenn Sie k1 sind.)
• Es kann jedes gängige verlustfreie Bilddateiformat verwendet werden, und das Bild kann in einer Datei gespeichert, angezeigt oder als Standarddatei ausgegeben werden.

Der kürzeste Code in Bytes gewinnt.

Beispiele

^{(Alle um 500% vergrößert.)}

Wenn die Eingabe ist, w=2, h=1, s=0ist die Ausgabe immer:

Wenn es sich bei der Eingabe w=2, h=1, s=1um eine Eingabe handelt, handelt es sich bei der Ausgabe um eines der folgenden Bilder mit gleicher Wahrscheinlichkeit:

Wenn der Eingang ist, w=2, h=1, s=2ist der Ausgang

oder möglicherweise

wenn das Netz PBC haben soll.

(Beachten Sie, dass das Starten des Pfades einen zweiten Schritt unmöglich machen würde.)

Hier sind einige mögliche Ausgaben für w=3, h=2, s=6PBC:

Hier ist eine mögliche Ausgabe w=3, h=3, s=9unter der Annahme von PBC:

Beachten Sie, dass der Pfad nicht alle Zellen abdecken musste, da der Schnittpunkt als zwei Schritte gezählt wurde. Wir können auch schließen, dass der Eckendpunkt die Startzelle war, da die Kreuzungsüberführung danach gezeichnet worden sein muss. So können wir die Reihenfolge der zufälligen Entscheidungen ableiten, die getroffen wurden:

start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end

Abschließend einige Beispiele für w=4, h=5, s=20und w=4, h=5, s=16:

CJam, 274

q~:K;:B;:A;{0aA*aB*:M5*5f*:I;K{[Bmr:QAmr:P]5f*:R;3Ym*{R.+:)2{1$0=I=2$W=@tI@0=@t:I;}:F~}/R2f+1FK({MQ=P=:EY4mr:D#&1{{MQMQ=PE2D#+tt:M;}:G~7,1>[W0_1_0_W]2/D=:Off*{[QP]5f*2f+.+_:H1F_OW%.+2FOW%.m2F}/H2FO~P+:P;Q+:Q;MQ=P=:E_5YD2%-*=!JK2-=+*1{D2+4%:D;G}?}?}fJ]}0?}g'P2NA5*SI,N2NI:+N*

Probieren Sie es online aus

Verwendet PBC und gibt im PGM-Format aus. Sie können :+das Ende entfernen , um eine bessere visuelle Ausgabe im Browser zu erhalten.

Es ist sehr langsam für größere Eingaben, besonders wenn die Schrittzahl in der Nähe des Bereichs liegt.

Beispielergebnis für Eingabe 4 3 10(skaliert 500%):

Kurze Erklärung:

Der allgemeine Ansatz ist:

• Wiederholen Sie alle folgenden Schritte, bis sie erfolgreich sind:
• 2 Matrizen initialisieren: eine Aufzeichnung, welche Seiten in jeder Zelle verwendet werden, und eine für das Bild
• wenn s = 0, sind wir fertig, sonst:
• Wähle eine zufällige Zelle und zeichne ein Quadrat, dann mache das folgende s-1 mal:
• wähle eine zufällige Richtung; Wenn diese Seite bereits verwendet wird, schlagen Sie fehl und beginnen Sie von vorne
• Markieren Sie die Seite als verwendet und zeichnen Sie die eigentliche Pipe im Bild (zeichnen Sie 3 benachbarte Linien der Länge 6, beginnend "hinter" dem mittleren Pixel der aktuellen Zelle, und fügen Sie dann einen Punkt hinzu, um das Ende der Pipe zu bedecken).
• Aktualisiere die aktuelle Position (gehe zur nächsten Zelle)
• Überprüfen Sie, ob die Zelle leer ist oder ob es sich um eine gültige Kreuzung handelt. Wenn nicht, versagen Sie und fangen Sie von vorne an
• Markieren Sie die in dieser Zelle verwendete Seite in der entgegengesetzten Richtung und setzen Sie die Schleife fort

QBasic, 517 516 Bytes

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
1CLS
IF s=0GOTO 9
x=5*INT(RND*w)
y=5*INT(RND*h)
GOSUB 7
FOR k=1TO s-1
r=INT(RND*4)+1
a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)=0GOTO 1
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
9IF c GOTO 1
END
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN

• Nimmt w, hund svon Benutzereingaben, durch Kommas getrennt.
• Die Ausgabe wird auf dem Bildschirm gezeichnet. Während das Programm nach einer Lösung sucht, kann es vorkommen, dass Teillösungen vergangen sind.
• Verwendet keine periodischen Randbedingungen. Ich fand es einfacher, Rohre zu zeichnen und zu testen, ohne mir Sorgen machen zu müssen, dass sich die Hälfte der Rohre auf einer Seite des Gitters und die andere auf der anderen befindet.

Der Ansatz hier ist, bei jedem Schritt eine zufällige Richtung zu wählen und von vorne zu beginnen, wenn dies zu einer ungültigen Bewegung führt. Wir zeichnen die Rohre, während die Anweisungen festgelegt werden, und POINTtesten anhand der Punkte auf dem Bildschirm unsere Gültigkeitsbedingungen. Ein Zug ist gültig, wenn er nicht über die Grenzen des Gitters hinausgeht und:

1. Die Zelle, in die verschoben wird, ist leer. oder
2. Beide
   1. Die Zelle, in die verschoben wird, enthält ein Rohr, das horizontal oder vertikal gerade durchgeht, und
   2. Der neue Rohrabschnitt verdoppelt keinen vorhandenen Rohrabschnitt

Wie die CJam-Antwort von aditsu ist dieser Code sehr langsam und kann verblüffend langsam sein, wenn er seinen signifikanten Bruchteil von ausmacht w*h. Bei meinem QB64-Setup wird die Frage 5,5,19ziemlich schnell beantwortet , es dauert jedoch länger, als ich bereit war, darauf zu warten 5,5,20.

Wenn Sie größere / dichter gepackte Beispiele ausführen möchten, ist hier mein ursprünglicher Ansatz unter Verwendung einer Tiefensuche . Es ist viel effizienter und kostet satte 300 zusätzliche Bytes.

RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
DIM t(s),m(s)
0
FOR z=1TO s
t(z)=-1
NEXT
i=5*INT(RND*w)
j=5*INT(RND*h)
k=1
1CLS
IF s=0GOTO 9
x=i
y=j
GOSUB 7
FOR z=1TO k-1
r=m(z)
GOSUB 6
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
IF c*(k=s)THEN k=k-1:GOTO 1 ELSE IF k=s GOTO 9
IF k<1GOTO 0
IF t(k)>=0GOTO 4
t(k)=0
f=30
WHILE f
r=INT(RND*4)+1
IF f AND 2^r THEN t(k)=t(k)*5+r:f=f-2^r
WEND
4r=t(k)MOD 5
m(k)=r
t(k)=t(k)\5
GOSUB 6
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)THEN k=k+1 ELSE IF t(k)>0GOTO 4 ELSE t(k)=-1:k=k-1
GOTO 1
6a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
RETURN
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN
9

Beispielausgabe für Eingaben 10, 10, 100, tatsächliche Größe:

Eine noch schickere Version finden Sie in diesem Kern . Abgesehen davon, dass der DFS-Algorithmus unbemerkt und ausführlich kommentiert ist, erhöht er die Ausgabe um einen konstanten Faktor und ermöglicht eine festgelegte Verzögerung zwischen den Schritten, sodass Sie den DFS-Algorithmus bei der Arbeit beobachten können. Hier ist ein Beispiellauf: