14
\$\begingroup\$

In Twitch Plays Pokémon, one of the most annoying obstacles one can face is an ice puzzle, where you must travel from one place to another by sliding all the way in one direction until you either hit a wall or a boulder.

Your task is to build a program that will generate a random difficult ice puzzle.

Your program will accept three numbers, M, N, and P, as input (with 10 <= M <= 30, 15 <= N <= 40, and 0 <= P < 65536):

12 18

and will output:

  • An M by N grid consisting of . and O, representing ice and a boulder respectively.
  • A position marker representing where the puzzle is entered from. This position marker consists of a letter L, R, T, or B, representing left, right, top, and bottom, followed by a number representing the position (from the left or top) on that side to be entered from.
  • A similar position marker representing where the puzzle is exited out of.
  • The shortest solution to the puzzle, consisting of a sequence of L, R, U, and D respectively.

Example output:

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

For an input M and N, the solution to the puzzle must have at least min(M, N) steps and move at least 2 (M + N) total spaces. (For reference, the above puzzle moves a total of 12 steps, moving 69 spaces.) Your puzzle generator must generate a different M by N puzzle with a different solution path (i.e. a different sequence of steps for each solution) for each seed P.

  • Note that the requirement of a different solution path is to avoid solutions that try to systematically generate rock paths, like Claudiu's solution here. If there are two or three pairs of identical solutions due to quirks in randomness, that will be okay, as long as the program is not intentionally trying to systematically generate puzzles with the same sequence of moves.

The shortest code to do the above wins.

\$\endgroup\$
15
  • 2
    \$\begingroup\$ I cannot understand the objective: "you must travel from one place to another by sliding all the way in one direction until you either hit a wall or a boulder." Is it good to hit walls or boulders? Where do you aim to go from the start? If you hit a boulder does the game end? What happens when you hit a wall? Is it just me or are the directions unclear? \$\endgroup\$
    – DavidC
    Mar 6, 2014 at 21:21
  • 3
    \$\begingroup\$ Oh, old memories of Pokémon Gold and Silver here. Find the exit, get HM07 and go to Blackthorn City. \$\endgroup\$ Mar 7, 2014 at 0:44
  • 4
    \$\begingroup\$ This reminds me of the ice levels in Chip's Challenge. \$\endgroup\$ Mar 7, 2014 at 5:57
  • 2
    \$\begingroup\$ Why not use > and < (or any character) for the enter and the exit? The puzzles will be easier to read. \$\endgroup\$
    – A.L
    Mar 11, 2014 at 1:06
  • 1
    \$\begingroup\$ @n.1: the entrance & exit are actually off the grid. that being said there'll never be a rock right in front of it so it could be counted as a blank spot, and can use <>v^ to point the direction in case of ambiguity (i.e. entrance on a corner). \$\endgroup\$
    – Claudiu
    Mar 11, 2014 at 1:54

3 Answers 3

6
\$\begingroup\$

Python, 672 548 characters, more interesting puzzles

Although going strictly by the rules, my other Python program beats this one, I decided to write one that would generate more interesting puzzles anyway. Here it is:

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

Indentation levels are space, tab, tab+space.

Samples:

$ 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

It uses P as a seed, so each P will generate the same puzzle, and each different P is exceedingly likely to be different:

$ 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

It works reasonably fast up to sizes of M=25,N=40 but past that it gets really slow. It should theoretically work for M=30, N=40 if you let it run long enough. I've manually written in the trail here since it is hard to follow - the program just outputs the puzzle.

$ 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

Explanation:

The program loops, generating a random start position on the top, a random end position on the bottom, and a random grid with a 12.5% chance for a boulder on any given spot. It then solves the puzzle with a breadth-first-search and if the solution exists and is bigger than min(H,W), it prints and exits.

\$\endgroup\$
5
\$\begingroup\$

Python, 235 206 185 176 characters

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]

Usage:

Input is through stdin of the form [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

You said the maps had to be different for each seed P... and they are:

$ 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

And an example w/ a different size:

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

Satisfies all the supplied objective criteria:

  • Each P leads to a different puzzle
  • There is only one solution, thus it is the shortest
  • The solution takes N + N%2 steps, which is at least N
  • The solution always takes more than 2 (M + N) total spaces

Explanation:

Each row is constructed by repeating a certain string element W times and limiting the length to W (I use H and W instead of M and N).

The first two rows depend on P to make each puzzle unique. Basically, note that P fits into a 16-bit unsigned integer. I convert P to binary, using . for 0 and O for 1:

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

The first row element is the last 15 bits, t[1:], while the second row element is the 1st bit, t[0]. I couldn't put it all on one row because the minimum width is 15, which wouldn't fit all 16 bits if P > 32767. Thus the first two rows uniquely represent each of the possible values of P.

The third row is a full wall so that the value of P doesn't affect the solution.

Then follow the actual maze elements. This line prints them all, repeating them up to the cap. The result is as you see above:

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

The rest was just figuring out how to solve the dynamically generated maze. This depends only on the width of the maze. I noted that the solutions, for a given width, were:

  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. Hence it's just URDR repeated and cut off at the right place, W+W%2.

print"B 1\nR",(H,3,3,H)[W%4],"\n",("URDR"*W)[:W+W%2]
\$\endgroup\$
12
  • 1
    \$\begingroup\$ how to the 33th bit of a integer does that work? \$\endgroup\$
    – masterX244
    Mar 10, 2014 at 20:58
  • \$\begingroup\$ @masterX244: Lots and lots of golfing... basically exploiting the repetitive nature of the output and doing some maths to make sure it all lines up properly \$\endgroup\$
    – Claudiu
    Mar 10, 2014 at 21:16
  • \$\begingroup\$ mostly wondering about how the "randomness" is made (PS the downvote was not from me) \$\endgroup\$
    – masterX244
    Mar 10, 2014 at 21:42
  • \$\begingroup\$ @masterX244: ah gotcha. I'll add an explanation \$\endgroup\$
    – Claudiu
    Mar 10, 2014 at 21:43
  • 1
    \$\begingroup\$ I didn't mean it in a negative way. It's clever for sure, I just hope aspiring game devs don't use this for actual puzzles :p \$\endgroup\$
    – Geobits
    Mar 10, 2014 at 22:44
4
\$\begingroup\$

Java - 2632

While I admire the technical purity of Claudiu's answer, I decided to try my hand at making slightly more difficult puzzles ;)

Basic steps (pretty simple):

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

I also mark each spot as 'nogo' as I'm sliding. If I end up on a nogo spot(or right in front of one which would mean a rock was going there), it's an invalid step.

So, basically the idea is to randomly generate a lot of maps, and keep the first one that is valid. I plan to make this smarter(backtracking, etc), but it works fine right now. It might also cut down on some redundant code, we'll see.

As it is, it generates small maps(15x10) almost instantly, medium(30x20) maps in a couple seconds, and large(40x30) in some random amount of time between 20 seconds and 20 minutes, depending on seed. It tests between 300k-500k maps/second on my machine, depending on size.

Side note: Sometimes the maps aren't too hard, simply because there are only as many rocks as steps, and unless the step takes you to a wall, most times there's only one option if you want to hit an actual rock. I'll fix that later by placing "random" rocks in safe spots after all the steps are drawn. Since nogo spots are already marked, that should be pretty simple. For now, just enjoy these examples:

Output showing different sizes/seeds:

$ 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

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

With line breaks:

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);              
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Could not while(o<3){...;o=...;} be for(;o<3;o=...){...;}, saving one byte? \$\endgroup\$ Jan 26, 2018 at 15:39
  • \$\begingroup\$ 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));. \$\endgroup\$ Jan 26, 2018 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.