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.

1 1 1 1 1

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.

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

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

Python, 150 147 140 bytes

-7 bytes thanks to wizzwizz4!

l=lambda g,i,j:1+max(0<i+m<6>j+n>0<g[i+m,j+n]<g[i,j]and l(g,i+m,j+n)for m,n in((-1,0),(1,0),(0,-1),(0,1)))

lambda g:max(l(g,*t)for t in g)-1

Try it online!

Like the other Python answer, this takes input in the form of a dictionary (x, y): value; however, I use 1-indexed dictionaries.

I definitely think this could be golfed some more, especially the in((-1,0),(1,0),(0,-1),(0,1)) part and the use of two lambdas.

Clean, 209 bytes

import StdEnv,Data.List

z=zipWith

$l=maximum[length k\p<-permutations[(v,[x,y])\y<-[0..]&u<-l,x<-[0..]&v<-u],(k,[m:n])<-map unzip(subsequences p)|prod(map(sum o map abs)(z(z(-))n[m:n]))==1&&and(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 3x3 or 2x4 on TIO and 4x4 and 3x5 locally.

Haskell, 165 bytes

Needs $texttt{-XNoMonomorphismRestriction}$:

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

(#)=elem

h=foldl max 0

Try it online!

Alternatively we could use notElem over (not.).(#) without the flag for $+2$ 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

  | r <- [0..length m-1]  -- all possible indices of xs (luckily it's square)

  = safeMaximum                        -- maximize ..

      [ x!y $                        -- .. initially we haven't visited any others

      | x <- r, y<-r                   -- .. all possible entries

-- For the purpose of golfing we define (!) in the list-comprehension, it takes the current entry (x,y) and all visited ones (p)

      , let (x!y) p = safeMaximum      -- maximize ..

          [ 1 + (u!v$(x,y):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]

          , (u,v) <-[(x+i,y),(x,y+i)]  -- next entry-candidate

          , u#r, 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

          ]

      ]

(#)=elem

JavaScript (ES7),  106 103 102  98 bytes

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

Try it online!

Jelly, 25 bytes

ZIASỊẠ

ŒỤṚŒPḊÇƇœị⁸>Ɲ€ẠƇṪL

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