9
\$\begingroup\$

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 # . . . . .
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Can you move to and from S and X in any direction? Is the maze always solvable? \$\endgroup\$ Mar 12, 2015 at 8:20
  • \$\begingroup\$ 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? \$\endgroup\$ Mar 12, 2015 at 13:36
  • 1
    \$\begingroup\$ @Calvin Yes, you you may move to and from S and X in any direction. The maze is assumed to be solvable. \$\endgroup\$
    – Luke D
    Mar 12, 2015 at 13:44
  • 1
    \$\begingroup\$ @IImari Yes, all rows have the same length, and yes, a "digit" is a single digit from 0 to 9 inclusive. \$\endgroup\$
    – Luke D
    Mar 12, 2015 at 13:47

2 Answers 2

4
\$\begingroup\$

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

Code with comments:

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
    }
}
\$\endgroup\$
3
\$\begingroup\$

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

  return r(o, f, 0) // start with a fake prev value
}

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  
\$\endgroup\$
4
  • \$\begingroup\$ We seem to share a mutual code unfathomability. \$\endgroup\$
    – seequ
    Mar 12, 2015 at 21:20
  • 1
    \$\begingroup\$ @Sieg why, isn't it crystal clear? I'll add an explanation tomorrow \$\endgroup\$
    – edc65
    Mar 12, 2015 at 21:32
  • \$\begingroup\$ @Sieg more fathomable? \$\endgroup\$
    – edc65
    Mar 13, 2015 at 0:14
  • \$\begingroup\$ Fathomable indeed. \$\endgroup\$
    – seequ
    Mar 13, 2015 at 5:40

Your Answer

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

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