1  2  3  4
5  6  7  8
9 10 11 12

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

diagonalesPrincipales :: Array (Int,Int) a -> [[a]]

λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

import Data.Array (Array, (!), bounds, listArray)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª solución
-- ===========

diagonalesPrincipales1 :: Array (Int,Int) a -> [[a]]
diagonalesPrincipales1 p =
  [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales1 m n]
  where (_,(m,n)) = bounds p

posicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales1 m n =
  [extension ij | ij <- iniciales]
  where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]]
        extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]]

-- 2ª solución
-- ===========

diagonalesPrincipales2 :: Array (Int,Int) a -> [[a]]
diagonalesPrincipales2 p =
  [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales2 m n]
  where (_,(m,n)) = bounds p

posicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]]
posicionesDiagonalesPrincipales2 m n =
  [zip [i..m] [1..n] | i <- [m,m-1..1]] ++
  [zip [1..m] [j..n] | j <- [2..n]]

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

verifica :: IO ()
verifica = hspec spec

specG :: (Array (Int,Int) Int -> [[Int]]) -> Spec
specG diagonalesPrincipales = do
  it "e1" $
    diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) `shouldBe`
      [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

spec :: Spec
spec = do
  describe "def. 1" $ specG diagonalesPrincipales1
  describe "def. 2" $ specG diagonalesPrincipales2

-- La verificación es
--    λ> verifica
--    2 examples, 0 failures

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_diagonalesPrincipales2 :: Positive Int -> Positive Int -> Bool
prop_diagonalesPrincipales2 (Positive m) (Positive n) =
  diagonalesPrincipales1 p == diagonalesPrincipales2 p
  where p = listArray ((1,1),(m,n)) [1..]

-- La comprobación es
--    λ> quickCheck prop_diagonalesPrincipales2
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> length (diagonalesPrincipales1 (listArray ((1,1),(10^4,10^4)) [1..]))
--    19999
--    (6.90 secs, 8,010,369,224 bytes)
--    λ> length (diagonalesPrincipales2 (listArray ((1,1),(10^4,10^4)) [1..]))
--    19999
--    (6.78 secs, 8,008,289,224 bytes)

from typing import TypeVar

from src.Posiciones_diagonales_principales import (
    posicionesDiagonalesPrincipales1, posicionesDiagonalesPrincipales2)

A = TypeVar('A')

# 1ª solución
# ===========

matriz = list[list[A]]

def diagonalesPrincipales1(p: matriz[A]) -> list[list[A]]:
    m = len(p)
    n = len(p[0])
    return [[p[i-1][j-1] for (i,j) in ijs]
            for ijs in posicionesDiagonalesPrincipales1(m, n)]

# 2ª solución
# ===========

def diagonalesPrincipales2(p: matriz[A]) -> list[list[A]]:
    m = len(p)
    n = len(p[0])
    return [[p[i-1][j-1] for (i,j) in ijs]
            for ijs in posicionesDiagonalesPrincipales2(m, n)]

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

def test_diagonalesPrincipales() -> None:
    for diagonalesPrincipales in [diagonalesPrincipales1,
                                  diagonalesPrincipales2]:
        assert diagonalesPrincipales([[ 1, 2, 3, 4],
                                      [ 5, 6, 7, 8],
                                      [ 9,10,11,12]]) == \
                    [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
    print("Verificado")

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

(ql:quickload "fiveam" :silent t)

(defpackage :diagonales-principales
  (:use :cl
        :fiveam))

(in-package :diagonales-principales)

;;; 1ª solución
;;; ===========

;;; (iniciales m n) es la lista de los elementos iniciales de las
;;; posiciones de las diagonales principales de una matriz con m filas y
;;; n columnas. Por ejemplo,
;;;    > (iniciales 3 4)
;;;    ((3 1) (2 1) (1 1) (1 2) (1 3) (1 4))
(defun iniciales (m n)
  (append (loop for i from m downto 2 collect (list i 1))
          (loop for j from 1 to n collect (list 1 j))))

;;; (extension ij m n) es extension de la diagonal principal a partir de
;;; la posicion ij en una matriz de orden mxn. Por ejemplo,
;;;    > (extension '(2 1) 3 4)
;;;    ((2 1) (3 2))
;;;    > (extension '(1 1) 3 4)
;;;    ((1 1) (2 2) (3 3))
;;;    > (extension '(2 3) 3 4)
;;;    ((2 3) (3 4))
(defun extension (ij m n)
  (let ((i (first ij))
        (j (second ij)))
    (loop for k from 0 to (min (- m i) (- n j))
          collect (list (+ i k) (+ j k)))))

;;; (posiciones-diagonales-principales1 m n) es la lista de las posiciones
;;; de las diagonales principales de una matriz con m filas y n
;;; columnas. Por ejemplo,
;;;    > (posiciones-diagonales-principales1 3 4)
;;;    (((3 1))
;;;     ((2 1) (3 2))
;;;     ((1 1) (2 2) (3 3))
;;;     ((1 2) (2 3) (3 4))
;;;     ((1 3) (2 4))
;;;     ((1 4)))
(defun posiciones-diagonales-principales1 (m n)
  (mapcar (lambda (ij) (extension ij m n)) (iniciales m n)))

(defun diagonales-principales1 (p)
  (let* ((dimension (array-dimensions p))
         (m (first dimension))
         (n (second dimension)))
    (mapcar (lambda (ijs)
              (mapcar (lambda (ij)
                        (aref p (1- (first ij)) (1- (second ij))))
                      ijs))
            (posiciones-diagonales-principales1 m n))))

;;; 2ª solución
;;; ===========

(defun posiciones-diagonales-principales2 (m n)
  (append
    (loop for i from m downto 1
          collect (loop for r from i to m
                        for c from 1 to n
                        collect (list r c)))
    (loop for j from 2 to n
          collect (loop for r from 1 to m
                        for c from j to n
                        collect (list r c)))))

(defun diagonales-principales2 (p)
  (let* ((dimension (array-dimensions p))
         (m (first dimension))
         (n (second dimension)))
    (mapcar (lambda (ijs)
              (mapcar (lambda (ij)
                        (aref p (1- (first ij)) (1- (second ij))))
                      ijs))
            (posiciones-diagonales-principales2 m n))))

;;; Verificación
;;; ============

(test diagonales-principales
  (mapc (lambda (func)
          (is (equal (funcall func (make-array '(3 4)
                                               :initial-contents
                                               '((1 2 3 4)
                                                 (5 6 7 8)
                                                 (9 10 11 12))))
                     '((9) (5 10) (1 6 11) (2 7 12) (3 8) (4)))))
        '(diagonales-principales1
          diagonales-principales2)))

(defun verifica ()
  (run 'diagonales-principales))

;;; La verificación es
;;;    (diagonales-principales::verifica)


;;; Equivalencia de las definiciones
;;; ================================

;;; (matriz-aleatoria) genera una matriz aleatoria. Por ejemplo.
;;;    > (matriz-aleatoria)
;;;    #2A((1 0 5) (0 5 8) (0 2 4) (5 6 9) (3 3 1) (0 5 8) (5 2 0))
;;;    DIAGONALES-PRINCIPALES> (matriz-aleatoria)
;;;    #2A((8 8) (5 4) (9 5) (3 8))
(defun matriz-aleatoria ()
  (let ((m (1+ (random 10)))
        (n (1+ (random 10))))
    (make-array (list  m n)
                :initial-contents
                (loop for i from 1 to m
                                   collect (loop for j from 1 to n
                                                 collect (random 10))))))

;;; La propiedad es
(test diagonales-principales-equiv
  (for-all ((p 'matriz-aleatoria))
    (is (equal (diagonales-principales1 p)
               (diagonales-principales2 p)))))

(defun comprueba ()
  (run 'diagonales-principales-equiv))

;;; La comprobación es
;;;    > (diagonales-principales::comprueba)
;;;
;;;    Running test DIAGONALES-PRINCIPALES-EQUIV ...

;;; Comparación de eficiencia
;;; =========================

;;; La comparación es
;;;    > (setf ejemplo (make-array '(3000 2000) :initial-element 0))
;;;    > (time (length (diagonales-principales1 ejemplo)))
;;;    0.829 seconds of real time
;;;    > (time (length (diagonales-principales2 ejemplo)))
;;;    1.017 seconds of real time