Ir al contenido principal

Posiciones de las diagonales principales

Las posiciones de una matriz con 3 filas y 4 columnas son

(1,1) (1,2) (1,3) (1,4)
(2,1) (2,2) (2,3) (2,4)
(3,1) (3,2) (3,3) (3,4)

Las posiciones de sus 6 diagonales principales son

[(3,1)]
[(2,1),(3,2)]
[(1,1),(2,2),(3,3)]
[(1,2),(2,3),(3,4)]
[(1,3),(2,4)]
[(1,4)]

Definir la función

posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]

tal que (posicionesdiagonalesprincipales m n) es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,

λ> mapM_ print (posicionesDiagonalesPrincipales 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)]
λ> mapM_ print (posicionesDiagonalesPrincipales 4 4)
[(4,1)]
[(3,1),(4,2)]
[(2,1),(3,2),(4,3)]
[(1,1),(2,2),(3,3),(4,4)]
[(1,2),(2,3),(3,4)]
[(1,3),(2,4)]
[(1,4)]
λ> mapM_ print (posicionesDiagonalesPrincipales 4 3)
[(4,1)]
[(3,1),(4,2)]
[(2,1),(3,2),(4,3)]
[(1,1),(2,2),(3,3)]
[(1,2),(2,3)]
[(1,3)]

Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.

Soluciones

A continuación se muestran

1. Soluciones en Haskell

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

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

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 :: (Int -> Int -> [[(Int, Int)]]) -> Spec
specG posicionesDiagonalesPrincipales = do
  it "e1" $
    posicionesDiagonalesPrincipales 3 4 `shouldBe`
      [[(3,1)],
       [(2,1),(3,2)],
       [(1,1),(2,2),(3,3)],
       [(1,2),(2,3),(3,4)],
       [(1,3),(2,4)],
       [(1,4)]]
  it "e2" $
    posicionesDiagonalesPrincipales 4 4 `shouldBe`
      [[(4,1)],
       [(3,1),(4,2)],
       [(2,1),(3,2),(4,3)],
       [(1,1),(2,2),(3,3),(4,4)],
       [(1,2),(2,3),(3,4)],
       [(1,3),(2,4)],
       [(1,4)]]
  it "e3" $
    posicionesDiagonalesPrincipales 4 3 `shouldBe`
      [[(4,1)],
       [(3,1),(4,2)],
       [(2,1),(3,2),(4,3)],
       [(1,1),(2,2),(3,3)],
       [(1,2),(2,3)],
       [(1,3)]]

spec :: Spec
spec = do
  describe "def. 1" $ specG posicionesDiagonalesPrincipales1
  describe "def. 2" $ specG posicionesDiagonalesPrincipales2

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

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

-- La propiedad es
prop_posicionesDiagonalesPrincipales_equiv :: Positive Int -> Positive Int -> Bool
prop_posicionesDiagonalesPrincipales_equiv (Positive m) (Positive n) =
  posicionesDiagonalesPrincipales1 m n ==
  posicionesDiagonalesPrincipales2 m n

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

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

-- La comparación es
--   λ> length (posicionesDiagonalesPrincipales1 (10^7) (10^6))
--   10999999
--   (6.14 secs, 3,984,469,440 bytes)
--   λ> length (posicionesDiagonalesPrincipales2 (10^7) (10^6))
--   10999999
--   (3.07 secs, 2,840,469,440 bytes)

2. Soluciones en Python

from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st

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

matriz = list[list[tuple[int, int]]]

def posicionesDiagonalesPrincipales1(m: int, n: int) -> matriz:
    def iniciales() -> list[tuple[int, int]]:
        return [(i,1) for i in range(m,1,-1)] + [(1,j) for j in range(1, n+1)]
    def extension(p: tuple[int, int]) -> list[tuple[int, int]]:
        (i,j) = p
        return [(i+k,j+k) for k in range(0, 1+min(m-i, n-j))]
    return [extension(ij) for ij in iniciales()]

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

def posicionesDiagonalesPrincipales2(m: int, n: int) -> matriz:
    return [list(zip(range(i,m+1), range(1,n+1))) for i in range(m,0,-1)] + \
           [list(zip(range(1,m+1), range(j,n+1))) for j in range(2,n+1)]

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

def test_posicionesDiagonalesPrincipales() -> None:
    for posicionesDiagonalesPrincipales in [posicionesDiagonalesPrincipales1,
                                            posicionesDiagonalesPrincipales2]:
        assert posicionesDiagonalesPrincipales(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)]]
        assert posicionesDiagonalesPrincipales(4, 4) == \
            [[(4,1)],
             [(3,1),(4,2)],
             [(2,1),(3,2),(4,3)],
             [(1,1),(2,2),(3,3),(4,4)],
             [(1,2),(2,3),(3,4)],
             [(1,3),(2,4)],
             [(1,4)]]
        assert posicionesDiagonalesPrincipales(4, 3) == \
            [[(4,1)],
             [(3,1),(4,2)],
             [(2,1),(3,2),(4,3)],
             [(1,1),(2,2),(3,3)],
             [(1,2),(2,3)],
             [(1,3)]]
    print("Verificado")

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

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.integers(min_value=1, max_value=100),
       st.integers(min_value=1, max_value=100))
def test_posicionesDiagonalesPrincipales_equiv(m: int, n: int) -> None:
    assert posicionesDiagonalesPrincipales1(m, n) == \
           posicionesDiagonalesPrincipales2(m, n)

# La comprobación es
#    >>> test_posicionesDiagonalesPrincipales_equiv()
#    >>>

# 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('posicionesDiagonalesPrincipales1(10**4, 2*10**3)')
#    3.32 segundos
#    >>> tiempo('posicionesDiagonalesPrincipales2(10**4, 2*10**3)')
#    2.16 segundos

2. Soluciones en Common Lisp

(ql:quickload "fiveam" :silent t)

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

(in-package :posiciones-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)))))

(defun posiciones-diagonales-principales-1 (m n)
  (mapcar (lambda (ij) (extension ij m n)) (iniciales m n)))

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

(defun posiciones-diagonales-principales-2 (m n)
  (flet ((iniciales ()
           (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)
           (let ((i (first ij))
                 (j (second ij)))
             (loop for k from 0 to (min (- m i) (- n j))
                   collect (list (+ i k) (+ j k))))))
    (mapcar (lambda (ij) (extension ij)) (iniciales))))

;;; 3ª definición
;;; =============

(defun posiciones-diagonales-principales-3 (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 posiciones-diagonales-principales-4 (m n)
  (let ((iniciales (append (loop for i from m downto 2 collect (list i 1))
                           (loop for j from 1 to n collect (list 1 j))))
        (result '()))
    (dolist (ij iniciales result)
      (let* ((i (first ij))
             (j (second ij))
             (lim (min (- m i) (- n j)))
             (diagonal (loop for k from 0 to lim collect (list (+ i k) (+ j k)))))
        (push diagonal result)))
    (nreverse result)))

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

(test posiciones-diagonales-principales
  (mapc (lambda (func)
          (is (equal (funcall func 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)))))
          (is (equal (funcall func '4 4) '(((4 1))
                                           ((3 1) (4 2))
                                           ((2 1) (3 2) (4 3))
                                           ((1 1) (2 2) (3 3) (4 4))
                                           ((1 2) (2 3) (3 4))
                                           ((1 3) (2 4))
                                           ((1 4)))))
          (is (equal (funcall func '4 3) '(((4 1))
                                           ((3 1) (4 2))
                                           ((2 1) (3 2) (4 3))
                                           ((1 1) (2 2) (3 3))
                                           ((1 2) (2 3))
                                           ((1 3))))))
        '(posiciones-diagonales-principales-1
          posiciones-diagonales-principales-2
          posiciones-diagonales-principales-3
          posiciones-diagonales-principales-4)))

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

;;; La verificación es
;;;    > (posiciones-diagonales-principales::verifica)
;;;
;;;    Running test POSICIONES-DIAGONALES-PRINCIPALES .........

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

;;; La propiedad es
(test posiciones-diagonales-principales-equiv
  (for-all ((m (gen-integer :min 1 :max 20))
            (n (gen-integer :min 1 :max 20)))
    (let ((res (posiciones-diagonales-principales-1 m n)))
      (is (equal (posiciones-diagonales-principales-2 m n) res))
      (is (equal (posiciones-diagonales-principales-3 m n) res))
      (is (equal (posiciones-diagonales-principales-4 m n) res)))))

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

;;; La comprobación es
;;;    > (posiciones-diagonales-principales::comprueba)
;;;
;;;    Running test POSICIONES-DIAGONALES-PRINCIPALES-EQUIV ...
;;;    (#<IT.BESE.FIVEAM::FOR-ALL-TEST-PASSED {10030E76B3}>)

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

;;; La comparación es
;;;   > (time (length (posiciones-diagonales-principales-1 3000 2000)))
;;;   0.453 seconds of real time
;;;   > (time (length (posiciones-diagonales-principales-2 3000 2000)))
;;;   0.807 seconds of real time
;;;   > (time (length (posiciones-diagonales-principales-3 3000 2000)))
;;;   0.440 seconds of real time
;;;   > (time (length (posiciones-diagonales-principales-4 3000 2000)))
;;;   0.672 seconds of real time