Given a 2D matrix:
matrix = [
[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]
]
How can we rotate the matrix anti-clockwise so that values are pushed like this?
matrix = [
[ 2, 3, 4, 8 ]
[ 1, 7, 11, 12 ]
[ 5, 6, 10, 16 ]
[ 9, 13, 14, 15 ]
]
This question is not a duplicate of this & this because what I'm trying to achieve is by rotating the values in anti-clockwise fashion.
My current implementation only prints out the values in anti-clockwise fashion, but it does not rotate the values.
layers = [_rows, _cols].min / 2
r1, r2, c3, c4 = 0, _rows, _cols, _cols
new_matrix = Array.new(_rows + 1) { Array.new(_cols + 1) }
(0..layers).each do |layer|
row_top_left, row_bottom_left, col_top_right, col_bottom_right = r1, r2, c3, c4
result = []
while row_top_left < row_bottom_left
result << matrix[row_top_left][layer]
row_top_left += 1
end
row_bottom_left = layer
while row_bottom_left < col_bottom_right
result << matrix[row_top_left][row_bottom_left]
row_bottom_left += 1
end
temp_col_bottom_right = col_bottom_right
temp_col_top_right = layer
while col_bottom_right > temp_col_top_right
result << matrix[col_bottom_right][temp_col_bottom_right]
col_bottom_right -= 1
end
# p row_top_left
tmp_row_top_left = layer
while col_top_right > tmp_row_top_left
result << matrix[tmp_row_top_left][col_top_right]
col_top_right -= 1
end
p result.cycle
r1 += 1
r2 -= 1
c3 -= 1
c4 -= 1The key idea is that the matrix needs to be rotated in the correct way. For example, let's say our matrix requires 2 rotation. Therefore:
matrix_rotation(
matrix.length - 1, # rows
matrix[0].length - 1, # columns
2, # Nom. of rotation
matrix # The matrix
)
matrix = [
# Original Iter: 1 Iter: 2
[ 1, 2, 3, 4 ], # [ 2, 3, 4, 8 ] # [ 3, 4, 8, 12 ]
[ 5, 6, 7, 8 ], # [ 1, 7, 11, 12 ] # [ 2, 11, 10, 16 ]
[ 9, 10, 11, 12 ], # [ 5, 6, 10, 16 ] # [ 1, 7, 6, 15 ]
[ 13, 14, 15, 16 ] # [ 9, 13, 14, 15 ] # [ 5, 9, 13, 14 ]
]
The dimension of the array is denoted: NxM where N and M can be any numbers, even or odd. For example 5x4, 4,4, 4x8 etc..
There is no such thing as "empty squares".
If you want to jump straight to the solution code, jump to the bottom section of this answer.
You need to break down the problem and solve each one independently.
Let us walk through each point separately:
You need a way to get the number of layers. The below matrix has 2 layers. How?
given a matrix:
matrix layers
--------------------------------
| 1, 2, 3, 4 | 0 0 0 0 |
| 5, 6, 7, 8 | 0 1 1 0 |
| 9, 10, 11, 12 | 0 1 1 0 |
| 13, 14, 15, 16 | 0 0 0 0 |
--------------------------------
To find the number of layers, simply do:
[rows, cols].min / 2
Thus the first problem is done.
This part requires a lot of thinking. Let us visualise:
matrix layers
--------------------------------
| 1, 2, 3, 4 | ↓ ← ← ↰ | 0 0 0 0 |
| 5, 6, 7, 8 | ↓ 1 1 ↑ | 0 ↓ ↰ 0 |
| 9, 10, 11, 12 | ↓ 1 1 ↑ | 0 ↳ → 0 |
| 13, 14, 15, 16 | ↳ → → → | 0 0 0 0 |
--------------------------------
This is achievable. We will have 4 for loops. Each loop will take care of:
Before I get into the loops, we need some container to store our values in spiral form.
Let us have a temp array to store the values:
# this array will get us the output of borders of the layer
row = []
For the sake of explanation, let us only work on the outer most layer. (i.e. 0th layer:
# this loop will output the top-left side of the matrix
# ==============================
# ↓ [ 1, 2, 3, 4 ]
# ↓ [ 5, 6, 7, 8 ]
# ↓ [ 9, 10, 11, 12 ]
# ↓ [ 13, 14, 15, 16 ]
# Output: [[1, 5, 9], [6] ]
# ==============================
(0...rows - 1 - layer).each do |i|
row << matrix[i][layer]
end
Note: 0 means the 0th layer.
# this loop will output the bottom side of the matrix
# ==============================
# ↓ [ 1, 2, 3, 4 ]
# ↓ [ 5, 6, 7, 8 ]
# ↓ [ 9, 10, 11, 12 ]
# ↓ [ 13, 14, 15, 16 ]
# ↪ → → → →
# Output: [[1, 5, 9, 13, 14, 15], [6, 10]]
# ==============================
(0...cols - 1 - layer).each do |i|
row << matrix[rows - 1 - layer][i]
end
# this loop will output the right side of the matrix
# ==============================
# ↓ [ 1, 2, 3, 4 ] ↑
# ↓ [ 5, 6, 7, 8 ] ↑
# ↓ [ 9, 10, 11, 12 ] ↑
# [ 13, 14, 15, 16 ] ↑
# ↪ → → → → ⤻
# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8], [6, 10, 11]]
# ==============================
(rows - 1 - layer).step(0 + 1, -1).each do |i|
row << matrix[i][cols - 1 - layer]
end
# this loop will output the top side of the matrix
# ==============================
# ← ← ← ← ↰
# ↓ [ 1, 2, 3, 4 ] ↑
# ↓ [ 5, 6, 7, 8 ] ↑
# ↓ [ 9, 10, 11, 12 ] ↑
# [ 13, 14, 15, 16 ] ↑
# ↪ → → → → ⤻
# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2], [6, 10, 11, 7]]
# ==============================
(cols - 1 - layer).step(0 + 1, -1).each do |i|
row << matrix[layer][i]
end
So now at this point, we have the values in the spiral form. But the most important aspect of this problem lies in this section. How does one shift the values? Funnily enough, we will use modulo.
The modulo will do the main thing here. It will allow us to shift values based on the rotate. But also give us the correct index in the array to start the shift. For example, if we want to rotate 2 times: 2 % 12 = 2 for the outer most layer.
# row = [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]
shift = rotate % row.size
# if we negate shift variable, we can get correct index
# i.e. row[-2] = 3
idx = -shift
Before we shift values, let us create another matrix which will contain the correct values:
# let us create a new matrix
result = (1..( rows * cols )).each_slice(rows).to_a
We will loop again in the same manner, but get the values from the idx in row. For example:
(0...rows - 1 - 0).each do |i|
result[i][layer] = row[idx]
idx += 1
idx %= row.size
end
(0...cols - 1 - 0).each do |i|
result[rows - 1 - 0][i] = row[idx]
idx += 1
idx %= row.size
end
(rows - 1 - 0).step(0 + 1, -1).each do |i|
result[i][cols - 1 - 0] = row[idx]
idx += 1
idx %= row.size
end
(cols - 1 - 0).step(0 + 1, -1).each do |i|
result[0][i] = row[idx]
idx += 1
idx %= row.size
end
Note: 0 is the 0th layer (for the sake of explanation)
matrix_4_x_4 = (1..16).each_slice(4).to_a
matrix_8_x_8 = (1..64).each_slice(8).to_a
def matrix_rotation(*args)
# let us extract rows & cols from our matrix. We also need to know how
# times to rotate.
rows, cols, rotate, matrix = args
# to find out how many layers our matrix have, simply get the min of the two (rows, cols)
# and divide it
layers, str_cols = [rows, cols].min / 2, ""
# needed to beatify our console output in table format
cols.times do str_cols << "%5s " end
# we will work on a temporary array
temp_rows = []
# so the first task is to loop n times, where n is the number of layers
(0...layers).each do |layer|
# this array will get us the output of borders of the layer
row = []
# this loop will output the top-left side of the matrix
# ==============================
# ↓ [ 1, 2, 3, 4 ]
# ↓ [ 5, 6, 7, 8 ]
# ↓ [ 9, 10, 11, 12 ]
# ↓ [ 13, 14, 15, 16 ]
# Output: [[1, 5, 9], [6] ]
# ==============================
(layer...rows - 1 - layer).each do |i|
row << matrix[i][layer]
end
# this loop will output the bottom side of the matrix
# ==============================
# ↓ [ 1, 2, 3, 4 ]
# ↓ [ 5, 6, 7, 8 ]
# ↓ [ 9, 10, 11, 12 ]
# ↓ [ 13, 14, 15, 16 ]
# ↪ → → → →
# Output: [[1, 5, 9, 13, 14, 15], [6, 10]]
# ==============================
(layer...cols - 1 - layer).each do |i|
row << matrix[rows - 1 - layer][i]
end
# this loop will output the right side of the matrix
# ==============================
# ↓ [ 1, 2, 3, 4 ] ↑
# ↓ [ 5, 6, 7, 8 ] ↑
# ↓ [ 9, 10, 11, 12 ] ↑
# [ 13, 14, 15, 16 ] ↑
# ↪ → → → → ⤻
# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8], [6, 10, 11]]
# ==============================
(rows - 1 - layer).step(layer + 1, -1).each do |i|
row << matrix[i][cols - 1 - layer]
end
# this loop will output the top side of the matrix
# ==============================
# ← ← ← ← ↰
# ↓ [ 1, 2, 3, 4 ] ↑
# ↓ [ 5, 6, 7, 8 ] ↑
# ↓ [ 9, 10, 11, 12 ] ↑
# [ 13, 14, 15, 16 ] ↑
# ↪ → → → → ⤻
# Output: [[1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2], [6, 10, 11, 7]]
# ==============================
(cols - 1 - layer).step(layer + 1, -1).each do |i|
row << matrix[layer][i]
end
temp_rows << row
end
# let us create a new matrix
result = (1..( rows * cols )).each_slice(rows).to_a
# we're going to loop in the same manner as before
(0...layers).each do |layer|
# based on current layer, get the values around that layer
row = temp_rows[layer]
# !important: the modulo will do the main thing here:
# It will allow us to shift values based on the rotate. But also
# gives us the correct index in the array to start the shift.
# For example, if we want to rotate 2 times: 2 % 12 = 2 for the outer most layer
shift = rotate % row.size
# when whe negate the shift value, we will get the correct index from the end of the array.
# row = [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]
# So -2 in row[-2] for the outer layer is 3. We increment idx, then row[-1] is 2 etc..
idx = -shift
(layer...rows - 1 - layer).each do |i|
result[i][layer] = row[idx]
idx += 1
idx %= row.size
end
(layer...cols - 1 - layer).each do |i|
result[rows - 1 - layer][i] = row[idx]
idx += 1
idx %= row.size
end
(rows - 1 - layer).step(layer + 1, -1).each do |i|
result[i][cols - 1 - layer] = row[idx]
idx += 1
idx %= row.size
end
(cols - 1 - layer).step(layer + 1, -1).each do |i|
result[layer][i] = row[idx]
idx += 1
idx %= row.size
end
end
result.each do |row| printf("#{str_cols}\n", *row) end
end
matrix_rotation(
matrix_8_x_8.size,
matrix_8_x_8.first.size,
2,
matrix_8_x_8
)