How to resolve the algorithm Zig-zag matrix step by step in the Haskell programming language

Published on 7 June 2024 03:52 AM
#Haskell

How to resolve the algorithm Zig-zag matrix step by step in the Haskell programming language

Table of Contents

Problem Statement

Produce a zig-zag array.

A   zig-zag   array is a square arrangement of the first   N2   natural numbers,   where the
numbers increase sequentially as you zig-zag along the array's   anti-diagonals. For a graphical representation, see   JPG zigzag   (JPG uses such arrays to encode images).

For example, given   5,   produce this array:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zig-zag matrix step by step in the Haskell programming language

Both snippets are Haskell implementations to solve the Zig-zag matrix problem. The Zig-zag matrix is a matrix with the numbers from 1 to n x n ordered in a zig-zag pattern. The first snippet implements the zigZag function using the Array data type from the Data.Array library and the sortBy function from the Data.List library. The compZig function is a custom comparison function that is used to sort the elements of the matrix in the correct order. The zigZag function takes an upper bound as input and returns an array with the zig-zag matrix.

The second snippet implements the zigZag function using a different approach. It uses the Data.Text library to format the output and the Data.List library to split the list of numbers into groups. The diagonals function generates the diagonals of the zig-zag matrix and the go function accumulates the elements of the diagonals into the final matrix. The main function calls the zigZag function with an input of 5 and prints the zig-zag matrix.

The time complexity of both algorithms is O(n^2), where n is the size of the matrix. The space complexity of the first algorithm is O(n^2), while the space complexity of the second algorithm is O(n).

Source code in the haskell programming language

import Data.Array (Array, array, bounds, range, (!))
import Text.Printf (printf)
import Data.List (sortBy)

compZig :: (Int, Int) -> (Int, Int) -> Ordering
compZig (x, y) (x_, y_) = compare (x + y) (x_ + y_) <> go x y
  where
    go x y
      | even (x + y) = compare x x_
      | otherwise = compare y y_

zigZag :: (Int, Int) -> Array (Int, Int) Int
zigZag upper = array b $ zip (sortBy compZig (range b)) [0 ..]
  where
    b = ((0, 0), upper)


-- format a 2d array of integers neatly
show2d a =
  unlines
    [ unwords
       [ printf "%3d" (a ! (x, y) :: Integer)
       | x <- axis fst ]
    | y <- axis snd ]
  where
    (l, h) = bounds a
    axis f = [f l .. f h]

main = mapM_ (putStr . ('\n' :) . show2d . zigZag) [(3, 3), (4, 4), (10, 2)]


import Data.Text (justifyRight, pack, unpack)
import Data.List (mapAccumL)
import Data.Bool (bool)

zigZag :: Int -> [[Int]]
zigZag = go <*> diagonals
  where
    go _ [] = []
    go n xss = (head <$> edge) : go n (dropWhile null (tail <$> edge) <> rst)
      where
        (edge, rst) = splitAt n xss

diagonals :: Int -> [[Int]]
diagonals n =
  snd $ mapAccumL go [0 .. (n * n) - 1] (slope <> [n] <> reverse slope)
  where
    slope = [1 .. n - 1]
    go xs h = (rst, bool id reverse (0 /= mod h 2) grp)
      where
        (grp, rst) = splitAt h xs

main :: IO ()
main =
  putStrLn $
  unlines $
  concatMap unpack . fmap (justifyRight 3 ' ' . pack . show) <$> zigZag 5

You may also check:How to resolve the algorithm CSV to HTML translation step by step in the zkl programming language
You may also check:How to resolve the algorithm Closures/Value capture step by step in the Arturo programming language
You may also check:How to resolve the algorithm Roots of unity step by step in the Ring programming language
You may also check:How to resolve the algorithm Shell one-liner step by step in the Run BASIC programming language
You may also check:How to resolve the algorithm Record sound step by step in the GUISS programming language