How to loop 2D array in a anti-clock wise fashion?

Question

Given a 2D array of m x n dimension, how can I loop through them in anti-clockwise fashion?

For example:

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

1st loop: 1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2
2nd loop: 6, 10, 11, 7, 6

I really don't mind if the implementation is given in ruby or js

My current solution is like this:

  (1..rotate).each do
    bottom_left_corner = i
    top_right_corner   = j
    start_nth_layer = 1; end_nth_layer = matrix.length - 2
    matrix.reverse_each do
      matrix[bottom_left_corner].unshift(matrix[bottom_left_corner - 1].shift) if bottom_left_corner > 0
      matrix[top_right_corner] << matrix[top_right_corner + 1].pop if top_right_corner < matrix.length - 1

      bottom_left_corner -= 1; top_right_corner += 1
    end

    nth_layer(matrix, start_nth_layer, end_nth_layer)

  end

Update

The output doesn't format doesn't matter, as long as it outputs the correct order.

Purpose of the problem

The purpose of this problem is traverse these arrays anti-clockwise, layer by layer, until no more layers. For each traversal, we shift the values in anti-clockwise. For example:

 Iteration 1:        Iteration 2:       Iteration 3:
 ==============      =============      ==============
 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

@TonyDong I'm attempting this interesting algorithm problem in hackerrank — Does, Oct 11 '18 at 16:00
@Does Is `matrix` length guaranteed to be the same as `matrix[n]` length? — choz, Oct 11 '18 at 16:01
Check this link for the answer https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/ — Tony Dong, Oct 11 '18 at 16:13
Your "2nd loop" should end with `7`. Note that `6` has already been traversed. — Cary Swoveland, Oct 11 '18 at 21:14
Your issue is not clear. What makes the first loop open (start with 1, and end right before 1) while the second loop closed (start with 6 and end with 6)? — sawa, Oct 12 '18 at 06:48
It is also not clear what to do when m is not even or n does not equal m. — sawa, Oct 12 '18 at 06:51
@sawa the constraint of the problem is that m will always be even — Does, Oct 12 '18 at 09:05

wang · Answer 1 · 2018-10-11T16:38:00.287

This is Matrix Layer Rotation problem. Here is my full solution:

function matrixRotation(matrix, rotate) {
    var r = matrix.length, c = matrix[0].length;
    var depth = Math.min(r,c)/2;
    for(var i=0;i<depth;i++) {
        var x = i, y = i, n = (r-i*2 - 2)*2 + (c-i*2-2)*2+4, dir = 'down', index=0;
        var buf = [];
        while(index < n) {
            buf.push(matrix[x][y]);
            if(dir == 'down') {
                if(x+1 >= r-i) {
                    dir = 'right';
                    y++;
                } else {
                    x++;
                }
            } else if(dir == 'right') {
                if(y+1 >= c-i) {
                    dir = 'up';
                    x--;
                } else {
                    y++;
                }
            } else if(dir == 'up') {
                if(x-1 <= i-1) {
                    dir = 'left';
                    y--;
                } else {
                    x--;
                }
            } else if(dir == 'left') {
                y--;
            }
            index++;
        }
        var move = rotate%n;
        buf = [...buf.slice(buf.length-move), ...buf.slice(0, buf.length-move)]
        x = i, y = i, dir = 'down', index = 0;
        while(index < n) {
            matrix[x][y] = buf[index];
            if(dir == 'down') {
                if(x+1 >= r-i) {
                    dir = 'right';
                    y++;
                } else {
                    x++;
                }
            } else if(dir == 'right') {
                if(y+1 >= c-i) {
                    dir = 'up';
                    x--;
                } else {
                    y++;
                }
            } else if(dir == 'up') {
                if(x-1 <= i-1) {
                    dir = 'left';
                    y--;
                } else {
                    x--;
                }
            } else if(dir == 'left') {
                y--;
            }
            index++;
        }
    }
    matrix.map(row => console.log(row.join(' ')));
}

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

matrixRotation(matrix, r);

score 0 · Answer 2 · answered Oct 11 '18 at 16:40

This approach should support any sizes of matrix and matrix[n]. Give it a try with various test cases if this works for you.

Note that I ignore any performance defects here.

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

while ( arr.flat().length ) {
  var res = [];

  // 1. Left side
  arr.forEach(x => res = res.concat( x.splice(0, 1) ));

  // 2. Bottom side
  if (arr.length) {
    res = res.concat( ...arr.splice(arr.length - 1, 1) );
  }

  // 3. Right side
  var tmp = [];
  if (arr.flat().length) {
    arr.forEach(x => tmp.push( x.splice(arr.length - 1, 1) ));
    res = res.concat( ...tmp.reverse() );
  }

  // 4. Top side
  if (arr.length) {
    tmp = [].concat( ...arr.splice(0, 1) );
    res = res.concat( tmp.reverse() );
  }

  result.push(res);
}

console.log(result);

score 0 · Answer 3 · answered Oct 11 '18 at 17:33

I would write this in a layered fashion, writing matrix transposition logic (that is, flipping a matrix over the northwest-southeast diagonal), using that and a simple reverse to build a counter-clockwise rotation of the matrix, using that rotation to build a clockwise spiral, and finally using transpose again alongside the clockwise spiral to build a counter-clockwise spiral.

I chose this order because a clockwise spiral is more commonly requested, but it would be easy enough to build the counterclockwise spiral directly. Hint: rotateClockwise = m => transpose(reverse(m)).

const reverse = a => [...a].reverse();
const transpose = m => m[0].map((c, i) => m.map(r => r[i]))
const rotateCounter = m => reverse(transpose(m))
const spiralClockwise = m => m.length < 2
  ? m[0]
  : m[0].concat(spiralClockwise(rotateCounter(m.slice(1))))
const spiralCounter = m => spiralClockwise(transpose(m))

console.log(spiralCounter([
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12]
]))

Note that the intermediate functions here are quite possibly useful in their own right. So this strikes me as a good way to break down the problem.

Looking over this again, I'm not sure whether your "1st loop"/"2nd loop" breakdown was just a demonstration of the algorithm or your expected output. This one creates a flat list of the entire path. If you want this as separate lists, then this may not help. — Scott Sauyet, Oct 11 '18 at 17:41

iGian · Answer 4 · 2018-10-11T23:09:45.283

Given the array:

array = 
  [
    [ '00', '01', '02', '03', '04', '05'],
    [ '10', '11', '12', '13', '14', '15'],
    [ '20', '21', '22', '23', '24', '25'],
    [ '30', '31', '32', '33', '34', '35']
  ]

This returns the external loop:

external_ccw_round = [array.map(&:shift), array.pop, array.map(&:pop).reverse, array.shift.reverse].flatten
#=> ["00", "10", "20", "30", "31", "32", "33", "34", "35", "25", "15", "05", "04", "03", "02", "01"]

Leaving just the core

array #=> [["11", "12", "13", "14"], ["21", "22", "23", "24"]]

For matrix with more than one row.

This is a method with a recursive implementation

Works on any matrix 2D.

def ccw_scan(array, result=[])
  return array if array.size <= 1
  result << [array.map(&:shift), array.pop, array.map(&:pop).reverse, array.shift.reverse]
  if array.size >= 2
    then ccw_scan(array, result)
  else result << array
  end
  result.flatten.compact
end

Call the method on the array:

ccw_scan(array)
#=> ["00", "10", "20", "30", "31", "32", "33", "34", "35", "25", "15", "05", "04", "03", "02", "01", "11", "21", "22", "23", "24", "14", "13", "12"]

Updated with a recursive method to get all the elements in spiral. — iGian, Oct 11 '18 at 18:25
@CarySwoveland, yes thanks, I missed `.compact` while editing. Your suspect is correct. — iGian, Oct 11 '18 at 23:18

engineersmnky · Answer 5 · 2018-10-11T19:34:15.423

This is how I went about it in ruby:

def counter_clockwise!(arr)
  return arr if arr.size <= 1
  rotation = [
    arr.map(&:shift)
      .concat(arr.pop,
              arr.map(&:pop).reverse,
              arr.shift.reverse).compact
  ]
  rotation.push(*send(__method__,arr)) unless arr.all?(&:empty?)
  rotation 
end

def counter_clockwise(arr)
  counter_clockwise!(arr.map(&:dup))
end

Example:

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

This method recursively processes the outside edges into groups ("Loops" in your original post). Obviously if you just wanted the counter clockwise spiral without the groups you could flatten the return value.

This will also process non M x N Matrices such as:

arr = [
  [   1,    2,   3,    4  , 72 ],
  [   5,    6,   7,    8  , 73 ],
  [   9,   10,        11  , 12 ],
  [  13,   14,        16  , 75 ],
  [  17,   18,  19,   20  , 76 ],
  [  21,   22,  23,   24  , 77 ]
]

counter_clockwise(arr) 
#=> [[1, 5, 9, 13, 17, 21, 22, 23, 24, 77, 76, 75, 12, 73, 72, 4, 3, 2],       
#   [6, 10, 14, 18, 19, 20, 16, 11, 8, 7]]

If you want each edge and can guarantee M x N then this will work too

def counter_clockwise_edges(arr)
  return arr if arr.size == 1
  arr = arr.transpose
  [arr.shift].push(*send(__method__,arr.map(&:reverse))) 
end
counter_clockwise_edges(arr)
#=> [[1, 5, 9, 13, 17, 21], 
     [22, 23, 24], 
     [20, 16, 12, 8, 4], 
     [3, 2], 
     [6, 10, 14, 18], 
     [19, 15, 11, 7]]

Cary Swoveland · Answer 6 · 2018-10-11T21:37:00.397

The following is a modification of my answer to this SO question, which differs from this one only in that the array is traversed in the opposite direction.

arr = matrix.map(&:dup).transpose
out = []
loop do
  out = out + arr.shift
  break out if arr.empty?
  arr = arr.transpose.reverse
end
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10, 11, 7]

The steps are as follows.

arr = matrix.map(&:dup).transpose
  #=> [[1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]]

I've duped the elements of matrix so that the latter will not be mutated.

out = []

out = out + arr.shift
  #=> [1, 5, 9, 13]
arr
  #=> [[2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]]    

arr = arr.transpose.reverse
  #=> [[14, 15, 16], [10, 11, 12], [6, 7, 8], [2, 3, 4]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16]
arr
  #=> [[10, 11, 12], [6, 7, 8], [2, 3, 4]]

arr = arr.transpose.reverse
  #=> [[12, 8, 4], [11, 7, 3], [10, 6, 2]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4]
arr
  #=> [[11, 7, 3], [10, 6, 2]]

arr = arr.transpose.reverse
  #=> [[3, 2], [7, 6], [11, 10]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]
arr
  #=> [[7, 6], [11, 10]]

arr = arr.transpose.reverse
  #=> [[6, 10], [7, 11]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10]
arr
  #=> [[7, 11]]

arr = arr.transpose.reverse
  #=> [[11], [7]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10, 11]
arr
  #=> [[7]]

arr = arr.transpose.reverse
  #=> [[7]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10, 11, 7]
arr
  #=> []

As arr is now empty we break and return out.

arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

How to loop 2D array in a anti-clock wise fashion?

Update

Purpose of the problem

6 Answers6

Linked