Print matrix in spiral order in Scala

Question

Problem:

Given a square or rectangular matrix, print its element in spiral order.

For example, if input matrix is this:

 1 2 3 4
 5 6 7 8
 9 10 11 12
 13 14 15 16

Output should be:

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

This code assumes a matrix of 6X5. I do feel it can look more elegant or functional. I want to get rid of vars.

import scala.util.Random
object MatrixSpiral extends App {
 val matrix = Array.fill(6)(Array.fill(5)(Random.nextInt(10)))
 matrix foreach (row => println(row.mkString(",")))
 var rows = 6
 var cols = 5
 var r = 0
 var c = 0
 var startR = 0
 var startC = 0
 println
 while (r < rows && c < cols) {
 for (i <- c until cols) {
 c = i; print(matrix(r)(i) + " ")
 }
 r += 1
 for (j <- r until rows) {
 r = j; print(matrix(j)(c) + " ")
 }
 c -= 1
 for (k <- c to startC by -1) {
 c = k; print(matrix(r)(k) + " ")
 }
 r -= 1
 for (l <- r to startR + 1 by -1) {
 r = l; print(matrix(l)(c) + " ")
 }
 rows -= 1
 cols -= 1
 c += 1
 startR = r
 startC = c
 }
}

Answer 1

You are using many indexes in your code.

That is, you are using an imperative style of programming.

Functional style is more about decomposing the problem in smaller even tiny steps and using recursion where reasonable.

To print out as a spiral the outermost part of a matrix what do you do?

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Output should be -

1 2 3 4 8 12 16
^ ^
First row Last column reversed but avoiding repeating 4
15 14 13
^
Last row reversed (again careful on repetions)
9 5
^
First column reversed omitting both first and last

And then? How to print the inside as a spiral? You just remove the outside, the first and last columns and the first and last items of each row and apply this process again.

This allows you to think, as much as possible in terms in concepts (print given row or column maybe reversed) instead of indexes, you find a way to simplify the problem and then establish a trivial base case (matrix empty = do not print)

So you can a program like this, in pseudocode:

def nth_row
def nth_column
def except_first
def except_last
def reversed
def spiral_print(matrix):
 if len(matrix) == 0: end
 L = len(matrix)
 print(nth_row(0, matrix))
 print(except_first(nth_column(L, matrix)))
 # last row and first column handling missing
 print_spiral(inside_matrix(matrix))

I do not know Scala specifics semantics, but here is an implementation in Python:

def column(i, matrix):
 return [row[i] for row in matrix]
def spiral(matrix):
 if len(matrix) == 0:
 return
 print(matrix[0])
 print(column(-1, matrix)[1:])
 print(matrix[-1][::-1][1:])
 print(column(0, matrix)[::-1][1:-1])
 spiral([row[1:-1] for row in matrix[1:-1]])

[::-1] means "reversed", and [1:-1] means "except first and last"

• vikrant: thanks for these directions. They were really helpful and I am able to proceed on them and came up with a more functional solution of this problem. Posting that version as an answer of the question.

Answer 2

As suggested by @Caridorc I tried implementing a more functional version of the solution. I do feel that this code can be made more elegant and some checks may be redundant.

def getRow(row: Int, m: Array[Array[Int]]): Seq[Int] = m(row)
 def getCol(col: Int, m: Array[Array[Int]]): Seq[Int] = (0 until m.length).map(i => m(i)(col)).toSeq
 def printNonEmpty(s: Seq[Int]) : Unit = if (s.isEmpty) print("") else print(s.mkString(","))
 def dropOuter(m: Array[Array[Int]]): Array[Array[Int]] = {
 val rows = m.length -1
 val cols = m(0).length -1
 (1 until rows).map { r =>
 (1 until cols).map { c =>
 m(r)(c)
 }.toArray
 }.toArray
 }
 def printSpiral(m: Array[Array[Int]]) : Unit ={
 m.size match {
 case 0 => print("")
 case _=>
 printNonEmpty(getRow(0, m));print(",")
 if (m(0).length > 0 ) {
 printNonEmpty(getCol(m(0).length -1, m).tail);print(",")
 }
 val bottom = getRow(m.length - 1, m)
 if (m.length > 0 && bottom.nonEmpty) {
 printNonEmpty(bottom.init.reverse);print(",")
 }
 if (m(0).size > 1) {
 val left = getCol(0, m).init
 if (left.tail.nonEmpty) {
 printNonEmpty(left.tail.reverse);
 print(",")
 }
 }
 printSpiral(dropOuter(m))
 }
 }
 println("==================")
 printSpiral(matrix)

• Caridorc: Cool, thanks for implementing this. You can ask a new follow-up question with this code if you think It can still be improved :)
• vikrant: yes, I am going to do that. Meanwhile posted a question which require similar kind of traversal and will highly value your feedback. codereview.stackexchange.com/questions/210450/…