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)
La 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)]
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_posicionesDiagonalesPrincipales2 :: Positive Int -> Positive Int -> Bool prop_posicionesDiagonalesPrincipales2 (Positive m) (Positive n) = posicionesDiagonalesPrincipales1 m n == posicionesDiagonalesPrincipales2 m n -- La comprobación es -- λ> quickCheck prop_posicionesDiagonalesPrincipales2 -- +++ 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