Construye un generador de rompecabezas de hielo + solucionador

En Twitch Plays Pokémon , uno de los obstáculos más molestos que uno puede enfrentar es un rompecabezas de hielo, en el que debe viajar de un lugar a otro deslizándose en una dirección hasta que golpee una pared o una roca.

Su tarea es construir un programa que genere un rompecabezas de hielo difícil al azar.

Su programa aceptará tres números, M, N, y P, como entrada (con 10 <= M <= 30, 15 <= N <= 40y 0 <= P < 65536):

12 18

y dará salida:

Una Mpor Nrejilla que consiste en .y O, en representación de hielo y un canto rodado respectivamente.
Un marcador de posición que representa desde dónde se ingresa el rompecabezas. Este marcador de posición consiste en una letra L, R, T, oB , en representación de la izquierda, derecha, superior e inferior, seguido de un número que representa la posición (desde la izquierda o la parte superior) en ese lado que se introduce desde.
Un marcador de posición similar que representa de dónde sale el rompecabezas.
La solución más corto para el rompecabezas, que consiste en una secuencia de L, R, U, y Drespectivamente.

Salida de ejemplo:

..O...O...........
............O.....
..O...............
.......O..........
..................
...........O......
O..O...........O..
..........O.......
..O..........O....
........O.........
O....O.........O..
............O.....
R 4
B 5
LDLDRULD
(Note that this output is actually invalid because it is not actually long enough.)

Para una entrada My N, la solución al rompecabezas debe tener al menos min(M, N)pasos y mover al menos 2 (M + N)espacios totales. (Para referencia, el rompecabezas anteriormente mueve un total de 12 pasos, moviendo 69 espacios.) Su generador rompecabezas debe generar una diferente Mpor Nrompecabezas con un camino de solución diferente (es decir, una secuencia diferente de pasos para cada solución) para cada semilla P.

Tenga en cuenta que el requisito de una ruta de solución diferente es evitar soluciones que intenten generar sistemáticamente rutas de roca, como la solución de Claudiu aquí . Si hay dos o tres pares de soluciones idénticas debido a peculiaridades en la aleatoriedad, eso estará bien, siempre y cuando el programa no esté tratando intencionalmente de generar sistemáticamente rompecabezas con la misma secuencia de movimientos.

El código más corto para hacer lo anterior gana.

code-golf Joe Z.
fuente

No puedo entender el objetivo: "debes viajar de un lugar a otro deslizándote completamente en una dirección hasta que choques contra una pared o una roca". ¿Es bueno golpear paredes o rocas? ¿A dónde quieres ir desde el principio? Si golpeas una roca, ¿termina el juego? ¿Qué sucede cuando golpeas una pared? ¿Soy solo yo o las instrucciones no son claras?

DavidC

Oh, viejos recuerdos de Pokémon Gold y Silver aquí. Encuentra la salida, toma HM07 y ve a Blackthorn City.

Victor Stafusa

Esto me recuerda los niveles de hielo en Chip's Challenge .

luser droog

¿Por qué no usar >y <(o cualquier carácter) para la entrada y la salida? Los rompecabezas serán más fáciles de leer.

En realidad, su salida de muestra no es válida: la ruta más corta LDLDRULDes de solo 8 pasos de largo

Claudiu

Respuestas:

Python, 672 548 caracteres, rompecabezas más interesantes

Aunque siguiendo estrictamente las reglas, mi otro programa de Python supera este, decidí escribir uno que generaría rompecabezas más interesantes de todos modos. Aquí está:

R=range;import random as J;X=J.randint
x=(0,1,-1,0);y=x[2:]+x
g=lambda r,c:(0<=r<H)+(0<=c<W)>1and f[r][c]or x[(r,c)in(A,E)]
l=lambda r,c:g(r+y[d],c+x[d])<1and(r,c)or l(r+y[d],c+x[d])
H,W,P=input();J.seed(P)
while 1:
 A=(-1,X(0,W));E=(H,X(0,W));f=[[X(0,7)for _ in R(W)]for _ in R(H)]
 q=[(A,'')];n=z={}
 while q and n!=E:
    n,O=q.pop()
    for d in R(4):
     N=l(*n)
     if g(n[0]+y[d],n[1]+x[d])and N not in z:q[:0]=[(N,O+"URLD"[d])];z[N]=1
 if(n==E)*len(O)>min(H,W):print"\n".join(''.join('O.'[c>0]for c in T)for T in f),"\nT",A[1],"\nB",E[1],"\n",O;break

Los niveles de sangría son espacio, tabulación, tabulación + espacio.

Muestras :

$ echo [10,15,0] | python ice2.py
.....OO........
...............
...O....O.OO..O
...........O...
..O....O.......
.......O....O..
....O..........
.............O.
..............O
...............
T 1
B 10
DLURDRURULDRD

Se utiliza Pcomo semilla, por lo que cada uno Pgenerará el mismo rompecabezas y Pes muy probable que cada uno sea diferente:

$ echo [10,15,1] | python ice2.py
.OOO.O.........
...O......O.O.O
.......O.......
..O..........OO
.....O.........
.............O.
.O.............
.O............O
O....O.........
......O........
T 14
B 8
DLDRDLURULD

Funciona razonablemente rápido hasta tamaños, M=25,N=40pero más allá de eso se vuelve realmente lento. Teóricamente debería funcionar M=30, N=40si lo dejas correr el tiempo suficiente. He escrito manualmente en el camino aquí ya que es difícil de seguir: el programa simplemente genera el rompecabezas.

$ echo [25,40,0] | python ice2.py
                   *
...................dO....urrrO..O..O....
....O.....O........dO....u..dO..........
..........O.....O..d....Ou.Odrrrrrrrrrrr
...........O.......d.O..Ou..O.....OOllld
.O....O.OO.........drrrrrrO....Olllud..O
O......O...O.O.....O............dO.ud...
O........OO..........O.........Od..ud..O
.........O......................d..ud...
....O.....O.O....O.....O........d..ud.O.
.....O..O...................O...d..udO..
.........O.........O..O.........d..ud...
.......O.O...O..O.OO....O...OOlldOOld...
........Olllllllllu....OO.OO..dOO...O...
.O.O....Od........u......O....d..O...O..
..O....O.d........u..O........d..O..O...
....O....d..O.....uO.....O....d.........
.........d........u...........d.........
.........d....O...u.O..O.....Od.O.......
........Od...O....u...........d.........
.O.....OuxrrrrO...u...OOOO..O.d.........
........udO..dO.O.u...........d.........
O..O.O..ud...d..urrO..........d.O...O...
........ud...d..u.O.O........Od..O...O..
..OO....ud..Od..u......OllllludO.....O..
..O....OldO..dOOlllllllld...Old...O..O..
             *
T 19
B 13
DRURDRDLDLULDLDLULDLURULDLURD

explicación :

El programa realiza un bucle, generando una posición de inicio aleatorio en la parte superior, una posición final aleatoria en la parte inferior y una cuadrícula aleatoria con la 12.5%posibilidad de una roca en cualquier punto dado. Luego resuelve el rompecabezas con una búsqueda de amplitud y, si la solución existe y es más grande que min(H,W), se imprime y sale.

Claudiu
fuente

Java - 2632

Mientras admiro la pureza técnica de la respuesta de Claudiu , decidí intentar hacer rompecabezas un poco más difíciles;)

Pasos básicos (bastante simples):

Randomize entry location
Step forward
For min(m,n)-1 steps:
    Rotate left or right
    Slide until I hit something or go a random distance
    Place a rock in front of stopping location
If I can slide straight to any wall:
    Slide to exit
Else
    Create another step and try again

If at any step I get trapped, start over
If BFS finds shorter path, start over

También marco cada lugar como 'nogo' mientras me deslizo. Si termino en un lugar nogo (o justo en frente de uno que significaría que una roca iría allí), es un paso no válido.

Entonces, básicamente la idea es generar aleatoriamente muchos mapas y mantener el primero que sea válido. Planeo hacer esto más inteligente (retroceso, etc.), pero funciona bien en este momento. También podría reducir el código redundante, ya veremos.

Tal como está, genera mapas pequeños (15x10) casi instantáneamente, mapas medianos (30x20) en un par de segundos y grandes (40x30) en una cantidad de tiempo aleatorio entre 20 segundos y 20 minutos, dependiendo de la semilla. Prueba entre 300k-500k mapas / segundo en mi máquina, dependiendo del tamaño.

Nota al margen: a veces los mapas no son demasiado difíciles, simplemente porque solo hay tantas rocas como escalones, y a menos que el escalón te lleve a una pared, la mayoría de las veces solo hay una opción si quieres golpear una roca real. Lo arreglaré más tarde colocando rocas "aleatorias" en lugares seguros después de que se hayan dibujado todos los pasos. Como los puntos nogo ya están marcados, eso debería ser bastante simple. Por ahora, solo disfruta de estos ejemplos:

Salida que muestra diferentes tamaños / semillas:

$ java I 30 20 6851              $ java I 15 10 1     $ java I 15 10 65513  

............................O.      .......O.......     ....O..........     
..............................      ...............     ...............     
..............................      .........O.....     .........O.....     
..........O......O............      .............O.     ..............O     
...............O...........O..      ...............     ...............     
..............................      .......O.......     .....O.O.......     
..............................      O..............     ...............     
........................O.....      ...............     ..........O....     
..............................      ...............     O..............     
...O.......................O..      ......O........     ...............     
O...............O.OO..........          
..............O..........O....          
...........O..................      T 14                R 6         
....O.........................      T 7                 T 14            
..............................      DLDLULURU           LULDLDRURU
..............................
..............................
.................O............
.O............................
..............................


B 28
R 9
ULURDLDLDRURDLDRURUR

Tamaño máximo 40x30:

$ java I 40 30 2

........................................
........................................
........................................
........................................
................O.......................
..........O.............................
........................................
.......O................................
.....................O..........O.......
......................O.................
.................................O......
......................................O.
........................................
........................................
..............................O.........
...........O............................
........................................
.......................................O
.........O...................O..........
....................O...................
...............................O........
............O..O......................O.
......O...........O.....................
..................O....O................
..................................O.....
........................................
..............................O.........
.....................................O..
...........O............................
...................O....................

B 19
B 11
URURDLULULDRDRDLULDLDLULURDLD

Golfizado:

import java.util.*;import java.awt.*;class I{int m,n,p,g,a[][],b[][];Random r;Point s,e,c;ArrayList<Integer>z;void Q(String q,int l){if(l>0)System.out.println(q);else System.out.print(q);}void G(String[]y){m=Integer.valueOf(y[0]);n=Integer.valueOf(y[1]);p=Integer.valueOf(y[2]);r=new Random(p);Q("",1);int o=0,i,j,u=0;char t,f[]={85,76,68,82};while(o<3){if(++u%20000==0)Q("\r#"+u,0);a=new int[m+2][n+2];b=new int[m+2][n+2];for(i=0;i<m+2;i++)for(j=0;j<n+2;j++)if(i==0||i==m+1||j==0||j==n+1)a[i][j]=2;s=new Point();int e=r.nextInt(m*2+n*2);if(e<m*2){s.x=e%m+1;s.y=e<m?0:n+1;}else{s.y=(e-m*2)%n+1;s.x=(e-m*2)<n?0:m+1;}if(s.x<1)g=3;else if(s.x>m)g=1;else if(s.y<1)g=2;else if(s.y>n)g=0;a[s.x][s.y]=0;c=new Point(s);z=new ArrayList<Integer>();z.add(g);for(i=0;i++<Math.min(m,n)-1;)if(N()<1&&N()<1)break;o=((z.size()>=Math.min(m,n)-1)?1:0)+F()+((V()==z.size())?1:0);}Q("\r",0);for(j=1;j<n+1;j++){for(i=1;i<m+1;i++)Q(String.valueOf(a[i][j]>0?'O':'.'),0);Q("",1);}Q("\n\n",0);if(s.x<1||s.x>m){t=s.x<1?'L':'R';u=s.y;}else{t=s.y<1?'T':'B';u=s.x;}Q(t+" "+u,1);if(e.x<1||e.x>m){t=e.x<1?'L':'R';u=e.y;}else{t=e.y<1?'T':'B';u=e.x;}Q(t+" "+u,1);for(i=0;i<z.size();)Q(String.valueOf(f[z.get(i++)]),0);Q("",1);}public static void main(String[]a){new I().G(a);}int F(){int c=0;while(C()<1&&c++<10)if(N()<1)return 0;return e==null?0:1;}int C(){int d=g<2?-1:1;if(g%2<1){int y=c.y;while(y>0&&y<n+1){y+=d;if(a[c.x][y]==1)return 0;}e=new Point(c.x,y);}else{int x=c.x;while(x>0&&x<m+1){x+=d;if(a[x][c.y]==1)return 0;}e=new Point(x,c.y);}a[e.x][e.y]=0;return 1;}int V(){if((s.x-e.x)+(s.y-e.y)<2)return 0;Queue<Point>q=new ArrayDeque<Point>();Queue<Integer>d=new ArrayDeque<Integer>();a[s.x][s.y]=-2;q.add(s);d.add(0);while(q.size()>0){Point t=q.poll();int h=d.poll(),i=0;if(t.equals(e))return h;for(;i<4;i++){Point n=S(a,t,i<2?0:1,i%2<1?-1:1,99,1);if(a[n.x][n.y]==-2)continue;a[n.x][n.y]=-2;q.add(n);d.add(h+1);}}return 0;}int N(){Point q;int d=g<2?-1:1,x,y;System.arraycopy(a,0,b,0,a.length);q=S(b,c,g,d,r.nextInt((g%2<1?n:m)/2)+2,0);if(q.x<1||q.y<1||q.x>m||q.y>n||q.equals(c)||b[q.x][q.y]!=0)return 0;x=q.x;y=q.y;if(g%2<1)y+=d;else x+=d;if(b[x][y]<0)return 0;b[q.x][q.y]=-1;b[x][y]=1;int f=r.nextInt(2)<1?-1:1;g=g%2<1?(f<0?1:3):(g=f<0?0:2);c=q;System.arraycopy(b,0,a,0,a.length);z.add(g);return 1;}Point S(int[][]u,Point f,int w,int d,int q,int s){int i=1,x=f.x,y=f.y;for(;i<=q;i++){if(w%2<1)y=f.y+i*d;else x=f.x+i*d;if(e!=null&&e.x==x&&e.y==y)return e;if(y<0||y>n+1||x<0||x>m+1)return f;if(s<1&&u[x][y]<1)u[x][y]=-1;if(u[x][y]>0){if(w%2<1)y-=d;else x-=d;return new Point(x,y);}}if(w%2<1)return new Point(f.x,f.y+i*d);else return new Point(f.x+i*d,f.y);}}

Con saltos de línea:

import java.util.*;
import java.awt.*;

class I{
    int m,n,p,g,a[][],b[][];
    Random r;
    Point s,e,c;
    ArrayList<Integer>z;

    void Q(String q,int l){if(l>0)System.out.println(q);else System.out.print(q);}

    void G(String[]y){
        m=Integer.valueOf(y[0]);
        n=Integer.valueOf(y[1]);
        p=Integer.valueOf(y[2]);
        r=new Random(p);
        Q("",1);

        int o=0,i,j,u=0;
        char t,f[]={85,76,68,82};
        while(o<3){
            if(++u%20000==0)
                Q("\r#"+u,0);

            a=new int[m+2][n+2];
            b=new int[m+2][n+2];
            for(i=0;i<m+2;i++)
                for(j=0;j<n+2;j++)
                    if(i==0||i==m+1||j==0||j==n+1)
                        a[i][j]=2;

            s=new Point(); 
            int e=r.nextInt(m*2+n*2);
            if(e<m*2){
                s.x=e%m+1;
                s.y=e<m?0:n+1;
            }else{
                s.y=(e-m*2)%n+1;
                s.x=(e-m*2)<n?0:m+1;
            }
            if(s.x<1)g=3;
            else if(s.x>m)g=1;
            else if(s.y<1)g=2;
            else if(s.y>n)g=0;

            a[s.x][s.y]=0;
            c=new Point(s);
            z=new ArrayList<Integer>();
            z.add(g);

            for(i=0;i++<Math.min(m,n)-1;)
                if(N()<1&&N()<1)
                        break;
            o=((z.size()>=Math.min(m,n)-1)?1:0)+F()+((V()==z.size())?1:0);
        }

        Q("\r",0);
        for(j=1;j<n+1;j++){
            for(i=1;i<m+1;i++)
                Q(String.valueOf(a[i][j]>0?'O':'.'),0);
            Q("",1);
        }
        Q("\n\n",0);
        if(s.x<1||s.x>m){
            t=s.x<1?'L':'R';
            u=s.y;
        }else{
            t=s.y<1?'T':'B';
            u=s.x;
        }
        Q(t+" "+u,1);
        if(e.x<1||e.x>m){
            t=e.x<1?'L':'R';
            u=e.y;
        } else {
            t=e.y<1?'T':'B';
            u=e.x;
        }
        Q(t+" "+u,1);
        for(i=0;i<z.size();)
            Q(String.valueOf(f[z.get(i++)]),0);
        Q("",1);
    }

    public static void main(String[]a){
        new I().G(a);
    }

    int F(){
        int c=0;
        while(C()<1&&c++<10)
            if(N()<1)
                return 0;
        return e==null?0:1;
    }

    int C(){
        int d=g<2?-1:1;
        if(g%2<1){
            int y=c.y;
            while(y>0&&y<n+1){
                y+=d;
                if(a[c.x][y]==1)
                    return 0;
            }
            e=new Point(c.x,y);
        }else{
            int x=c.x;
            while(x>0&&x<m+1){
                x+=d;
                if(a[x][c.y]==1)
                    return 0;
            }
            e=new Point(x,c.y);
        }
        a[e.x][e.y]=0;
        return 1;
    }


    int V(){
        if((s.x-e.x)+(s.y-e.y)<2)
            return 0;
        Queue<Point>q=new ArrayDeque<Point>();
        Queue<Integer>d=new ArrayDeque<Integer>();
        a[s.x][s.y]=-2;

        q.add(s);
        d.add(0);
        while(q.size()>0){
            Point t=q.poll();
            int h=d.poll(),i=0;
            if(t.equals(e))
                return h;
            for(;i<4;i++){
                Point n=S(a,t,i<2?0:1,i%2<1?-1:1,99,1);
                if(a[n.x][n.y]==-2)
                    continue;
                a[n.x][n.y]=-2;
                q.add(n);d.add(h+1);
            }
        }
        return 0;
    }


    int N(){
        Point q;
        int d=g<2?-1:1,x,y;
        System.arraycopy(a,0,b,0,a.length);
        q=S(b,c,g,d,r.nextInt((g%2<1?n:m)/2)+2,0);      
        if(q.x<1||q.y<1||q.x>m||q.y>n||q.equals(c)||b[q.x][q.y]!=0)
            return 0;
        x=q.x;
        y=q.y;
        if(g%2<1)
            y+=d;
        else
            x+=d;
        if(b[x][y]<0)
            return 0;
        b[q.x][q.y]=-1;
        b[x][y]=1;
        int f=r.nextInt(2)<1?-1:1;          
        g=g%2<1?(f<0?1:3):(g=f<0?0:2);
        c=q;
        System.arraycopy(b,0,a,0,a.length);
        z.add(g);
        return 1;
    }

    Point S(int[][]u,Point f,int w,int d,int q,int s){
        int i=1,x=f.x,y=f.y;
        for(;i<=q;i++){
            if(w%2<1)
                y=f.y+i*d;
            else
                x=f.x+i*d;
            if(e!=null&&e.x==x&&e.y==y)
                return e;
            if(y<0||y>n+1||x<0||x>m+1)
                return f;
            if(s<1&&u[x][y]<1)
                u[x][y]=-1;
            if(u[x][y]>0){
                if(w%2<1)
                    y-=d;
                else
                    x-=d;
                return new Point(x,y);
            }
        }
        if(w%2<1)
            return new Point(f.x,f.y+i*d);
        else
            return new Point(f.x+i*d,f.y);              
    }
}

Geobits
fuente

¿No podría while(o<3){...;o=...;}ser for(;o<3;o=...){...;}, guardar un byte?

Jonathan Frech

if(w%2<1)return new Point(f.x,f.y+i*d);else return new Point(f.x+i*d,f.y);-> return new Point(f.x+(w%2<1?0:i*d),f.y+(w%2<1?f.y:0));.

Jonathan Frech

Python, 235 206 185 176 caracteres

H,W,P=input()
t=''
for x in range(16):t+=".O"[(P>>x)%2]
for n in[t[1:],t[0],"O","...O"]+["."]*(H-5)+[".O.."]:print(n*W)[:W]
print"B 1\nR",(H,3)[-W%4/2],"\n",("URDR"*W)[:W+W%2]

Uso :

La entrada es a través de stdin del formulario [M, N, P].

$ echo [14, 17, 2] | python ice.py
O..............O.
.................
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR

Dijiste que los mapas tenían que ser diferentes para cada semilla P... y son:

$ echo [14, 17, 233] | python ice.py
..O.OOO..........
OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR
$ echo [14, 17, 65133] | python ice.py
.OO.OO..OOOOOOO.O
OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR

Y un ejemplo con un tamaño diferente:

$ echo [10, 15, 65133] | python ice.py
.OO.OO..OOOOOOO
OOOOOOOOOOOOOOO
OOOOOOOOOOOOOOO
...O...O...O...
...............
...............
...............
...............
...............
.O...O...O...O.
B 1
R 10
URDRURDRURDRURDR

Satisface todos los criterios objetivos suministrados:

Cada uno Plleva a un rompecabezas diferente
Solo hay una solución, por lo tanto, es la más corta.
La solución toma N + N%2medidas, que es al menosN
La solución siempre toma más que 2 (M + N)espacios totales

explicación :

Cada fila se construye repitiendo un cierto elemento de cadena Wveces y limitando la longitud a W(yo uso Hy en Wlugar de My N).

Las dos primeras filas dependen Ppara hacer que cada rompecabezas sea único. Básicamente, tenga Pen cuenta que cabe en un entero sin signo de 16 bits. Convierto Pa binario, usando .para 0 y Opara 1:

t=''
for x in range(16):t+=".O"[(P>>x)%2]

El primer elemento de fila es los últimos 15 bits, t[1:]mientras que la segunda fila de elementos es la primera bit, t[0]. No pude ponerlo todo en una fila porque el ancho mínimo es 15, que no encajaría en todos los 16 bits si P> 32767. Por lo tanto, las dos primeras filas representan de forma única cada uno de los valores posibles de P.

La tercera fila es un muro completo para que el valor de Pno afecte a la solución.

Luego sigue los elementos del laberinto real. Esta línea los imprime a todos, repitiéndolos hasta la tapa. El resultado es como ves arriba:

for n in[t[1:],t[0],"O","O..."]+["."]*(H-5)+["..O."]:print(n*W)[:W]

El resto solo estaba descubriendo cómo resolver el laberinto generado dinámicamente. Esto depende solo del ancho del laberinto. Noté que las soluciones, para un ancho dado, eran:

  W  | solution 
-----+---------
  1  | UR
  2  | UR
  3  | UR DR
  4  | UR DR 
  5  | UR DR UR
  6  | UR DR UR
  7  | UR DR UR DR
  8  | UR DR UR DR

etc Por lo tanto es sólo URDRrepite y se cortó en el lugar correcto, W+W%2.

print"B 1\nR",(H,3,3,H)[W%4],"\n",("URDR"*W)[:W+W%2]

Claudiu
fuente

¿Cómo funciona el número 33 de un entero?

masterX244

@ masterX244: Montones y montones de golf ... básicamente explotando la naturaleza repetitiva de la salida y haciendo algunos cálculos para asegurarse de que todo se alinea correctamente

Claudiu

sobre todo preguntándose cómo se hace la "aleatoriedad" (PS, el

voto negativo

@ masterX244: ah, te tengo. Agregaré una explicación

Claudiu

No lo dije en forma negativa. Es inteligente con seguridad, solo espero que los aspirantes a desarrolladores de juegos no usen esto para rompecabezas reales: p

Geobits