Spiral Matrix

A Spiral Matrix is a square -matrix filled with natural numbers, starting from in the top-left corner, increasing in inward, clockwise spiral order, like these examples:

Even though one can define a spiral matrix for each size , your task is to implement a function generating a spiral -matrix only for odd . Note that such matrices can be generated recursively because the spiral matrix of size can be constructed from the spiral matrix of size as follows:

where is basically the matrix whose all elements are increased by .

Racket

In Racket, implement a function (spiral-matrix n) that accepts a positive odd integer and returns the spiral matrix of size n. A matrix is represented as a list of its rows, e.g. is represented as

'((1 2 3)
  (8 9 4)
  (7 6 5))

Your file is to be called spiral-matrix.rkt and must provide the function spiral-matrix. Hence, the head of your file should start with

#lang racket
(provide spiral-matrix)

; your code here

Hint

To generate a sequences of numbers, you may use the function (range start end step) generating a sequence of numbers starting at start and whose successive elements are computed by adding step until end. Note that the element end is excluded. E.g.

> (range 5 0 -1)
'(5 4 3 2 1)

Examples

The following shows the behaviour of the spiral-matrix function.

> (spiral-matrix 3)
'((1 2 3)
  (8 9 4)
  (7 6 5))

> (spiral-matrix 1)
'((1))

Racket Solution

#lang racket

(provide spiral-matrix)


(define (mat-add xss n)
	(map (curry map (curry + n)) xss))


(define (wrap x ys z)
  (cons x (append ys (list z))))


(define (spiral-matrix n)
  (define (extendH x)
    (map wrap
         (range (- (* 4 n) 4) (- (* 3 n) 2) -1)
         x
         (range (+ n 1) (- (* 2 n) 1))))

  (define (extendV x)
    (wrap (range 1 (+ 1 n))
          x
          (range (- (* 3 n) 2) (- (* 2 n) 2) -1)))

  (if (equal? 1 n)
    '((1))
    (let ((smaller (spiral-matrix (- n 2))))
	(extendV (extendH (mat-add smaller (- (* 4 n) 4)))))))

Haskell

In Haskell, implement a function spiralMatrix :: Int -> Matrix that accepts a positive odd integer and returns the spiral matrix of size . A matrix is represented as a list of its rows by data type type Matrix = [[Int]], e.g. is represented as

[[1, 2, 3]
,[8, 9, 4]
,[7, 6, 5]]

Your task is to be called SpiralMatrix.rkt and must export the spiralMatrix function. Hence, the head of your file should read

module SpiralMatrix ( spiralMatrix ) where
type Matrix = [[Int]]

-- your code goes here

Hint

You may find the function zipWith3 f xs ys zs useful which processes three lists xs, ys, zs simultaneously applying the ternary function f to the triples of corresponding elements, e.g.,

> zipWith3 (\c1 c2 c3 -> [c1,c2,c3]) "abcd" "blaa" "haha"
["abh","bla","cah","daa"]

Generating a sequence of numbers in Haskell can be done by [start,start+step..end], e.g.,

> [5,4..1]
[5,4,3,2,1]

In comparison with the Scheme function range, the final number end is included in the generated sequence.

Examples

The following shows the behaviour of the spiralMatrix function.

> spiralMatrix 3
[[1,2,3]
,[8,9,4]
,[7,6,5]]

> spiralMatrix 1
[[1]]

Haskell Solution

module Task4 ( spiralMatrix ) where
type Matrix = [[Int]]

matAdd xss n = (map . map) (+ n) xss

wrap x ys z = x:ys++[z]

spiralMatrix 1 = [[1]]
spiralMatrix n = extendV $ extendH $ matAdd smaller (4*n-4) where
        smaller = spiralMatrix (n - 2)
        extendH x = zipWith3 wrap [4*n-4,4*n-5..3*n-1] x [n+1..2*n-2]
        extendV x = wrap [1..n] x [3*n-2,3*n-3..2*n-1]