2
\$\begingroup\$

I have a task formulated like this

Please print a matrix in spiral order, clockwise from outer rings to inner rings.

I decided to implement it in Clojure.

(def matrix '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)))

(def big-matrix '(
    ( 1   2  3  4  5  6  7  8  9 )
    ( 32 33 34 35 36 37 38 39 10 )
    ( 31 56 57 58 59 60 61 40 11 )
    ( 30 55 72 73 74 75 62 41 12 )
    ( 29 54 71 80 81 76 63 42 13 )
    ( 28 53 70 79 78 77 64 43 14 )
    ( 27 52 69 68 67 66 65 44 15 )
    ( 26 51 50 49 48 47 46 45 16 )
    ( 25 24 23 22 21 20 19 18 17 ))
)

(defn get-str
  ([] "")
  ([a] a)
  ([a b] (str a " " b)))

(defn print-first-row [matrix] (reduce get-str (first matrix)))
(defn print-last-elements [matrix] (reduce get-str (map last matrix)))
(defn print-last-row-reversed [matrix] (reduce get-str (reverse (last matrix))))
(defn print-first-elements-reversed [matrix] (reduce get-str (reverse (map first matrix))))

(defn spiral (
    [matrix]
      (spiral matrix :first-row)
  )(
    [matrix op]
      (if (not (empty? matrix))
      (cond
        (= op :first-row) (str (print-first-row matrix) " " (spiral (rest matrix) :last-els))
        (= op :last-els)  (str (print-last-elements matrix) " " (spiral (map butlast matrix) :last-row))
        (= op :last-row)  (str (print-last-row-reversed matrix) " " (spiral (butlast matrix) :first-els))
        (= op :first-els) (str (print-first-elements-reversed matrix) " " (spiral (map rest matrix) :first-row)))
      )
  )
)

(spiral matrix)
(spiral big-matrix)
(spiral '())

Output:

For the first matrix the function call (spiral matrix) returns string "1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 "

The task itself is pretty simple but I am pretty new to Clojure so I would like to hear any possible improvements for this code. Thanks!

\$\endgroup\$
5
\$\begingroup\$

First, some style notes:

  1. When defining a sequential piece of data, it's conventional to use a vector instead of a list:

    (def matrix [[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15 16]])
    

    This avoids having to write those pesky 's.

  2. It's conventional to leave no whitespace between an opening bracket and its first contained element, and similarly between a closing bracket and its last contained element:

    (def big-matrix
      [[1 2 3 4 5 6 7 8 9]
       [32 33 34 35 36 37 38 39 10]
       [31 56 57 58 59 60 61 40 11]
       [30 55 72 73 74 75 62 41 12]
       [29 54 71 80 81 76 63 42 13]
       [28 53 70 79 78 77 64 43 14]
       [27 52 69 68 67 66 65 44 15]
       [26 51 50 49 48 47 46 45 16]
       [25 24 23 22 21 20 19 18 17]])
    

    If you think it's more readable, though, you could align the single-digit numbers in the first row with the double-digit numbers in the other rows (as you did in your question):

    [ 1  2  3  4  5  6  7  8  9]
    
  3. It's conventional to indent the function body the same amount as the argument vector in multi-arity functions, and to indent the "then" part of an if expression by two spaces. If you don't have an "else" expression, it's conventional to use when instead of if.

    Also, it's conventional to use the idiom (seq ,,,) instead of the more verbose (not (empty? ,,,)) and to use case instead of cond when you're comparing a value to several constants:

    (defn spiral
      ([matrix]
       (spiral matrix :first-row))
      ([matrix op]
       (when (seq matrix)
         (case op
           :first-row (str (print-first-row matrix) " " (spiral (rest matrix) :last-els))
           :last-els  (str (print-last-elements matrix) " " (spiral (map butlast matrix) :last-row))
           :last-row  (str (print-last-row-reversed matrix) " " (spiral (butlast matrix) :first-els))
           :first-els (str (print-first-elements-reversed matrix) " " (spiral (map rest matrix) :first-row))))))
    

Your approach of converting everything to strings as early as possible and then implementing your logic as string concatenation causes a lot of verbosity in your code. I would instead try to work with richer data (sequences of numbers, in this case) as much as possible:

(defn first-row [matrix] (first matrix))
(defn last-elements [matrix] (map last matrix))
(defn last-row-reversed [matrix] (reverse (last matrix)))
(defn first-elements-reversed [matrix] (reverse (map first matrix)))

(defn drop-first-row [matrix] (rest matrix))
(defn drop-last-elements [matrix] (map butlast matrix))
(defn drop-last-row [matrix] (butlast matrix))
(defn drop-first-elements [matrix] (map rest matrix))

(defn spiral
  ([matrix]
   (spiral matrix :first-row))
  ([matrix op]
   (when (seq matrix)
     (case op
       :first-row (concat (first-row matrix)
                          (spiral (drop-first-row matrix) :last-els))
       :last-els  (concat (last-elements matrix)
                          (spiral (drop-last-elements matrix) :last-row))
       :last-row  (concat (last-row-reversed matrix)
                          (spiral (drop-last-row matrix) :first-els))
       :first-els (concat (first-elements-reversed matrix)
                          (spiral (drop-first-elements matrix) :first-row))))))

Then you can use clojure.string/join to convert to a string as the last step:

(require '[clojure.string :as str])

(str/join " " (spiral matrix))
;=> "1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10"

This solution still has a lot of repetition, though; you basically have four of everything, one for each direction of the spiral. You could eliminate this repetition by just taking the top row each iteration, then rotating the rest of the matrix by an angle of \$\tau/4\$ counterclockwise.

So first you need a function to perform that sort of rotation. To visualize the algorithm I'm going to use, get a square physical object and hold it in front of you. Rotate it by an angle of \$\tau/2\$ around the axis passing through its top-left corner and its bottom-right corner. Then rotate it by an angle of \$\tau/2\$ around the axis passing through the midpoints of its left and right sides. You should see that this is equivalent to rotating the object by an angle of \$\tau/4\$ counterclockwise around the axis perpendicular to its surface.

Coming back to matrices, that first rotation is just transposing the matrix, and the second rotation is just reversing the order of its rows. Clojure has a built-in reverse function, and you could write a transpose function yourself, but there's already one available in core.matrix, so I'm just going to use that. Add the library to your dependencies:

[net.mikera/core.matrix "0.52.1"]

The transpose function is in the clojure.core.matrix namespace:

(require '[clojure.core.matrix :as m])

And now we can write our rotate function easily:

(defn rotate [matrix]
  (reverse (m/transpose matrix)))

Now that all the pieces in place, we can write our spiral function. If the matrix is empty ((seq matrix) returns nil), we just return nil. Otherwise, the spiral sequence of the matrix is equal to the concatenation of the first row of the matrix with the spiral of the rotation of the rest of the matrix:

(defn spiral [matrix]
  (when (seq matrix) (concat (first matrix) (-> matrix rest rotate spiral))))

I'm using the thread-first macro -> here because I think it makes it easier to read. Sanity check:

(str/join " " (spiral matrix))
;=> "1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10"
\$\endgroup\$
  • \$\begingroup\$ Wow, thank you so much for your efforts to put such an informative answer here. I really appreciate it. \$\endgroup\$ – cliffroot Jun 10 '16 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.