{"id":7044,"date":"2022-05-24T12:03:08","date_gmt":"2022-05-24T10:03:08","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7044"},"modified":"2022-05-24T12:05:46","modified_gmt":"2022-05-24T10:05:46","slug":"matriz-zigzagueante","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/matriz-zigzagueante\/","title":{"rendered":"Matriz zigzagueante"},"content":{"rendered":"<p>La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n\u00b2 primeros n\u00fameros naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es<\/p>\n<pre lang=\"text\">\n    0  1  5  6 14\n    2  4  7 13 15\n    3  8 12 16 21\n    9 11 17 20 22\n   10 18 19 23 24\n<\/pre>\n<p>La colocaci\u00f3n de los elementos se puede ver gr\u00e1ficamente en esta figura<\/p>\n<p><a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png?resize=600%2C600\" alt=\"\" width=\"600\" height=\"600\" class=\"aligncenter size-full wp-image-7046\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png?w=600&amp;ssl=1 600w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png?resize=150%2C150&amp;ssl=1 150w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2022\/05\/ZigZag.png?resize=300%2C300&amp;ssl=1 300w\" sizes=\"(max-width: 600px) 100vw, 600px\" data-recalc-dims=\"1\" \/><\/a><\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   zigZag :: Int -> Matrix Int\n<\/pre>\n<p>tal que <code>(zigZag n)<\/code> es la matriz zigzagueante de orden <code>n<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> zigZag 5\n   \u250c                \u2510\n   \u2502  0  1  5  6 14 \u2502\n   \u2502  2  4  7 13 15 \u2502\n   \u2502  3  8 12 16 21 \u2502\n   \u2502  9 11 17 20 22 \u2502\n   \u2502 10 18 19 23 24 \u2502\n   \u2514                \u2518\n   \u03bb> zigZag 4\n   \u250c             \u2510\n   \u2502  0  1  5  6 \u2502\n   \u2502  2  4  7 12 \u2502\n   \u2502  3  8 11 13 \u2502\n   \u2502  9 10 14 15 \u2502\n   \u2514             \u2518\n   \u03bb> maximum (zigZag 1500)\n   2249999\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort, sortBy)\nimport Data.Matrix (Matrix, fromList)\nimport Test.QuickCheck (Positive (Positive), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nzigZag1 :: Int -> Matrix Int\nzigZag1 n = fromList n n (elementosZigZag n)\n\n-- (elementosZigZag n) es la lista de los elementos de la matriz\n-- zizagueante de orden n. Por ejemplo.\n--    \u03bb> elementosZigZag 5\n--    [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]\nelementosZigZag :: Int -> [Int]\nelementosZigZag n =\n  map snd (sort (zip (ordenZigZag n) [0..]))\n\n-- (ordenZigZag n) es la lista de puntos del cuadrado nxn recorridos en\n-- zig-zag por las diagonales secundarias. Por ejemplo,\n--    \u03bb> ordenZigZag 4\n--    [(1,1), (1,2),(2,1), (3,1),(2,2),(1,3), (1,4),(2,3),(3,2),(4,1),\n--     (4,2),(3,3),(2,4), (3,4),(4,3), (4,4)]\nordenZigZag :: Int -> [(Int,Int)]\nordenZigZag n = concat [aux n m | m <- [2..2*n]]\n    where aux k m | odd m     = [(x,m-x) | x <- [max 1 (m-k)..min k (m-1)]]\n                  | otherwise = [(m-x,x) | x <- [max 1 (m-k)..min k (m-1)]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nzigZag2 :: Int -> Matrix Int\nzigZag2 n = fromList n n (elementosZigZag2 n)\n\nelementosZigZag2 :: Int -> [Int]\nelementosZigZag2 n =\n  map snd (sort (zip (ordenZigZag2 n) [0..]))\n\nordenZigZag2 :: Int -> [(Int,Int)]\nordenZigZag2 n = sortBy comp [(x,y) | x <- [1..n], y <- [1..n]]\n    where comp (x1,y1) (x2,y2) | x1+y1 < x2+y2 = LT\n                               | x1+y1 > x2+y2 = GT\n                               | even (x1+y1)  = compare y1 y2\n                               | otherwise     = compare x1 x2\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_zigZag :: Positive Int -> Bool\nprop_zigZag (Positive n) =\n  zigZag1 n == zigZag2 n\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_zigZag\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (zigZag1 5000)\n--    25000000\n--    (2.57 secs, 1,800,683,952 bytes)\n--    \u03bb> length (zigZag2 5000)\n--    25000000\n--    (2.20 secs, 1,800,683,952 bytes)\n--\n--    \u03bb> maximum (zigZag1 1100)\n--    1209999\n--    (2.12 secs, 1,840,095,864 bytes)\n--    \u03bb> maximum (zigZag2 1100)\n--    1209999\n--    (21.27 secs, 11,661,088,256 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Matriz_zigzagueante.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n\u00b2 primeros n\u00fameros 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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[2],"tags":[569],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7044"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7044"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7044\/revisions"}],"predecessor-version":[{"id":7047,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7044\/revisions\/7047"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7044"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7044"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7044"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}