No Twitch Plays Pokémon , um dos obstáculos mais irritantes que se pode enfrentar é um quebra-cabeça de gelo, onde você deve viajar de um lugar para outro deslizando todo o caminho em uma direção até atingir uma parede ou uma pedra.

Sua tarefa é criar um programa que gere um quebra-cabeça de gelo aleatório e difícil.

Seu programa vai aceitar três números, M, N, e P, como entrada (com 10 <= M <= 30, 15 <= N <= 40e 0 <= P < 65536):

12 18

e produzirá:

• Um Mpor Ngrade consistindo em .e O, representando gelo e uma rocha, respectivamente.
• Um marcador de posição que representa de onde o quebra-cabeça é inserido. Este marcador de posição consiste de uma letra L, R, T, ouB , em representação da esquerda, direita, superior e inferior, seguida por um número que representa a posição (a partir da esquerda ou superior) em que o lado a ser introduzido a partir de.
• Um marcador de posição semelhante que representa de onde o quebra-cabeça sai.
• A solução mais curto para o quebra-cabeças, que consiste de uma sequência de L, R, U, e D, respectivamente.

Exemplo de saída:

..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 uma entrada Me N, a solução do quebra-cabeça deve ter pelo menos min(M, N)etapas e mover pelo menos 2 (M + N)espaços totais. (Para referência, o quebra-cabeça acima move-se um total de 12 passos, movendo-se 69 espaços.) O gerador de quebra-cabeças deve gerar um diferente Mpor Nquebra-cabeças com uma solução caminho diferente (isto é, uma sequência diferente de passos para cada solução) para cada semente P.

• Observe que o requisito de um caminho de solução diferente é evitar soluções que tentam gerar sistematicamente caminhos de rochas, como a solução de Claudiu aqui . Se houver dois ou três pares de soluções idênticas devido a peculiaridades da aleatoriedade, tudo bem, desde que o programa não esteja tentando intencionalmente gerar sistematicamente quebra-cabeças com a mesma sequência de movimentos.

O código mais curto para executar as ações acima vence.

Python, 672 548 caracteres, quebra-cabeças mais interessantes

Embora seguindo estritamente as regras, meu outro programa Python supera esse, decidi escrever um que gerasse quebra-cabeças mais interessantes de qualquer maneira. Aqui 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

Os níveis de recuo são espaço, tabulação, tabulação + espaço.

Amostras :

$ 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

Ele é usado Pcomo uma semente, para que cada Pum gere o mesmo quebra-cabeça e cada um deles Pseja extremamente provável que seja 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 razoavelmente rápido em tamanhos M=25,N=40anteriores, mas fica realmente lento. Teoricamente, deve funcionar M=30, N=40se você permitir que ele funcione por tempo suficiente. Escrevi manualmente na trilha aqui, já que é difícil de seguir - o programa apenas mostra o quebra-cabeça.

$ 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

Explicação :

O programa faz um loop, gerando uma posição inicial aleatória no topo, uma posição final aleatória na parte inferior e uma grade aleatória com a 12.5%chance de uma pedra em qualquer ponto. Em seguida, ele resolve o quebra-cabeça com uma busca pela primeira vez e, se a solução existe e é maior que min(H,W), imprime e sai.

Java - 2632

Enquanto admiro a pureza técnica da resposta de Claudiu , decidi tentar fazer quebra-cabeças um pouco mais difíceis;)

Etapas básicas (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

Também marquei cada ponto como 'nogo' enquanto deslizava. Se eu acabar em um ponto nogo (ou bem na frente de um que significaria que uma pedra estava indo para lá), é um passo inválido.

Então, basicamente, a idéia é gerar aleatoriamente muitos mapas e manter o primeiro válido. Pretendo tornar isso mais inteligente (retorno, etc), mas funciona bem agora. Também pode reduzir alguns códigos redundantes, veremos.

Como é, gera mapas pequenos (15x10) quase instantaneamente, mapas médios (30x20) em alguns segundos e grandes (40x30) em uma quantidade aleatória de tempo entre 20 segundos e 20 minutos, dependendo da semente. Ele testa entre 300k-500k mapas / segundo na minha máquina, dependendo do tamanho.

Nota lateral: Às vezes, os mapas não são muito difíceis, simplesmente porque existem apenas tantas pedras quanto degraus e, a menos que o degrau o leve a uma parede, na maioria das vezes há apenas uma opção se você quiser bater em uma pedra real. Corrigirei isso mais tarde, colocando rochas "aleatórias" em locais seguros depois que todas as etapas forem traçadas. Como as manchas nogo já estão marcadas, isso deve ser bem simples. Por enquanto, aproveite estes exemplos:

Saída mostrando diferentes tamanhos / sementes:

$ 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

Tamanho 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

Golfe:

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);}}

Com quebras de linha:

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);              
    }
}

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 :

A entrada é feita através do stdin do formulário [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

Você disse que os mapas tinham que ser diferentes para cada semente P... e eles são:

$ 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

E um exemplo com um tamanho 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

Satisfaz todos os critérios objetivos fornecidos:

• Cada um Pleva a um quebra-cabeça diferente
• Existe apenas uma solução, portanto, é a mais curta
• A solução toma N + N%2medidas, que são pelo menosN
• A solução sempre ocupa mais que o 2 (M + N)total de espaços

Explicação :

Cada linha é construída repetindo um determinado elemento de string Wvezes e limitando o comprimento a W(eu uso He em Wvez de Me N).

As duas primeiras linhas dependem Ppara tornar cada quebra-cabeça único. Basicamente, observe que Pse encaixa em um número inteiro não assinado de 16 bits. Converter Ppara binário, usando .para 0 e Opara 1:

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

O primeiro elemento da linha são os últimos 15 bits t[1:], enquanto o segundo elemento da linha é o primeiro bit t[0],. Não pude colocar tudo em uma linha porque a largura mínima é 15, que não caberia em todos os 16 bits se P> 32767. Portanto, as duas primeiras linhas representam exclusivamente cada um dos valores possíveis de P.

A terceira linha é uma parede completa, de modo que o valor de Pnão afeta a solução.

Em seguida, siga os elementos reais do labirinto. Esta linha imprime todos eles, repetindo-os até o limite. O resultado é como você vê acima:

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

O resto foi apenas descobrir como resolver o labirinto gerado dinamicamente. Isso depende apenas da largura do labirinto. Observei que as soluções, para uma determinada largura, eram:

  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

Por isso, é apenas URDRrepetido e cortado no lugar certo W+W%2,.

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