patternpythonMinor
Matrix rotation algorithm - follow-up
Viewed 0 times
algorithmmatrixfollowrotation
Problem
In a response to this post I wrote a solution in Python. It passed all the test cases given, so I would like help making it more pythonic and reducing the almost repeated lines.
Link to the source of the question on HackerRank.
Link to the source of the question on HackerRank.
# input
M, N, rotations = map(int, input().split())
matrix = []
for row in range(M):
matrix.append(list(map(int, input().split())))
# flatten the rings into a list
layers = int(min(N, M)/2)
ring = [[] for layer in range(layers)]
for level in range(layers):
top = (N-1) - 2 * level
side = (M-1) - 2 * level
for row in range(top): # right
ring[level].append(matrix[level][level + row])
for col in range(side): # down
ring[level].append(matrix[level + col][level + top])
for row in range(top): # left
ring[level].append(matrix[level + side][level + top - row])
for col in range(side): # up
ring[level].append(matrix[level + side - col][level])
# rotate each layer
for level in range(layers):
r = rotations % len(ring[level])
ring[level] = ring[level][r:] + ring[level][:r]
# fill the array with the rotated elements
for level in range(layers):
top = (N-1) - 2 * level
side = (M-1) - 2 * level
for row in range(top):
matrix[level][level + row] = ring[level].pop(0) # right
for col in range(side):
matrix[level + col][level + top] = ring[level].pop(0) # down
for row in range(top):
matrix[level + side][level + top - row] = ring[level].pop(0) # left
for col in range(side):
matrix[level + side - col][level] = ring[level].pop(0) # up
# print the rotated matrix
for row in range(M):
for col in range(N):
print(matrix[row][col], "", end="")
print()Solution
List comprehensions
Whenever you see a list initialization to
later filled in by
consider rewriting with a list comprehension.
For example:
Can be rewritten on a single line:
Note that I renamed
this is a common convention when then loop variable is unused.
Another example of that is this list comprehension later in your code:
Like earlier, rename
Integer division with
Instead of this:
Another, a more natural way to achieve the same effect using integer division with
Coding style
The body of this for-loop is overindented:
Possibly it's a result of the copy-pasting?
Either way,
a PEP8 checker would catch this.
It's recommended to use four spaces for an indent level,
and to use only spaces and never tabs for indenting code.
Reducing duplicated code
The current implementation works like this:
Step 1 and 3 have very similar code, as you yourself noticed.
One way to reduce that is to implement shifting in-place,
without using the additional storage
by doing something like this (\$k\$ is the number of rotations):
Easier said than done? Yes. Calculating the \$(i + k)\$-th position will be tricky.
I'd say your original implementation with the similar lines is fine:
it's easy to understand, and it passed the tests anyway.
Whenever you see a list initialization to
[],later filled in by
.append(...) calls in a loop,consider rewriting with a list comprehension.
For example:
matrix = []
for row in range(M):
matrix.append(list(map(int, input().split())))Can be rewritten on a single line:
matrix = [list(map(int, input().split())) for _ in range(M)]Note that I renamed
row to _,this is a common convention when then loop variable is unused.
Another example of that is this list comprehension later in your code:
ring = [[] for layer in range(layers)]Like earlier, rename
layer to _:ring = [[] for _ in range(layers)]Integer division with
//Instead of this:
layers = int(min(N, M)/2)Another, a more natural way to achieve the same effect using integer division with
//:layers = min(N, M) // 2Coding style
The body of this for-loop is overindented:
# rotate each layer
for level in range(layers):
r = rotations % len(ring[level])
ring[level] = ring[level][r:] + ring[level][:r]Possibly it's a result of the copy-pasting?
Either way,
a PEP8 checker would catch this.
It's recommended to use four spaces for an indent level,
and to use only spaces and never tabs for indenting code.
Reducing duplicated code
The current implementation works like this:
- put each layer into
ring
- rotate the values in each layer in
ring
- overwrite the layers in the matrix from
ring
Step 1 and 3 have very similar code, as you yourself noticed.
One way to reduce that is to implement shifting in-place,
without using the additional storage
ring,by doing something like this (\$k\$ is the number of rotations):
- save the first \$k\$ items in a list
- overwrite the \$i\$-th values by the \$(i+k)\$-th values. The last \$k\$ values will come from the values we saved in the previous step.
Easier said than done? Yes. Calculating the \$(i + k)\$-th position will be tricky.
I'd say your original implementation with the similar lines is fine:
it's easy to understand, and it passed the tests anyway.
Code Snippets
matrix = []
for row in range(M):
matrix.append(list(map(int, input().split())))matrix = [list(map(int, input().split())) for _ in range(M)]ring = [[] for layer in range(layers)]ring = [[] for _ in range(layers)]layers = int(min(N, M)/2)Context
StackExchange Code Review Q#99073, answer score: 5
Revisions (0)
No revisions yet.