Outward spiraling

Question

I am looking for a loop through a matrix similar to Looping in a spiral , but looping outside, instead of inside out. Can someone help me with a good way to do this for a matrix of any size, ideally in Ruby?

Example: In a 3x4 matrix, I want to start from [0,0] to the right, and then go down as soon as it reaches [3,0], move left to [3,2], etc.

[0,0] [1,0] [2,0] [3,0] [0,1] [1,1] [2,1] [3,1] [0,2] [1,2] [2,2] [3,2] 

The movement order is shown below:

 0 1 2 3 9 10 11 4 8 7 6 5 

And the output will be:

 [0,0], [1,0], [2,0], [3,0], [3,1], [3,2], [2,2], [1,2], [0,2], [0,1], [1,1], [2,1] 

Answer 1

Without loss of generality, write an array as:

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

Desired Result:

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

I use the helper:

 def rotate_anticlockwise(arr) arr.map(&:reverse).transpose end 

For instance:

 rotate_anticlockwise(arr) #=> [[4, 5, 6, 7], # [3, 14, 15, 8], # [2, 13, 16, 9], # [1, 12, 11, 10]] 

Now we can calculate the desired result as follows:

 out = [] a = arr.map(&:dup) while a.any? out.concat(a.shift) a = rotate_anticlockwise(a) end out # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 

Answer 2

This is a problem that has always fascinated me. @CarySwoveland has a trick that makes it really elegant in Ruby. Here is a one line method:

 def spiral(matrix) matrix.empty? ? [] : matrix.shift + spiral(matrix.transpose.reverse) end arr = [[ 1, 2, 3, 4,], [12, 13, 14, 5,], [11, 16, 15, 6,], [10, 9, 8, 7,]] spiral(arr) # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 

However, one of the drawbacks of this approach is that it mutates the original arr matrix:

 arr # => [[12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]] 

There are several answers in this gist that also deserve attention.

Answer 3

Here is a working C code that prints a 2D matrix clockwise from the outside inward.

 int n = 2, m = 5; int arr[2][5] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int top = 0, bottom = n-1, right = m-1, left = 0, i=0, j=0; printf("%d ", arr[i][j]); while(1){ if(top>bottom || left>right) break; if(bottom==top){ for(j=left; j<=right; j++) printf("%d ", arr[top][j]); break; } if(right==left){ for(i=top; i<=bottom; i++) printf("%d ", arr[left][i]); break; } int first = 1; while(j<=right){ if(first){ j++; first = 0; continue; } printf("%d ", arr[i][j]); j++; } j--; right--; first = 1; while(i<=bottom){ if(first){ i++; first = 0; continue; } printf("%d ", arr[i][j]); i++; } i--; bottom--; first = 1; while(j>=left){ if(first){ j--; first = 0; continue; } printf("%d ", arr[i][j]); j--; } j++; left++; first = 1; while(i>=top+1){ if(first){ i--; first = 0; continue; } printf("%d ", arr[i][j]); i--; } i++; top++; } 

The logic and rationale of the code is that you keep the boundaries of the matrix, which has not yet been printed. Therefore, at the beginning of the procedure, the upper bound = 0, bottom = n-1, left = 0, right = n-1.

At each iteration in the outer loop, you check to see if the remaining matrix defined by the boundaries degenerates into a matrix of rows or columns. Or, if all the elements of the matrix were printed, after which it leaves the loop.

In addition, the “first” variable in each inner while loop keeps track of whether the value we're printing is the first value for this line / col. The first value will not be printed, because it has already been printed in a loop immediately before it.

Difficulty of time: O(n)
Space Complexity: O(1)

where n is the number of elements in the array.

Answer 4

This method does what you need, it passes through an external spiral and then recursively calls itself a loop through internal spirals

 def inward_spiral(height, width, current_height, current_width) if height <= 0 || width <= 0 return end # Right (width-1).times do puts "[#{current_width}, #{current_height}]" current_width += 1 end # Down (height-1).times do puts "[#{current_width}, #{current_height}]" current_height += 1 end # Left if height > 1 (width-1).times do puts "[#{current_width}, #{current_height}]" current_width -= 1 end end # Up if width > 1 (height-2).times do puts "[#{current_width}, #{current_height}]" current_height -= 1 end end puts "[#{current_width}, #{current_height}]" inward_spiral(height-2, width-2, current_width + 1, current_height) end 

And then call it inward_spiral(3,4,0,0)

You can also fill in the matrix to draw a spiral, if at each step you fill it with the fact that you get something like this:

 → → → → ↴ ↱ → → ↴ ↓ ↑ ↱ ↴ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ↓ ↓ ↓ ↑ ↑ ✓ ↓ ↓ ↑ ↑ ← ⤶ ↓ ↑ ← ← ← ⤶