Предисловие: это дополнительный вопрос к этот.
Я запрограммировал Boggle Game Solver на R (исходный код см. на этой странице github) и нашел его производительность разочаровывает.
Вот как это работает...
# Say we have the following set of letters
bog.letters <- c("t", "e", "n", "s", "d", "a", "i", "o",
"l", "e", "r", "o", "c", "f", "i", "e")
# We get the list of paths (permutations) from a pre-existing list
paths <- paths.by.length[[6]] # 6th element corresponds to 8-element "paths"
dim(paths) # [1] 183472 8
# The following function is the key here,
# mapping the 183,472 combinations to the 16 letters
candidates <- apply(X = paths, MARGIN = 1, FUN = function(x) paste(bog.letters[x], collapse=""))
# The only remaining thing is to intersect the candidate words
# with the actual words from our dictionary
dict.words <- dict.fr$mot[dict.fr$taille == 8]
valid.words <- intersect(candidates, dict.words)
Воспроизводимый пример для слов-кандидатов из 13 букв
bog.letters <- c("t", "e", "n", "s", "d", "a", "i", "o", "l", "e", "r", "o", "c", "f", "i", "e")
n.letters <- 13
paths <- structure(list(V1 = c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), V2 = c(2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2), V3 = c(3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3),
V4 = c(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4), V5 = c(7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7), V6 = c(6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6), V7 = c(5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5), V8 = c(9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
9, 9, 9, 9, 9, 9, 9, 9), V9 = c(10, 10, 10, 10, 10, 10, 10,
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
10, 10, 10, 10, 10, 10, 10, 10), V10 = c(11, 11, 11, 11,
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 13, 13, 13, 13,
13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14), V11 = c(8, 8,
12, 12, 12, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 14, 14,
14, 14, 14, 14, 14, 11, 11, 11, 11, 11, 11, 11, 11), V12 = c(12,
12, 15, 15, 16, 15, 15, 12, 12, 14, 16, 12, 12, 15, 15, 11,
11, 11, 11, 15, 15, 15, 8, 12, 12, 12, 15, 15, 16, 16), V13 = c(15,
16, 14, 16, 15, 12, 16, 8, 16, 13, 12, 8, 15, 12, 14, 8,
12, 15, 16, 11, 12, 16, 12, 8, 15, 16, 12, 16, 12, 15)), .Names = c("V1",
"V2", "V3", "V4", "V5", "V6", "V7", "V8", "V9", "V10", "V11",
"V12", "V13"), row.names = c(NA, 30L), class = "data.frame")
candidates <- apply(X = paths, MARGIN = 1, FUN = function(x) paste(bog.letters[x], collapse=""))
Для такого небольшого списка путей это довольно быстро. Но фактическое количество путей для 13-буквенных слов составляет 2 644 520. Таким образом, поиск всех кандидатов может занять минуту или даже больше. Используя doSNOW, я могу распараллелить поиск, значительно сократив общее время, но у этого есть огромный недостаток: при использовании обычного цикла я могу выйти/прерваться, когда достигну точки, где больше нет слов. найденный. Это неочевидно (невозможно?) для параллельных процессов.
Итак, мой вопрос: можете ли вы придумать лучшую функцию/алгоритм для этой задачи? Некоторые веб-сайты предоставляют решения для игры Boggle за считанные секунды... Либо они сгенерировали все возможные комбинации букв и сохраняют результаты в базе данных (!), в противном случае они явно используют лучший алгоритм (и, возможно, скомпилированный язык) для достижения этих результатов.
Любые идеи?
