Escriba un programa o función que tome tres enteros, un ancho w, un alto hy un conteo de pasos s. Dibujará s pasos de caminata aleatorios que no se cruzan entre sí en una imagen 5*wpor 5*hpíxel, donde cada celda de 5 por 5 píxeles está vacía (beige puro) o uno de estos doce "tubos" simples:

La imagen de arriba se amplía para mostrar detalles. Aquí están las tuberías a tamaño real:

^{(Las líneas grises son solo para separar los tipos de tubería).}

La caminata aleatoria será una sola ruta de tubería continua que comienza en un punto final de tubería (uno de los cuatro tipos de tubería inferiores) y termina en otro punto final de tubería.

Comience con un vacío wpor hcuadrícula y elija aleatoriamente una celda como punto de partida. Luego, elija al azar una de las cuatro direcciones para comenzar y dibuje el punto final de la tubería correspondiente. Esta celda inicial marca el primer paso en su caminata y cada vez que dibuja una nueva celda o sobrescribe una existente, cuenta como otro paso dado.

Ahora, repetidamente, elija al azar ir a la derecha, izquierda o recta, dibujando la celda de tubería apropiada si la dirección elegida es válida. Retroceda y vuelva a elegir si una dirección no es válida hasta sque se forme la ruta de paso completa . La ruta debe terminar con un punto final de tubería, que puede estar en cualquier lugar de la cuadrícula, dependiendo del curso que tomó la ruta.

Es muy importante tener en cuenta que solo las dos celdas de tubería recta se pueden sobrescribir, y solo por la celda de tubería recta de la orientación opuesta, el resultado es una celda de intersección. De lo contrario, todas las tuberías deben colocarse en celdas vacías.

Cuando se dibuja una intersección, la parte de la ruta que está más lejos de la celda inicial debe dibujarse en la parte superior.

Depende de usted si la red tiene o no condiciones de contorno periódicas (PBC), es decir, si una tubería que sale de un lado de la red saldrá por el otro lado. Sin PBC, el límite de la cuadrícula cuenta como una barrera con la que puede toparse al igual que otras tuberías.

Casos especiales

• Cuando ses 0, no se deben dibujar tuberías y la salida debe estar en blanco 5*wpor 5*himagen (es decir, todo beige).

• Cuando ses 1 un trozo de tubo único

  (Tamaño real: )

  debe dibujarse en la celda inicial elegida al azar.

Otros detalles

• Puede suponer que ses como mucho, w*hpor lo que siempre será posible un camino. (Aunque son posibles caminos más largos debido a las intersecciones).
• wy hsiempre será positivo
• Todas las elecciones aleatorias deben ser uniformemente aleatorias. por ejemplo, no debe evitar hacer intersecciones cuando sean posibles, incluso si esto facilita el problema. Se permiten generadores de números pseudoaleatorios.
• Se pueden usar tres colores visualmente distintos en lugar del negro, azul y beige.
• Sus imágenes de salida se pueden ampliar para que sean realmente 5*w*kpor 5*h*kpíxeles, donde kes un entero positivo. (Se recomienda ampliar los ejemplos que publique incluso si suk es 1.)
• Se puede usar cualquier formato de archivo de imagen sin pérdida común y la imagen se puede guardar en un archivo, mostrar o arrojar sin formato a stdout.

El código más corto en bytes gana.

Ejemplos

^{(Todo ampliado en un 500%).}

Si la entrada es w=2, h=1, s=0entonces, la salida siempre será:

Si la entrada es w=2, h=1, s=1entonces, la salida será una de estas imágenes con la misma posibilidad:

Si la entrada es w=2, h=1, s=2entonces la salida será

o posiblemente

si se supone que la cuadrícula tiene PBC.

(Tenga en cuenta que comenzar el camino como haría un segundo paso imposible).

Aquí hay algunas salidas posibles para w=3, h=2, s=6, suponiendo PBC:

Aquí hay una salida posible para w=3, h=3, s=9, suponiendo PBC:

Tenga en cuenta que la ruta no necesitaba cubrir todas las celdas debido a que la intersección cuenta como dos pasos. Además, podemos deducir que el punto final de la esquina era la celda inicial, ya que el paso elevado de la intersección debe haberse dibujado después. Por lo tanto, podemos inferir la secuencia de elecciones aleatorias que se hicieron:

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

Finalmente, aquí hay ejemplos de w=4, h=5, s=20y 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*

Pruébalo en línea

Utiliza PBC, salidas en formato PGM. Puede eliminar el :+extremo cercano para obtener una salida visual más agradable en el navegador.

Es muy lento para entradas más grandes, especialmente si el conteo de pasos está cerca del área.

Ejemplo de resultado para entrada 4 3 10(escala 500%):

Breve explicacion:

El enfoque general es:

• repita todos los siguientes pasos hasta que tenga éxito:
• Inicialice 2 matrices: una grabación de los lados que se utilizan en cada celda y otra para la imagen
• si s = 0, hemos terminado, de lo contrario:
• elige una celda aleatoria y dibuja un cuadrado, luego haz lo siguiente s-1 veces:
• elige una dirección aleatoria; si ese lado ya está en uso, falla y comienza de nuevo
• marque el lado como se usa y dibuje la tubería real en la imagen (dibujando 3 líneas adyacentes de longitud 6, comenzando justo "después" del píxel central de la celda actual, luego agregando un punto para tapar el extremo de la tubería)
• actualizar la posición actual (pasar a la siguiente celda)
• verifique si la celda está vacía o si es un cruce válido; si no, falla y comienza de nuevo
• marque el lado en la dirección opuesta a la utilizada en esta celda, luego continúe el ciclo

QBasic, 517516 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

• Toma w, hy sde la entrada del usuario, separados por comas.
• La salida se dibuja en la pantalla. Mientras el programa busca una solución, puede ver soluciones parciales parpadeando.
• No utiliza condiciones límite periódicas. Me resultó más fácil dibujar y probar la conexión de tuberías sin tener que preocuparme de que la mitad de la tubería esté en un lado de la cuadrícula y la otra mitad en el otro.

El enfoque aquí es intentar una dirección aleatoria en cada paso y comenzar de nuevo desde el principio si resulta en un movimiento no válido. Dibujamos las tuberías a medida que se deciden las instrucciones y las usamos POINTpara probar puntos en la pantalla para nuestras condiciones de validez. Un movimiento es válido si no sale de los límites de la cuadrícula y:

1. La celda movida a está vacía; o
2. Ambos
   1. La celda movida contiene una tubería que pasa directamente, ya sea horizontal o verticalmente, y
   2. La nueva sección de tubería no duplica la sección de tubería existente.

Al igual que la respuesta CJam de aditsu , este código es muy lento y puede ser muy lento si ses una fracción significativa de w*h. En mi configuración QB64, aparece una respuesta con 5,5,19bastante rapidez, pero lleva más tiempo del que estaba dispuesto a esperar 5,5,20.

Si desea ejecutar ejemplos más grandes / más densos, aquí está mi enfoque original usando una búsqueda profunda . Es mucho más eficiente, a costa de la friolera de 300 bytes adicionales.

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

Ejemplo de salida para entradas 10, 10, 100, tamaño real:

Una versión aún más elegante se puede encontrar en esta esencia . Además de ser poco entusiasta y completamente comentado, escala la salida por un factor constante y permite un retraso establecido entre los pasos, lo que le permite ver el algoritmo DFS en funcionamiento. Aquí hay un ejemplo de ejecución: