Imprime un laberinto al azar

19

Escriba un programa que genere e imprima un laberinto aleatorio utilizando el algoritmo de su elección. El laberinto debe ser diferente para múltiples ejecuciones del programa. La altura y el ancho se dan como argumentos de línea de comando. Use |para pared vertical, -para pared horizontal y +para esquina. El laberinto está delimitado por paredes y las entradas están marcadas por paredes faltantes. El laberinto contiene un tesoro #que debe ser accesible desde al menos una entrada.

$ python2 random-maze.py 4 5
+-+-+
  |#|
|   |
+---+
code-challenge ascii-art maze Alexandru
fuente
+1 Gran pregunta. Sin embargo, algunos puntos. 1: ¿Cómo se marca la salida? ¿Es un símbolo como *o hay dos entradas separadas? 2: Probablemente debería especificar que la salida debe ser accesible.
snmcdonald
1
@snmcdonald: hagámoslo divertido y agreguemos un tesoro :).
Alexandru
2
Puedo ver un seguimiento de golf, sobre cómo resolverlos ... :)
st0le
@ st0le: ya tengo algunas ideas. Envíame un correo si quieres discutir.
Alexandru
1
El tipo de rompecabezas no se especifica aquí. Veo que la gente respondió como si fuera un [código-golf]. ¿Era esa la intención? Si es así, ¿lo etiqueta como tal?
dmckee 01 de

Respuestas:

5

Creo que esto técnicamente no es un generador de laberintos, pero crea un resultado similar a un laberinto: https://gist.github.com/803450 .

Sé que hay un código horrible allí, y solo funciona menos de la mitad del tiempo, y el resultado no parece correcto para las paredes que sobresalen de otras paredes. Pero está lo suficientemente cerca como para que no me moleste en arreglar el resto.

Algunos resultados de ejemplo:

→ ruby random-maze.rb 30 30
+----+-+-----------++-+----+
|    + |           ++ |    |
++  +  | ++ ++   +    + ++ ++
|  ++ ++ |  |    +---+  +   |
| +      | +| +   +++  +  + |
|   +   +| +| +-+  |   + +  |
|        +  +    + + ++  |+ |
| + ++ +  ++   + |  +   ++| |
| |  | ++  + +----+ + +-+ | |
| +  |  +-+  |+        |  | |
|   +-+  +| ++  ++ + + |  | |
| ++   +  + |  ++|   + | ++ |
|  + + + +  +---++-+   +++  |
| +  |  +| +    |  ++   |   |
| | +++ +| + ++ +--+  + |---+
|#+ | |  |   +++     +  +   |
++  | ++ +-+  ++ +--+  +  + |
|  ++  |    +     ++| +  ++ |
| ++   +--------+  +| + +   |
| |     |      +++  |  +  +-+
| |     | +--+  |++ |+ | ++
| |     |  +--+ | | || |  |
| |     +-+     +-+ |+ |+ |
| | +---+   ++      +  |  |
| +-|     +    +      ++ ++
|   +       ++   +---+   |
|              ++   +  +-+
|                 +   ++
+-+ +-------------+---+
Nemo157
fuente
1
Buena idea. Puntos extra si lo arreglas;)
Alexandru
Esto fue solo una rápida extracción y cambio de salida para un algoritmo que utilicé para generar un laberinto para una de mis asignaciones uni . El algoritmo real es robado principalmente de una publicación de blog de CHEVYRAY . Podría arreglarlo este fin de semana, no estoy seguro de si el formato de salida funcionará por completo ya que no es un verdadero laberinto, pero intentaré acercarlo lo más posible mientras se vea bien.
Nemo157
Me parece un muy buen laberinto.
Alexandru
8

Python, 375 caracteres

import random,sys
H,V=map(int,sys.argv[1:])
H-=1
V-=1
b,h,v,p=' -|+'
M=H/2*h
n=random.randint(1,(H/2)*(V/2-1))
for i in range(V/2):
 e=s=t='';N=v
 for j in range(H/2):
  if i and(random.randint(0,1)or j==0):s+=N+b;t+=v;N=v;M=M[1:]+p
  else:s+=M[0]+h;t+=b;N=p;M=M[1:]+h
  n-=1;t+=' #'[n==0]
 if H&1:s+=s[-1];t+=b;e=h
 print s+N+'\n'+t+v
if V&1:print t+v
print h.join(M)+e+h+p

Esto genera un laberinto con una entrada y un tesoro colocado al azar. El laberinto es un simple laberinto de árboles binarios .

$ ./maze.py 15 15
--------------+
              |
| | ----------+
| |           |
| +-----+ | --+
|       | |   |
| --+ --+ +---+
|   |   |     |
| --+-+ +---+ |
|     |     | |
| --+ +-+ --+ |
|   |   |   |#|
| | | --+ --+-+
| | |   |     |
+-+-+---+-----+
Keith Randall
fuente
Tal vez fue intencionado, pero la fila superior (justo debajo de la pared) siempre es un pasillo largo.
Alexandru
Sí, y la columna de la izquierda siempre es un corredor largo también. Esta es una propiedad del tipo de laberinto que estoy generando.
Keith Randall el
Oh. Los laberintos son muy bonitos :).
Alexandru
6

Ruby 1.9.2p136: 90

eval ARGV[0]
z=[l="+"+"-"*@w+"+"]
@h.times{z<<"|"+" "*@w+"|"}
z[rand(@h)+1]="|#"
puts z<<l

Salida

$> ruby maze.rb "@h=8;@w=8;"

+------+
|      |
|      |
|      |
|      |
|#
|      |
+------+

Oye, nadie dijo que tenía que ser un buen laberinto. OK, OK, haré una real ahora.


fuente
Bien, pero asegúrese de que respeta el protocolo (altura y anchura desde la línea de comando, laberinto impreso en stdout).
Alexandru
En realidad, no dice nada sobre stdout (tampoco es una estipulación razonable porque alguien podría estar usando un lenguaje que no imprime en stdout) y se acepta comúnmente que las entradas son para una función / método. Para la persona que rechaza votar esto, resuelve el problema como se especifica, así que no odies al mazer, odia el laberinto.
En realidad no tanto como se especifica en la pregunta. Ver meta.codegolf.stackexchange.com/questions/13/… . Además, a diferencia de JavaScript, Ruby admite la lectura y escritura de argumentos en la salida estándar. Su solución es hacer trampa en comparación con otros que resolvieron el problema de la manera correcta.
Alexandru
No se puede editar Quise decir 'incompleto', no 'hacer trampa'. Me gusta la idea del laberinto.
Alexandru
Luego, los otros idiomas tienen que incluir el código que se necesita para llamarlos o incluir #!/usr/bin/env python, por ejemplo, en su código. Como dije, escribiré una solución real también, esto fue solo señalar la mala calidad de la pregunta en sí (y muchas otras) y demuestra que necesitamos tener mejores pautas. Y finalmente, señalar una pregunta no hace que la respuesta a la pregunta sean las reglas reales del sitio. Pero bien, aquí está tu nueva versión ...
3

C 844

#include <stdlib.h>
#include <time.h>
h,w,*m,y,x,z;d(t,b,l,r){int i=b-t,j=r-l;if(i>1&&j>1){i=(rand()%--i)|1;j=(rand()%--j)|1;z=rand()%4;x=rand()%i+t;x|=1;for(y=t;y<i+t;y++)if(y!=x||!z)m[y*w+j+l]=124;x=rand()%(b-i-t)+i+t;x|=1;for(y=t+i;y<b+1;y++)if(y!=x||!(z-1))m[y*w+j+l]=124;y=rand()%j+l;y|=1;for(x=l;x<j+l;x++)if(y!=x||!(z-2))m[(i+t)*w+x]=45;y=rand()%(r-j-l)+j+l;y|=1;for(x=l+j;x<r+1;x++)if(y!=x||!(z-3))m[(i+t)*w+x]=45;m[(i+t)*w+j+l]=43;m[(t-1)*w+l+j]=43;m[(b+1)*w+j+l]=43;m[(i+t)*w+l-1]=43;m[(i+t)*w+r+1]=43;d(t,t+i-1,l,l+j-1);d(t+i+1,b,l,l+j-1);d(t,t+i-1,l+j+1,r);d(t+i+1,b,l+j+1,r);}}main(int c,char**v){h=atoi(v[1]),w=atoi(v[2]),m=calloc(h*w,4);srand(time(0));while(y<h){while(x<w){m[y*h+x]=(!y||y==h-1)?(!x||x==w-1)?43:45:(!x||x==w-1)?124:32;x++;}y++;x=0;}d(1,h-2,1,w-2);z=rand()%(w-2);z|=1;m[z]=32;z=rand()%(w-2);z|=1;m[h*(w-2)+z]=35;}

Probar:

#include <stdio.h>//beginning
for(y=0;y<h;y++){for(x=0;x<w;x++){putchar(m[y*h+x]);}putchar('\n');}getchar();//end

3x3

+ +
| # |
+ - +

7x8

+ - + - - +
El | El |
+ + - + - +
El | El |
El | + - + - +
El | El | # |
+ - + - + - +

18x20

+ - + - + + --- + --- + - + - +
El | El | El | El | El |
El | + + + - + --- + + - +
El | El | El | El |
+ + + - + --- + - + - + - +
El | El | El | El |
+ - + + - + - + - + --- + - + - +
El | El | El | El | El | El |
El | + + + + - + - - + |
El | El | El | El | El |
El | El | El | + - + - + ---- + |
El | El | El | El | El |
+ + + - + - + - + - - + - +
El | El | El | El | El |
El | + + - + - + - - + |
El | El | El | El | El |
El | El | El | El | # | El | El |
+ - + - + - + --- + ----- + - +
snmcdonald
fuente
Este es un desafío de código , no un código de golf . ¿Por qué el código apenas legible?
Braden Best
-1. No solo se ofusca este código, sino que no hay instrucciones claras sobre cómo se debe compilar y cómo se deben implementar los dos bloques de código. Las instrucciones de uso son escasas, si no faltan por completo. Es obvio que su respuesta es un código de golf. Pero la pregunta no es . Por lo tanto, el código debe ser legible y autónomo para copiar / pegar / compilar fácilmente, de modo que otros puedan verificar que realmente funciona sin tener que descifrar cómo consiguió que el código funcione en primer lugar.
Braden Best
0

Aquí hay una solución java simple:

import java.util.*;

public class MazeGen {
    public static void main(String[]a){
        int w,l;
        Random rand=new Random(System.currentTimeMillis()%1000+System.nanoTime());
        if(a.length==2){
            w=Integer.parseInt(a[0]);
            l=Integer.parseInt(a[1]);
        }else{
            System.out.println("No command line arguments, taking from STDIN.");
            Scanner input=new Scanner(System.in);
            w=input.nextInt();
            l=input.nextInt();
            input.close();
        }
        char[][]maze=new char[w][l];
        for(int x=0;x<w;x++){
            for(int y=0;y<l;y++){
                maze[x][y]=' ';
            }
        }
        for(int x=0;x<w;x++){
            maze[x][0]=maze[x][l-1]='|';
        }
        for(int y=0;y<l;y++){
            maze[0][y]=maze[w-1][y]='-';
        }
        maze[0][0]=maze[w-1][0]=maze[w-1][l-1]=maze[0][l-1]='+';
        int dor=1+rand.nextInt(l-2);
        maze[0][dor]=' ';
        int tx=2+rand.nextInt(w-3),ty=1+rand.nextInt(l-2);
        maze[tx][ty]='#';
        if(ty<dor-1){
            maze[tx][ty+1]='|';
            if(tx==w-2){
                maze[tx+1][ty+1]='+';
            }
            if(tx==1){
                maze[0][ty+1]='+';
            }
        }
        if(ty>dor+1){
            maze[tx][ty-1]='|';
            if(tx==w-2){
                maze[tx+1][ty-1]='+';
            }
            if(tx==1){
                maze[0][ty-1]='+';
            }
        }
        if(ty==dor&&tx>3&&(maze[tx][ty+1]==' '||maze[tx][ty-1]==' ')){
            maze[tx-1][ty]='-';
        }
        if(dor>5){
            int z=2+rand.nextInt(dor-3);
            int q=1+rand.nextInt(w-3);
            for(int i=0;i<w;i++){
                if(i==0||i==w-1){
                    maze[i][z]='+';
                }else if(i!=q&&maze[i][z]==' '){
                    maze[i][z]='|';
                }
            }

        }
        if(l-dor>5){
            int z=dor+2+rand.nextInt(l-dor-3);
            int q=1+rand.nextInt(w-3);
            for(int i=0;i<w;i++){
                if(i==0||i==w-1){
                    maze[i][z]='+';
                }else if(i!=q&&maze[i][z]==' '){
                    maze[i][z]='|';
                }
            }

        }
        for(char[]row:maze){
            System.out.println(row);
        }
    }
}

Algunos resultados de muestra:

3x3:

+ +
|#|
+-+

4x4:

+ -+
| #|
|  |
+--+

4x5:

+-+ +
|#| |
|   |
+---+

5x5:

+ --+
|   |
|   |
| |#|
+-+-+

5x8:

+ --+--+
|   |  |
|      |
| # |  |
+---+--+

8x15:

+---- ----+---+
|         |   |
|         |   |
|         |   |
|             |
| #|      |   |
|         |   |
+---------+---+
SuperJedi224
fuente