11
\$\begingroup\$

This is theMatrix Rotation problem fromhackerrank.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 11 2 3 45 6 7 89 10 11 1213 14 15 16

Sample Output #00

2 3 4 81 7 11 125 6 10 169 13 14 15

Sample Input #01

4 4 21 2 3 45 6 7 89 10 11 1213 14 15 16

Sample Output #01

3 4 8 122 11 10 161 7 6 155 9 13 14

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

from copy import deepcopyaM, aN, R = map(int, input().split())pivots = min(aM, aN)//2refMat = []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.

Gareth Rees's user avatar
Gareth Rees
50.1k3 gold badges130 silver badges211 bronze badges
askedJul 30, 2015 at 1:20
benSooraj's user avatar
\$\endgroup\$
13
  • 1
    \$\begingroup\$It doesn’t seem that slow to me. Are there particular cases that are causing you problems?\$\endgroup\$CommentedJul 30, 2015 at 6:05
  • \$\begingroup\$@alexwlchan, it does become slow when the inputs, for example, are of the dimensionrows = 136, columns = 240 and rotations = 212131\$\endgroup\$CommentedJul 30, 2015 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\$CommentedJul 30, 2015 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\$CommentedAug 3, 2015 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\$CommentedAug 3, 2015 at 21:29

1 Answer1

8
\$\begingroup\$

Much better algorithm in my view:

Consider first matrix example

1   2  3  45   6  7  89  10 11 1213 14 15 16R=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 ismin(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.

holroy's user avatar
holroy
11.8k1 gold badge27 silver badges59 bronze badges
answeredOct 15, 2015 at 13:46
Jan's user avatar
\$\endgroup\$
5
  • \$\begingroup\$Isc2’[i] a typo? It's not really correct syntax.\$\endgroup\$CommentedOct 15, 2015 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\$CommentedOct 15, 2015 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 (iec1[i] is valid)\$\endgroup\$CommentedOct 15, 2015 at 14:36
  • \$\begingroup\$How would you generate the originalc1 andc2 array? Do you have a general formula for when the number of circles increases?\$\endgroup\$CommentedFeb 28, 2016 at 19:04
  • \$\begingroup\$I am not quite sure, what you are asking for. How to calculate the number of circles I wrotemin(M,N)/2. The initial creation ofc_n (can I use the math env in comments also?) looks trivial to me ;). Would you like to see the start of it?\$\endgroup\$CommentedFeb 29, 2016 at 7:08

You mustlog in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.