ruby - rotate Matrix anti-clockwise by n position

Question

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  ]
]

Note

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 & Problem

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 -= 1

update v0.1

The 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 ]
]

Update v0.2

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".

Answer 1

TL:DR

If you want to jump straight to the solution code, jump to the bottom section of this answer.

Explanation

You need to break down the problem and solve each one independently.

Problems

1. Get the number of layers
2. Loop in reverse spiral form to just get the expected values
3. Shift them based on the rotation parameter given

Let us walk through each point separately:

---

Get the number of layers

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.

---

Loop in reverse spiral form to just get the expected values

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:

1. left (top to bottom)
2. bottom (left to right)
3. right (bottom to top)
4. top (right to left)

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:

1st Loop (Left: top to bottom)

# 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.

2nd Loop (Bottom: Left to Right)

# 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

3rd Loop (Right: Bottom to Top)

# 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

4th Loop (Top: Right to Left)

# 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

---

Shift them based on the rotation parameter given

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)

Solution

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
)

Answer 2

Code

def nxt(rows, cols, row, col)
  case row     
  when rows[:first]
    col == cols[:last]  ? [row+1, col] : [row, col+1]
  when rows[:last]
    col == cols[:first] ? [row-1, col] : [row, col-1]
  else
    col == cols[:last]  ? [row+1, col] : [row-1, col]
  end
end

def rotate_array_times(matrix, n)
  arr = matrix.dup.map(&:dup)
  nrows, ncols = arr.size, arr.first.size     
  0.upto([nrows, ncols].min/2-1) do |m|
    rows = { first: m, last: nrows-m-1 }
    cols = { first: m, last: ncols-m-1 }
    rect_size = 2 * (nrows + ncols) - 8*m - 4
    rotations = n % rect_size
    row = col = rrow = rcol = m
    rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }
    rect_size.times do
      arr[row][col] = matrix[rrow][rcol]
      row, col   = nxt(rows, cols,  row,  col)
      rrow, rcol = nxt(rows, cols, rrow, rcol)
    end
  end
  arr
end

Examples

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

(1..3).each { |n| p rotate_array_times(matrix, n) }
  [[2,  3,  4,  8],
   [1,  7, 11, 12],
   [5,  6, 10, 16],
   [9, 13, 14, 15]]

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

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

matrix = (1..24).each_slice(4).to_a
  #=> [[ 1,  2,  3,  4],
  #    [ 5,  6,  7,  8],
  #    [ 9, 10, 11, 12],
  #    [13, 14, 15, 16],
  #    [17, 18, 19, 20],
  #    [21, 22, 23, 24]]
(1..3).each { |n| p rotate_array_times(matrix, n) }
  #=> [[ 2,  3,  4,  8],
  #    [ 1,  7, 11, 12],
  #    [ 5,  6, 15, 16],
  #    [ 9, 10, 19, 20],
  #    [13, 14, 18, 24],
  #    [17, 21, 22, 23]]

  #   [[ 3,  4,  8, 12],
  #    [ 2, 11, 15, 16],
  #    [ 1,  7, 19, 20],
  #    [ 5,  6, 18, 24],
  #    [ 9, 10, 14, 23],
  #    [13, 17, 21, 22]]

  #   [[ 4,  8, 12, 16],
  #    [ 3, 15, 19, 20],
  #    [ 2, 11, 18, 24],
  #    [ 1,  7, 14, 23],
  #    [ 5,  6, 10, 22],
  #    [ 9, 13, 17, 21]]

matrix = (1..48).each_slice(8).to_a
  #=> [[ 1,  2,  3,  4,  5,  6,  7,  8],
  #    [ 9, 10, 11, 12, 13, 14, 15, 16],
  #    [17, 18, 19, 20, 21, 22, 23, 24],
  #    [25, 26, 27, 28, 29, 30, 31, 32],
  #    [33, 34, 35, 36, 37, 38, 39, 40],
  #    [41, 42, 43, 44, 45, 46, 47, 48]]

(1..3).each { |n| p rotate_array_times(matrix, n) }
[[ 2,  3,  4,  5,  6,  7,  8, 16],
 [ 1, 11, 12, 13, 14, 15, 23, 24],
 [ 9, 10, 20, 21, 22, 30, 31, 32],
 [17, 18, 19, 27, 28, 29, 39, 40],
 [25, 26, 34, 35, 36, 37, 38, 48],
 [33, 41, 42, 43, 44, 45, 46, 47]]

[[ 3,  4,  5,  6,  7,  8, 16, 24], 
 [ 2, 12, 13, 14, 15, 23, 31, 32],
 [ 1, 11, 21, 22, 30, 29, 39, 40],
 [ 9, 10, 20, 19, 27, 28, 38, 48],
 [17, 18, 26, 34, 35, 36, 37, 47], 
 [25, 33, 41, 42, 43, 44, 45, 46]]

[[ 4,  5,  6,  7,  8, 16, 24, 32],
 [ 3, 13, 14, 15, 23, 31, 39, 40],
 [ 2, 12, 22, 30, 29, 28, 38, 48],
 [ 1, 11, 21, 20, 19, 27, 37, 47],
 [ 9, 10, 18, 26, 34, 35, 36, 46],
 [17, 25, 33, 41, 42, 43, 44, 45]]

Explanation

nxt

Given row and column indices row and col, nxt(rows, cols, row, col) returns the indices [next_row, next_col] of the "next" element on the perimeter of a subarray that is to replace the element (also on the perimeter) at indices [row, col] in a single iteration. The subarray is given by the hashes rows and cols which each have keys :first and :last.

Let's consider an an array arr with 4 elements (rows), each element (row) having 6 values (columns). Then

nrows, ncols = arr.size, arr.first.size
  #=> [4, 6]

If m = 0

rows = { first: m, last: nrows-m-1 }
  #=> {:first=>0, :last=>3}
cols = { first: m, last: ncols-m-1 }
  #=> {:first=>0, :last=>5}

It is seen that rows and cols describes the "perimeter" of he array matrix. We can see how nxt works as follows.

first_row, first_col = rows[:first], cols[:first]
row, col = first_row, first_col
print "[#{row}, #{col}]"
loop do
  next_row, next_col = nxt(rows, cols, row, col)
  print "->[#{next_row}, #{next_col}]"
  row, col = next_row, next_col
  (puts; break) if [row, col] == [first_row, first_col]
end
[0, 0]->[0, 1]->[0, 2]->[0, 3]->[0, 4]->[0, 5]->[1, 5]->[2, 5]->[3, 5]->
[3, 4]->[3, 3]->[3, 2]->[3, 1]->[3, 0]->[2, 0]->[1, 0]->[0, 0]

If m = 1, the above calculation yields

[1, 1]->[1, 2]->[1, 3]->[1, 4]->[2, 4]->[2, 3]->[2, 2]->[2, 1]->[1, 1]

rotate_array_times

This method constructs a deep copy of matrix, arrr, whose elements are rotated in the prescribed matter n times and then returns the resulting array.

To speed calculations, n is replaced by a modulus of itself. For a 4x4 array, for example, after 12 iterations the perimeter of the array would be back to its original value. Therefore, it is sufficient to perform n % 12 rotations.

matrix contains n = [matrix.size, matrix.first.size].min subarrays whose perimeters are to be rotated. The top-left corner of each subarray is given by the coordinate [m,m], where m = 0..n-1.

For the subarray specified by m the first step is to determine the location of the element of matrix that is to replace the element of arr at [m,m]. That is done in the line

rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }

("rrow" and "rcol" for "replacement row" and "replacement col", respectively). At this time the element of arr at location row #=> m, col #=> m is to be replaced the element of matrix at the location given by rrow and rcol. The following operations then performed as many times as there are elements in the perimeter of the subarray which are to be rotated:

arr[row][col] = matrix[rrow][rcol]
row, col   = nxt(rows, cols,  row,  col)
rrow, rcol = nxt(rows, cols, rrow, rcol)

Tweaking efficiency

A modest improvement in efficiency could be achieved by replacing the line

rotations.times { rrow, rcol = nxt(rows, cols, rrow, rcol) }

with

rrow, rcol = first_replacement_loc(rows, cols, rotations)

and adding the following method.

def first_replacement_loc(rows, cols, rotations)
  ncm1 = cols[:last]-cols[:first]       
  nrm1 = rows[:last]-rows[:first]
  return [rows[:first], cols[:first]+rotations] if rotations <= ncm1
  rotations -= ncm1
  return [rows[:first]+rotations, cols[:last]] if rotations <= nrm1
  rotations -= nrm1
  return [rows[:last], cols[:last]-rotations] if rotations <= ncm1
  rotations -= ncm1
  [rows[:last]-rotations, cols[:first]]
end