wikiti
8/21/2015 - 1:13 AM

## Print or traverse a matrix in spiral order

Print or traverse a matrix in spiral order using Ruby language

``````# Helper method to clone objects
def deep_clone(object)
end

# The concept y pretty simple: imagine that you have the following matrix:
#      1  2  3  4
#     10 11 12  5
#      9  8  7  6
#
# Represented in ruby like so:
# [[1,2,3,4],[10,11,12,5],[9,8,7,6]]
#
# The result of traveling it in spiral order should be [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
#
# The trick is to "peel layers" from the matrix's borders (top, right, botto and left) until it's fully empty.
#
#     TOP LAYER
#     output: [1, 2, 3, 4]
#      1  2  3  4
#      |  |  |  |
#     10 11 12  5     10 11 12  5
#      9  8  7  6      9  8  7  6
#   --------------------------------
#     RIGHT LAYER
#     output: [1, 2, 3, 4, 5, 6]
#
#     10 11 12 - 5    10 11 12
#      9  8  7 - 6     9  8  7
#   --------------------------------
#     BOTTOM LAYER
#     output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
#
#     10 11 12        10 11 12
#      |  |  |
#      9  8  7
#   --------------------------------
#     LEFT LAYER
#     output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#
#     10 - 11 12      11 12
#   --------------------------------
#     TOP LAYER
#     output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
#
#     11 12
#      ^  ^
#   --------------------------------
#     END
#     output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
#
# Note that the borders from left and bottom layers must be reversed in order to traverse them properly.
#
def spiral_matrix(matrix)
# Copy the matrix (optional) and prepare the output array.
matrix = deep_clone(matrix)
output = []

# Lambdas to execute depending on the current case. In summary, they will do the following:
# top    -> remove the first array, which is the first row.
# right  -> for each row, remove the last element (last column) and return all of them packed (map).
# bottom -> remove the last array, which is the last row. The result must be reversed.
# left   -> for each row, remove the first element (first column) and return all of them packed (map). The result must be reversed.
actions = {
top:    lambda{ matrix.shift                       },
right:  lambda{ matrix.map { |f| f.pop }           },
bottom: lambda{ matrix.pop.reverse                 },
left:   lambda{ matrix.map { |f| f.shift }.reverse }
}
# `cases` will iterate the above hash keys like following: top, right, bottom, left, top, right, ...
cases = actions.keys.cycle

# Repeat until the matrix is empty (this will call the lambdas from the hash of above).
output.concat actions[ cases.next ].call() until matrix.empty?

# Return output array.
output
end

# Test it!
matrix = [
[ 1,  2,  3,  4],
[12, 13, 14,  5],
[11, 16, 15,  6],
[10,  9,  8,  7]
]
puts spiral_matrix(matrix).join(', ') # 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16``````