英文:
Recursive maze solver in R
问题
以下是您要的代码的中文翻译部分：
我想在R中解决一个迷宫问题。我创建了一个受到相应Python代码启发的函数：[使用Python解决迷宫问题：简单递归和A*搜索](https://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/?fbclid=IwAR2yW5f60jw3-agzkCl7HyNxSDfc5sAy7lFhz2OR4O1BBt674bpbWoyA-YQ)。
我有一个迷宫（即一个矩阵），其中：0 = 空白空间，1 = 墙（无法到达的单元格），2 = 终点，3 = 已访问。
设置迷宫：
```R
data = c(rep(1, 20),
c(4,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1),
c(1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,2),
rep(1, 20))
maze = matrix(data, 4, 20, byrow = TRUE)
我的尝试：
search = function(x, y){
if (maze[x,y] == 2){
print(paste('我在点', x, y))
return(TRUE)
} else if (maze[x,y]==1){
print(paste('点', x, y, '是墙'))
return(FALSE)
} else if (maze[x,y]==3){
print(paste('点', x, y, '已访问'))
return(FALSE)
}
#标记为已访问
print(paste('点', x, y, '已访问'))
maze[x,y] = 3
if((x < length(maze[,1]) & search(x+1, y))
| (y > 1 & search(x,y-1))
| (x > 1 & search(x-1,y))
| (y < length(maze[1,]) & search(x,y+1))){
return(TRUE)
}
return(FALSE)
}
search(x= 2, y = 1)
不幸的是，代码出现错误：
[1] "点 2 1 已访问"
[1] "点 3 1 是墙"
Error in if (maze[x, y] == 2) { : argument is of length zero
我看到了else语句的问题，因为函数停在一个空白单元格（即0）。
<details>
<summary>英文:</summary>
I want to solve a maze in R. I created a function inspired by corresponding Python code: [Solving mazes using Python: Simple recursivity and A* search](https://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/?fbclid=IwAR2yW5f60jw3-agzkCl7HyNxSDfc5sAy7lFhz2OR4O1BBt674bpbWoyA-YQ).
I have a maze (i.e. a matrix), where: 0 = empty space, 1 = wall (unreachable cell), 2 = finish, 3 = already visited.
Set up the maze:
data = c(rep(1, 20),
c(4,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1),
c(1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,2),
rep(1, 20))
maze = matrix(data, 4, 20, byrow = TRUE)
My attempt:
search = function(x, y){
if (maze[x,y] == 2){
print(paste('i am in point', x, y))
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
if((x < length(maze[,1]) & search(x+1, y))
| (y > 1 & search(x,y-1))
| (x > 1 & search(x-1,y))
| (y < length(maze[1,]) & search(x,y+1))){
return(TRUE)
}
return(FALSE)
}
search(x= 2, y = 1)
Unfortunately, the code errors:
[1] "visited point 2 1"
[1] "wall in point 3 1"
Error in if (maze[x, y] == 2) { : argument is of length zero
I see problem with `else` statement, because function stops on a cell which is empty, i.e. 0.
</details>
# 答案1
**得分**: 4
I took a slightly different route than @Ben.
我采用了与@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.
我想要查看路径，所以我还添加了两个额外的函数。第一个是`colorPrint`，它将矩阵中的'3'着色。第二个是`directedPrint`，它将3替换为指向旅行方向的箭头。
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)
这两个函数中的大部分代码都是用于重建矩阵的“外观”。（`cat`会将矩阵打印为单个数字字符串）
These functions are called in `search` every time `'2'` is found.
这些函数在每次找到'2'时都在`search`中调用。
Here's my `search` function.
以下是我的`search`函数。
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.
您将使用它，类似于您最初描述的方式。但是，我必须说，您提供的数据在前20个条目中有墙壁，这意味着迷宫搜索没有任何地方可去。
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.)
在控制台中，您将看到每条可能的路线。但是，我只显示了一条通往终点的路线。（我将其制作为图像，以便您可以看到颜色和间距。）
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`函数。其中有一行新代码，如果`== 2`。
To use this one, you'll need to create a list in the global environment.
要使用这个版本，您需要在全局环境中创建一个列表。
<details>
<summary>英文:</summary>
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][1]][1]
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][2]][2]
[1]: https://i.stack.imgur.com/XbZgU.png
[2]: https://i.stack.imgur.com/oKIfv.png
</details>
# 答案2
**得分**: 2
我认为在R中使这个代码工作可能需要一些调整。首先，Python数组是从0开始索引的，而R是从1开始索引的。所以你的错误可能是在矩阵中访问零索引元素。此外，在递归调用函数时，你可能需要将`maze`矩阵作为参数传递回去。
我根据Python示例（6 x 6矩阵）调整了你的演示。这里数字 '2' 表示终点位置。`search` 函数将分别检查是否越界。要查看迷宫是如何解决的，你可以取消注释 `maze` 的`print`语句。
```R
data <- c(
0, 0, 0, 0, 0, 1,
1, 1, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0,
0, 1, 1, 0, 0, 1,
0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 2
)
maze <- matrix(data, 6, 6, byrow = TRUE)
search <- function(maze, x, y) {
# 检查是否越界
if (x < 1 | x > length(maze[,1])) return (F)
if (y < 1 | y > length(maze[1,])) return (F)
# 检查是否到达终点，已经访问过，或者撞到墙上
if (maze[x, y] == 2){
print(paste('我到达终点了: ', x, y))
return(TRUE)
} else if (maze[x, y] == 3){
print(paste('已经访问过的点: ', x, y))
return(FALSE)
} else if (maze[x, y] == 1){
print(paste('墙在这个位置: ', x, y))
return(FALSE)
}
# 将点标记为已访问
maze[x,y] = 3
print(paste('访问点: ', x, y))
# 可选：显示解决后的迷宫
# print(maze)
# 检查下一个移动的方向
if (search(maze, x + 1, y)) return (T)
if (search(maze, x, y - 1)) return (T)
if (search(maze, x - 1, y)) return (T)
if (search(maze, x, y + 1)) return (T)
# 没有其他可行的移动
return(F)
}
search(maze, x = 1, y = 1)
输出
[1] "访问点: 1 1"
[1] "墙在这个位置: 2 1"
[1] "访问点: 1 2"
[1] "墙在这个位置: 2 2"
[1] "已经访问过的点: 1 1"
[1] "访问点: 1 3"
[1] "访问点: 2 3"
[1] "访问点: 3 3"
[1] "墙在这个位置: 4 3"
[1] "访问点: 3 2"
[1] "墙在这个位置: 4 2"
[1] "访问点: 3 1"
[1] "访问点: 4 1"
[1] "访问点: 5 1"
[1] "访问点: 6 1"
[1] "已经访问过的点: 5 1"
[1] "墙在这个位置: 6 2"
[1] "已经访问过的点: 4 1"
[1] "墙在这个位置: 5 2"
[1] "已经访问过的点: 3 1"
[1] "墙在这个位置: 4 2"
[1] "墙在这个位置: 2 1"
[1] "已经访问过的点: 3 2"
[1] "墙在这个位置: 2 2"
[1] "已经访问过的点: 3 3"
[1] "已经访问过的点: 2 3"
[1] "墙在这个位置: 3 4"
[1] "墙在这个位置: 2 2"
[1] "已经访问过的点: 1 3"
[1] "访问点: 2 4"
[1] "墙在这个位置: 3 4"
[1] "已经访问过的点: 2 3"
[1] "访问点: 1 4"
[1] "已经访问过的点: 2 4"
[1] "已经访问过的点: 1 3"
[1] "访问点: 1 5"
[1] "访问点: 2 5"
[1] "访问点: 3 5"
[1] "访问点: 4 5"
[1] "墙在这个位置: 5 5"
[1] "访问点: 4 4"
[1] "访问点: 5 4"
[1] "访问点: 6 4"
[1] "访问点: 6 3"
[1] "墙在这个位置: 6 2"
[1] "访问点: 5 3"
[1] "已经访问过的点: 6 3"
[1] "墙在这个位置: 5 2"
[1] "墙在这个位置: 4 3"
[1] "已
<details>
<summary>英文:</summary>
I think a few things may have been needed to make this work in R. First, python arrays are 0-indexed, but R is 1 indexed. So your error may be accessing a zero index element in the matrix. Also, you may need to feed back your `maze` matrix as an argument when recursively calling your function.
I adapted your demo based on the python example (6 x 6 matrix). The number '2' represents the finish position here. The function `search` will check if out of bounds separately. To see how the maze is solved, you can uncomment the `print` statement of `maze`.
data <- c(
0, 0, 0, 0, 0, 1,
1, 1, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0,
0, 1, 1, 0, 0, 1,
0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 2
)
maze <- matrix(data, 6, 6, byrow = TRUE)
search <- function(maze, x, y) {
# Check if out of bounds
if (x < 1 | x > length(maze[,1])) return (F)
if (y < 1 | y > length(maze[1,])) return (F)
# Check if at end, already visited, or hitting a wall
if (maze[x, y] == 2){
print(paste('i am at the end: ', x, y))
return(TRUE)
} else if (maze[x, y] == 3){
print(paste('already visited point: ', x, y))
return(FALSE)
} else if (maze[x, y] == 1){
print(paste('wall in point: ', x, y))
return(FALSE)
}
# Set point as visited
maze[x,y] = 3
print(paste('visiting point: ', x, y))
# Optional show maze as solved
# print(maze)
# Check clockwise positions for next move
if (search(maze, x + 1, y)) return (T)
if (search(maze, x, y - 1)) return (T)
if (search(maze, x - 1, y)) return (T)
if (search(maze, x, y + 1)) return (T)
# No other move found
return(F)
}
search(maze, x = 1, y = 1)
**Output**
[1] "visiting point: 1 1"
[1] "wall in point: 2 1"
[1] "visiting point: 1 2"
[1] "wall in point: 2 2"
[1] "already visited point: 1 1"
[1] "visiting point: 1 3"
[1] "visiting point: 2 3"
[1] "visiting point: 3 3"
[1] "wall in point: 4 3"
[1] "visiting point: 3 2"
[1] "wall in point: 4 2"
[1] "visiting point: 3 1"
[1] "visiting point: 4 1"
[1] "visiting point: 5 1"
[1] "visiting point: 6 1"
[1] "already visited point: 5 1"
[1] "wall in point: 6 2"
[1] "already visited point: 4 1"
[1] "wall in point: 5 2"
[1] "already visited point: 3 1"
[1] "wall in point: 4 2"
[1] "wall in point: 2 1"
[1] "already visited point: 3 2"
[1] "wall in point: 2 2"
[1] "already visited point: 3 3"
[1] "already visited point: 2 3"
[1] "wall in point: 3 4"
[1] "wall in point: 2 2"
[1] "already visited point: 1 3"
[1] "visiting point: 2 4"
[1] "wall in point: 3 4"
[1] "already visited point: 2 3"
[1] "visiting point: 1 4"
[1] "already visited point: 2 4"
[1] "already visited point: 1 3"
[1] "visiting point: 1 5"
[1] "visiting point: 2 5"
[1] "visiting point: 3 5"
[1] "visiting point: 4 5"
[1] "wall in point: 5 5"
[1] "visiting point: 4 4"
[1] "visiting point: 5 4"
[1] "visiting point: 6 4"
[1] "visiting point: 6 3"
[1] "wall in point: 6 2"
[1] "visiting point: 5 3"
[1] "already visited point: 6 3"
[1] "wall in point: 5 2"
[1] "wall in point: 4 3"
[1] "already visited point: 5 4"
[1] "already visited point: 6 4"
[1] "already visited point: 5 4"
[1] "visiting point: 6 5"
[1] "already visited point: 6 4"
[1] "wall in point: 5 5"
[1] "i am at the end: 6 6"
[1] TRUE
**Maze Solution**
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 3 3 3 3 3 1
[2,] 1 1 3 3 3 1
[3,] 0 0 0 1 3 0
[4,] 0 1 1 3 3 1
[5,] 0 1 0 3 1 0
[6,] 0 1 0 3 3 2
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论