11
\$\begingroup\$

This is the Matrix Rotation problem from hackerrank.com.

You are given a 2D matrix, \$a\$, of dimension \$M×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 \$4×5\$ 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 Visualization

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

Input

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

Print the rotated matrix.

Constraints

  • \$2 \le M, N \le 300\$
  • \$1 \le R \le 10^9\$
  • \$\min(M, N) ≡ 0 \pmod 2\$
  • \$1 \le a_{ij} \le 10^8\$, where \$i \in [1\ldots M]\$ and \$j \in [1\ldots N]\$

Sample Input #00

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #00

2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15

Sample Input #01

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Sample Output #01

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

Following is how I tried to solve the problem, but it runs just too slow:

from copy import deepcopy

aM, aN, R = map(int, input().split())

pivots = min(aM, aN)//2
refMat = []
baseMat = []

for i in range(aM):
    readInput = list(map(int, input().split()))
    baseMat.append(readInput)

refMat = deepcopy(baseMat)

for i in range(pivots):
    cLimit = (aN - 1) - i
    rLimit = (aM - 1) - i
    loopLength = (aM + aN - 2 - 4*i)*2 
    nbrOfRotations = R%loopLength

    for rotnIndex in range(nbrOfRotations):

        # Corner movements
        # Pivot
        refMat[i][i] = baseMat[i][i + 1]
        # Column End
        refMat[i][cLimit] = baseMat[i + 1][cLimit]
        # Row End
        refMat[rLimit][i] = baseMat[rLimit - 1][i]
        # Pivot diagonal
        refMat[rLimit][cLimit] = baseMat[rLimit][cLimit - 1]

        # Top movement
        for j in range(i+1, cLimit):
            refMat[i][j] = baseMat[i][j + 1]

        # Bottom movement
        for j in range(i+1, cLimit):
            refMat[rLimit][j] = baseMat[rLimit][j - 1]

        # Left movement
        for j in range(i+1, rLimit):
            refMat[j][i] = baseMat[j - 1][i]

        # Right movement
        for j in range(i+1, rLimit):
            refMat[j][cLimit] = baseMat[j + 1][cLimit]

        baseMat = deepcopy(refMat)

for i in refMat:
    for e in i:
        print(e, end = " ")
    print()

Note: No advanced libraries such as NumPy, SciPy etc. are allowed. However, I would love to know if they offer a better workaround.

\$\endgroup\$
  • 1
    \$\begingroup\$ It doesn’t seem that slow to me. Are there particular cases that are causing you problems? \$\endgroup\$ – alexwlchan Jul 30 '15 at 6:05
  • \$\begingroup\$ @alexwlchan, it does become slow when the inputs, for example, are of the dimension rows = 136, columns = 240 and rotations = 212131 \$\endgroup\$ – benSooraj Jul 30 '15 at 9:15
  • 1
    \$\begingroup\$ I was wondering if there is any way to pre-compute the new position of any element, instead of shifting them around. Or some other better/efficient way to get this done. Thanks for your inputs. \$\endgroup\$ – benSooraj Jul 30 '15 at 9:18
  • \$\begingroup\$ There isn't really a need to actually move the elements, just update the starting one for each layer, and all the rest just follow behind it. As an example, if you are rotating 1 2 3 4 you can just start later on (at 2) and print each answer from there \$\endgroup\$ – spyr03 Aug 3 '15 at 19:54
  • 1
    \$\begingroup\$ @BenSoorajM it may take a while to do the full code for me, I'll get back to you in a couple of days \$\endgroup\$ – spyr03 Aug 3 '15 at 21:29
7
\$\begingroup\$

Much better algorithm in my view:

Consider first matrix example

1   2  3  4
5   6  7  8
9  10 11 12
13 14 15 16

R=rotations

convert in 2 circles (at least either M or N is even, thus there is no single center point):

c1 = [1,2,3,4,8,12,16,15,14,13,9,5]
c2 = [6,7,11,10]

for each position calculate actual value:

c1’[i] = c1[(i+R)%c1.length]
c2’[i] = c2[(i+R)%c2.length]
…

The number of circles is min(M, N)/2 hence this strange constraint in the task :)

This solves in linear \$O(M+N)\$ complexity rather than your cubic \$O(M\cdot N\cdot R)\$ complexity.

EDIT: of course revert the circles back to the matrix format.

\$\endgroup\$
  • \$\begingroup\$ Is c2’[i] a typo? It's not really correct syntax. \$\endgroup\$ – SuperBiasedMan Oct 15 '15 at 13:56
  • 1
    \$\begingroup\$ It is pseudo syntax and means derived. This algorithm is not language specific and c2_derived I considered too long :) keeps you awake :P I also hope, that c1.length will be extracted in a local variable, that cN will be an array and so on… \$\endgroup\$ – Jan Oct 15 '15 at 13:58
  • \$\begingroup\$ yes sorry I didn't follow it at first. I could tell it was partly psuedo code I just wasn't familiar with the derived notation in the middle of what's normal Python syntax otherwise (ie c1[i] is valid) \$\endgroup\$ – SuperBiasedMan Oct 15 '15 at 14:36
  • \$\begingroup\$ How would you generate the original c1 and c2 array? Do you have a general formula for when the number of circles increases? \$\endgroup\$ – holroy Feb 28 '16 at 19:04
  • \$\begingroup\$ I am not quite sure, what you are asking for. How to calculate the number of circles I wrote min(M,N)/2. The initial creation of c_n (can I use the math env in comments also?) looks trivial to me ;). Would you like to see the start of it? \$\endgroup\$ – Jan Feb 29 '16 at 7:08

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.