Skip to content

Instantly share code, notes, and snippets.

@wikiti
Last active September 6, 2022 05:11
Show Gist options
  • Save wikiti/f367f9bbced61957a077 to your computer and use it in GitHub Desktop.
Save wikiti/f367f9bbced61957a077 to your computer and use it in GitHub Desktop.
Print or traverse a matrix in spiral order using Ruby language
# Helper method to clone objects
def deep_clone(object)
Marshal.load(Marshal.dump(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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment