Last active
September 6, 2022 05:11
-
-
Save wikiti/f367f9bbced61957a077 to your computer and use it in GitHub Desktop.
Print or traverse a matrix in spiral order using Ruby language
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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