Scala algorithm: Read a matrix as a spiral
Published
Algorithm goal
For a matrix, read it in a clockwise spiral order. For example, if this is the matrix:
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Would be read as:
1 | 2 | 3 | 6 | 9 | 8 | 7 | 4 | 5 |
Test cases in Scala
Algorithm in Scala
26 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!
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):
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
After the second transformation, it would look like this:
6 | 9 |
5 | 8 |
4 | 7 |
Scala concepts & Hints
Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.
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').
Range
The
(1 to n)
syntax produces a "Range" which is a representation of a sequence of numbers.