14
\$\begingroup\$

You are a taxicab driver in San Francisco. As is typical of taxicab drivers, you are navigating a grid where the only valid directions you can move are the left, right, up, and down. However, San Fransisco is very hilly so the distance between two adjacent intersections is not necessarily the same. More specifically, the distance between an intersection at altitude a and an adjacent intersection at altitude b would be 1 + |a - b|. Your goal is to find all the shortest paths from your origin at the top left of the map to your destination at the bottom right.

Input

A two-dimensional grid of integer altitudes in whichever format is most convenient (two-dimensional array, one-dimensional array with width and/or height, etc.).

Output

A sequence of directions to travel to arrive at the bottom right corner of the input from the top left in the shortest distance possible given the distance between two adjacent intersections of altitudes a and b is given by the formula 1 + |a - b|. If there are multiple solutions output all solutions.

Though I use U, D, L, and R for up, down, left, and right in the examples below your program may use any four distinct strings to represent the directions so long as it is consistent with them in and across all inputs.

Examples

Input:
0 3 0 0 0
0 2 0 2 0
0 0 0 3 0
Output:
D D R R U U R R D D

Input:
3
Output:
<empty>

Input:
11 11 11
11 11 11
11 11 11
Output:
R R D D
R D R D
R D D R
D R R D
D R D R
D D R R

Input:
7 8 1 -1 0
4 4 6 -1 7
3 4 4  2 8
2 5 2 -1 2
Output:
D R D R R D R
D R D R D R R

This is so the answer with the shortest byte count wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Are the altitudes always less than 10 ? (they are on the examples, but will they always be?) \$\endgroup\$ – Dada Nov 11 '16 at 22:00
  • \$\begingroup\$ @Dada the altitudes are not necessarily less than 10 (they can also be negative), I have updated the examples accordingly. \$\endgroup\$ – 0 ' Nov 11 '16 at 23:00
  • \$\begingroup\$ when i saw that this post was active i was suuuuuuper excited - i thought someone had posted an answer in taxi ! maybe one day \$\endgroup\$ – space junk Aug 18 '17 at 16:01
2
\$\begingroup\$

JavaScript (ES6), 228 212 200 194 bytes

a=>w=>(B=1/0,(F=(r,p,s,b=a[p])=>p-a.length+1?1/b&&([...a[p]='RDUL'].map((c,d)=>d|p%w<w-1&&d-3|p%w&&F(r+c,P=p+[1,w,-w,-1][d],s+1+Math.abs(b-a[P]))),a[p]=b):R=s>B?R:s<B?(B=s,r):R+' '+r)('',0,0),R)

Input

One-dimensional array a and width w in currying syntax (a)(w)

Output

A space-separated list of solutions such as "DRDRRDR DRDRDRR"

Formatted and commented

a => w => (                            // given an array 'a' and a width 'w'
  B = 1 / 0,                           // B = best score so far, initialized as +Infinity
  (                                    //
    F = (                              // F = recursive function with:
      r,                               //   - r = current path (string)
      p,                               //   - p = current position in grid
      s,                               //   - s = current score
      b = a[p]                         //   - b = backup of current cell
    ) =>                               //
    p - a.length + 1 ?                 // if we haven't reached our destination:
      1 / b && (                       //   if the current cell is valid:
        [...a[p] = 'RDUL']             //     invalidate the current cell
        .map((c, d) =>                 //     for each possible direction:
          d | p % w < w - 1 &&         //       check right boundary
          d - 3 | p % w &&             //       check left boundary
          F(                           //       do a recursive call with:
            r + c,                     //         - new direction appended to the path
            P = p + [1, w, -w, -1][d], //         - updated position
            s + 1 + Math.abs(b - a[P]) //         - updated score
          )                            //
        ),                             //
        a[p] = b                       //     restore current cell value
      )                                //
    :                                  // else:
      R = s > B ?                      //   if the current score is worse than B:
        R                              //     keep the previous solution
      : s < B ?                        //   if the current score is better than B:
        (B = s, r)                     //     update best score / store path as new solution
      : R + ' ' + r                    //   if it's just as good: append path to solution
  )('', 0, 0),                         // initial call to F with r = '', p = 0, s = 0
  R                                    // return solution
)                                      //

Test cases

let f =

a=>w=>(B=1/0,(F=(r,p,s,b=a[p])=>p-a.length+1?1/b&&([...a[p]='RDUL'].map((c,d)=>d|p%w<w-1&&d-3|p%w&&F(r+c,P=p+[1,w,-w,-1][d],s+1+Math.abs(b-a[P]))),a[p]=b):R=s>B?R:s<B?(B=s,r):R+' '+r)('',0,0),R)

console.log(f([
  0, 3, 0, 0, 0,
  0, 2, 0, 2, 0,
  0, 0, 0, 3, 0
])(5));

console.log(f([
  3
])(1));

console.log(f([
  11, 11, 11,
  11, 11, 11,
  11, 11, 11
])(3));

console.log(f([
  7, 8, 1, -1, 0,
  4, 4, 6, -1, 7,
  3, 4, 4,  2, 8,
  2, 5, 2, -1, 2
])(5));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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