ruby - rotate Matrix anti-clockwise by n position

Viewed 920

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

4 Answers

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

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
)

This is another implementation (I didn't make a method, just the logic that needs to be improved).

array = (1..24).each_slice(6).to_a
array.each { |e| p e }
puts 

n = 4 # sub matrix rows
m = 6 # sub matrix cols
x = 0 # x row origin (corner) of the rotation
y = 0 # y col origin (corner) of the rotation
rotations = 2 # negative is ccw, positive is cw

raise "Sub matrix too small, must be 2x2 at least" if m < 2 || n < 2
# to add: check if the submatrix is inside the matrix, given the origin x, y
y_size = array.size
x_size = array.size
idx_map = Array.new(n){ [] }
m.times.map { |mm| n.times.map { |nn| idx_map[nn][mm] = [nn + x, mm + y] } }
before = [(idx_map.map(&:shift)).concat(idx_map.pop).concat(idx_map.map(&:pop).reverse).concat(idx_map.shift.reverse)].flatten(1)
after = before.rotate(rotations)
tmp = array.map(&:dup)
before.size.times.map { |idx| array[before[idx][0]][before[idx][1]] = tmp[after[idx][0]][after[idx][1]]}

array.each { |e| p e }

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

You can also rotate a 3x3 sub-matrix starting in (1, 1), so, for example n = 3, m = 3, x = 1, y = 1 and rotations = -1:

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

I thought it would be interesting to benchmark my code against @Humbledore's. (@iGian: I can add your code to the benchmark if you can edit your answer to wrap it in a method with arguments matrix and nbr_rotations).

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 cary1(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

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

def cary2(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 = m
    rrow, rcol = first_replacement_loc(rows, cols, rotations)
    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

def humbledore(matrix, rotate)
  rows, cols = matrix.size, matrix.first.size
  layers, str_cols = [rows, cols].min / 2, ""
  # cols.times do str_cols << "%5s " end
  temp_rows = []
  (0...layers).each do |layer|
    row = []
    (layer...rows - 1 - layer).each do |i|
      row << matrix[i][layer]
    end
    (layer...cols - 1 - layer).each do |i|
      row << matrix[rows - 1 - layer][i]
    end
    (rows - 1 - layer).step(layer + 1, -1).each do |i|
      row << matrix[i][cols - 1 - layer]
    end
    (cols - 1 - layer).step(layer + 1, -1).each do |i|
      row << matrix[layer][i]
    end
    temp_rows << row
  end
  result = (1..( rows * cols )).each_slice(rows).to_a
  (0...layers).each do |layer|
    row = temp_rows[layer]
    shift = rotate % row.size
    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
end

require 'benchmark'

def test(rows, cols, rotations)
  puts "\nrows = #{rows}, cols = #{cols}, rotations = #{rotations}"
  matrix = (1..rows*cols).each_slice(cols).to_a
  Benchmark.bm do |x|
    x.report("Cary1") { cary1(matrix, rotations) }
    x.report("Cary2") { cary2(matrix, rotations) }
    x.report("Humbledore") { humbledore(matrix, rotations) }
  end
end

test 10,10,1
rows = 10, cols = 10, rotations = 1
   user         system      total        real
   Cary1       0.000000   0.000000   0.000000 (  0.000077)
   Cary2       0.000000   0.000000   0.000000 (  0.000074)
   Humbledore  0.000000   0.000000   0.000000 (  0.000051)

test 10,10,78
rows = 10, cols = 10, rotations = 78
   user         system      total        real
   Cary1       0.000000   0.000000   0.000000 (  0.000079)
   Cary2       0.000000   0.000000   0.000000 (  0.000061)
   Humbledore  0.000000   0.000000   0.000000 (  0.000053)

test 100,100,378
rows = 100, cols = 100, rotations = 378
   user         system      total        real
   Cary1       0.000000   0.000000   0.000000 (  0.007673)
   Cary2       0.015625   0.000000   0.015625 (  0.005168)
   Humbledore  0.000000   0.000000   0.000000 (  0.002919)

test 500,500,1950
rows = 500, cols = 500, rotations = 1950
   user         system      total        real
   Cary1       0.171875   0.000000   0.171875 (  0.166671)
   Cary2       0.140625   0.000000   0.140625 (  0.137141)
   Humbledore  0.046875   0.000000   0.046875 (  0.053705)

test 500,1000,2950
rows = 500, cols = 1000, rotations = 2950
   user         system      total        real
   Cary1       0.296875   0.000000   0.296875 (  0.292997)
   Cary2       0.234375   0.000000   0.234375 (  0.248384)
   Humbledore  0.125000   0.000000   0.125000 (  0.103964)

Benchmark reports execution times in seconds. The results are found to be quite consistent.

Notice that in all of the tests I performed the number of columns of the array is at least as large as the number of rows. That's because a NoMethodError (undefined method '[]=' for nil:NilClass) exception was raised in Humbledore's code whenever the number of rows exceeded the number of columns. (Try test 3,2,1, for example.) The error message occurred in the second line of the following block of code.

(layer...cols - 1 - layer).each do |i|
  result[rows - 1 - layer][i] = row[idx]
  idx += 1
  idx %= row.size
end

I expect the problem is easily fixable.

Related