# 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. Jan 4, 2014 at 15:55
• You didn't specify that the random map must be different each time :) Jan 4, 2014 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 Jan 4, 2014 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? Jan 4, 2014 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? Jan 4, 2014 at 18:11

# 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 :) Jan 5, 2014 at 14:19
• Nice streamlining. And you print out the map right away. Jan 5, 2014 at 14:19
• And 〚 〛 for brackets (it is correct unicode symbols) Jan 5, 2014 at 14:26
• Can you explain the selection criterion, Norm[# - #2] & @@ # < 2 || # \[Union] u == u & Jan 5, 2014 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. Jan 5, 2014 at 15:44

### 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


## 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+)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


# Python 3 (695)

import random as r
if __name__=='__main__':
x=144
g,t=*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=*x
d=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<99:print('\n'+str(d))


Dijkstra !

## Example output:

0000202000
2011000111
0000002000
0101001000
0000100110
1110100101
0020101000
0011200000
1010101010
0000001000

6

• if __name__ == "__main__" and the corresponding indent isn't necessary Dec 1, 2020 at 1:30

# 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)". Jan 5, 2014 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 = 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]][past_path[-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. Jan 5, 2014 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. Jan 6, 2014 at 0:46

# JavaScript (541)

z=10
l=[]
p=[]
f=[]
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=0
l=99
Q=
for(o=Math.min;Q.length;){if(!P[s=Q.splice(0,1)]){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)>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, 314

import random,itertools as t
r=range(10)
a,d=[[random.choice(*6+*3+)for i in r]for j in r],eval([*10]*10)
a=a=d=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
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? Jan 5, 2014 at 2:53
• @WolframH Of course: en.wikipedia.org/wiki/… Jan 5, 2014 at 3:16
• I could make it print '\n'.join(map(str,a)); I did print a for the sake of golf. Jan 5, 2014 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). Jan 5, 2014 at 13:36
• Yeah. Actually 100 is overkill; 99 is all that is needed. Jan 5, 2014 at 22:22