17
\$\begingroup\$

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 . Shortest answer wins - get creative!

\$\endgroup\$
12
  • 1
    \$\begingroup\$ @Arnauld good idea, edited! \$\endgroup\$ – Daniel H. Jun 15 '20 at 18:46
  • \$\begingroup\$ Is it possible a position is visited twice? \$\endgroup\$ – Abigail Jun 15 '20 at 20:02
  • 1
    \$\begingroup\$ Can you include an example where the solution contains Us and Ls? Now it seems the skier will never move "away" from the goal. \$\endgroup\$ – Abigail Jun 15 '20 at 20:03
  • 1
    \$\begingroup\$ How does the first test case work at the end going up 1 and then down 3? \$\endgroup\$ – Noodle9 Jun 15 '20 at 20:51
  • 1
    \$\begingroup\$ 'The skier also cannot go upwards then immediately thereafter go down a steep slope of 3 or 4 units, he must already be headed downwards before taking a steep slope' - slightly ambiguous: must the skier be headed downwards, or can he be going flat (neither up nor down) before embarking on a steep slope? \$\endgroup\$ – Dominic van Essen Jun 16 '20 at 7:18
11
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Impressive! Its output for the second test case is of the same length, so it's correct. I'll add this new solution as a possible solution for this case. \$\endgroup\$ – Daniel H. Jun 15 '20 at 23:17
  • 4
    \$\begingroup\$ I can't seem to grow tired of reading your JS submissions. Always impressive work. \$\endgroup\$ – RGS Jun 16 '20 at 0:09
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ This is great! May I ask, when programming in languages that are so non-human-readable like J, how do you not lose your mind? Do you write the program in a more readable language then transcompile somehow? \$\endgroup\$ – Daniel H. Jun 18 '20 at 17:00
  • 1
    \$\begingroup\$ This was mostly written in the J REPL. :-) If you roughly know what you want to do (recurse, add offsets, check and filter routes, sort) it's just writing them step by step in small functions. Until then it's perfectly readable if you know J. Only in the final phase I format this in a written out way and see if I can reorder some stuff to save some bytes. \$\endgroup\$ – xash Jun 18 '20 at 17:18

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.