1
\$\begingroup\$

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
  }

}
\$\endgroup\$
1
\$\begingroup\$

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"

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – vikrant Dec 27 '18 at 6:29
1
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Cool, thanks for implementing this. You can ask a new follow-up question with this code if you think It can still be improved :) \$\endgroup\$ – Caridorc Dec 28 '18 at 11:42
  • \$\begingroup\$ 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/… \$\endgroup\$ – vikrant Dec 28 '18 at 19:36

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.