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"

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)