Length of the Longest Descent

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP

8

$begingroup$

Your task is to determine the length of the longest descent down a “mountain” represented as a grid of integer heights. A “descent” is any path from a starting cell to orthogonally adjacent cells with strictly decreasing heights (i.e. not diagonal and not to the same height). For instance, you can move from 5-4-3-1 but not 5-5-4-3-3-2-1. The length of this path is how many cell movements there are from the starting cell to the ending cell, thus 5-4-3-1 is length 3.

You will receive a rectangular grid as input and you should output an integer indicating the longest descent.

Examples

1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1

The length of the longest descent down this mountain is 5. The longest path starts at the 7, moves left, up, left, up, and then left (7-6-5-4-2-1). Since there are 5 movements in this path, the path length is 5.

They might be all the same number.

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Since this height map is flat, the longest descent is 0. (not 19, since the path sequence must be strictly descending)

Height maps can be made up of larger numbers than single-digit numbers.

10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15

The longest path here is of length 6. (21, 20, 18, 17, 14, 12, 10)

…And even bigger numbers are fine too.

949858 789874  57848  43758 387348
  5848 454115   4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464  94849 151654 151648 484364

The longest descent here is of length 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)

Rules and Notes

  • Grids may be taken in any convenient format. Specify your format in your answer.
  • You may assume the height map is perfectly rectangular, is nonempty, and contains only positive integers in the signed 32-bit integer range.
  • The longest descent path can begin and end anywhere on the grid.
  • You do not need to describe the longest descent path in any way. Only its length is required.
  • Shortest code wins
share|improve this question

$endgroup$

  • $begingroup$
    How should the last example be interpreted?
    $endgroup$
    – Peter Taylor
    Jan 3 at 18:11

  • $begingroup$
    @PeterTaylor I’m not sure what you mean.
    $endgroup$
    – Beefster
    Jan 3 at 19:00

  • $begingroup$
    I think the last example is just a matrix of multi digit numbers
    $endgroup$
    – Embodiment of Ignorance
    Jan 3 at 19:08

  • $begingroup$
    @EmbodimentofIgnorance, ah, yes, I see. It would be a lot easier to spot the path with two-digit numbers rather than 4 to 6.
    $endgroup$
    – Peter Taylor
    Jan 3 at 21:08

  • 1

    $begingroup$
    @Οurous: just rectangular. Not jagged.
    $endgroup$
    – Beefster
    Jan 3 at 21:21

8

$begingroup$

Your task is to determine the length of the longest descent down a “mountain” represented as a grid of integer heights. A “descent” is any path from a starting cell to orthogonally adjacent cells with strictly decreasing heights (i.e. not diagonal and not to the same height). For instance, you can move from 5-4-3-1 but not 5-5-4-3-3-2-1. The length of this path is how many cell movements there are from the starting cell to the ending cell, thus 5-4-3-1 is length 3.

You will receive a rectangular grid as input and you should output an integer indicating the longest descent.

Examples

1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1

The length of the longest descent down this mountain is 5. The longest path starts at the 7, moves left, up, left, up, and then left (7-6-5-4-2-1). Since there are 5 movements in this path, the path length is 5.

They might be all the same number.

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Since this height map is flat, the longest descent is 0. (not 19, since the path sequence must be strictly descending)

Height maps can be made up of larger numbers than single-digit numbers.

10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15

The longest path here is of length 6. (21, 20, 18, 17, 14, 12, 10)

…And even bigger numbers are fine too.

949858 789874  57848  43758 387348
  5848 454115   4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464  94849 151654 151648 484364

The longest descent here is of length 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)

Rules and Notes

  • Grids may be taken in any convenient format. Specify your format in your answer.
  • You may assume the height map is perfectly rectangular, is nonempty, and contains only positive integers in the signed 32-bit integer range.
  • The longest descent path can begin and end anywhere on the grid.
  • You do not need to describe the longest descent path in any way. Only its length is required.
  • Shortest code wins
share|improve this question

$endgroup$

  • $begingroup$
    How should the last example be interpreted?
    $endgroup$
    – Peter Taylor
    Jan 3 at 18:11

  • $begingroup$
    @PeterTaylor I’m not sure what you mean.
    $endgroup$
    – Beefster
    Jan 3 at 19:00

  • $begingroup$
    I think the last example is just a matrix of multi digit numbers
    $endgroup$
    – Embodiment of Ignorance
    Jan 3 at 19:08

  • $begingroup$
    @EmbodimentofIgnorance, ah, yes, I see. It would be a lot easier to spot the path with two-digit numbers rather than 4 to 6.
    $endgroup$
    – Peter Taylor
    Jan 3 at 21:08

  • 1

    $begingroup$
    @Οurous: just rectangular. Not jagged.
    $endgroup$
    – Beefster
    Jan 3 at 21:21

8

8

8

$begingroup$

Your task is to determine the length of the longest descent down a “mountain” represented as a grid of integer heights. A “descent” is any path from a starting cell to orthogonally adjacent cells with strictly decreasing heights (i.e. not diagonal and not to the same height). For instance, you can move from 5-4-3-1 but not 5-5-4-3-3-2-1. The length of this path is how many cell movements there are from the starting cell to the ending cell, thus 5-4-3-1 is length 3.

You will receive a rectangular grid as input and you should output an integer indicating the longest descent.

Examples

1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1

The length of the longest descent down this mountain is 5. The longest path starts at the 7, moves left, up, left, up, and then left (7-6-5-4-2-1). Since there are 5 movements in this path, the path length is 5.

They might be all the same number.

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Since this height map is flat, the longest descent is 0. (not 19, since the path sequence must be strictly descending)

Height maps can be made up of larger numbers than single-digit numbers.

10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15

The longest path here is of length 6. (21, 20, 18, 17, 14, 12, 10)

…And even bigger numbers are fine too.

949858 789874  57848  43758 387348
  5848 454115   4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464  94849 151654 151648 484364

The longest descent here is of length 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)

Rules and Notes

  • Grids may be taken in any convenient format. Specify your format in your answer.
  • You may assume the height map is perfectly rectangular, is nonempty, and contains only positive integers in the signed 32-bit integer range.
  • The longest descent path can begin and end anywhere on the grid.
  • You do not need to describe the longest descent path in any way. Only its length is required.
  • Shortest code wins
share|improve this question

$endgroup$

Your task is to determine the length of the longest descent down a “mountain” represented as a grid of integer heights. A “descent” is any path from a starting cell to orthogonally adjacent cells with strictly decreasing heights (i.e. not diagonal and not to the same height). For instance, you can move from 5-4-3-1 but not 5-5-4-3-3-2-1. The length of this path is how many cell movements there are from the starting cell to the ending cell, thus 5-4-3-1 is length 3.

You will receive a rectangular grid as input and you should output an integer indicating the longest descent.

Examples

1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1

The length of the longest descent down this mountain is 5. The longest path starts at the 7, moves left, up, left, up, and then left (7-6-5-4-2-1). Since there are 5 movements in this path, the path length is 5.

They might be all the same number.

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Since this height map is flat, the longest descent is 0. (not 19, since the path sequence must be strictly descending)

Height maps can be made up of larger numbers than single-digit numbers.

10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15

The longest path here is of length 6. (21, 20, 18, 17, 14, 12, 10)

…And even bigger numbers are fine too.

949858 789874  57848  43758 387348
  5848 454115   4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464  94849 151654 151648 484364

The longest descent here is of length 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)

Rules and Notes

  • Grids may be taken in any convenient format. Specify your format in your answer.
  • You may assume the height map is perfectly rectangular, is nonempty, and contains only positive integers in the signed 32-bit integer range.
  • The longest descent path can begin and end anywhere on the grid.
  • You do not need to describe the longest descent path in any way. Only its length is required.
  • Shortest code wins

code-golf grid

share|improve this question

share|improve this question

share|improve this question

share|improve this question

edited Jan 3 at 21:27

Beefster

asked Jan 3 at 17:31

BeefsterBeefster

1,083722

1,083722

  • $begingroup$
    How should the last example be interpreted?
    $endgroup$
    – Peter Taylor
    Jan 3 at 18:11

  • $begingroup$
    @PeterTaylor I’m not sure what you mean.
    $endgroup$
    – Beefster
    Jan 3 at 19:00

  • $begingroup$
    I think the last example is just a matrix of multi digit numbers
    $endgroup$
    – Embodiment of Ignorance
    Jan 3 at 19:08

  • $begingroup$
    @EmbodimentofIgnorance, ah, yes, I see. It would be a lot easier to spot the path with two-digit numbers rather than 4 to 6.
    $endgroup$
    – Peter Taylor
    Jan 3 at 21:08

  • 1

    $begingroup$
    @Οurous: just rectangular. Not jagged.
    $endgroup$
    – Beefster
    Jan 3 at 21:21

  • $begingroup$
    How should the last example be interpreted?
    $endgroup$
    – Peter Taylor
    Jan 3 at 18:11

  • $begingroup$
    @PeterTaylor I’m not sure what you mean.
    $endgroup$
    – Beefster
    Jan 3 at 19:00

  • $begingroup$
    I think the last example is just a matrix of multi digit numbers
    $endgroup$
    – Embodiment of Ignorance
    Jan 3 at 19:08

  • $begingroup$
    @EmbodimentofIgnorance, ah, yes, I see. It would be a lot easier to spot the path with two-digit numbers rather than 4 to 6.
    $endgroup$
    – Peter Taylor
    Jan 3 at 21:08

  • 1

    $begingroup$
    @Οurous: just rectangular. Not jagged.
    $endgroup$
    – Beefster
    Jan 3 at 21:21

$begingroup$
How should the last example be interpreted?
$endgroup$
– Peter Taylor
Jan 3 at 18:11

$begingroup$
How should the last example be interpreted?
$endgroup$
– Peter Taylor
Jan 3 at 18:11

$begingroup$
@PeterTaylor I’m not sure what you mean.
$endgroup$
– Beefster
Jan 3 at 19:00

$begingroup$
@PeterTaylor I’m not sure what you mean.
$endgroup$
– Beefster
Jan 3 at 19:00

$begingroup$
I think the last example is just a matrix of multi digit numbers
$endgroup$
– Embodiment of Ignorance
Jan 3 at 19:08

$begingroup$
I think the last example is just a matrix of multi digit numbers
$endgroup$
– Embodiment of Ignorance
Jan 3 at 19:08

$begingroup$
@EmbodimentofIgnorance, ah, yes, I see. It would be a lot easier to spot the path with two-digit numbers rather than 4 to 6.
$endgroup$
– Peter Taylor
Jan 3 at 21:08

$begingroup$
@EmbodimentofIgnorance, ah, yes, I see. It would be a lot easier to spot the path with two-digit numbers rather than 4 to 6.
$endgroup$
– Peter Taylor
Jan 3 at 21:08

1

1

$begingroup$
@Οurous: just rectangular. Not jagged.
$endgroup$
– Beefster
Jan 3 at 21:21

$begingroup$
@Οurous: just rectangular. Not jagged.
$endgroup$
– Beefster
Jan 3 at 21:21

7 Answers
7

active

oldest

votes

8

$begingroup$

JavaScript (ES7),  106 103 102  98 bytes

f=(m,n=b=-1,x,y,p)=>m.map((r,Y)=>r.map((v,X)=>(x-X)**2+(y-Y)**2-1|v/p?b=n<b?b:n:f(m,n+1,X,Y,v)))|b

Try it online!

Commented

f = (                        // f = recursive function taking:
  m,                         //   m  = input matrix
  n = b = -1,                //   n    = length of the current path; b = best length so far
  x, y,                      //   x, y = coordinates of the previous cell
  p                          //   p    = value of the previous cell
) =>                         //
  m.map((r, Y) =>            // for each row r at position Y in m:
    r.map((v, X) =>          //   for each value v at position X in r:
      (x - X) ** 2 +         //     compute the squared Euclidean distance
      (y - Y) ** 2           //     between (x, y) and (X, Y)
      - 1                    //     if A) the above result is not equal to 1
      | v / p ?              //     or B) v is greater than or equal to p:
        b = n < b ? b : n    //       end of path: update b to n if n >= b
      :                      //     else:
        f(m, n + 1, X, Y, v) //       do a recursive call
    )                        //   end of inner map()
  ) | b                      // end of outer map(); return b

How?

During the first iteration, $x$, $y$ and $p$ are all undefined and both tests (A and B in the comments) evaluate to NaN, which triggers the recursive call. Therefore, all cells are considered as a possible starting point of the path.

share|improve this answer

$endgroup$

    6

    $begingroup$

    Jelly,  23 21  20 bytes

    -2 thanks to Erik the Outgolfer

    ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’
    

    Try it online! (way too inefficient for the examples – path here is 95 94 93 83 77 40 10 so 6 is yielded)

    How?

    ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’ - Link: list of lists of integers, M
    ŒỤ                   - multi-dimensional indices sorted by values
      ŒP                 - power-set
              Ƈ          - filter, keep those for which:
             Ʋ           -   last four links as a monad:
         Ɲ               -     for each pair of neighbours:
        ạ                -       absolute difference
          §              -     sum each
           Ị             -     insignificant?
            Ạ            -     all?
               œị        - multi-dimensional index into:
                 ⁸       -   chain's left argument, M
                    Ƈ    - filter, keep only those:
                   Ƒ     -   unaffected by?:
                  Q      -     de-duplicate
                     Ṫ   - tail
                      L  - length
                       ’ - decrement
    

    share|improve this answer

    $endgroup$

      3

      $begingroup$

      Python 2, 150 147 140 136 134 132 125 123 120 bytes

      l=lambda g,i,j:max(0<g.get(t)<g[i,j]and-~l(g,*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
      lambda g:max(l(g,*t)for t in g)
      

      Try it online!

      Takes input in the form of a dictionary (x, y): value.

      -7 bytes thanks to wizzwizz4, -2 bytes thanks to Jonathan Allen, -2 bytes thanks to BMO

      Alternative, 123 121 bytes

      l=lambda i,j:max(0<g.get(t)<g[i,j]and-~l(*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
      g=input();print max(l(*t)for t in g)
      

      Try it online!

      Essentially the same solution, just with the final lambda replaced by an actual program. I personally like the first one better, but this one comes close in byte count by allowing g to be used as a global variable.

      share|improve this answer

      $endgroup$

        2

        $begingroup$

        Clean, 211 207 bytes

        import StdEnv,Data.List
        z=zipWith
        $l=maximum[length k-1\p<-permutations[(v,[x,y])\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]
        

        Try it online!

        A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
        The TIO driver takes the same format as the examples through STDIN.

        It’s too slow to run any of the examples on TIO and probably locally too, but works in theory.

        This one does the same thing faster, can do 3×3 or 2×4 on TIO and 4×4 and 3×5 locally.

        Indented:

        $ l
            = maximum
                [ length k-1
                \p <- permutations
                    [ (v, [x, y])
                    \y <- [0..] & u <- l
                    , x <- [0..] & v <- u
                    ]
                , (k, [m: n]) <- map unzip
                    (subsequences p)
                | and
                    [ all
                        ((>) 2 o sum o map abs)
                        (zipWith (zipWith (-)) n [m:n])
                        :
                        zipWith (>) k (tl k)
                    ]
                ]
        

        share|improve this answer

        $endgroup$

          2

          $begingroup$

          Python 3, 219 bytes

          e,m=len,enumerate
          b=lambda g,x,y:[b(g,i,j)for o in[-1,1]for i,j in[(x+o,y),(x,y+o)]if e(g)>i>=0<=j<e(g[x])and g[x][y]<g[i][j]]
          l=lambda t:e(t)and 1+max(map(l,t))
          d=lambda g:max(l(b(g,x,y))for x,r in m(g)for y,_ in m(r))
          

          Try it online!

          Grid is represented as list of lists:

          [
              [1, 2, 3, 2, 2],
              [3, 4, 5, 5, 5],
              [3, 4, 6, 7, 4],
              [3, 3, 5, 6, 2],
              [1, 1, 2, 3, 1],
          ]
          

          Original ungolfed code:

          def potential_neighbours(x, y):
              return [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
          
          def neighbours(grid, x, y):
              result = 
              for i, j in potential_neighbours(x, y):
                  if 0 <= i < len(grid) and 0 <= j < len(grid[x]) and grid[x][y] < grid[i][j]:
                      result += [(i, j)]
              return result
          
          def build_tree(grid, x, y):
              return [build_tree(grid, i, j) for i, j in neighbours(grid, x, y)]
          
          def longest_path_in_tree(tree):
              if len(tree) == 0:
                  return 0
              return 1 + max(map(longest_path_in_tree, tree))
          
          def longest_descent(grid):
              trees = [build_tree(grid, x, y) for x, row in enumerate(grid) for y, _ in enumerate(row)]
              return max(map(longest_path_in_tree, trees))
          

          share|improve this answer

          $endgroup$

            2

            $begingroup$

            Haskell, 188 186 bytes

            Needs $texttt{-XNoMonomorphismRestriction}$:

            f m|c<-[0..length(m!!0)-1],r<-[0..length m-1]=h[g[(x,y)]|x<-r,y<-c,let g((x,y):p)=h[1+g(k:p)|i<-[-1,1],k@(u,v)<-[(x+i,y),(x,y+i)],u#r,v#c,m!!u!!v<m!!x!!y,not$k#p]]
            (#)=elem
            h=foldl max 0
            

            Try it online!

            Alternatively we could use notElem over (not.).(#) without the flag for $+4$ bytes:

            Try it online!

            Explanation & Ungolfed

            Strategy: Recursively try all feasible paths, keeping track of visited entries and maximize their length.

            Let’s first define some helpers.. Since we need elem and notElem, let’s use (#) for elem. Also, to maximize we’ll need a total function (maximize is not), returning $0$ when the list is empty:

            safeMaximum = foldl max 0
            

            Now we’re ready to define our recursive function fun :: [[Integer]] -> Integer:

            fun xs
              | c <- [0..length(m!!0)-1]             -- all possible indices of xs' columns
              , r <- [0..length m-1]                 -- all possible indices of xs' rows
              = safeMaximum                          -- maximize ..
                  [ g [(x,y)]                        -- .. initially we haven't visited any others
                  | x <- c, y<-r                     -- .. all possible entries
            -- For the purpose of golfing we define g in the list-comprehension, it takes all visited entries (p) where (x,y) is the most recent
                  , let g((x,y):p) = safeMaximum     -- maximize ..
                      [ 1 + g(k:p)                   -- .. recurse, adding (x,y) to the visited nodes & increment (the next path will be 1 longer)
                      | i <- [-1,1]                  -- offsets [left/up,right/down]
                      , k@(u,v) <-[(x+i,y),(x,y+i)]  -- next entry-candidate
                      , u#c, v#r                     -- make sure indices are in bound ..
                      , m!!u!!v < m!!x!!y            -- .. , the the path is decreasing
                      , not$(u,v)#p                  -- .. and we haven't already visited that element
                      ]
                  ]
            

            share|improve this answer

            $endgroup$

            • $begingroup$
              How does this take grids? List of lists?
              $endgroup$
              – Beefster
              Jan 4 at 17:42

            • $begingroup$
              @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
              $endgroup$
              – BMO
              Jan 4 at 17:46

            1

            $begingroup$

            Python 3, 263 227 bytes

            def f(m):
             p={(x,y):[c for i in[-1,1]for c in[(x,y+i),(x+i,y)]]for x,y in m};d={c:0 for c in p if not p[c]}
             while len(p)-len(d):
              for c in p:
               for b in p[c]:
                if b in d:d[c]=max(d[b]+1,d.get(c,0))
             return max(d.values())
            

            Try it online!

            -2 bytes thanks to BMO

            Takes grids in the format {(0, 0): 1, (1, 0): 2, ...}. This format can be generated from the example format using the following utility function:

            lambda s,e=enumerate:{(x,y):int(n)for y,l in e(s.split('n'))for x,n in e(l.split())}
            

            share|improve this answer

            $endgroup$

              Your Answer

              StackExchange.ifUsing(“editor”, function () {
              return StackExchange.using(“mathjaxEditing”, function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [[“\$”, “\$”]]);
              });
              });
              }, “mathjax-editing”);

              StackExchange.ifUsing(“editor”, function () {
              StackExchange.using(“externalEditor”, function () {
              StackExchange.using(“snippets”, function () {
              StackExchange.snippets.init();
              });
              });
              }, “code-snippets”);

              StackExchange.ready(function() {
              var channelOptions = {
              tags: “”.split(” “),
              id: “200”
              };
              initTagRenderer(“”.split(” “), “”.split(” “), channelOptions);

              StackExchange.using(“externalEditor”, function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using(“snippets”, function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: ‘answer’,
              autoActivateHeartbeat: false,
              convertImagesToLinks: false,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: null,
              bindNavPrevention: true,
              postfix: “”,
              imageUploader: {
              brandingHtml: “Powered by u003ca class=”icon-imgur-white” href=”https://imgur.com/”u003eu003c/au003e”,
              contentPolicyHtml: “User contributions licensed under u003ca href=”https://creativecommons.org/licenses/by-sa/3.0/”u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href=”https://stackoverflow.com/legal/content-policy”u003e(content policy)u003c/au003e”,
              allowUrls: true
              },
              onDemand: true,
              discardSelector: “.discard-answer”
              ,immediatelyShowMarkdownHelp:true
              });

              }
              });

              draft saved
              draft discarded

              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin(‘.new-post-login’, ‘https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f178326%2flength-of-the-longest-descent%23new-answer’, ‘question_page’);
              }
              );

              Post as a guest

              Required, but never shown

              7 Answers
              7

              active

              oldest

              votes

              7 Answers
              7

              active

              oldest

              votes

              active

              oldest

              votes

              active

              oldest

              votes

              8

              $begingroup$

              JavaScript (ES7),  106 103 102  98 bytes

              f=(m,n=b=-1,x,y,p)=>m.map((r,Y)=>r.map((v,X)=>(x-X)**2+(y-Y)**2-1|v/p?b=n<b?b:n:f(m,n+1,X,Y,v)))|b
              

              Try it online!

              Commented

              f = (                        // f = recursive function taking:
                m,                         //   m  = input matrix
                n = b = -1,                //   n    = length of the current path; b = best length so far
                x, y,                      //   x, y = coordinates of the previous cell
                p                          //   p    = value of the previous cell
              ) =>                         //
                m.map((r, Y) =>            // for each row r at position Y in m:
                  r.map((v, X) =>          //   for each value v at position X in r:
                    (x - X) ** 2 +         //     compute the squared Euclidean distance
                    (y - Y) ** 2           //     between (x, y) and (X, Y)
                    - 1                    //     if A) the above result is not equal to 1
                    | v / p ?              //     or B) v is greater than or equal to p:
                      b = n < b ? b : n    //       end of path: update b to n if n >= b
                    :                      //     else:
                      f(m, n + 1, X, Y, v) //       do a recursive call
                  )                        //   end of inner map()
                ) | b                      // end of outer map(); return b
              

              How?

              During the first iteration, $x$, $y$ and $p$ are all undefined and both tests (A and B in the comments) evaluate to NaN, which triggers the recursive call. Therefore, all cells are considered as a possible starting point of the path.

              share|improve this answer

              $endgroup$

                8

                $begingroup$

                JavaScript (ES7),  106 103 102  98 bytes

                f=(m,n=b=-1,x,y,p)=>m.map((r,Y)=>r.map((v,X)=>(x-X)**2+(y-Y)**2-1|v/p?b=n<b?b:n:f(m,n+1,X,Y,v)))|b
                

                Try it online!

                Commented

                f = (                        // f = recursive function taking:
                  m,                         //   m  = input matrix
                  n = b = -1,                //   n    = length of the current path; b = best length so far
                  x, y,                      //   x, y = coordinates of the previous cell
                  p                          //   p    = value of the previous cell
                ) =>                         //
                  m.map((r, Y) =>            // for each row r at position Y in m:
                    r.map((v, X) =>          //   for each value v at position X in r:
                      (x - X) ** 2 +         //     compute the squared Euclidean distance
                      (y - Y) ** 2           //     between (x, y) and (X, Y)
                      - 1                    //     if A) the above result is not equal to 1
                      | v / p ?              //     or B) v is greater than or equal to p:
                        b = n < b ? b : n    //       end of path: update b to n if n >= b
                      :                      //     else:
                        f(m, n + 1, X, Y, v) //       do a recursive call
                    )                        //   end of inner map()
                  ) | b                      // end of outer map(); return b
                

                How?

                During the first iteration, $x$, $y$ and $p$ are all undefined and both tests (A and B in the comments) evaluate to NaN, which triggers the recursive call. Therefore, all cells are considered as a possible starting point of the path.

                share|improve this answer

                $endgroup$

                  8

                  8

                  8

                  $begingroup$

                  JavaScript (ES7),  106 103 102  98 bytes

                  f=(m,n=b=-1,x,y,p)=>m.map((r,Y)=>r.map((v,X)=>(x-X)**2+(y-Y)**2-1|v/p?b=n<b?b:n:f(m,n+1,X,Y,v)))|b
                  

                  Try it online!

                  Commented

                  f = (                        // f = recursive function taking:
                    m,                         //   m  = input matrix
                    n = b = -1,                //   n    = length of the current path; b = best length so far
                    x, y,                      //   x, y = coordinates of the previous cell
                    p                          //   p    = value of the previous cell
                  ) =>                         //
                    m.map((r, Y) =>            // for each row r at position Y in m:
                      r.map((v, X) =>          //   for each value v at position X in r:
                        (x - X) ** 2 +         //     compute the squared Euclidean distance
                        (y - Y) ** 2           //     between (x, y) and (X, Y)
                        - 1                    //     if A) the above result is not equal to 1
                        | v / p ?              //     or B) v is greater than or equal to p:
                          b = n < b ? b : n    //       end of path: update b to n if n >= b
                        :                      //     else:
                          f(m, n + 1, X, Y, v) //       do a recursive call
                      )                        //   end of inner map()
                    ) | b                      // end of outer map(); return b
                  

                  How?

                  During the first iteration, $x$, $y$ and $p$ are all undefined and both tests (A and B in the comments) evaluate to NaN, which triggers the recursive call. Therefore, all cells are considered as a possible starting point of the path.

                  share|improve this answer

                  $endgroup$

                  JavaScript (ES7),  106 103 102  98 bytes

                  f=(m,n=b=-1,x,y,p)=>m.map((r,Y)=>r.map((v,X)=>(x-X)**2+(y-Y)**2-1|v/p?b=n<b?b:n:f(m,n+1,X,Y,v)))|b
                  

                  Try it online!

                  Commented

                  f = (                        // f = recursive function taking:
                    m,                         //   m  = input matrix
                    n = b = -1,                //   n    = length of the current path; b = best length so far
                    x, y,                      //   x, y = coordinates of the previous cell
                    p                          //   p    = value of the previous cell
                  ) =>                         //
                    m.map((r, Y) =>            // for each row r at position Y in m:
                      r.map((v, X) =>          //   for each value v at position X in r:
                        (x - X) ** 2 +         //     compute the squared Euclidean distance
                        (y - Y) ** 2           //     between (x, y) and (X, Y)
                        - 1                    //     if A) the above result is not equal to 1
                        | v / p ?              //     or B) v is greater than or equal to p:
                          b = n < b ? b : n    //       end of path: update b to n if n >= b
                        :                      //     else:
                          f(m, n + 1, X, Y, v) //       do a recursive call
                      )                        //   end of inner map()
                    ) | b                      // end of outer map(); return b
                  

                  How?

                  During the first iteration, $x$, $y$ and $p$ are all undefined and both tests (A and B in the comments) evaluate to NaN, which triggers the recursive call. Therefore, all cells are considered as a possible starting point of the path.

                  share|improve this answer

                  share|improve this answer

                  share|improve this answer

                  edited Jan 4 at 19:54

                  answered Jan 3 at 19:01

                  ArnauldArnauld

                  73.4k689308

                  73.4k689308

                      6

                      $begingroup$

                      Jelly,  23 21  20 bytes

                      -2 thanks to Erik the Outgolfer

                      ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’
                      

                      Try it online! (way too inefficient for the examples – path here is 95 94 93 83 77 40 10 so 6 is yielded)

                      How?

                      ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’ - Link: list of lists of integers, M
                      ŒỤ                   - multi-dimensional indices sorted by values
                        ŒP                 - power-set
                                Ƈ          - filter, keep those for which:
                               Ʋ           -   last four links as a monad:
                           Ɲ               -     for each pair of neighbours:
                          ạ                -       absolute difference
                            §              -     sum each
                             Ị             -     insignificant?
                              Ạ            -     all?
                                 œị        - multi-dimensional index into:
                                   ⁸       -   chain's left argument, M
                                      Ƈ    - filter, keep only those:
                                     Ƒ     -   unaffected by?:
                                    Q      -     de-duplicate
                                       Ṫ   - tail
                                        L  - length
                                         ’ - decrement
                      

                      share|improve this answer

                      $endgroup$

                        6

                        $begingroup$

                        Jelly,  23 21  20 bytes

                        -2 thanks to Erik the Outgolfer

                        ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’
                        

                        Try it online! (way too inefficient for the examples – path here is 95 94 93 83 77 40 10 so 6 is yielded)

                        How?

                        ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’ - Link: list of lists of integers, M
                        ŒỤ                   - multi-dimensional indices sorted by values
                          ŒP                 - power-set
                                  Ƈ          - filter, keep those for which:
                                 Ʋ           -   last four links as a monad:
                             Ɲ               -     for each pair of neighbours:
                            ạ                -       absolute difference
                              §              -     sum each
                               Ị             -     insignificant?
                                Ạ            -     all?
                                   œị        - multi-dimensional index into:
                                     ⁸       -   chain's left argument, M
                                        Ƈ    - filter, keep only those:
                                       Ƒ     -   unaffected by?:
                                      Q      -     de-duplicate
                                         Ṫ   - tail
                                          L  - length
                                           ’ - decrement
                        

                        share|improve this answer

                        $endgroup$

                          6

                          6

                          6

                          $begingroup$

                          Jelly,  23 21  20 bytes

                          -2 thanks to Erik the Outgolfer

                          ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’
                          

                          Try it online! (way too inefficient for the examples – path here is 95 94 93 83 77 40 10 so 6 is yielded)

                          How?

                          ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’ - Link: list of lists of integers, M
                          ŒỤ                   - multi-dimensional indices sorted by values
                            ŒP                 - power-set
                                    Ƈ          - filter, keep those for which:
                                   Ʋ           -   last four links as a monad:
                               Ɲ               -     for each pair of neighbours:
                              ạ                -       absolute difference
                                §              -     sum each
                                 Ị             -     insignificant?
                                  Ạ            -     all?
                                     œị        - multi-dimensional index into:
                                       ⁸       -   chain's left argument, M
                                          Ƈ    - filter, keep only those:
                                         Ƒ     -   unaffected by?:
                                        Q      -     de-duplicate
                                           Ṫ   - tail
                                            L  - length
                                             ’ - decrement
                          

                          share|improve this answer

                          $endgroup$

                          Jelly,  23 21  20 bytes

                          -2 thanks to Erik the Outgolfer

                          ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’
                          

                          Try it online! (way too inefficient for the examples – path here is 95 94 93 83 77 40 10 so 6 is yielded)

                          How?

                          ŒỤŒPạƝ§ỊẠƲƇœị⁸QƑƇṪL’ - Link: list of lists of integers, M
                          ŒỤ                   - multi-dimensional indices sorted by values
                            ŒP                 - power-set
                                    Ƈ          - filter, keep those for which:
                                   Ʋ           -   last four links as a monad:
                               Ɲ               -     for each pair of neighbours:
                              ạ                -       absolute difference
                                §              -     sum each
                                 Ị             -     insignificant?
                                  Ạ            -     all?
                                     œị        - multi-dimensional index into:
                                       ⁸       -   chain's left argument, M
                                          Ƈ    - filter, keep only those:
                                         Ƒ     -   unaffected by?:
                                        Q      -     de-duplicate
                                           Ṫ   - tail
                                            L  - length
                                             ’ - decrement
                          

                          share|improve this answer

                          share|improve this answer

                          share|improve this answer

                          edited Jan 3 at 22:54

                          answered Jan 3 at 20:28

                          Jonathan AllanJonathan Allan

                          51.1k534166

                          51.1k534166

                              3

                              $begingroup$

                              Python 2, 150 147 140 136 134 132 125 123 120 bytes

                              l=lambda g,i,j:max(0<g.get(t)<g[i,j]and-~l(g,*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                              lambda g:max(l(g,*t)for t in g)
                              

                              Try it online!

                              Takes input in the form of a dictionary (x, y): value.

                              -7 bytes thanks to wizzwizz4, -2 bytes thanks to Jonathan Allen, -2 bytes thanks to BMO

                              Alternative, 123 121 bytes

                              l=lambda i,j:max(0<g.get(t)<g[i,j]and-~l(*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                              g=input();print max(l(*t)for t in g)
                              

                              Try it online!

                              Essentially the same solution, just with the final lambda replaced by an actual program. I personally like the first one better, but this one comes close in byte count by allowing g to be used as a global variable.

                              share|improve this answer

                              $endgroup$

                                3

                                $begingroup$

                                Python 2, 150 147 140 136 134 132 125 123 120 bytes

                                l=lambda g,i,j:max(0<g.get(t)<g[i,j]and-~l(g,*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                                lambda g:max(l(g,*t)for t in g)
                                

                                Try it online!

                                Takes input in the form of a dictionary (x, y): value.

                                -7 bytes thanks to wizzwizz4, -2 bytes thanks to Jonathan Allen, -2 bytes thanks to BMO

                                Alternative, 123 121 bytes

                                l=lambda i,j:max(0<g.get(t)<g[i,j]and-~l(*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                                g=input();print max(l(*t)for t in g)
                                

                                Try it online!

                                Essentially the same solution, just with the final lambda replaced by an actual program. I personally like the first one better, but this one comes close in byte count by allowing g to be used as a global variable.

                                share|improve this answer

                                $endgroup$

                                  3

                                  3

                                  3

                                  $begingroup$

                                  Python 2, 150 147 140 136 134 132 125 123 120 bytes

                                  l=lambda g,i,j:max(0<g.get(t)<g[i,j]and-~l(g,*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                                  lambda g:max(l(g,*t)for t in g)
                                  

                                  Try it online!

                                  Takes input in the form of a dictionary (x, y): value.

                                  -7 bytes thanks to wizzwizz4, -2 bytes thanks to Jonathan Allen, -2 bytes thanks to BMO

                                  Alternative, 123 121 bytes

                                  l=lambda i,j:max(0<g.get(t)<g[i,j]and-~l(*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                                  g=input();print max(l(*t)for t in g)
                                  

                                  Try it online!

                                  Essentially the same solution, just with the final lambda replaced by an actual program. I personally like the first one better, but this one comes close in byte count by allowing g to be used as a global variable.

                                  share|improve this answer

                                  $endgroup$

                                  Python 2, 150 147 140 136 134 132 125 123 120 bytes

                                  l=lambda g,i,j:max(0<g.get(t)<g[i,j]and-~l(g,*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                                  lambda g:max(l(g,*t)for t in g)
                                  

                                  Try it online!

                                  Takes input in the form of a dictionary (x, y): value.

                                  -7 bytes thanks to wizzwizz4, -2 bytes thanks to Jonathan Allen, -2 bytes thanks to BMO

                                  Alternative, 123 121 bytes

                                  l=lambda i,j:max(0<g.get(t)<g[i,j]and-~l(*t)for d in(-1,1)for t in((i+d,j),(i,j+d)))
                                  g=input();print max(l(*t)for t in g)
                                  

                                  Try it online!

                                  Essentially the same solution, just with the final lambda replaced by an actual program. I personally like the first one better, but this one comes close in byte count by allowing g to be used as a global variable.

                                  share|improve this answer

                                  share|improve this answer

                                  share|improve this answer

                                  edited Jan 3 at 23:05

                                  answered Jan 3 at 20:18

                                  ArBoArBo

                                  29115

                                  29115

                                      2

                                      $begingroup$

                                      Clean, 211 207 bytes

                                      import StdEnv,Data.List
                                      z=zipWith
                                      $l=maximum[length k-1\p<-permutations[(v,[x,y])\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]
                                      

                                      Try it online!

                                      A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
                                      The TIO driver takes the same format as the examples through STDIN.

                                      It’s too slow to run any of the examples on TIO and probably locally too, but works in theory.

                                      This one does the same thing faster, can do 3×3 or 2×4 on TIO and 4×4 and 3×5 locally.

                                      Indented:

                                      $ l
                                          = maximum
                                              [ length k-1
                                              \p <- permutations
                                                  [ (v, [x, y])
                                                  \y <- [0..] & u <- l
                                                  , x <- [0..] & v <- u
                                                  ]
                                              , (k, [m: n]) <- map unzip
                                                  (subsequences p)
                                              | and
                                                  [ all
                                                      ((>) 2 o sum o map abs)
                                                      (zipWith (zipWith (-)) n [m:n])
                                                      :
                                                      zipWith (>) k (tl k)
                                                  ]
                                              ]
                                      

                                      share|improve this answer

                                      $endgroup$

                                        2

                                        $begingroup$

                                        Clean, 211 207 bytes

                                        import StdEnv,Data.List
                                        z=zipWith
                                        $l=maximum[length k-1\p<-permutations[(v,[x,y])\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]
                                        

                                        Try it online!

                                        A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
                                        The TIO driver takes the same format as the examples through STDIN.

                                        It’s too slow to run any of the examples on TIO and probably locally too, but works in theory.

                                        This one does the same thing faster, can do 3×3 or 2×4 on TIO and 4×4 and 3×5 locally.

                                        Indented:

                                        $ l
                                            = maximum
                                                [ length k-1
                                                \p <- permutations
                                                    [ (v, [x, y])
                                                    \y <- [0..] & u <- l
                                                    , x <- [0..] & v <- u
                                                    ]
                                                , (k, [m: n]) <- map unzip
                                                    (subsequences p)
                                                | and
                                                    [ all
                                                        ((>) 2 o sum o map abs)
                                                        (zipWith (zipWith (-)) n [m:n])
                                                        :
                                                        zipWith (>) k (tl k)
                                                    ]
                                                ]
                                        

                                        share|improve this answer

                                        $endgroup$

                                          2

                                          2

                                          2

                                          $begingroup$

                                          Clean, 211 207 bytes

                                          import StdEnv,Data.List
                                          z=zipWith
                                          $l=maximum[length k-1\p<-permutations[(v,[x,y])\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]
                                          

                                          Try it online!

                                          A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
                                          The TIO driver takes the same format as the examples through STDIN.

                                          It’s too slow to run any of the examples on TIO and probably locally too, but works in theory.

                                          This one does the same thing faster, can do 3×3 or 2×4 on TIO and 4×4 and 3×5 locally.

                                          Indented:

                                          $ l
                                              = maximum
                                                  [ length k-1
                                                  \p <- permutations
                                                      [ (v, [x, y])
                                                      \y <- [0..] & u <- l
                                                      , x <- [0..] & v <- u
                                                      ]
                                                  , (k, [m: n]) <- map unzip
                                                      (subsequences p)
                                                  | and
                                                      [ all
                                                          ((>) 2 o sum o map abs)
                                                          (zipWith (zipWith (-)) n [m:n])
                                                          :
                                                          zipWith (>) k (tl k)
                                                      ]
                                                  ]
                                          

                                          share|improve this answer

                                          $endgroup$

                                          Clean, 211 207 bytes

                                          import StdEnv,Data.List
                                          z=zipWith
                                          $l=maximum[length k-1\p<-permutations[(v,[x,y])\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|and[all((>)2o sum o map abs)(z(z(-))n[m:n]):z(>)k(tl k)]]
                                          

                                          Try it online!

                                          A brute-force solution taking a list-of-lists-of-integers ([[Int]]).
                                          The TIO driver takes the same format as the examples through STDIN.

                                          It’s too slow to run any of the examples on TIO and probably locally too, but works in theory.

                                          This one does the same thing faster, can do 3×3 or 2×4 on TIO and 4×4 and 3×5 locally.

                                          Indented:

                                          $ l
                                              = maximum
                                                  [ length k-1
                                                  \p <- permutations
                                                      [ (v, [x, y])
                                                      \y <- [0..] & u <- l
                                                      , x <- [0..] & v <- u
                                                      ]
                                                  , (k, [m: n]) <- map unzip
                                                      (subsequences p)
                                                  | and
                                                      [ all
                                                          ((>) 2 o sum o map abs)
                                                          (zipWith (zipWith (-)) n [m:n])
                                                          :
                                                          zipWith (>) k (tl k)
                                                      ]
                                                  ]
                                          

                                          share|improve this answer

                                          share|improve this answer

                                          share|improve this answer

                                          edited Jan 3 at 21:58

                                          answered Jan 3 at 18:57

                                          ΟurousΟurous

                                          6,55211033

                                          6,55211033

                                              2

                                              $begingroup$

                                              Python 3, 219 bytes

                                              e,m=len,enumerate
                                              b=lambda g,x,y:[b(g,i,j)for o in[-1,1]for i,j in[(x+o,y),(x,y+o)]if e(g)>i>=0<=j<e(g[x])and g[x][y]<g[i][j]]
                                              l=lambda t:e(t)and 1+max(map(l,t))
                                              d=lambda g:max(l(b(g,x,y))for x,r in m(g)for y,_ in m(r))
                                              

                                              Try it online!

                                              Grid is represented as list of lists:

                                              [
                                                  [1, 2, 3, 2, 2],
                                                  [3, 4, 5, 5, 5],
                                                  [3, 4, 6, 7, 4],
                                                  [3, 3, 5, 6, 2],
                                                  [1, 1, 2, 3, 1],
                                              ]
                                              

                                              Original ungolfed code:

                                              def potential_neighbours(x, y):
                                                  return [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
                                              
                                              def neighbours(grid, x, y):
                                                  result = 
                                                  for i, j in potential_neighbours(x, y):
                                                      if 0 <= i < len(grid) and 0 <= j < len(grid[x]) and grid[x][y] < grid[i][j]:
                                                          result += [(i, j)]
                                                  return result
                                              
                                              def build_tree(grid, x, y):
                                                  return [build_tree(grid, i, j) for i, j in neighbours(grid, x, y)]
                                              
                                              def longest_path_in_tree(tree):
                                                  if len(tree) == 0:
                                                      return 0
                                                  return 1 + max(map(longest_path_in_tree, tree))
                                              
                                              def longest_descent(grid):
                                                  trees = [build_tree(grid, x, y) for x, row in enumerate(grid) for y, _ in enumerate(row)]
                                                  return max(map(longest_path_in_tree, trees))
                                              

                                              share|improve this answer

                                              $endgroup$

                                                2

                                                $begingroup$

                                                Python 3, 219 bytes

                                                e,m=len,enumerate
                                                b=lambda g,x,y:[b(g,i,j)for o in[-1,1]for i,j in[(x+o,y),(x,y+o)]if e(g)>i>=0<=j<e(g[x])and g[x][y]<g[i][j]]
                                                l=lambda t:e(t)and 1+max(map(l,t))
                                                d=lambda g:max(l(b(g,x,y))for x,r in m(g)for y,_ in m(r))
                                                

                                                Try it online!

                                                Grid is represented as list of lists:

                                                [
                                                    [1, 2, 3, 2, 2],
                                                    [3, 4, 5, 5, 5],
                                                    [3, 4, 6, 7, 4],
                                                    [3, 3, 5, 6, 2],
                                                    [1, 1, 2, 3, 1],
                                                ]
                                                

                                                Original ungolfed code:

                                                def potential_neighbours(x, y):
                                                    return [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
                                                
                                                def neighbours(grid, x, y):
                                                    result = 
                                                    for i, j in potential_neighbours(x, y):
                                                        if 0 <= i < len(grid) and 0 <= j < len(grid[x]) and grid[x][y] < grid[i][j]:
                                                            result += [(i, j)]
                                                    return result
                                                
                                                def build_tree(grid, x, y):
                                                    return [build_tree(grid, i, j) for i, j in neighbours(grid, x, y)]
                                                
                                                def longest_path_in_tree(tree):
                                                    if len(tree) == 0:
                                                        return 0
                                                    return 1 + max(map(longest_path_in_tree, tree))
                                                
                                                def longest_descent(grid):
                                                    trees = [build_tree(grid, x, y) for x, row in enumerate(grid) for y, _ in enumerate(row)]
                                                    return max(map(longest_path_in_tree, trees))
                                                

                                                share|improve this answer

                                                $endgroup$

                                                  2

                                                  2

                                                  2

                                                  $begingroup$

                                                  Python 3, 219 bytes

                                                  e,m=len,enumerate
                                                  b=lambda g,x,y:[b(g,i,j)for o in[-1,1]for i,j in[(x+o,y),(x,y+o)]if e(g)>i>=0<=j<e(g[x])and g[x][y]<g[i][j]]
                                                  l=lambda t:e(t)and 1+max(map(l,t))
                                                  d=lambda g:max(l(b(g,x,y))for x,r in m(g)for y,_ in m(r))
                                                  

                                                  Try it online!

                                                  Grid is represented as list of lists:

                                                  [
                                                      [1, 2, 3, 2, 2],
                                                      [3, 4, 5, 5, 5],
                                                      [3, 4, 6, 7, 4],
                                                      [3, 3, 5, 6, 2],
                                                      [1, 1, 2, 3, 1],
                                                  ]
                                                  

                                                  Original ungolfed code:

                                                  def potential_neighbours(x, y):
                                                      return [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
                                                  
                                                  def neighbours(grid, x, y):
                                                      result = 
                                                      for i, j in potential_neighbours(x, y):
                                                          if 0 <= i < len(grid) and 0 <= j < len(grid[x]) and grid[x][y] < grid[i][j]:
                                                              result += [(i, j)]
                                                      return result
                                                  
                                                  def build_tree(grid, x, y):
                                                      return [build_tree(grid, i, j) for i, j in neighbours(grid, x, y)]
                                                  
                                                  def longest_path_in_tree(tree):
                                                      if len(tree) == 0:
                                                          return 0
                                                      return 1 + max(map(longest_path_in_tree, tree))
                                                  
                                                  def longest_descent(grid):
                                                      trees = [build_tree(grid, x, y) for x, row in enumerate(grid) for y, _ in enumerate(row)]
                                                      return max(map(longest_path_in_tree, trees))
                                                  

                                                  share|improve this answer

                                                  $endgroup$

                                                  Python 3, 219 bytes

                                                  e,m=len,enumerate
                                                  b=lambda g,x,y:[b(g,i,j)for o in[-1,1]for i,j in[(x+o,y),(x,y+o)]if e(g)>i>=0<=j<e(g[x])and g[x][y]<g[i][j]]
                                                  l=lambda t:e(t)and 1+max(map(l,t))
                                                  d=lambda g:max(l(b(g,x,y))for x,r in m(g)for y,_ in m(r))
                                                  

                                                  Try it online!

                                                  Grid is represented as list of lists:

                                                  [
                                                      [1, 2, 3, 2, 2],
                                                      [3, 4, 5, 5, 5],
                                                      [3, 4, 6, 7, 4],
                                                      [3, 3, 5, 6, 2],
                                                      [1, 1, 2, 3, 1],
                                                  ]
                                                  

                                                  Original ungolfed code:

                                                  def potential_neighbours(x, y):
                                                      return [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
                                                  
                                                  def neighbours(grid, x, y):
                                                      result = 
                                                      for i, j in potential_neighbours(x, y):
                                                          if 0 <= i < len(grid) and 0 <= j < len(grid[x]) and grid[x][y] < grid[i][j]:
                                                              result += [(i, j)]
                                                      return result
                                                  
                                                  def build_tree(grid, x, y):
                                                      return [build_tree(grid, i, j) for i, j in neighbours(grid, x, y)]
                                                  
                                                  def longest_path_in_tree(tree):
                                                      if len(tree) == 0:
                                                          return 0
                                                      return 1 + max(map(longest_path_in_tree, tree))
                                                  
                                                  def longest_descent(grid):
                                                      trees = [build_tree(grid, x, y) for x, row in enumerate(grid) for y, _ in enumerate(row)]
                                                      return max(map(longest_path_in_tree, trees))
                                                  

                                                  share|improve this answer

                                                  share|improve this answer

                                                  share|improve this answer

                                                  answered Jan 3 at 22:09

                                                  NishiokaNishioka

                                                  1213

                                                  1213

                                                      2

                                                      $begingroup$

                                                      Haskell, 188 186 bytes

                                                      Needs $texttt{-XNoMonomorphismRestriction}$:

                                                      f m|c<-[0..length(m!!0)-1],r<-[0..length m-1]=h[g[(x,y)]|x<-r,y<-c,let g((x,y):p)=h[1+g(k:p)|i<-[-1,1],k@(u,v)<-[(x+i,y),(x,y+i)],u#r,v#c,m!!u!!v<m!!x!!y,not$k#p]]
                                                      (#)=elem
                                                      h=foldl max 0
                                                      

                                                      Try it online!

                                                      Alternatively we could use notElem over (not.).(#) without the flag for $+4$ bytes:

                                                      Try it online!

                                                      Explanation & Ungolfed

                                                      Strategy: Recursively try all feasible paths, keeping track of visited entries and maximize their length.

                                                      Let’s first define some helpers.. Since we need elem and notElem, let’s use (#) for elem. Also, to maximize we’ll need a total function (maximize is not), returning $0$ when the list is empty:

                                                      safeMaximum = foldl max 0
                                                      

                                                      Now we’re ready to define our recursive function fun :: [[Integer]] -> Integer:

                                                      fun xs
                                                        | c <- [0..length(m!!0)-1]             -- all possible indices of xs' columns
                                                        , r <- [0..length m-1]                 -- all possible indices of xs' rows
                                                        = safeMaximum                          -- maximize ..
                                                            [ g [(x,y)]                        -- .. initially we haven't visited any others
                                                            | x <- c, y<-r                     -- .. all possible entries
                                                      -- For the purpose of golfing we define g in the list-comprehension, it takes all visited entries (p) where (x,y) is the most recent
                                                            , let g((x,y):p) = safeMaximum     -- maximize ..
                                                                [ 1 + g(k:p)                   -- .. recurse, adding (x,y) to the visited nodes & increment (the next path will be 1 longer)
                                                                | i <- [-1,1]                  -- offsets [left/up,right/down]
                                                                , k@(u,v) <-[(x+i,y),(x,y+i)]  -- next entry-candidate
                                                                , u#c, v#r                     -- make sure indices are in bound ..
                                                                , m!!u!!v < m!!x!!y            -- .. , the the path is decreasing
                                                                , not$(u,v)#p                  -- .. and we haven't already visited that element
                                                                ]
                                                            ]
                                                      

                                                      share|improve this answer

                                                      $endgroup$

                                                      • $begingroup$
                                                        How does this take grids? List of lists?
                                                        $endgroup$
                                                        – Beefster
                                                        Jan 4 at 17:42

                                                      • $begingroup$
                                                        @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
                                                        $endgroup$
                                                        – BMO
                                                        Jan 4 at 17:46

                                                      2

                                                      $begingroup$

                                                      Haskell, 188 186 bytes

                                                      Needs $texttt{-XNoMonomorphismRestriction}$:

                                                      f m|c<-[0..length(m!!0)-1],r<-[0..length m-1]=h[g[(x,y)]|x<-r,y<-c,let g((x,y):p)=h[1+g(k:p)|i<-[-1,1],k@(u,v)<-[(x+i,y),(x,y+i)],u#r,v#c,m!!u!!v<m!!x!!y,not$k#p]]
                                                      (#)=elem
                                                      h=foldl max 0
                                                      

                                                      Try it online!

                                                      Alternatively we could use notElem over (not.).(#) without the flag for $+4$ bytes:

                                                      Try it online!

                                                      Explanation & Ungolfed

                                                      Strategy: Recursively try all feasible paths, keeping track of visited entries and maximize their length.

                                                      Let’s first define some helpers.. Since we need elem and notElem, let’s use (#) for elem. Also, to maximize we’ll need a total function (maximize is not), returning $0$ when the list is empty:

                                                      safeMaximum = foldl max 0
                                                      

                                                      Now we’re ready to define our recursive function fun :: [[Integer]] -> Integer:

                                                      fun xs
                                                        | c <- [0..length(m!!0)-1]             -- all possible indices of xs' columns
                                                        , r <- [0..length m-1]                 -- all possible indices of xs' rows
                                                        = safeMaximum                          -- maximize ..
                                                            [ g [(x,y)]                        -- .. initially we haven't visited any others
                                                            | x <- c, y<-r                     -- .. all possible entries
                                                      -- For the purpose of golfing we define g in the list-comprehension, it takes all visited entries (p) where (x,y) is the most recent
                                                            , let g((x,y):p) = safeMaximum     -- maximize ..
                                                                [ 1 + g(k:p)                   -- .. recurse, adding (x,y) to the visited nodes & increment (the next path will be 1 longer)
                                                                | i <- [-1,1]                  -- offsets [left/up,right/down]
                                                                , k@(u,v) <-[(x+i,y),(x,y+i)]  -- next entry-candidate
                                                                , u#c, v#r                     -- make sure indices are in bound ..
                                                                , m!!u!!v < m!!x!!y            -- .. , the the path is decreasing
                                                                , not$(u,v)#p                  -- .. and we haven't already visited that element
                                                                ]
                                                            ]
                                                      

                                                      share|improve this answer

                                                      $endgroup$

                                                      • $begingroup$
                                                        How does this take grids? List of lists?
                                                        $endgroup$
                                                        – Beefster
                                                        Jan 4 at 17:42

                                                      • $begingroup$
                                                        @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
                                                        $endgroup$
                                                        – BMO
                                                        Jan 4 at 17:46

                                                      2

                                                      2

                                                      2

                                                      $begingroup$

                                                      Haskell, 188 186 bytes

                                                      Needs $texttt{-XNoMonomorphismRestriction}$:

                                                      f m|c<-[0..length(m!!0)-1],r<-[0..length m-1]=h[g[(x,y)]|x<-r,y<-c,let g((x,y):p)=h[1+g(k:p)|i<-[-1,1],k@(u,v)<-[(x+i,y),(x,y+i)],u#r,v#c,m!!u!!v<m!!x!!y,not$k#p]]
                                                      (#)=elem
                                                      h=foldl max 0
                                                      

                                                      Try it online!

                                                      Alternatively we could use notElem over (not.).(#) without the flag for $+4$ bytes:

                                                      Try it online!

                                                      Explanation & Ungolfed

                                                      Strategy: Recursively try all feasible paths, keeping track of visited entries and maximize their length.

                                                      Let’s first define some helpers.. Since we need elem and notElem, let’s use (#) for elem. Also, to maximize we’ll need a total function (maximize is not), returning $0$ when the list is empty:

                                                      safeMaximum = foldl max 0
                                                      

                                                      Now we’re ready to define our recursive function fun :: [[Integer]] -> Integer:

                                                      fun xs
                                                        | c <- [0..length(m!!0)-1]             -- all possible indices of xs' columns
                                                        , r <- [0..length m-1]                 -- all possible indices of xs' rows
                                                        = safeMaximum                          -- maximize ..
                                                            [ g [(x,y)]                        -- .. initially we haven't visited any others
                                                            | x <- c, y<-r                     -- .. all possible entries
                                                      -- For the purpose of golfing we define g in the list-comprehension, it takes all visited entries (p) where (x,y) is the most recent
                                                            , let g((x,y):p) = safeMaximum     -- maximize ..
                                                                [ 1 + g(k:p)                   -- .. recurse, adding (x,y) to the visited nodes & increment (the next path will be 1 longer)
                                                                | i <- [-1,1]                  -- offsets [left/up,right/down]
                                                                , k@(u,v) <-[(x+i,y),(x,y+i)]  -- next entry-candidate
                                                                , u#c, v#r                     -- make sure indices are in bound ..
                                                                , m!!u!!v < m!!x!!y            -- .. , the the path is decreasing
                                                                , not$(u,v)#p                  -- .. and we haven't already visited that element
                                                                ]
                                                            ]
                                                      

                                                      share|improve this answer

                                                      $endgroup$

                                                      Haskell, 188 186 bytes

                                                      Needs $texttt{-XNoMonomorphismRestriction}$:

                                                      f m|c<-[0..length(m!!0)-1],r<-[0..length m-1]=h[g[(x,y)]|x<-r,y<-c,let g((x,y):p)=h[1+g(k:p)|i<-[-1,1],k@(u,v)<-[(x+i,y),(x,y+i)],u#r,v#c,m!!u!!v<m!!x!!y,not$k#p]]
                                                      (#)=elem
                                                      h=foldl max 0
                                                      

                                                      Try it online!

                                                      Alternatively we could use notElem over (not.).(#) without the flag for $+4$ bytes:

                                                      Try it online!

                                                      Explanation & Ungolfed

                                                      Strategy: Recursively try all feasible paths, keeping track of visited entries and maximize their length.

                                                      Let’s first define some helpers.. Since we need elem and notElem, let’s use (#) for elem. Also, to maximize we’ll need a total function (maximize is not), returning $0$ when the list is empty:

                                                      safeMaximum = foldl max 0
                                                      

                                                      Now we’re ready to define our recursive function fun :: [[Integer]] -> Integer:

                                                      fun xs
                                                        | c <- [0..length(m!!0)-1]             -- all possible indices of xs' columns
                                                        , r <- [0..length m-1]                 -- all possible indices of xs' rows
                                                        = safeMaximum                          -- maximize ..
                                                            [ g [(x,y)]                        -- .. initially we haven't visited any others
                                                            | x <- c, y<-r                     -- .. all possible entries
                                                      -- For the purpose of golfing we define g in the list-comprehension, it takes all visited entries (p) where (x,y) is the most recent
                                                            , let g((x,y):p) = safeMaximum     -- maximize ..
                                                                [ 1 + g(k:p)                   -- .. recurse, adding (x,y) to the visited nodes & increment (the next path will be 1 longer)
                                                                | i <- [-1,1]                  -- offsets [left/up,right/down]
                                                                , k@(u,v) <-[(x+i,y),(x,y+i)]  -- next entry-candidate
                                                                , u#c, v#r                     -- make sure indices are in bound ..
                                                                , m!!u!!v < m!!x!!y            -- .. , the the path is decreasing
                                                                , not$(u,v)#p                  -- .. and we haven't already visited that element
                                                                ]
                                                            ]
                                                      

                                                      share|improve this answer

                                                      share|improve this answer

                                                      share|improve this answer

                                                      edited Jan 4 at 17:51

                                                      answered Jan 3 at 19:33

                                                      BMOBMO

                                                      11.8k22188

                                                      11.8k22188

                                                      • $begingroup$
                                                        How does this take grids? List of lists?
                                                        $endgroup$
                                                        – Beefster
                                                        Jan 4 at 17:42

                                                      • $begingroup$
                                                        @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
                                                        $endgroup$
                                                        – BMO
                                                        Jan 4 at 17:46

                                                      • $begingroup$
                                                        How does this take grids? List of lists?
                                                        $endgroup$
                                                        – Beefster
                                                        Jan 4 at 17:42

                                                      • $begingroup$
                                                        @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
                                                        $endgroup$
                                                        – BMO
                                                        Jan 4 at 17:46

                                                      $begingroup$
                                                      How does this take grids? List of lists?
                                                      $endgroup$
                                                      – Beefster
                                                      Jan 4 at 17:42

                                                      $begingroup$
                                                      How does this take grids? List of lists?
                                                      $endgroup$
                                                      – Beefster
                                                      Jan 4 at 17:42

                                                      $begingroup$
                                                      @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
                                                      $endgroup$
                                                      – BMO
                                                      Jan 4 at 17:46

                                                      $begingroup$
                                                      @Beefster: Yes, it says [[Integer]] is list of lists. Though in the linked TIO you have a wrapper parse :: String -> [[Integer]], st. you can use strings split on spaces and new-lines.
                                                      $endgroup$
                                                      – BMO
                                                      Jan 4 at 17:46

                                                      1

                                                      $begingroup$

                                                      Python 3, 263 227 bytes

                                                      def f(m):
                                                       p={(x,y):[c for i in[-1,1]for c in[(x,y+i),(x+i,y)]]for x,y in m};d={c:0 for c in p if not p[c]}
                                                       while len(p)-len(d):
                                                        for c in p:
                                                         for b in p[c]:
                                                          if b in d:d[c]=max(d[b]+1,d.get(c,0))
                                                       return max(d.values())
                                                      

                                                      Try it online!

                                                      -2 bytes thanks to BMO

                                                      Takes grids in the format {(0, 0): 1, (1, 0): 2, ...}. This format can be generated from the example format using the following utility function:

                                                      lambda s,e=enumerate:{(x,y):int(n)for y,l in e(s.split('n'))for x,n in e(l.split())}
                                                      

                                                      share|improve this answer

                                                      $endgroup$

                                                        1

                                                        $begingroup$

                                                        Python 3, 263 227 bytes

                                                        def f(m):
                                                         p={(x,y):[c for i in[-1,1]for c in[(x,y+i),(x+i,y)]]for x,y in m};d={c:0 for c in p if not p[c]}
                                                         while len(p)-len(d):
                                                          for c in p:
                                                           for b in p[c]:
                                                            if b in d:d[c]=max(d[b]+1,d.get(c,0))
                                                         return max(d.values())
                                                        

                                                        Try it online!

                                                        -2 bytes thanks to BMO

                                                        Takes grids in the format {(0, 0): 1, (1, 0): 2, ...}. This format can be generated from the example format using the following utility function:

                                                        lambda s,e=enumerate:{(x,y):int(n)for y,l in e(s.split('n'))for x,n in e(l.split())}
                                                        

                                                        share|improve this answer

                                                        $endgroup$

                                                          1

                                                          1

                                                          1

                                                          $begingroup$

                                                          Python 3, 263 227 bytes

                                                          def f(m):
                                                           p={(x,y):[c for i in[-1,1]for c in[(x,y+i),(x+i,y)]]for x,y in m};d={c:0 for c in p if not p[c]}
                                                           while len(p)-len(d):
                                                            for c in p:
                                                             for b in p[c]:
                                                              if b in d:d[c]=max(d[b]+1,d.get(c,0))
                                                           return max(d.values())
                                                          

                                                          Try it online!

                                                          -2 bytes thanks to BMO

                                                          Takes grids in the format {(0, 0): 1, (1, 0): 2, ...}. This format can be generated from the example format using the following utility function:

                                                          lambda s,e=enumerate:{(x,y):int(n)for y,l in e(s.split('n'))for x,n in e(l.split())}
                                                          

                                                          share|improve this answer

                                                          $endgroup$

                                                          Python 3, 263 227 bytes

                                                          def f(m):
                                                           p={(x,y):[c for i in[-1,1]for c in[(x,y+i),(x+i,y)]]for x,y in m};d={c:0 for c in p if not p[c]}
                                                           while len(p)-len(d):
                                                            for c in p:
                                                             for b in p[c]:
                                                              if b in d:d[c]=max(d[b]+1,d.get(c,0))
                                                           return max(d.values())
                                                          

                                                          Try it online!

                                                          -2 bytes thanks to BMO

                                                          Takes grids in the format {(0, 0): 1, (1, 0): 2, ...}. This format can be generated from the example format using the following utility function:

                                                          lambda s,e=enumerate:{(x,y):int(n)for y,l in e(s.split('n'))for x,n in e(l.split())}
                                                          

                                                          share|improve this answer

                                                          share|improve this answer

                                                          share|improve this answer

                                                          edited Jan 3 at 20:54

                                                          answered Jan 3 at 18:58

                                                          wizzwizz4wizzwizz4

                                                          1,2171035

                                                          1,2171035

                                                              draft saved
                                                              draft discarded

                                                              If this is an answer to a challenge…

                                                              • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.

                                                              • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
                                                                Explanations of your answer make it more interesting to read and are very much encouraged.

                                                              • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.

                                                              More generally…

                                                              • …Please make sure to answer the question and provide sufficient detail.

                                                              • …Avoid asking for help, clarification or responding to other answers (use comments instead).

                                                              draft saved

                                                              draft discarded

                                                              StackExchange.ready(
                                                              function () {
                                                              StackExchange.openid.initPostLogin(‘.new-post-login’, ‘https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f178326%2flength-of-the-longest-descent%23new-answer’, ‘question_page’);
                                                              }
                                                              );

                                                              Post as a guest

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Required, but never shown

                                                              Related Post

                                                              Leave a Reply

                                                              Your email address will not be published. Required fields are marked *