What is the fastest safe way down a mountain?

Question

Intro

Help! I'm stuck on a snow-covered mountain and I need to get down as fast as possible, preferably without dying. I have a map showing how high each part of the mountain is above the normal ground.

I am a novice skier, which means I like to stick to slopes that aren't too steep. I'm willing to go down just two moderately steep sections, however - but not back to back!

Rules

Your program's job is to, given a n x m matrix of height values, navigate from the skier's current position (the top left corner) to the base (the bottom right corner). Height values will be given as integers between 0 and 25, with 25 being the highest possible point and 0 being the base of the mountain. It should be noted the mountain does not have to start at 25 units high, but will always finish at the 0 in the bottom right corner.

There are a few constraints:

• The skier can move up, down, left, or right on the map. No diagonals.
• The skier is usually only comfortable on slopes that bring him down 2 units or less.
• The only exception to the above rule is that the skier can go down a maximum of two sections that will bring him down 3 or 4 units.
• The skier can move upwards if necessary, but only one unit at a time. The skier also cannot go upwards or flat then immediately thereafter go down a steep slope of 3 or 4 units, he must already be headed downwards before taking a steep slope. Also, his first move cannot be to go down a steep slope, and he cannot do two steep slopes back to back.
• It is possible for the skier to visit a location twice (as seen in the fourth example - this is due to the fact that the skier cannot go down two steep slopes in a row)

Input

As mentioned above, the map will be given by a matrix containing integer values from 0 to 25, with a 0 in the bottom left corner (there could be zeroes in other places on the map). These maps will always have at lease one best solution but could have several worse solutions. These matrices will always have spaces and line breaks as separators - double spaces will be used if the integer is just one character (see examples below)

Output

Your program is to output a sequence of moves (the format of this sequence does not matter so long as it is coherent) that shows the best way down the mountain - meaning fewest moves on the map. These moves can be represented by any strings, numbers, or characters you like, so long as they are distinct and are described in your solution. A sample output might look like RRDDRRRURRDDDDRR, where R means right, D means down, U means up, and L means left.

Test cases

Input 1:

10 13 13 13 13
8  9  11 13 25
0  7  11 12 23
6  5  2  2  0

Sample output 1:

DRDDRRR

Input 2:

16 12 12 10 8 6 
14 12 6  8  0 4 
10 20 4  2  1 2 
8  20 10 8  4 0 
9  8  9  25 2 0 

Sample output 2:

DDDDRRURRDR or DRURRRRDDDD

Input 3:

20 19 15 11 0  9  15 6 
18 20 13 12 11 9  18 12
16 25 9  7  6  2  1  1 
12 20 10 4  4  4  3  2 
13 12 13 0  0  0  0  0 

Sample output 3:

RRDDRRDRRRD

Input 4:

20 18 10 11 12 0 
19 11 1  4  5  0 
18 16 3  3  3  3 
19 8  7  17 19 3 
18 20 11 12 13 3 
17 17 16 16 14 2 
20 21 11 14 11 0

Sample output 4:

DDDDDRRRRULLULRURRRDDDD

Scoring:

This is code-golf. Shortest answer wins - get creative!

Answer 1

JavaScript (ES6),  223 ... 205  199 bytes

f=(m,x=o=0,y=0,n=2,V,s,p='',r=m[y]||0,v=r[x],h=V%32-v%32|0)=>63>>h+1&v<64&!p[o.length-1]?h<3||s*n--?1+r[x+!m[y+1]]?[...'LURD'].map((c,d)=>r[f(m,x+--d%2,y+~-d%2,n,r[x]+=32,6>>h&1,p+c),x]=v)&&o:o=p:0:0

Try it online!

Commented

The 5 least significant bits of the cells are left unchanged. The upper bits are used to count the number of times a cell has been visited in a given path.

We need quite a lot of variables to fully describe the skier status at any given time, notably the possibility to do a big steep slope.

Header

f = (                      // a recursive function taking:
  m,                       //   m[] = input matrix
  x =                      //   (x, y) = current position, starting at (0, 0)
  o = 0,                   //   o = output string, initialized to a numerical value
  y = 0,                   //
  n = 2,                   //   n = remaining number of big steep slopes
  V,                       //   V = value of the previous cell
  s,                       //   s = a flag that is set if a big steep slope is allowed
                           //       for this turn
  p = '',                  //   p = current path string
  r = m[y] || 0,           //   r[] = current row (using 0 as a fallback)
  v = r[x],                //   v = value of the current cell (or undefined)
  h = V % 32 - v % 32 | 0  //   h = height between the previous and the current cell
) =>                       //       (0 if V is undefined)
  (...)                    //

Tests

63 >> h + 1 &              // if the height is greater than or equal to -1 and less
                           // than or equal to 4 and
v < 64 &                   // v is defined and less than 64 and
!p[o.length - 1] ?         // the current path is shorter than the best solution or
                           // we don't have a solution yet (in which case o.length - 1
                           // is NaN):
  h < 3 ||                 //   if the height is less than 3 or
  s * n-- ?                //   a big steep slope is allowed and we can still do one:
    1 + r[x + !m[y + 1]] ? //     if we haven't reached the bottom-right cell,
                           //     i.e. m[y + 1] is defined or 1 + r[x + 1] is not NaN:
      (...)                //       process the recursive calls
    :                      //     else:
      o = p                //       update the solution to this path
  :                        //   else:
    0                      //     do nothing
:                          // else:
  0                        //   do nothing

Recursive calls

[...'LURD'].map((c, d) =>  // for each direction character c at index d:
  r[                       //   we will eventually restore r[x]
    f(                     //     recursive call:
      m,                   //       m[] is unchanged
      x + --d % 2,         //       add dx to x
      y + ~-d % 2,         //       add dy to y
      n,                   //       n is unchanged
      r[x] += 32,          //       add 32 to the current cell
      6 >> h & 1,          //       set s if h is either 1 or 2
      p + c                //       append c to the path
    ),                     //     end of recursive call
    x                      //     restore r[x] to ...
  ] = v                    //   ... v
) && o                     // end of map(); yield o

Answer 2

J, 185 bytes

Far from perfect, but it's something. Could theoretically save 17 bytes by omitting the check for revisiting places, but then the last example ran out of memory on my machine and I couldn't truthfully say all examples were verified. :-)

Takes in the map and outputs a list of offset coordinates 1 0,0 1,_1 0,0 _1 that I've mapped to DRUL in TIO for easier comparison.

}.@{.@(((](\:+/"2)@#~[*/@((4((1>=&3-_1|.2=])*>&0*3>[:+/\3=])@:|(+:<:i.4)I.0,2-/\({~ ::_"_ 0<"1))*3>[:+/[:="1/~<"1@])0 2+/\@|:])[:,/((,-)=i.2),~"1 2/])^:(0=<:@$@[-:+/@{.@])^:_&(1 1 2$0))

Try it online!

How it works

(1 1 2$0)

We keep the routes as a list of offsets, starting with 0 0.

(…)^:(0 = <:@$@[ -: +/@{.@])^:_

Do until the head of the list – which is nearest the bottom right – equals the dimensions of the map - 1.

[: ,/ ((,-)=i.2) ,~"1 2/ ]

Each route gets the 4 offsets added, so we have 4 times as many routes: (0 0,1 0),(0 0,0 1),(0 0,_1 0),(0 0, 0 _1). Then we have to filter these routes based on several checks.

0 2 +/\@|: ]

List of offsets -> List of absolute coordinates, transposed so each routes' first points are in one list, then each routes' second points are in one list, etc:

0 0,0 0, 0 0,0  0
1 0,0 1,_1 0,0 _1

This format seems more suitable for the checks, but maybe a (…)"2 would have been enough. However, now each check can build up a matrix saying which coordinate is ok and which not and in the end we can easily reduce it.

3 > [: +/ [: ="1/~ <"1@]

No place should be visited 3 times. This check is just to keep the number of routes from exploding.

0, 2 -/\ ({~ ::_"_ 0<"1)

Gets the height values from the map at the absolute coordinates. If something is out of range, it will be replaced with infinity. Then we'll get the diff between neighboring heights and prepend 0 so the matrix will align with the previous one. Now we have (given the first map):

0  0 0 0
2 _3 _ _

With

4 …@| (+:<:i.4) I.

we sort the height diffs into 4 categories: 0 = not reachable, 1 = climb up, 2 = gentle slope, 3 = steep slope.

3 > [: +/\ 3=]

Less then 3 steep slopes.

>&0

Point must be reachable

1 > =&3 - _1 |. 2 = ]

3 is only allowed if 2 was in front of it.

] …@ #~ [ */

A route is only taken if all of its coordinates passed all tests.

(\:+/"2)

Sort the routes based on their last, absolute coordinate.

}.@{.

Finally the loop has ended and the first route contains the best route written in offsets, with only a 0 0 at the top that gets dropped.