# Matrix rotation

Continuing on my VB.NET quest, I came across this slightly more challenging problem.

You are given a 2D matrix, a, of dimension $M$x$N$ and a positive integer $R$. You have to rotate the matrix $R$ times and print the resultant matrix. Rotation should be in anti-clockwise direction.

Rotation of a 4x5 matrix is represented by the following figure. Note that in one rotation, you have to shift elements by one step only (refer sample tests for more clarity).

It is guaranteed that the minimum of $M$ and $N$ will be even.

Input Format

First line contains three space separated integers, $M$, $N$ and $R$, where $M$ is the number of rows, $N$ is number of columns in matrix, and $R$ is the number of times the matrix has to be rotated. Then $M$ lines follow, where each line contains $N$ space separated positive integers. These M lines represent the matrix.

Output Format

Print the rotated matrix.

Constraints

• 2 <= $M$, $N$ <= 300
• 1 <= $R$ <= $10^9$
• $min$($M$, $N$) % 2 == 0

Imports System
Imports System.Collections.Generic
Imports System.Text

Module Solution
Public Sub Main()
Dim input() As String = Console.ReadLine().Split(" ")
Dim M As Integer = CInt(input(0))
Dim N As Integer = CInt(input(1))
Dim R As Integer = CInt(input(2))

Dim matrix(,) As String
Dim layers As List(Of List(Of String))

layers = GetLayers(matrix)

Dim rotatedLayer(), layer() As String
Dim start As Integer

For i As Integer = 0 To layers.Count - 1
' Determine the new starting point of the layer after R rotations
start = R Mod layers(i).Count
layer = layers(i).ToArray()

If start = 0 Then
' Any multiple of the length of the layer = no rotation
rotatedLayer = layer
Else
' Build the rotated layer by copying from start->end
' And then 0->start
ReDim rotatedLayer(layer.Length - 1)
Array.Copy(layer, start, rotatedLayer, 0, layer.Length - start)
Array.Copy(layer, 0, rotatedLayer, layer.Length - start, start)
End If

Next

PrintMatrix(matrix)
End Sub

Private Function ReadInMatrix(M As Integer, N As Integer) As String(,)
Dim line() As String
Dim matrix(M-1,N-1) As String

For i As Integer = 0 to M-1

For j As Integer = 0 to N-1
matrix (i,j) = line(j)
Next j
Next i

Return matrix
End Function

Private Function GetLayers(ByRef matrix(,) As String) As List(Of List(Of String))
Dim M As Integer = 1 + UBound(matrix, 1)
Dim N As Integer = 1 + UBound(matrix, 2)
Dim layerCount As Integer = Math.Min(M, N) / 2
Dim layers As New List(Of List(Of String))

Dim k As Integer

For i As Integer = 0 To layerCount - 1

' Walk along the top row extracting layer values
For k = i To N - 1 - i Step 1
Next

' Walk along right column extracting layer values
For k = i + 1 To M - 2 - i Step 1
layers(i).Add(matrix(k, N - 1 - i))
Next

' Walk back along bottom row extracting layer values
For k = N - 1 - i To i Step -1
layers(i).Add(matrix(M - 1 - i, k))
Next

' Walk back up left column extracting layer values
For k = M - 2 - i To i + 1 Step -1
Next
Next

Return layers
End Function

Private Sub AddRotatedLayer(layerIndex As Integer, layer() As String, ByRef matrix(,) As String)
Dim index As Integer = 0
Dim M As Integer = 1 + UBound(matrix, 1)
Dim N As Integer = 1 + UBound(matrix, 2)

Dim k As Integer

For k = layerIndex To N - 1 - layerIndex Step 1
matrix(layerIndex, k) = layer(index)
index += 1
Next

For k = layerIndex + 1 To M - 2 - layerIndex Step 1
matrix(k, N - 1 - layerIndex) = layer(index)
index += 1
Next

For k = N - 1 - layerIndex To layerIndex Step -1
matrix(M - 1 - layerIndex, k) = layer(index)
index += 1
Next

For k = M - 2 - layerIndex To layerIndex + 1 Step -1
matrix(k, layerIndex) = layer(index)
index += 1
Next
End Sub

Private Sub PrintMatrix(ByRef matrix As String(,))
Dim M As Integer = 1 + UBound(matrix, 1)
Dim N As Integer = 1 + UBound(matrix, 2)

Dim sb As New StringBuilder

For i As Integer = 0 To M - 1
sb.Clear()

For j As Integer = 0 To N - 1
sb.Append(String.Format("{0} ", matrix(i, j)))
Next j

Console.WriteLine(sb.ToString().Trim())
Next i
End Sub

End Module


I was unable to use Linq and some of the goodness it offers (Concat, Skip). I would love any and all feedback, but am very interested in:

1. General "VB-ness"
2. Is there a better algorithm for solving this?
3. Is there a better way to "walk" around each layer of the matrix when constructing the 1x$N$ arrays?
• Any chance you could add comments so we can know what you're doing at each stage? I'm assuming that you're not doing one rotation at a time, correct? – Barry Carter Mar 26 '16 at 15:45
• @BarryCarter, that is correct - with modulo you can determine the starting point of the layer after $R$ rotations; I have added some comments - let me know if anything else doesn't make sense – Tony Mar 26 '16 at 16:06
• I have to say, at a quick glance, this is pretty good. Instead of layers being a list of a list, you could just do one layer at a time. since you already add one layer at a time, you could change GetLayers to get one layer at a time. – the_lotus Apr 6 '16 at 15:24

Personally, I think it looks good. I would add error handling. You have a nice list of constraints and adding a few if statement to validate those contain would be a good idea.

For fun, I decided to try a different algorithm. The idea is to have your matrix in a one dimensional matrix. Then we loop each layer and get the list of indexes that represent that layer. It's easy to rotate the layer since we know the indexes. If you want to keep a 2D matrix, you could store the x,y position instead of the index.

This code is just to show the algorithm. You should add string builder, ect..

Module Module1

Sub Main()

Dim m() As Integer
Dim w, h, r As Integer

w = 5 ' matrix width
h = 4 ' matrix height
r = 2 ' rotation

m = GetMatrix(w, h)
DisplayMatrix(m, w)

RotateMatrix(m, w, h, r)

DisplayMatrix(m, w)

End Sub

Public Sub RotateMatrix(ByVal m() As Integer, ByVal w As Integer, ByVal h As Integer, ByVal r As Integer)

Dim indexes As List(Of Integer)
Dim tmp As New List(Of Integer)

' Loop all layers
For l As Integer = 0 To (Math.Min(w, h) / 2) - 1
indexes = GetLayerIndexes(w, h, l)

' Display the indexes representing that layer
'Console.WriteLine()
'For i As Integer = 0 To indexes.Count - 1
'    Console.Write(indexes(i) & " ")
'Next
'Console.WriteLine()

tmp.Clear()

For i As Integer = 0 To r - 1
Next

For i As Integer = 0 To indexes.Count - r
m(indexes(i)) = m(indexes((i + r) Mod indexes.Count))
Next

For i As Integer = 0 To r - 1
m(indexes(indexes.Count - r + i)) = tmp(i)
Next
Next

End Sub

Public Function GetMatrix(ByVal w As Integer, ByVal h As Integer) As Integer()

Dim size As Integer = w * h
Dim m(size) As Integer

For i As Integer = 0 To size - 1
m(i) = i
Next

Return m
End Function

Public Sub DisplayMatrix(ByVal m() As Integer, ByVal w As Integer)

Console.WriteLine()

For i As Integer = 0 To m.Count - 1 - 1
Console.Write(m(i).ToString("00") & " ")

If ((i + 1) Mod w) = 0 Then
Console.WriteLine()
End If
Next

End Sub

Public Function GetLayerIndexes(ByVal w As Integer, ByVal h As Integer, ByVal l As Integer) As List(Of Integer)

Dim index, lw, lh As Integer
Dim indexes As New List(Of Integer)

lw = w - l - l ' width of layer
lh = h - 1 - l - l ' height of layer
index = l + (l * w) - 1 ' Top Left

' Top
For x = 0 To lw - 1
index += 1
Next

' Right
For y = 0 To lh - 1
index += w
Next

' Bottom
For x = 0 To lw - 2
index -= 1