Portal Maze Shortest Path

Your goal is to write a program that creates a random 10x10 map using 0, 1, and 2, and finds the shortest path from top-left to bottom-right, assuming that:

0 represents a grass field: anyone can walk on it;
1 represents a wall: you cannot cross it;
2 represents a portal: when entering a portal, you can move to any other portal in the map.

Specs:

• The top-left element and the bottom-right one must be 0;
• When creating the random map, every field should have 60% chance of being a 0, 30% of being a 1 and 10% of being a 2;
• You can move in any adjacent field (even diagonal ones);
• Your program should output the map and the number of steps of the shortest path;
• If there isn't a valid path that leads to the bottom-right field, your program should output the map only;
• You can use any resource you'd like to;
• Shortest code wins.

Calculating steps:
A step is an actual movement; every time you change field, you increment the counter.

Output:

0000100200
0100100010
1000000111
0002001000
1111100020
0001111111
0001001000
0020001111
1100110000
0000020100

9

• Can't we just produce the program for the shortest path? Generating is another question. – Mikaël Mayer Jan 4 '14 at 15:55
• You didn't specify that the random map must be different each time :) – marinus Jan 4 '14 at 15:59
• @marinus LoooL! Well, in the specs I wrote the generating chances, so I guess that writing a standard map with 60 0, 30 1 and 10 2 won't be a right solution :P – Vereos Jan 4 '14 at 16:04
• @MikaëlMayer I guess you've got a point, but I think it would be more challenging like this. Am I wrong? – Vereos Jan 4 '14 at 16:05
• As this is a code-golf question, the winning criteria is shortest code. What happens if that code is really slow and takes centuries to run? – Victor Stafusa Jan 4 '14 at 18:11

GolfScript, 182 characters

;0{41 3 10rand?/3%}98*0]10/n*n+.[12n*.]*.0{[/(,\+{,)1$+}*;]}:K~\2K:P+${[.12=(]}%.,,{.{\1==}+2$\,{~;.P?0<!P*3,{10+}%1+{2$1$-\3$+}%+~}%{2$~0<@@?-1>&2$[~;@)](\@if}++%}/-1=1=.0<{;}*


Examples:

0000001002
1010000001
0011010000
2001020000
0100100011
0110100000
0100000100
0010002010
0100110000
0012000210
6

0000100000
0100000001
1100000000
1011010000
0010001100
0101010200
0000200012
1100100110
0000011001
2201010000
11

0012010000
1000100122
0000001000
0111010100
0010012001
1020100110
1010101000
0102011111
0100100010
2102100110


Mathematica (344)

Bonus: highlighting of the path

n = 10;
m = RandomChoice[{6, 3, 1} -> {0, 1, 2}, {n, n}];
m[[1, 1]] = m[[n, n]] = 0;

p = FindShortestPath[Graph@DeleteDuplicates@Join[Cases[#, Rule[{ij__}, {k_, l_}] /;
0 < k <= n && 0 < l <= n && m[[ij]] != 1 && m[[k, l]] != 1] &@
Flatten@Table[{i, j} -> {i, j} + d, {i, n}, {j, n}, {d, Tuples[{-1, 0, 1}, 2]}],
Rule @@@ Tuples[Position[m, 2], 2]], {1, 1}, {n, n}];

Grid@MapAt[Style[#, Red] &, m, p]
If[# > 0, #-1] &@Length[p]


I create the graph of all possible movies to neighbor vertices and add all possible "teleports".

Mathematica, 208 202 chars

Base on David Carraher and ybeltukov's solutions. And thanks to ybeltukov's suggestion.

m=RandomChoice[{6,3,1}->{0,1,2},n={10,10}];m〚1,1〛=m〚10,10〛=0;Grid@m
{s,u}=m~Position~#&/@{0,2};If[#<∞,#]&@GraphDistance[Graph[{n/n,n},#<->#2&@@@Select[Subsets[s⋃u,{2}],Norm[#-#2]&@@#<2||#⋃u==u&]],n/n,n]

• Nice, +1! Further optimization: n/n instead of n/10 :) – ybeltukov Jan 5 '14 at 14:19
• Nice streamlining. And you print out the map right away. – DavidC Jan 5 '14 at 14:19
• And 〚 〛 for brackets (it is correct unicode symbols) – ybeltukov Jan 5 '14 at 14:26
• Can you explain the selection criterion, Norm[# - #2] & @@ # < 2 || # \[Union] u == u & – DavidC Jan 5 '14 at 14:30
• @DavidCarraher Norm[# - #2] & @@ # < 2 means the distance between two points is less then 2, so they must be adjacent. # ⋃ u == u means both points are in u. – alephalpha Jan 5 '14 at 15:44

Python 3, 279

Some Dijkstra variant. Ugly, but golfed as much as I could...

from random import*
R=range(10)
A={(i,j):choice([0,0,1]*3+[2])for i in R for j in R}
A[0,0]=A[9,9]=0
for y in R:print(*(A[x,y]for x in R))
S=[(0,0,0,0)]
for x,y,a,c in S:A[x,y]=1;x*y-81or print(c)+exit();S+=[(X,Y,b,c+1)for(X,Y),b in A.items()if a+b>3or~-b and-2<X-x<2and-2<Y-y<2]


Sample Run

0 1 1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 1 0 0
0 1 2 1 2 1 0 0 1 0
0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 1
1 0 0 1 0 0 1 1 1 0
0 0 0 0 1 0 0 0 0 1
0 1 2 1 0 1 1 0 0 0
10


Mathematica 316 279 275

The basic object is a 10x10 array with approximately 60 0's, 30 1's and 10 2's. The array is used to modify a 10x10 GridGraph, with all edges connected. Those nodes which correspond to cells holding 1 in the array are removed from the graph. Those nodes "holding 2's" are all connected to each other. Then the Shortest Path is sought between vertex 1 and vertex 100. If such a path does not exist, the map is returned; if such a path does exist, the map and the shortest path length are shown.

m = Join[{0}, RandomChoice[{6, 3, 1} -> {0, 1, 2}, 98], {0}];
{s,t,u}=(Flatten@Position[m,#]&/@{0,1,2});
g=Graph@Union[EdgeList[VertexDelete[GridGraph@{10,10},t]],Subsets[u,{2}]
/.{a_,b_}:>a \[UndirectedEdge] b];
If[IntegerQ@GraphDistance[g,1,100],{w=Grid@Partition[m,10],
Length@FindShortestPath[g,1,100]-1},w]


Sample Run:

• "You can move in any adjacent field (even diagonal ones)". – alephalpha Jan 5 '14 at 10:39

Python (1923)

Backtracking Search

Admittedly not the shortest or the most efficient, although there is some memoization present.

import random
l = 10
map = [
[(lambda i: 0 if i < 7 else 1 if i < 10 else 2)(random.randint(1, 10))
for i in range(0, l)]
for i in range(0, l)
]
map[0][0] = map[l-1][l-1] = 0
print "\n".join([" ".join([str(i) for i in x]) for x in map])

paths = {}
def step(past_path, x, y):
shortest = float("inf")
shortest_path = []

current_path = past_path + [(x, y)]
pos = map[x][y]
if (x, y) != (0, 0):
past_pos = map[past_path[-1][0]][past_path[-1][1]]

if (((x, y) in paths or str(current_path) in paths)
and (pos != 2 or past_pos == 2)):
return paths[(x, y)]
elif x == l-1 and y == l-1:
return ([(x, y)], 1)

if pos == 1:
return (shortest_path, shortest)
if pos == 2 and past_pos != 2:
for i2 in range(0, l):
for j2 in range(0, l):
pos2 = map[i2][j2]
if pos2 == 2 and (i2, j2) not in current_path:
path, dist = step(current_path, i2, j2)
if dist < shortest and (x, y) not in path:
shortest = dist
shortest_path = path
else:
for i in range(x - 1, x + 2):
for j in range(y - 1, y + 2):
if i in range(0, l) and j in range(0, l):
pos = map[i][j]
if pos in [0, 2] and (i, j) not in current_path:
path, dist = step(current_path, i, j)
if dist < shortest and (x, y) not in path:
shortest = dist
shortest_path = path
dist = 1 + shortest
path = [(x, y)] + shortest_path
if dist != float("inf"):
paths[(x, y)] = (path, dist)
else:
paths[str(current_path)] = (path, dist)
return (path, dist)

p, d = step([], 0, 0)
if d != float("inf"):
print p, d

• Wow, now that's a character count for a code golf! I think your ball landed in the rough. – Tim Seguine Jan 5 '14 at 21:00
• Haha yeah I didn't bother golfing the code or trying to find the shortest implementation, but put the character count up so people would know they could ignore this solution. It just seemed like a fun problem. – vinod Jan 6 '14 at 0:46

JavaScript (541)

z=10
l=[[0]]
p=[]
f=[[0]]
P=[]
for(i=0;++i<z;)l[i]=[],f[i]=[]
for(i=0;++i<99;)P[i]=0,l[i/z|0][i%z]=99,f[i/z|0][i%z]=(m=Math.random(),m<=.6?0:m<=.9?1:(p.push(i),2))
f[9][9]=0
l[9][9]=99
Q=[0]
for(o=Math.min;Q.length;){if(!P[s=Q.splice(0,1)[0]]){P[s]=1
for(i=-2;++i<2;)for(j=-2;++j<2;){a=i+s/z|0,b=j+s%z
if(!(a<0||a>9||b<0||b>9)){q=l[a][b]=o(l[s/z|0][s%z]+1,l[a][b])
if(f[a][b]>1){Q=Q.concat(p)
for(m=0;t=p[m];m++)l[t/z|0][t%z]=o(l[t/z|0][t%z],q+1)}!f[a][b]?Q.push(a*z+b):''}}}}for(i=0;i<z;)console.log(f[i++])
console.log((k=l[9][9])>98?"":k)


Graph generation happens in the first five lines. f contains the fields, p holds the portals. The actual search is implemented via BFS.

Example output:

> node maze.js
[ 0, 0, 0, 0, 1, 0, 0, 0, 2, 0 ]
[ 0, 1, 1, 0, 0, 1, 0, 0, 0, 2 ]
[ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0 ]
[ 1, 1, 1, 0, 2, 2, 0, 1, 0, 1 ]
[ 1, 1, 0, 0, 0, 0, 1, 0, 0, 0 ]
[ 1, 1, 0, 0, 1, 0, 0, 0, 1, 1 ]
[ 0, 0, 1, 1, 0, 1, 0, 0, 2, 0 ]
[ 0, 0, 1, 0, 1, 2, 0, 1, 0, 1 ]
[ 1, 0, 0, 0, 1, 1, 1, 0, 1, 1 ]
[ 0, 1, 0, 0, 0, 0, 0, 0, 1, 0 ]

>node maze.js
[ 0, 0, 0, 0, 1, 0, 1, 0, 0, 1 ]
[ 0, 2, 0, 1, 1, 2, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
[ 0, 0, 0, 1, 2, 1, 1, 0, 1, 0 ]
[ 2, 0, 1, 0, 2, 2, 2, 0, 1, 0 ]
[ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0 ]
[ 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 ]
[ 0, 1, 2, 0, 0, 0, 0, 0, 0, 1 ]
[ 1, 0, 2, 1, 0, 1, 2, 0, 0, 1 ]
[ 0, 1, 2, 0, 0, 0, 0, 0, 0, 0 ]
5

Python 3 (695)

import random as r
if __name__=='__main__':
x=144
g,t=[1]*x,[]
p=lambda i:12<i<131 and 0<i%12<11
for i in range(x):
if p(i):
v=r.random()
g[i]=int((v<=0.6 or i in (13,130)) and .1 or v<=0.9 and 1 or 2)
if g[i]>1:t+=[i]
print(g[i],end='\n' if i%12==10 else '')
d=[99]*x
d[13]=0
n = list(range(x))
m = lambda i:[i-1,i+1,i-12,i+12,i-13,i+11,i+11,i+13]
while n:
v = min(n,key=lambda x:d[x])
n.remove(v)
for s in m(v)+(t if g[v]==2 else []):
if p(s) and g[s]!=1 and d[v]+(g[s]+g[v]<4)<d[s]:
d[s]=d[v]+(g[s]+g[v]<3)
if d[130]<99:print('\n'+str(d[130]))


Dijkstra !

Example output:

0000202000
2011000111
0000002000
0101001000
0000100110
1110100101
0020101000
0011200000
1010101010
0000001000

6


Python, 314

import random,itertools as t
r=range(10)
a,d=[[random.choice([0]*6+[1]*3+[2])for i in r]for j in r],eval([[99]*10]*10)
a[0][0]=a[9][9]=d[0][0]=0
for q,i,j,m,n in t.product(r*10,r,r,r,r):
if a[m][n]!=1and abs(m-i)<2and abs(n-j)<2or a[i][j]==a[m][n]==2:d[m][n]=min(d[i][j]+1,d[m][n])
w=d[9][9]
print a,w*(w!=99)


It's a disgusting implementation of Bellman-Ford. This algorithm is O(n^6)! (Which is okay for n=10)

• The map looks really ugly. Does this work if more than 10 steps are needed? – Reinstate Monica Jan 5 '14 at 2:53
• @WolframH Of course: en.wikipedia.org/wiki/… – Sanjeev Murty Jan 5 '14 at 3:16
• I could make it print '\n'.join(map(str,a)); I did print a for the sake of golf. – Sanjeev Murty Jan 5 '14 at 3:19
• I didn't doubt the correctness of the algorithm :-). I just hadn't realized that you loop often enough (which you do; r*10` has 100 elements). – Reinstate Monica Jan 5 '14 at 13:36
• Yeah. Actually 100 is overkill; 99 is all that is needed. – Sanjeev Murty Jan 5 '14 at 22:22