Matrix rotation

Question

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).

matrix-rotation

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))
 matrix = ReadInMatrix(M,N)
 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
 AddRotatedLayer(i, rotatedLayer, matrix)
 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
 line = Console.ReadLine().Split(" ")
 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
 layers.Add(New List(Of String))
 ' Walk along the top row extracting layer values
 For k = i To N - 1 - i Step 1
 layers(i).Add(matrix(i, k))
 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
 layers(i).Add(matrix(k, i))
 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?

• user1149: 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?
• Anthony: @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
• the_lotus: 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.

Answer 1

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)
 Console.ReadLine()
 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
 tmp.Add(m(indexes(i)))
 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
 indexes.Add(index)
 Next
 ' Right
 For y = 0 To lh - 1
 index += w
 indexes.Add(index)
 Next
 ' Bottom
 For x = 0 To lw - 2
 index -= 1
 indexes.Add(index)
 Next
 ' Left
 For y = 0 To lh - 2
 index -= w
 indexes.Add(index)
 Next
 Return indexes
 End Function
End Module