Another one from the Leetcode challenge. This time, get the elements (single values) from the matrix in a spiral order with a starting position of [1,1].
So, the basic idea is to retrieve a vector of elements from a matrix in the following order:
In this order, we get the vector with the following elements:
So, we need to create the boundaries, count the rows | columns and return a vector of elements. Here is the useless function:
## return elements from matrix in spiral order
matrix_spiral <- function(mat) {
mr <- dim(mat)[1]
nc <- dim(mat)[2]
total_len <- mr*nc
#path #TRUE -> visited; FALSE -> unvisited
visit <- matrix(FALSE, nrow=mr, ncol=nc)
#helper variables
gor <- 1
dol <- mr
levo <- 1
desno <- nc
res <- vector()
while (length(res) < total_len) {
for (i in levo:nc) {
if (!visit[gor, i]) {
res <- c(res, mat[gor,i])
visit[gor, i] <- TRUE
} }
gor <- gor + 1
for (i in gor:mr) {
if (!visit[i, desno]) {
res <- c(res, mat[i,desno])
visit[i, desno] <- TRUE
} }
desno <- desno - 1
if (gor <= dol) {
for (i in desno:levo) {
if (!visit[dol, i]) {
res <- c(res, mat[dol,i])
visit[dol, i] <- TRUE
} }
dol <- dol - 1
}
if (levo <= desno) {
for (i in dol:gor) {
if (!visit[i, levo]) {
res <- c(res, mat[i,levo])
visit[i, levo] <- TRUE
} }
levo <- levo + 1
} }
return(res)
}
As always, the complete code is available on Github in Useless_R_function repository. The sample file in this repository is here (filename: Spiral_matrix.R). Check the repository for future updates.
Happy R-coding and stay healthy!
[…] article was first published on R – TomazTsql, and kindly contributed to R-bloggers]. (You can report issue about the content on this page […]
LikeLike
[…] Tomaz Kastrun forgot to remove The Club from his REPL: […]
LikeLike
Hmmm… seems (without analytic justification) that there should be an algorithm which, treating the array as a vector, generates the re-ordered indices automatically. I’ll have to look for some such.
LikeLike
I finished it! This code runs way faster than the original. I’ll leave future improvements up to the fan-base.
spirMat <- function(mat, handed = c('left','right'),…){
#later: more input validation
mdim <- base::dim(mat) # so I can bail if not an array
inCount <- 1:length(mat) # to be used later
# which way?
if (handed =='right') x <- x[,ncol(x):1]
# hmmm, save some heavy thinking by using a matching index array
# this will have values matching the index order in as.vector(imat)
imat <- array(1:length(mat),c(mdim[1],mdim[2]))
mseq <- iseq <- NULL
nrow <- mdim[1]
ncol <- mdim[2]
# use indexing to get actual array values, which for iseq magically are teh same as the locations…
vecmat <- as.vector(t(mat))
ivecmat 2 && ncol > 2) {
iseq <- c( iseq, ivecmat[c(1:ncol, ncol*(2:nrow), (nrow-1)*(ncol)+(ncol-1):1, ((nrow-2):1)* ncol + 1)])
mseq <- c(mseq, vecmat[c(1:ncol, ncol*(2:nrow), (nrow-1)*(ncol)+(ncol-1):1, ((nrow-2):1)* ncol + 1)])
mat <- mat[2:(nrow-1),2:(ncol-1),drop=FALSE]
vecmat <- as.vector(t(mat))
imat <- imat[2:(nrow-1),2:(ncol-1),drop=FALSE]
ivecmat <- as.vector(t(imat))
# here we catch a 1xN or Nx1 remaining bit
if (nrow(mat) ==1 || ncol(mat) == 1) {
mseq <- c(mseq, as.vector(mat))
iseq <- c(iseq, as.vector(t(imat)))
} else {
nrow <- nrow -2
ncol <- ncol -2
# check for exactly 2 rows
if(nrow(mat) == 2 ) {
# for 2xN don't want 4th term used in ncol == 2 section
iseq <- c(iseq, ivecmat[c(1:ncol, ncol*(2:nrow), (nrow-1)*(ncol)+(ncol-1):1)])
mseq <- c(mseq, vecmat[c(1:ncol, ncol*(2:nrow), (nrow-1)*(ncol)+(ncol-1):1)])
} else {
#exactly 2 columns
if( ncol(mat) == 2) {
iseq <- c( iseq, ivecmat[c(1:ncol, ncol*(2:nrow), (nrow-1)*(ncol)+(ncol-1):1, ((nrow-2):1)* ncol + 1)])
mseq <- c(mseq, vecmat[c(1:ncol, ncol*(2:nrow), (nrow-1)*(ncol)+(ncol-1):1, ((nrow-2):1)* ncol + 1)])
}
}
} #end of outer else
} #end while
return(invisible(list(spiral = mseq, idx = iseq)))
}
LikeLike