Dodanie kolejnego podejścia, mający:
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"
zaczynamy:
matches = lapply(strsplit(word, NULL)[[1]], function(x) which(x == board, arr.ind = TRUE))
który jest prosty -prawdopodobnie unavoidable- poszukiwanie wskaźników „pokładzie” pasujących każdą literę słowa. Jest to „lista” zawierająca indeksy wiersz/COL jak:
#[[1]]
# row col
#[1,] 1 1
#[2,] 2 1
#[3,] 1 3
#
#[[2]]
# row col
#[1,] 2 3
#[2,] 3 3
#
##.....
uwzględniając, że musimy dowiedzieć się, stopniowo, czy indeks w każdym elemencie ma sąsiada (czyli prawo/lewo/góra/dół komórka) w następnym elemencie. Na przykład.musimy coś takiego:
as.matrix(find_neighbours(matches[[1]], matches[[2]], dim(board)))
# [,1] [,2]
#[1,] FALSE FALSE
#[2,] FALSE FALSE
#[3,] TRUE FALSE
który informuje nas, że rząd 3 matches[[1]]
jest sąsiadem rzędu 1 matches[[2]]
, tj [1, 3]
i [2, 3]
są rzeczywiście sąsiednich komórek. Musimy to dla każdego kolejnego elementu „pasuje”:
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
Teraz mamy parami („I” z „i + 1”) sąsiad mecze musimy zakończyć łańcuch. W tym przykładzie chcielibyśmy mieć wektor taki jak c(1, 2, 1, 1)
, który zawiera informację, że wiersz 1 are_neighs[[1]]
jest połączony łańcuchem z wierszem 2 z are_neighs[[2]]
, który jest połączony łańcuchem 1 z are_neighs[[3]]
, który jest połączony łańcuchem 1 z are_neighs[[4]]
. To pachnie jak „igraph” problem, ale nie jestem tak obeznany z nim (mam nadzieję, że ktoś ma lepszy pomysł), więc o to naiwne podejście, aby ta łańcuchowym:
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]
która zwraca:
row_connections
# [,1] [,2] [,3] [,4]
#[1,] 1 2 1 1
Mając ten wektor teraz można wyodrębnić odpowiednie łańcucha z „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
, które można stosować w celu wyodrębnienia odpowiedniego łańcucha wiersz/col o indeksach od „pasuje”:
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
Zawijanie to wszystko w funkcji (find_neighbours
jest zdefiniowana wewnątrz):
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
}
Możemy spróbować:
ff("APPLE", board)
#[[1]]
# row col
#[1,] 1 3
#[2,] 2 3
#[3,] 3 3
#[4,] 3 4
#[5,] 4 4
A z więcej niż jednego meczy:
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
Chociaż jest elastyczny zwracając wiele dopasowań, nie zwraca wszystkich możliwych dopasowań i, w dużym skrócie, jest to spowodowane użyciem match
podczas budowania łańcucha sąsiadów - zamiast tego można użyć wyszukiwania liniowego, ale w chwili obecnej - dodaje znaczący kod złożoność.
Witamy w StackOverflow. Zapoznaj się z tymi wskazówkami, jak utworzyć [minimalny, pełny i weryfikowalny przykład] (http://stackoverflow.com/help/mcve), a także ten post w [tworzeniu świetnego przykładu w R] (http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example).Być może poniższe wskazówki dotyczące [zadawania dobrego pytania] (http://stackoverflow.com/help/how-to-ask) również mogą być warte przeczytania. – lmo
Nigdy nie myślałem o pisaniu kodów do gier w R! :) –