(  1  6 11  2 )
   (  7 12  3  8 )
   (  3  8  4  9 )

   [1,6,11,2,8,9]
   [1,6,11,3,8,9]
   [1,6,12,3,8,9]
   [1,7,12,3,8,9]
   [1,6,11,3,4,9]
   [1,6,12,3,4,9]
   [1,7,12,3,4,9]
   [1,6,12,8,4,9]
   [1,7,12,8,4,9]
   [1,7, 3,8,4,9]

   caminoMaxSuma :: Matrix Int -> [Int]

   λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [1,7,12,8,4,9]
   λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
   187001249

module Camino_de_maxima_suma_en_una_matriz where

import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición de caminoMaxSuma (con caminos1)
-- =============================================

caminoMaxSuma1 :: Matrix Int -> [Int]
caminoMaxSuma1 m =
  head [c | c <- cs, sum c == k]
  where cs = caminos1 m
        k  = maximum (map sum cs)

caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
  reverse (map reverse (caminos1Aux m (nf,nc)))
  where nf = nrows m
        nc = ncols m

-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m
-- desde la posición (1,1) hasta la posición p. Por ejemplo,
caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]
caminos1Aux m (1,1) = [[m!(1,1)]]
caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]
caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]
caminos1Aux m (i,j) = [m!(i,j) : xs
                      | xs <- caminos1Aux m (i,j-1) ++
                              caminos1Aux m (i-1,j)]

-- 2ª definición de caminoMaxSuma (con caminos2)
-- =============================================

caminoMaxSuma2 :: Matrix Int -> [Int]
caminoMaxSuma2 m =
  head [c | c <- cs, sum c == k]
  where cs = caminos2 m
        k  = maximum (map sum cs)

caminos2 :: Matrix Int -> [[Int]]
caminos2 m =
  map reverse (matrizCaminos m ! (nrows m, ncols m))

matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = q
  where
    q = matrix (nrows m) (ncols m) f
    f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]
    f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]
    f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]

-- 3ª definición de caminoMaxSuma (con programación dinámica)
-- ==========================================================

caminoMaxSuma3 :: Matrix Int -> [Int]
caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))
  where nf = nrows m
        nc = ncols m
        q  = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])
caminoMaxSumaAux m = q
  where
    nf = nrows m
    nc = ncols m
    q  = matrix nf nc f
      where
        f (1,1) = (m!(1,1),[m!(1,1)])
        f (1,j) = (k + m!(1,j), m!(1,j):xs)
          where (k,xs) = q!(1,j-1)
        f (i,1) = (k + m!(i,1), m!(i,1):xs)
          where (k,xs) = q!(i-1,1)
        f (i,j) | k1 > k2   = (k1 + m!(i,j), m!(i,j):xs)
                | otherwise = (k2 + m!(i,j), m!(i,j):ys)
          where (k1,xs) = q!(i,j-1)
                (k2,ys) = q!(i-1,j)

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))
--    21
--    (3.92 secs, 1,778,557,904 bytes)
--    λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))
--    21
--    (1.16 secs, 798,889,488 bytes)
--    λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))
--    21
--    (0.00 secs, 680,256 bytes)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]
  it "e2" $
    caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]
  it "e3" $
    caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0007 seconds
--    3 examples, 0 failures

from collections import defaultdict
from sys import setrecursionlimit
from timeit import Timer, default_timer

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definición de caminoMaxSuma (con caminos1)
# =============================================

def caminoMaxSuma1(m: list[list[int]]) -> list[int]:
    cs = caminos1(m)
    k = max((sum(c) for c in cs))
    return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos1 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 2ª definición de caminoMaxSuma (con caminos2)
# =============================================

def caminoMaxSuma2(m: list[list[int]]) -> list[int]:
    cs = caminos2(m)
    k = max((sum(c) for c in cs))
    return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos2 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 3ª definición de caminoMaxSuma (con programación dinámica)
# ==========================================================

def caminoMaxSuma3(m: list[list[int]]) -> list[int]:
    nf = len(m)
    nc = len(m[0])
    return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1]))

# diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los
# puntos de la matriz p y sus valores son los pares formados por la
# máxima suma de los caminos hasta dicho punto y uno de los caminos con
# esa suma. Por ejemplo,
#    >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])
#    {(1, 1): (1, [1]),
#     (1, 2): (7, [6, 1]),
#     (1, 3): (18, [11, 6, 1]),
#     (1, 4): (20, [2, 11, 6, 1]),
#     (2, 1): (8, [7, 1]),
#     (3, 1): (11, [3, 7, 1]),
#     (2, 2): (20, [12, 7, 1]),
#     (2, 3): (23, [3, 12, 7, 1]),
#     (2, 4): (31, [8, 3, 12, 7, 1]),
#     (3, 2): (28, [8, 12, 7, 1]),
#     (3, 3): (32, [4, 8, 12, 7, 1]),
#     (3, 4): (41, [9, 4, 8, 12, 7, 1])}
def diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]:
    m = len(p)
    n = len(p[0])
    q: dict[tuple[int, int], tuple[int, list[int]]] = {}
    q[(1, 1)] = (p[0][0], [p[0][0]])
    for j in range(2, n + 1):
        (k, xs) = q[(1, j-1)]
        q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs)
    for i in range(2, m + 1):
        (k,xs) = q[(i-1,1)]
        q[(i, 1)] =  (k + p[i-1][0], [p[i-1][0]] + xs)
    for i in range(2, m + 1):
        for j in range(2, n + 1):
            (k1,xs) = q[(i,j-1)]
            (k2,ys) = q[(i-1,j)]
            if k1 > k2:
                q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs)
            else:
                q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys)
    return q

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    1.92 segundos
#    >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.65 segundos
#    >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.00 segundos

# # Verificación
# # ============

def test_caminoMaxSuma() -> None:
    assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    print("Verificado")

# La verificación es
#    >>> test_caminoMaxSuma()
#    Verificado