I took a slightly different route than @Ben.
I wanted to see the routes, so I've also got two additional functions. The first one is colorPrint, which adds color to the '3's in the matrix. The second is directedPrint, which replaces the 3's with the arrows pointing to the direction of travel.
Most of the code in both functions is to rebuild the 'appearance' of a matrix. (cat would print a matrix a single string of numbers)
These functions are called in search every time '2' is found.
library(crayon)
library(tidyverse)
colorPrint <- function(mazish) {
cols <- ncol(mazish)
rows <- nrow(mazish)
mazish <- gsub(", ", " ", # add color to values == 3
lapply(1:rows,
function(k) {
toString(mazish[k, ])
}) %>% unlist()
) %>% gsub(pattern = "3", replacement = green("3"))
rowing <- paste0("[", 1:rows, ",]") # rebuild matrix 'appearance' for cat
coling <- paste0("[,", 1:cols, "]")
# 4 spaces between each value
cat(" ", coling, "\n", paste0(rowing, " ", mazish, "\n"))
}
directedPrint <- function(mazish, directed) {
directed <- data.frame(matrix(unlist(directed), ncol = 2,
nrow = length(directed), byrow = T)) %>%
setNames(c("x", "y")) %>%
mutate(direct = case_when( # determine the direction of travel
lag(x) < x | lead(x) > x ~ '⬇', # first entry doesn't have any lags
lag(y) < y | lead(y) > y ~ '⮕',
lag(x) > x | lead(x) < x ~ '⬆',
lag(y) > y | lead(y) < y ~ '⬅',
TRUE ~ '·'))
cols <- ncol(mazish)
rows <- nrow(mazish)
mazishD <- matrix(as.character(mazish), nrow = rows, ncol = cols) # char matrix
lapply(1:nrow(directed), # replace 3's with arrows
function(j) {
where <-
what <- directed[j, "direct"]
mazishD[directed[j, "x"], directed[j, "y"]] <<- red(what)
})
rowing <- paste0("[", 1:rows, ",]") # build the 'appearance' of a matrix
coling <- paste0("[,", 1:cols, "]")
lmaz <- gsub(", ", " ", # prep for `cat` to appear as a matrix
lapply(1:rows,
function(k) {
toString(mazishD[k, ]) # 1 string per row for cat
}) %>% unlist()) %>% # arrows take more than 1 char space
str_replace_all(" \033", paste0(" \U200A\U2006", "\033"))
rowSp <- ifelse(substr(lmaz, 1, 1) == "\033", " \U200A\U2006", " ")
cat(" ", coling, "\n", paste0(rowing, rowSp, lmaz, "\n"))
}
Here's my search function.
search = function(maze, x, y, directions = NULL){
if(!exists("directions")) {
directions <- list()
}
directions <- append(directions, c(x, y))
if (x == 0 | y == 0) { # outside of matrix limits
return(FALSE)
} else if (x > nrow(maze) | y > ncol(maze)) { # outside of matrix limits
return(FALSE)
} else if (maze[x, y] == 2){
print(paste('I am in point', x, y))
colorPrint(maze) # print with 3's colored
directedPrint(maze, directions) # print solution with arrows
return(TRUE)
} else if (maze[x, y] == 1){
print(paste('wall in point', x, y))
return(FALSE)
} else if (maze[x, y] == 3){
print(paste('visited point', x, y))
return(FALSE)
}
#set as marked
print(paste('visited point', x, y))
maze[x, y] <- 3 # annotate path of travel
if((x < nrow(maze) & search(maze, x + 1, y, directions))
| (y > 1 & search(maze, x, y - 1, directions))
| (x > 1 & search(maze, x - 1, y, directions))
| (y < ncol(maze) & search(maze, x, y + 1, directions))) {
return(TRUE)
}
return(FALSE)
}
You'll use this similar to how you had initially described. However, I have to say that the data you provided has walls for the first 20 entries, meaning that there is nowhere for the maze search to go.
set.seed(253)
dt <- sample(c(
sample(c(rep(0, 10), c(rep(1, 4))), 49, replace = T), # random 0s, 1s
2), 50, replace = F) # only [1] 2
maze = matrix(dt, 5, 10, byrow = TRUE)
search(maze, 1, 1)
In the console, you'll see every possible route. However, I've only shown one route to the finish. (I made this an image so you would see the color & spacing.)
![enter image description here]()
You could always add collectors so you could see how many times it cycled and how many steps to each solution were needed.
This uses an external list. Here is the updated search function. there is one new line where if == 2.
search = function(maze, x, y, directions = NULL){
if(!exists("directions")) {
directions <- list()
}
directions <- append(directions, c(x, y))
if (x == 0 | y == 0) { # outside of matrix limits
return(FALSE)
} else if (x > nrow(maze) | y > ncol(maze)) { # outside of matrix limits
return(FALSE)
} else if (maze[x, y] == 2){
print(paste('I am in point', x, y))
colorPrint(maze) # print with 3's colored
directedPrint(maze, directions) # print solution with arrows
d[[length(d) + 1]] <<- length(directions) # how many directions were taken?
return(TRUE)
} else if (maze[x, y] == 1){
print(paste('wall in point', x, y))
return(FALSE)
} else if (maze[x, y] == 3){
print(paste('visited point', x, y))
return(FALSE)
}
#set as marked
print(paste('visited point', x, y))
maze[x, y] <- 3 # annotate path of travel
if((x < nrow(maze) & search(maze, x + 1, y, directions))
| (y > 1 & search(maze, x, y - 1, directions))
| (x > 1 & search(maze, x - 1, y, directions))
| (y < ncol(maze) & search(maze, x, y + 1, directions))) {
return(TRUE)
}
return(FALSE)
}
To use this one, you'll need to create a list in the global environment.
d = list()
dt2 <- matrix(data = c(rep(0, 5), 1,
1, 1, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 2,
rep(0, 5), 1),
nrow = 6, ncol = 6, byrow = F)
search(dt2, 1, 1)
This returned 43 solutions, where the shortest sequence was 20 steps & the longest was 48.
![enter image description here]()
