Scala algorithm: Read a matrix as a spiral

Published , last updated

Algorithm goal

For a matrix, read it in a clockwise spiral order. For example, if this is the matrix:

123
456
789

Would be read as:

123698745

Explanation

There are different approaches to this problem, but this approach is the most interesting as it first of all does not mutate the matrix nor perform any heavy transformations of the inputs: by representing the matrix indices in the form of a pair of Ranges, we can simply get the indices and then after getting those indices, extract the respective elements.

The key concept here is that if we take the top part of the matrix, and then rotate it anti-clockwise, that is our next set of indices, and we just keep on going. To do that, in each iteration, the horizontal range becomes the vertical range (without the first line), and vertical range becomes the horizontal range, reversed. (this is © from www.scala-algorithms.com)

In essence, the example matrix would be treated like this (where the outline indicates what we are selecting in this iteration):

123
456
789

After the second transformation, it would look like this:

69
58
47

The rest of the Explanation is available for subscribers.

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Scala concepts & Hints

  1. Drop, Take, dropRight, takeRight

    Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

    assert(List(1, 2, 3).drop(2) == List(3))
    
    assert(List(1, 2, 3).take(2) == List(1, 2))
    
    assert(List(1, 2, 3).dropRight(2) == List(1))
    
    assert(List(1, 2, 3).takeRight(2) == List(2, 3))
    
    assert((1 to 5).take(2) == (1 to 2))
    
  2. Lazy List

    The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').

  3. Range

    The (1 to n) syntax produces a "Range" which is a representation of a sequence of numbers.

    assert((1 to 5).toString == "Range 1 to 5")
    
    assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")
    
    assert((1 to 5).toList == List(1, 2, 3, 4, 5))
    

Algorithm in Scala

27 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for access!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Test cases in Scala

assert(
  getIndicesBased(
    Vector(
      Vector(1, 2, 3),
      Vector(4, 5, 6),
      Vector(7, 8, 9),
      Vector(10, 11, 12)
    )
  ).toVector == Vector(1, 2, 3, 6, 9, 12, 11, 10, 7, 4, 5, 8)
)
assert(
  getIndicesBased(
    Vector(
      Vector(1, 2, 3, 4),
      Vector(5, 6, 7, 8),
      Vector(9, 10, 11, 12),
      Vector(13, 14, 15, 16),
      Vector(17, 18, 19, 20)
    )
  ).toVector == Vector(
    1, 2, 3, 4, 8, 12, 16, 20, 19, 18, 17, 13, 9, 5, 6, 7, 11, 15, 14, 10
  )
)
assert(getIndicesBased(Vector(Vector(1, 2, 3))).toVector == Vector(1, 2, 3))
assert(
  getIndicesBased(Vector(Vector(1), Vector(2), Vector(3))).toVector ==
    Vector(1, 2, 3)
)

View the rest of Scala algorithms