4
\$\begingroup\$

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?
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Barry Carter Mar 26 '16 at 15:45
  • \$\begingroup\$ @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 \$\endgroup\$ – Tony Mar 26 '16 at 16:06
  • \$\begingroup\$ 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. \$\endgroup\$ – the_lotus Apr 6 '16 at 15:24
1
\$\begingroup\$

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
\$\endgroup\$

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.