Thêm cách tiếp cận khác, có:
board = structure(c("A", "A", "Q", "Q", "Q", "Q", "Q", "Q", "A", "P",
"P", "Q", "Q", "Q", "L", "E", "Q", "Q", "Q", "Q"), .Dim = 4:5, .Dimnames = list(
NULL, NULL))
word = "APPLE"
chúng ta bắt đầu với:
matches = lapply(strsplit(word, NULL)[[1]], function(x) which(x == board, arr.ind = TRUE))
mà là một đơn giản tìm kiếm -probably unavoidable- của chỉ số của "ban" phù hợp với từng chữ cái của từ này. Đó là một "danh sách" có chứa các chỉ số hàng/col như:
#[[1]]
# row col
#[1,] 1 1
#[2,] 2 1
#[3,] 1 3
#
#[[2]]
# row col
#[1,] 2 3
#[2,] 3 3
#
##.....
Có đó, chúng ta cần phải tìm hiểu, dần dần, cho dù một chỉ số trong mỗi phần tử có một người hàng xóm (tức là phải/trái/lên/xuống ô) trong phần tử tiếp theo. Ví dụ.chúng ta cần cái gì đó như:
as.matrix(find_neighbours(matches[[1]], matches[[2]], dim(board)))
# [,1] [,2]
#[1,] FALSE FALSE
#[2,] FALSE FALSE
#[3,] TRUE FALSE
mà chúng ta biết, rằng hàng 3 matches[[1]] là một người hàng xóm của hàng 1 trong tổng số matches[[2]], ví dụ: [1, 3] và [2, 3] là, quả thật vậy, các tế bào lân cận. Chúng tôi cần điều này cho mỗi phần tử liên tiếp trong "trận đấu":
are_neighs = Map(function(x, y) which(find_neighbours(x, y, dim(board)), TRUE),
matches[-length(matches)], matches[-1])
are_neighs
#[[1]]
# [,1] [,2]
#[1,] 3 1
#
#[[2]]
# [,1] [,2]
#[1,] 2 1
#[2,] 1 2
#
#[[3]]
# [,1] [,2]
#[1,] 2 1
#
#[[4]]
# [,1] [,2]
#[1,] 1 1
Bây giờ chúng ta có cặp ("i" với "i + 1") hàng xóm phù hợp chúng ta cần phải hoàn thành chuỗi. Đối với ví dụ này, chúng tôi muốn có một vectơ như c(1, 2, 1, 1) chứa thông tin rằng hàng 1 của are_neighs[[1]] bị xích với hàng 2 của are_neighs[[2]] bị xích với hàng 1 của are_neighs[[3]] bị xích với hàng 1 của are_neighs[[4]]. Đây có mùi giống như một "igraph" vấn đề, nhưng tôi không quá quen thuộc với nó (hy vọng ai đó có một ý tưởng tốt hơn), vì vậy đây là một cách tiếp cận ngây thơ để nhận được rằng chaining:
row_connections = matrix(NA_integer_, nrow(are_neighs[[1]]), length(are_neighs))
row_connections[, 1] = 1:nrow(are_neighs[[1]])
cur = are_neighs[[1]][, 2]
for(i in 1:(length(are_neighs) - 1)) {
im = match(cur, are_neighs[[i + 1]][, 1])
cur = are_neighs[[i + 1]][, 2][im]
row_connections[, i + 1] = im
}
row_connections = row_connections[complete.cases(row_connections), , drop = FALSE]
nào trả về:
row_connections
# [,1] [,2] [,3] [,4]
#[1,] 1 2 1 1
có vector này, bây giờ, chúng ta có thể trích xuất các chuỗi tương ứng từ "are_neighs":
Map(function(x, i) x[i, ], are_neighs, row_connections[1, ])
#[[1]]
#[1] 3 1
#
#[[2]]
#[1] 1 2
#
#[[3]]
#[1] 2 1
#
#[[4]]
#[1] 1 1
mà có thể được sử dụng để trích xuất các chuỗi hàng/col phù hợp của các chỉ số từ "trận đấu":
ans = vector("list", nrow(row_connections))
for(i in 1:nrow(row_connections)) {
connect = Map(function(x, i) x[i, ], are_neighs, row_connections[i, ])
ans[[i]] = do.call(rbind, Map(function(x, i) x[i, ], matches, c(connect[[1]][1], sapply(connect, "[", 2))))
}
ans
#[[1]]
# row col
#[1,] 1 3
#[2,] 2 3
#[3,] 3 3
#[4,] 3 4
#[5,] 4 4
Bao bì nó tất cả trong một hàm (find_neighbours được định nghĩa bên trong):
library(Matrix)
ff = function(word, board)
{
matches = lapply(strsplit(word, NULL)[[1]], function(x) which(x == board, arr.ind = TRUE))
find_neighbours = function(x, y, d)
{
neighbours = function(i, j, d = d)
{
ij = rbind(cbind(i, j + c(-1L, 1L)), cbind(i + c(-1L, 1L), j))
ijr = ij[, 1]; ijc = ij[, 2]
ij = ij[((ijr > 0L) & (ijr <= d[1])) & ((ijc > 0L) & (ijc <= d[2])), ]
ij[, 1] + (ij[, 2] - 1L) * d[1]
}
x.neighs = lapply(1:nrow(x), function(i) neighbours(x[i, 1], x[i, 2], dim(board)))
y = y[, 1] + (y[, 2] - 1L) * d[1]
x.sparse = sparseMatrix(i = unlist(x.neighs),
j = rep(seq_along(x.neighs), lengths(x.neighs)),
x = 1L, dims = c(prod(d), length(x.neighs)))
y.sparse = sparseMatrix(i = y, j = seq_along(y), x = 1L, dims = c(prod(d), length(y)))
ans = crossprod(x.sparse, y.sparse, boolArith = TRUE)
ans
}
are_neighs = Map(function(x, y) which(find_neighbours(x, y, dim(board)), TRUE), matches[-length(matches)], matches[-1])
row_connections = matrix(NA_integer_, nrow(are_neighs[[1]]), length(are_neighs))
row_connections[, 1] = 1:nrow(are_neighs[[1]])
cur = are_neighs[[1]][, 2]
for(i in 1:(length(are_neighs) - 1)) {
im = match(cur, are_neighs[[i + 1]][, 1])
cur = are_neighs[[i + 1]][, 2][im]
row_connections[, i + 1] = im
}
row_connections = row_connections[complete.cases(row_connections), , drop = FALSE]
ans = vector("list", nrow(row_connections))
for(i in 1:nrow(row_connections)) {
connect = Map(function(x, i) x[i, ], are_neighs, row_connections[i, ])
ans[[i]] = do.call(rbind, Map(function(x, i) x[i, ], matches, c(connect[[1]][1], sapply(connect, "[", 2))))
}
ans
}
Chúng tôi có thể thử nó:
ff("APPLE", board)
#[[1]]
# row col
#[1,] 1 3
#[2,] 2 3
#[3,] 3 3
#[4,] 3 4
#[5,] 4 4
Và với nhiều hơn một trận đấu:
ff("AQQP", board)
#[[1]]
# row col
#[1,] 1 1
#[2,] 1 2
#[3,] 2 2
#[4,] 2 3
#
#[[2]]
# row col
#[1,] 1 3
#[2,] 1 2
#[3,] 2 2
#[4,] 2 3
#
#[[3]]
# row col
#[1,] 1 3
#[2,] 1 4
#[3,] 2 4
#[4,] 2 3
Mặc dù, nó linh hoạt trong việc trả về nhiều kết quả phù hợp, nó không trả về tất cả các kết quả phù hợp và tóm lại, đó là vì việc sử dụng match khi xây dựng chuỗi các hàng xóm - một tìm kiếm tuyến tính có thể được sử dụng thay thế. phức tạp.
Chào mừng bạn đến với StackOverflow. Hãy xem các mẹo này về cách tạo ra [ví dụ tối thiểu, đầy đủ và có thể xác minh được] (http://stackoverflow.com/help/mcve), cũng như bài đăng này trên [tạo một ví dụ tuyệt vời trong R] (http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example).Có lẽ những lời khuyên sau đây về [hỏi một câu hỏi hay] (http://stackoverflow.com/help/how-to-ask) cũng có thể đáng đọc. – lmo
không bao giờ nghĩ đến việc viết mã cho trò chơi trong R! :) –