Matriz zigzagueante
La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es
1 2 3 4 5 |
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24 |
La colocación de los elementos se puede ver gráficamente en esta figura
Definir la función
1 |
zigZag :: Int -> Matrix Int |
tal que (zigZag n)
es la matriz zigzagueante de orden n
. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
λ> zigZag 5 ┌ ┐ │ 0 1 5 6 14 │ │ 2 4 7 13 15 │ │ 3 8 12 16 21 │ │ 9 11 17 20 22 │ │ 10 18 19 23 24 │ └ ┘ λ> zigZag 4 ┌ ┐ │ 0 1 5 6 │ │ 2 4 7 12 │ │ 3 8 11 13 │ │ 9 10 14 15 │ └ ┘ λ> maximum (zigZag 1500) 2249999 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
import Data.List (sort, sortBy) import Data.Matrix (Matrix, fromList) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== zigZag1 :: Int -> Matrix Int zigZag1 n = fromList n n (elementosZigZag n) -- (elementosZigZag n) es la lista de los elementos de la matriz -- zizagueante de orden n. Por ejemplo. -- λ> elementosZigZag 5 -- [0,1,5,6,14,2,4,7,13,15,3,8,12,16,21,9,11,17,20,22,10,18,19,23,24] elementosZigZag :: Int -> [Int] elementosZigZag n = map snd (sort (zip (ordenZigZag n) [0..])) -- (ordenZigZag n) es la lista de puntos del cuadrado nxn recorridos en -- zig-zag por las diagonales secundarias. Por ejemplo, -- λ> ordenZigZag 4 -- [(1,1), (1,2),(2,1), (3,1),(2,2),(1,3), (1,4),(2,3),(3,2),(4,1), -- (4,2),(3,3),(2,4), (3,4),(4,3), (4,4)] ordenZigZag :: Int -> [(Int,Int)] ordenZigZag n = concat [aux n m | m <- [2..2*n]] where aux k m | odd m = [(x,m-x) | x <- [max 1 (m-k)..min k (m-1)]] | otherwise = [(m-x,x) | x <- [max 1 (m-k)..min k (m-1)]] -- 2ª solución -- =========== zigZag2 :: Int -> Matrix Int zigZag2 n = fromList n n (elementosZigZag2 n) elementosZigZag2 :: Int -> [Int] elementosZigZag2 n = map snd (sort (zip (ordenZigZag2 n) [0..])) ordenZigZag2 :: Int -> [(Int,Int)] ordenZigZag2 n = sortBy comp [(x,y) | x <- [1..n], y <- [1..n]] where comp (x1,y1) (x2,y2) | x1+y1 < x2+y2 = LT | x1+y1 > x2+y2 = GT | even (x1+y1) = compare y1 y2 | otherwise = compare x1 x2 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_zigZag :: Positive Int -> Bool prop_zigZag (Positive n) = zigZag1 n == zigZag2 n -- La comprobación es -- λ> quickCheck prop_zigZag -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (zigZag1 5000) -- 25000000 -- (2.57 secs, 1,800,683,952 bytes) -- λ> length (zigZag2 5000) -- 25000000 -- (2.20 secs, 1,800,683,952 bytes) -- -- λ> maximum (zigZag1 1100) -- 1209999 -- (2.12 secs, 1,840,095,864 bytes) -- λ> maximum (zigZag2 1100) -- 1209999 -- (21.27 secs, 11,661,088,256 bytes) |
El código se encuentra en GitHub.