Sua tarefa é determinar o comprimento da descida mais longa em uma "montanha" representada como uma grade de alturas inteiras. Uma "descida" é qualquer caminho de uma célula inicial para células adjacentes ortogonalmente com alturas estritamente decrescentes (isto é, não na diagonal nem na mesma altura). Por exemplo, você pode passar de 5-4-3-1, mas não 5-5-4-3-3-2-1. O comprimento desse caminho é quantos movimentos celulares existem da célula inicial para a célula final, portanto, 5-4-3-1 é o comprimento 3.

Você receberá uma grade retangular como entrada e deverá produzir um número inteiro indicando a descida mais longa.

Exemplos

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

O comprimento da descida mais longa nesta montanha é 5. O caminho mais longo começa no 7, move-se para a esquerda, para cima, para a esquerda, para cima e para a esquerda (7-6-5-4-2-1). Como existem 5 movimentos nesse caminho, o comprimento do caminho é 5.

Eles podem ter o mesmo número.

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

Como esse mapa de altura é plano, a descida mais longa é 0. (não 19, pois a sequência do caminho deve ser estritamente descendente)

Os mapas de altura podem ser compostos por números maiores que os números de um dígito.

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

O caminho mais longo aqui é de comprimento 6. (21, 20, 18, 17, 14, 12, 10)

... E números ainda maiores também são bons.

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

A descida mais longa aqui é de comprimento 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 132645)

Regras e Notas

• As grades podem ser obtidas em qualquer formato conveniente. Especifique seu formato na sua resposta.
• Você pode assumir que o mapa de altura é perfeitamente retangular, não é vazio e contém apenas números inteiros positivos no intervalo inteiro de 32 bits assinado.
• O caminho de descida mais longo pode começar e terminar em qualquer lugar da grade.
• Você não precisa descrever o caminho de descida mais longo de nenhuma maneira. Somente seu comprimento é necessário.
• O código mais curto vence

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

Experimente online!

Comentado

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

Quão?

$x$$y$$p$

Geléia ,  23 21  20 bytes

-2 graças a Erik, o Outgolfer

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

Experimente online! (muito ineficiente para os exemplos - o caminho aqui é o95 94 93 83 77 40 10que6é produzido)

Quão?

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

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)

Experimente online!

Recebe entrada na forma de um dicionário (x, y): value.

-7 bytes graças a wizzwizz4, -2 bytes graças a Jonathan Allen, -2 bytes graças a BMO

Alternativa, 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)

Experimente online!

Essencialmente a mesma solução, apenas com o lambda final substituído por um programa real. Pessoalmente, eu gosto mais do primeiro, mas esse chega perto da contagem de bytes, permitindo gser usado como uma variável global.

Limpo , 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)]]

Experimente online!

Uma solução de força bruta usando uma lista de listas de números inteiros ( [[Int]]).
O driver TIO usa o mesmo formato que os exemplos por meio do STDIN.

É muito lento para executar qualquer um dos exemplos no TIO e provavelmente localmente também, mas funciona em teoria.

Este faz a mesma coisa mais rapidamente, pode fazer 3x3 ou 2x4 no TIO e 4x4 e 3x5 localmente.

Recuado:

$ 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)
            ]
        ]

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

Experimente online!

Grade é representada como lista de listas:

[
    [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],
]

Código original não destruído:

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

Haskell , 188 186 bytes

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

Experimente online!

notElem(not.).(#)$+4$

Experimente online!

Explicação e Sem Golfe

Estratégia: tente recursivamente todos os caminhos possíveis, mantendo o controle das entradas visitadas e maximizando seu tamanho.

elemnotElem(#)elemmaximize$0$

safeMaximum = foldl max 0

Agora estamos prontos para definir nossa função recursiva 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
          ]
      ]

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

Experimente online!

-2 bytes graças ao BMO

Toma grades no formato {(0, 0): 1, (1, 0): 2, ...}. Este formato pode ser gerado a partir do formato de exemplo usando a seguinte função de utilitário:

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