В Twitch Plays Pokémon одним из самых раздражающих препятствий, с которыми можно столкнуться, является ледяная головоломка, где вы должны путешествовать из одного места в другое, скользя полностью в одном направлении, пока не столкнетесь ни со стеной, ни с валуном.

Ваша задача - создать программу, которая будет генерировать случайную сложную ледяную головоломку.

Ваша программа будет принимать три числа, M, Nи P, в качестве входных данных (с 10 <= M <= 30, 15 <= N <= 40и 0 <= P < 65536):

12 18

и выведет:

• MПо Nсетке , состоящей из .и O, представляющих лед и валуна соответственно.
• Маркер положения, представляющий, откуда вводится головоломка. Это положение маркера состоит из буквы L, R, TилиB , представляющие собой слева, справа, сверху и снизу, а затем число , представляющее положение (слева или сверху) на той стороне , чтобы ввести с.
• Аналогичный маркер позиции, представляющий, из чего выходит головоломка.
• Кратчайшее решение головоломки, состоящий из последовательности L, R, Uи Dсоответственно.

Пример вывода:

..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.)

Для ввода Mи N, решение головоломки должно иметь как минимум min(M, N)шаги и перемещаться как минимум на 2 (M + N)все места. (Для справки, выше головоломка двигается в общей сложности 12 шагов, перемещение 69 мест.) Ваша головоломка генератор должен генерировать различный Mпо Nголоволомке с другим путем решения (то есть другая последовательность шагов для каждого раствора) для каждого семени P.

• Обратите внимание, что требование другого пути решения состоит в том, чтобы избегать решений, которые пытаются систематически генерировать пути породы, как решение Клавдия здесь . Если есть две или три пары идентичных решений из-за причуд в случайности, это будет хорошо, если программа не намеренно пытается систематически генерировать головоломки с одинаковой последовательностью ходов.

Самый короткий код, чтобы сделать вышеупомянутые победы.

Python, 672 548 символов, более интересные загадки

Несмотря на то, что моя программа на Python идет строго по правилам, она превосходит эту, но я решил написать такую, которая в любом случае породила бы больше интересных головоломок. Вот:

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

Уровни отступа: пробел, табуляция, табуляция + пробел.

Образцы :

$ 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

Он использует Pв качестве начального числа, поэтому каждый из них Pбудет генерировать одну и ту же головоломку, и каждая из Pних с большой вероятностью будет отличаться:

$ 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

Он работает достаточно быстро до размеров, M=25,N=40но в прошлом он становится действительно медленным. Теоретически это должно работать, M=30, N=40если вы позволите ему работать достаточно долго. Я написал здесь след вручную, потому что за ним трудно следить - программа просто выводит головоломку.

$ 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

Пояснение :

Программа зацикливается, генерируя случайную начальную позицию сверху, случайную конечную позицию внизу и случайную сетку с 12.5%шансом на валун в любом заданном месте. Затем он решает головоломку с помощью поиска в ширину, и, если решение существует и больше, чем min(H,W), оно печатает и выходит.

Ява - 2632

Хотя я восхищаюсь технической чистотой ответа Клавдия , я решил попробовать свои силы в создании немного более сложных головоломок;)

Основные шаги (довольно просто):

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

Я также отмечаю каждое пятно как «nogo», когда я скользлю. Если я окажусь в каком-то месте (или прямо перед тем, что означало бы, что там идет камень), это неверный шаг.

Итак, в основном идея состоит в том, чтобы случайным образом генерировать много карт и сохранять первую действительную. Я планирую сделать это умнее (возврат и т. Д.), Но сейчас он работает нормально. Это может также сократить некоторый избыточный код, мы увидим.

Как таковой, он генерирует маленькие карты (15x10) почти мгновенно, средние (30x20) карты за пару секунд, а большие (40x30) в произвольное количество времени от 20 секунд до 20 минут, в зависимости от начального числа. Он тестирует между 300k-500k карт в секунду на моей машине, в зависимости от размера.

Примечание: иногда карты не слишком сложны, просто потому, что в них только столько камней, сколько шагов, и если шаг не приведет вас к стене, в большинстве случаев есть только один вариант, если вы хотите ударить по настоящему камню. Я исправлю это позже, поместив «случайные» камни в безопасные места после прохождения всех этапов. Так как пятна nogo уже отмечены, это должно быть довольно просто. А пока просто наслаждайтесь этими примерами:

Вывод, показывающий разные размеры / семена:

$ 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

Максимальный размер 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

Golfed:

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

С переносами строк:

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 символов

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]

Использование :

Ввод осуществляется через стандартный ввод формы [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

Вы сказали, что карты должны быть разными для каждого семени P... и они:

$ 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

И пример с другим размером:

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

Удовлетворяет всем поставленным объективным критериям:

• Каждый Pведет к другой загадке
• Есть только одно решение, поэтому оно самое короткое
• Решение принимает N + N%2меры, по крайней мере,N
• Решение всегда занимает больше 2 (M + N)места

Пояснение :

Каждая строка создается путем повторения определенного времени строкового элемента Wи ограничения длины W(я использую Hи Wвместо Mи N).

Первые две строки зависят от того, Pчтобы каждая головоломка была уникальной. Обратите внимание, что Pвписывается в 16-разрядное целое число без знака. Я конвертирую Pв двоичный файл, используя .для 0 и Oдля 1:

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

Первый элемент строки - это последние 15 битов, t[1:]а второй элемент строки - это 1-й бит t[0]. Я не могу поместить все это в одну строку, потому что минимальная ширина равна 15, что не подходит всем 16 битам, если P> 32767. Таким образом, первые две строки однозначно представляют каждое из возможных значений P.

Третий ряд представляет собой полную стену, поэтому значение Pне влияет на решение.

Затем следуйте фактическим элементам лабиринта. Эта строка печатает их все, повторяя их до колпачка. Результат, как вы видите выше:

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

Остальные просто выясняли, как решить динамически генерируемый лабиринт. Это зависит только от ширины лабиринта. Я отметил, что решения для данной ширины были:

  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

и т.д. Следовательно, это просто URDRповторяется и обрезается в нужном месте W+W%2.

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