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
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
Definir la función
zigZag :: Int -> Array (Int,Int) Int
tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,
λ> elems (zigZag 3) [0,1,5, 2,4,6, 3,7,8] λ> elems (zigZag 4) [0,1,5,6, 2,4,7,12, 3,8,11,13, 9,10,14,15] λ> elems (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] λ> take 15 (elems (zigZag 1000)) [0,1,5,6,14,15,27,28,44,45,65,66,90,91,119]
Soluciones
import Data.Array import Data.List (sortBy) -- 1ª solución -- =========== zigZag :: Int -> Array (Int,Int) Int zigZag n = array ((1,1),(n,n)) (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 n m | odd m = [(x,m-x) | x <- [max 1 (m-n)..min n (m-1)]] | otherwise = [(m-x,x) | x <- [max 1 (m-n)..min n (m-1)]] -- 2ª solución -- =========== zigZag2 :: Int -> Array (Int,Int) Int zigZag2 n = array ((1,1),(n,n)) (zip (ordenZigZag2 n) [0..]) -- (ordenZigZag2 n) es la lista de puntos del cuadrado nxn recorridos en -- zig-zag por las diagonales secundarias. Por ejemplo, -- λ> ordenZigZag2 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)] 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 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> take 15 (elems (zigZag 1000)) -- [0,1,5,6,14,15,27,28,44,45,65,66,90,91,119] -- (2.19 secs, 330463712 bytes) -- -- λ> take 15 (elems (zigZag2 1000)) -- [0,1,5,6,14,15,27,28,44,45,65,66,90,91,119] -- (48.75 secs, 4540478152 bytes)