# Downhill Maze Solver

A downhill maze is given as a series of rows of space separated digits from 0 to 9 inclusive, plus one "S" and one "X", where the S denotes the start and the X denotes the finish. In a downhill maze, you may only go to a space that is adjacent to you to the north, south, east, or west (no diagonals), and you may only go to spaces with a value less than or equal to the value you are currently on.

The program should output a path to navigate through the maze in the same format as the input, only all traversed spaces should have a "." in them, and all unvisited spaces should have a "#" in them. The starting and ending cells should also keep their "S" and "X", respectively. You can assume there is always a solution to the maze.

Example input:

3 3 3 3 2 1 S 8 9
3 1 1 3 3 0 6 8 7
1 2 2 4 3 2 5 9 7
1 2 1 5 4 3 4 4 6
1 1 X 6 4 4 5 5 5

Example output:

. . . . # # S . #
. # # . . # # . .
. # # # . # # # .
. # # # . # # # .
. . X # . . . . .
• Can you move to and from S and X in any direction? Is the maze always solvable? Mar 12 '15 at 8:20
• Also, can we assume that all the rows have the same length? And, just to clarify, a "digit" means a single decimal digit from 0 to 9 inclusive, right? Mar 12 '15 at 13:36
• @Calvin Yes, you you may move to and from S and X in any direction. The maze is assumed to be solvable. Mar 12 '15 at 13:44
• @IImari Yes, all rows have the same length, and yes, a "digit" is a single digit from 0 to 9 inclusive. Mar 12 '15 at 13:47

# C# - 463

Accepts input via STDIN, and should produce an optimal path, tested for the given test case, but not otherwise. Assumes there is always a solution.

I'm in a bit of a hurry, I have a deadline in 7 hours, but this just looked like too much fun to miss out on. I'm also out of practice. It could be very embarrassing if this goes wrong, but it's reasonably golfed.

using C=System.Console;class P{static void Main(){var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+');int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L;var K=new int[L];for(K[s]=s+2;j-->0;)for(i=0;i<L;i+=2){System.Action<int>M=z=>{if((z+=i)>=0&z<L&&S[z]<=S[i]&K[z]<1&K[i]>0&(i%w==z%w|i/w==z/w))K[z]=i+1;};M(2);M(-2);M(w);M(-w);}for(w=e;w!=s+1;w=i){i=K[w]-1;K[w]=-1;}for(;++j<L;)C.Write(j%2<1?K[j]<0?j==s?'S':j==e?'X':'.':'#':S[j]);}}

using C=System.Console;

class P
{
static void Main()
{
var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+'); // read in the map, replace X with + because + < 0
int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L; // find start, end, width, length

var K=new int[L]; // this stores how we got to each point as loc+1 (0 means we havn't visited it)

for(K[s]=s+2; // can't risk this being 0
j-->0;) // do L passes
for(i=0;i<L;i+=2) // each pass, look at every location
{
// if a whole load of bouds checks, point new location (i+z) at i
System.Action<int>M=z=>{if((z+=i)>=0&z<L&&S[z]<=S[i]&K[z]<1&K[i]>0&(i%w==z%w|i/w==z/w))K[z]=i+1;};
// try and move in each direction
M(2);
M(-2);
M(w);
M(-w);
}

for(w=e;w!=s+1;w=i) // find route back
{
i=K[w]-1; // previous location
K[w]=-1; // set this so we know we've visited it
}

for(;++j<L;) // print out result
C.Write(j%2<1?K[j]<0?j==s?'S':j==e?'X':'.':'#':S[j]); // if K < 0, we visit it, otherwise we don't
}
}

# JavaScript (ES6) 219

A function returning true or false. The solution (if found) is output on the console. It does not try to find an optimal solution.

f=o=>(r=(m,p,w=0,v=m[p])=>
v>':'
?console.log(' '+m.map(v=>v<0?'#':v,m[f]='X').join(' '))
:v<=w&&[1,-1,y,-y].some(d=>r([...m],d+p,v),m[p]='.')
)(o.match(/[^ ]/g).map((v,p)=>v>'S'?(f=p,0):v>':'?v:v<'0'?(y=y||~p,v):~v,y=0),f)

Ungolfed to death and explained more than needed

f=o=>{
var r = ( // recursive search function
m, // maze array (copy of)
p, // current position
w  // value at previous position
)=>
{
var v = m[p]; // get value at current position
if (v == 'S') // if 'S', solution found, output and return true
{
m[f] = 'X'; // put again 'X' at finish position
m = m.map(v => { // scan array to obtain '#'
if (v < 0) // a numeric value not touched during search
return '#'
else
return v
}).join(' '); // array to string again, with added blanks (maybe too many)
console.log(' '+m) // to balance ' '
return true; // return false will continue the search and find all possible solutions
}
if (v <= w) // search go on if current value <= previous (if numeric, they both are negative)
{
m[p]='.'; // mark current position
return [1,-1,y,-y].some(d=>r([...m], d+p, v)) // scan in all directions
}
// no more paths, return false and backtrack
return false
}

var f, // finish position (but it is the start of the search)
y = 0; // offset to next/prev row
o = o.match(/[^ ]/g) // string to char array, removing ' 's
.map((v,p) => // array scan to find f and y, and transform numeric chars to numbers
{
if (v > 'S') // check if 'X'
{
f = p;
return 0; // 'X' position mapped to min value
}
if (v > ':') // check if 'S'
return v; // no change
if (v < '0') // check if newline
{
if (!y) y = ~p; // position of first newline used to find y offset
return v; // no change
}
return ~v; // map numeric v to -v-1 so have range (-1..-10)
})

}

Test in Firefox/FireBug console

f('3 3 3 3 2 1 S 8 9\n3 1 1 3 3 0 6 8 7\n1 2 2 4 3 2 5 9 7\n1 2 1 5 4 3 4 4 6\n1 1 X 6 4 4 5 5 5')

Output

. . . . # # S . #
. # # . . # # . .
. # # # . # # # .
. # # # . # # # .
. . X # . . . . .

true
• We seem to share a mutual code unfathomability. Mar 12 '15 at 21:20
• @Sieg why, isn't it crystal clear? I'll add an explanation tomorrow Mar 12 '15 at 21:32
• @Sieg more fathomable? Mar 13 '15 at 0:14
• Fathomable indeed. Mar 13 '15 at 5:40