mirror of
https://github.com/TheAlgorithms/Python.git
synced 2024-11-27 15:01:08 +00:00
53b2926704
* Enable ruff PGH003 rule * Fix * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Fix --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
134 lines
3.5 KiB
Python
134 lines
3.5 KiB
Python
"""
|
||
This program print the matrix in spiral form.
|
||
This problem has been solved through recursive way.
|
||
Matrix must satisfy below conditions
|
||
i) matrix should be only one or two dimensional
|
||
ii) number of column of all rows should be equal
|
||
"""
|
||
|
||
|
||
def check_matrix(matrix: list[list[int]]) -> bool:
|
||
# must be
|
||
matrix = [list(row) for row in matrix]
|
||
if matrix and isinstance(matrix, list):
|
||
if isinstance(matrix[0], list):
|
||
prev_len = 0
|
||
for row in matrix:
|
||
if prev_len == 0:
|
||
prev_len = len(row)
|
||
result = True
|
||
else:
|
||
result = prev_len == len(row)
|
||
else:
|
||
result = True
|
||
else:
|
||
result = False
|
||
|
||
return result
|
||
|
||
|
||
def spiral_print_clockwise(a: list[list[int]]) -> None:
|
||
"""
|
||
>>> spiral_print_clockwise([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
|
||
1
|
||
2
|
||
3
|
||
4
|
||
8
|
||
12
|
||
11
|
||
10
|
||
9
|
||
5
|
||
6
|
||
7
|
||
"""
|
||
if check_matrix(a) and len(a) > 0:
|
||
a = [list(row) for row in a]
|
||
mat_row = len(a)
|
||
if isinstance(a[0], list):
|
||
mat_col = len(a[0])
|
||
else:
|
||
for dat in a:
|
||
print(dat)
|
||
return
|
||
|
||
# horizotal printing increasing
|
||
for i in range(mat_col):
|
||
print(a[0][i])
|
||
# vertical printing down
|
||
for i in range(1, mat_row):
|
||
print(a[i][mat_col - 1])
|
||
# horizotal printing decreasing
|
||
if mat_row > 1:
|
||
for i in range(mat_col - 2, -1, -1):
|
||
print(a[mat_row - 1][i])
|
||
# vertical printing up
|
||
for i in range(mat_row - 2, 0, -1):
|
||
print(a[i][0])
|
||
remain_mat = [row[1 : mat_col - 1] for row in a[1 : mat_row - 1]]
|
||
if len(remain_mat) > 0:
|
||
spiral_print_clockwise(remain_mat)
|
||
else:
|
||
return
|
||
else:
|
||
print("Not a valid matrix")
|
||
return
|
||
|
||
|
||
# Other Easy to understand Approach
|
||
|
||
|
||
def spiral_traversal(matrix: list[list]) -> list[int]:
|
||
"""
|
||
>>> spiral_traversal([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])
|
||
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
|
||
|
||
Example:
|
||
matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
|
||
Algorithm:
|
||
Step 1. first pop the 0 index list. (which is [1,2,3,4] and concatenate the
|
||
output of [step 2])
|
||
Step 2. Now perform matrix’s Transpose operation (Change rows to column
|
||
and vice versa) and reverse the resultant matrix.
|
||
Step 3. Pass the output of [2nd step], to same recursive function till
|
||
base case hits.
|
||
Dry Run:
|
||
Stage 1.
|
||
[1, 2, 3, 4] + spiral_traversal([
|
||
[8, 12], [7, 11], [6, 10], [5, 9]]
|
||
])
|
||
Stage 2.
|
||
[1, 2, 3, 4, 8, 12] + spiral_traversal([
|
||
[11, 10, 9], [7, 6, 5]
|
||
])
|
||
Stage 3.
|
||
[1, 2, 3, 4, 8, 12, 11, 10, 9] + spiral_traversal([
|
||
[5], [6], [7]
|
||
])
|
||
Stage 4.
|
||
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5] + spiral_traversal([
|
||
[5], [6], [7]
|
||
])
|
||
Stage 5.
|
||
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5] + spiral_traversal([[6, 7]])
|
||
Stage 6.
|
||
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] + spiral_traversal([])
|
||
"""
|
||
if matrix:
|
||
return list(matrix.pop(0)) + spiral_traversal(
|
||
[list(row) for row in zip(*matrix)][::-1]
|
||
)
|
||
else:
|
||
return []
|
||
|
||
|
||
# driver code
|
||
if __name__ == "__main__":
|
||
import doctest
|
||
|
||
doctest.testmod()
|
||
|
||
a = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
|
||
spiral_print_clockwise(a)
|