如何使用递归生成器为算法步骤制作动画
How to animate algorithm steps using a recursive generator
我使用递归辅助函数构建了一个 boggle 求解器算法。
它使用 trie 数据结构来快速检查现有前缀是否在字典中有任何单词。
我想为算法的每一步制作动画，以显示如何在 HTML table 中找到每个单词，但无法使其正常工作。
算法如下：
const trie = '' // instantiated trie class (omitted for brevity)
const list = '' // imported dictionary (omitted for brevity)
// inputs are all the cells inside the table that hold the letters
const inputs = document.getElementsByClassName("input");
// size is the size of the table (ex. 4x4, 8x8, etc...)
const size = document.getElementById("size").valueAsNumber;
// populating the trie with every word in the dictionary
for (let item of list) {
trie.insert(item);
}
const movements = (i, j) => [
{ row: i, column: j + 1, move: "RIGHT" },
{ row: i + 1, column: j + 1, move: "BOTTOM_RIGHT" },
{ row: i + 1, column: j, move: "BOTTOM" },
{ row: i + 1, column: j - 1, move: "BOTTOM_LEFT" },
{ row: i, column: j - 1, move: "LEFT" },
{ row: i - 1, column: j - 1, move: "TOP_LEFT" },
{ row: i - 1, column: j, move: "TOP" },
{ row: i - 1, column: j + 1, move: "TOP_RIGHT" },
];
// takes a 2D array as input (ex. [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'h']])
export const findWords = (matrix) => {
const words = [];
const iterate = (i, j, word, visited) => {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
if (trie.find(word).length) {
if (trie.contains(word)) {
words.push(word);
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
iterate(row, column, word, { ...visited });
}
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
iterate(i, j, "", {});
}
}
return words;
};
可在此处找到可用的应用程序示例：https://jsfiddle.net/Msiric/24x765bn/
下面是使用生成器时的代码：
export const findWords = (matrix) => {
const words = [];
const iterate = function* (i, j, word, visited, color) {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
// highlighting the current cell here
inputs[j + size * i].classList.add(color);
if (trie.find(word).length) {
if (trie.contains(word)) {
words.push(word);
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
yield* iterate(
row,
column,
word,
{ ...visited },
column % 2 === 0 ? "blue" : "red"
);
// the cell should be unhighlighted once this cell is done
inputs[j + size * i].classList.remove(color);
}
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red").next();
}
}
return words;
};
这样做只会显示算法的最终状态，这不是我想要的。
我想显示每个单元格被突出显示或未突出显示，因为每个步骤都在执行并且每个单词都在被发现。
我还尝试包括 setTimeout 函数来延迟辅助函数的执行，但这也没有用。
它只是导致随机闪烁，因为单元格 highlighted/unhighlighted 乱序。
感谢任何帮助
在 javascript 中，您无法在同步函数执行期间渲染某些内容。任何尝试进行 DOM 更改的代码只会对这些更改进行排队，在运行时执行同步函数时无法绘制这些更改。
因此，你必须让你的函数异步，就像这个例子
https://jsfiddle.net/ep783cgw/2/
虽然我不确定你想如何形象化它，但我已经制作了一个 renderState 函数，你可以根据自己的喜好定义它。
// modify it as per your liking
const renderState = (anim,i,j,move) => {
const {row,column} = move
anim.innerText = `${i}_${j}-${row}_${column}-${move.move}`
}
// show noticable delay in animation
const delay = (ms) => new Promise(res => setTimeout(res, ms))
// make findWords async
const findWords = async (matrix) => {
const words = [];
const anim = document.querySelector('#result');
const iterate = async (i, j, word, visited) => {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
if (trie.find(word).length) {
if (trie.contains(word)) {
words.push(word);
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
// render the DOM
renderState(anim,i,j, move);
// wait for 200ms using await. Browser will draw the DOM in this time
await delay(200);
// iterate again using await
await iterate(row, column, word, { ...visited });
}
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
await iterate(i, j, "", {});
}
}
return words;
};
// make handleSubmit async
const handleSubmit = async (e) => {
e.preventDefault();
const inputs = document.querySelectorAll(".input");
const result = document.getElementById("result");
const size = document.getElementById("size").valueAsNumber;
const matrix = [];
for (let i = 0; i < size; i++) {
const row = [];
for (let j = 0; j < size; j++) {
row.push(inputs[j + size * i].value.toLowerCase());
}
matrix.push(row);
}
// use await to get output of findWords
const words = await findWords(matrix);
result.innerHTML = words;
};
要了解更多信息，请访问这些链接
- Event Loop Description | MDN
- A Whosebug answer on similar topic
编辑：我刚刚注意到您没有正确使用生成器函数。
为了更好地利用生成器函数，您应该创建一个生成器实例并对其调用 next() 以生成所有值。但是在你的代码中，你写了
iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red").next();
在每次 .next() 调用之前创建新实例的位置。因此，iterate 生成器不会生成所有值。
因此，上面的行应该是
const instance = iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red")
while(!instance.next().done)
您可以阅读生成器函数的示例here
代码太多了，我现在无法接受。但一般建议是您不要尝试将算法与显示混合使用。
在算法中，跟踪您测试的动作及其结果。在这里完全不用担心如何显示它。
完成后，进行测试，一次一个，突出显示网格。在这里使用 setInterval 或链式 setTimeout 很容易，因为您只是迭代尝试列表。每次你只需要取消设置当前突出显示，然后为路径上的单元格设置它，可能对路径的第一个和最后一个单元格有不同的显示，当你点击一个合法的单词时可能会有不同的东西（动画添加加入名单？）
让我们假设我们有一个部分看起来像这样的网格：
\ x
y \ 0 1 2 3
+---+---+---+---+
0 | · | · | O | · |
+---+---+---+---+
1 | · | O | F | · |
+---+---+---+---+
2 | Z | L | · | H |
+---+---+---+---+
3 | · | I | S | · |
+---+---+---+---+
也许每个测试都会产生类似
的结果
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'}],
stuck: false,
isWord: false
}
（假设“FOO”不在您的字典中。）
然后，因为你没有被卡住，你最终添加 {x: 1, y: 2, c: 'L'}，你将有 isWord: true ("FOOL") 和 stuck: false（因为 trie 说那里是 F-O-O-L).
下的节点
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'},
{x: 1, y: 2, c: 'L'}],
stuck: false,
isWord: true
}
但是当你尝试添加 {x: 0, y: 2, c: 'Z'} 时，trie 告诉你没有单词开头 F-O-O-Z，你可以记录它不是单词，你被卡住了。
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'},
{x: 0, y: 2, c: 'Z'}],
stuck: true,
isWord: false
}
最终，您将尝试这个七个字母的单词：
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, c: 'O'},
{x: 1, y: 2, c: 'L'}, {x: 1, y: 3, c: 'I'}, {x: 2, y: 3, c: 'S'},
{x: 3, y: 2, c: 'H'}],
stuck: false,
isWord: true
}
请注意，这些可能是您的算法的唯一输出，因为从这些测试生成单词列表很简单：
.filter (t => t .isWord)
.map (({path}) => path .map (n => n .c) .join (''))
const uniqueWords = [... new Set (words)]
主要更新
自从我发布以上内容以来，我一直在断断续续地思考这个问题。这是一种尝试以接近这种方式的方式进行的尝试。 （如果您使用代码段的“全屏”选项，它可能看起来会更好。）：
// *************************
// Main function
// *************************
const run = () =>
Promise.resolve (showLoading())
.then (getDictionary)
.then (trie)
.then (buildPuzzle)
.then (tap (displayPuzzle))
.then (solvePuzzle)
// .then (tap (console .log))
.then (displaySolution)
.then (showWordCount)
// *************************
// Utility functions
// *************************
const tap = (fn) => (x) => (fn (x), x)
const range = (lo, hi) => [... Array (hi - lo)] .map ((_, i) => i + lo)
const last = (xs) => xs [xs .length - 1]
const titleCase = ([c, ...cs]) => c .toUpperCase() + cs.join('')
const showLoading = () => // not really a utility function, but no place better
document .getElementById ('word') .textContent ='Loading ...'
// *************************
// Dictionary handling -trie
// *************************
const getDictionary = () =>
//fetch ('http://fourwindssoft.com/scott/words/')
fetch ('https://norvig.com/ngrams/enable1.txt')
.then (s => s .text ())
.then (s => s .split ('\n'))
const trie = (words) =>
words .reduce (insertWord, {})
const insertWord = (trie, [c, ...cs]) =>
c ? {...trie, [c]: insertWord (trie [c] || {}, cs)} : {...trie, $: 1}
const find = (trie) => ([c = '', ...cs]) =>
trie && (cs .length == 0 ? trie [c] : find (trie[c]) (cs))
const contains = (trie) => (word) =>
'$' in (find (trie) (word) || {})
// *************************
// Board creation
// *************************
const buildPuzzle = (trie) => ({trie, letters: roll (dice)})
const dice =
'a|a|c|i|o|t, a|b|i|l|t|y, a|b|j|m|o|qu, a|c|d|e|m|p, a|c|e|l|r|s, a|d|e|n|v|z, a|h|m|o|r|s, b|i|f|o|r|x, d|e|n|o|s|w, d|k|n|o|t|u, e|e|f|h|i|y, e|g|k|l|u|y, e|g|i|n|t|v, e|h|i|n|p|s, e|l|p|s|t|u, g|i|l|r|u|w'
.split (', ') .map (d => d.split ('|'))
const roll = (dice) => shuffle (dice) .map (pickOne)
const shuffle = (xs, i = Math .floor (Math .random () * xs .length)) =>
xs .length == 0
? []
: [xs[i], ... shuffle ([... xs .slice (0, i), ... xs .slice (i + 1)])]
const pickOne = (xs) => xs [Math .floor (Math .random () * xs .length)]
// *************************
// Initial display
// *************************
const displayPuzzle = ({letters}) =>
letters .forEach ((l, i) => document .getElementById (`c${i}`) .textContent = titleCase (l))
// *************************
// Solving puzzle
// *************************
const solvePuzzle = ({trie, letters}) =>
({letters, tests: search (letters, neighbors, trie)})
// see https://link.fourwindssoft.com/30 for derivation or other grid sizes
const neighbors =
[[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]]
const search = (letters, neighbors, words, path = []) =>
path .length == 0
? letters .flatMap ((l, i) => search (letters, neighbors, find (words) (l) || {}, [i]))
: [
{path, isWord : words ? '$' in words && path.length > 2 : false, stuck: !words},
... neighbors [last (path)]
.filter ((i) => ! path .includes (i))
.flatMap ((i) => words
? search (letters, neighbors, find (words) (letters [i]), [...path, i])
: []
)
]
// *************************
// Display algorithm process
// *************************
const displaySolution = ({letters, tests}) =>
showPaths (letters) (tests)
const showPaths = (letters) => ([t, ...ts]) =>
t == undefined
? Promise.resolve(true)
: showPath (letters) (t) .then (() => showPaths (letters) (ts))
const showPath = (letters) => (t) => {
document .getElementById ('word') .textContent = t.path .map (n => letters [n]) .join('')
return highlightPath (50) (t.path)
.then (() => {
if (t.isWord) {
document.getElementById ('board') .classList .add ('match')
} else if (t.stuck) {
document.getElementById ('board') .classList .add ('stuck')
}
})
.then (delay (t.isWord ? 1500: 500) (clearHighlighting))
.then (handleWord (t, letters))
.then (() => {
const classList = document.getElementById ('board') .classList
classList .remove ('stuck')
classList .remove ('match')
})
}
const highlightPath = (t) => (path) => seq (
path .map ((n) => delay (t) (highlightCell (n)))
)
const seq = (promGens) =>
promGens .reduce ((c, n) => c .then (n), Promise.resolve(true))
const delay = (time) => (thunk) => () =>
new Promise ((res) => {setTimeout (() => {thunk(); res()}, time)})
const highlightCell = (n) => () =>
document .getElementById (`c${n}`) .classList .add ('highlighted')
const clearHighlighting = () =>
document .querySelectorAll ('#board td') .forEach ((node) => node .classList .remove ('highlighted'))
const handleWord = (t, letters) => {
if (t.isWord) {
const text = t.path .map (p => letters [p]) .join('')
const match = [...document .querySelectorAll ('#found li')] .find (node => node .textContent == text)
if (match) {
match .scrollIntoView ()
match .classList .add ('item-used')
setTimeout (() => match .classList .remove ('item-used'), 6000) // uggh, 6000 should match css animation!
} else {
const li = document .createElement ('li')
li. appendChild (document .createTextNode(text))
document .getElementById('found') .appendChild (li)
li .scrollIntoView ()
li .classList .add ('item-highlight')
setTimeout (() => li .classList .remove ('item-highlight'), 6000)
}
}
return t
}
const showWordCount = () => // ugly to use the DOM for this info, but too much refactoring to fix
document .getElementById ('word') .textContent = `${document.querySelectorAll('#found li') .length} words`
// *************************
// Start everything
// *************************
run ()
table {background: #999; padding: .25em; border: 1px solid black;}
td {border: 1px solid black; padding: .25em; background: white; text-align: center; width: 1em; height: 1em;}
td.highlighted {background: #ccc;}
table.stuck, table.stuck td.highlighted {background: #f99;}
table.match, table.match td.highlighted {background: #9f9;}
pre {width: 10em; text-align: center; color: #666;}
code {font-size: 2em;}
.container {display: flex; flex-direction: row;}
#results {height: 10em; width: 8em; margin-left: .5em; padding: .5em; background: #ddd; overflow: auto;}
#results ul {list-style: none; padding: 0; margin: 0em;}
@keyframes fadenew {from {background: #6f6} to {background: transparent;}}
li.item-highlight {animation: fadenew 6s;}
@keyframes fadeused {from {background: #f66} to {background: transparent;}}
li.item-used {animation: fadeused 6s;}
<div class="container">
<div id="demo">
<table id="board">
<tr><td id="c0">?</td><td id="c1">?</td><td id="c2">?</td><td id="c3">?</td></tr>
<tr><td id="c4">?</td><td id="c5">?</td><td id="c6">?</td><td id="c7">?</td></tr>
<tr><td id="c8">?</td><td id="c9">?</td><td id="c10">?</td><td id="c11">?</td></tr>
<tr><td id="c12">?</td><td id="c13">?</td><td id="c14">?</td><td id="c15">?</td></tr>
</table>
<pre><code id="word"></code></pre>
</div>
<div id="results">
<ul id ="found"></ul>
</div>
</div>
我确实对上面的建议稍作修改。路径只是整数列表，索引到作为网格的平面字母数组。每个索引的邻居列表是硬编码的，尽管最初，当摆弄不同的网格大小时，我 calculated them.
代码加载字典，这里是 Peter Norvig 的 enable1 list, turns it into a trie, with the fairly simple trie function. We randomly create a puzzle, using simulated dice，它应该与原始的 Boggle 字典非常匹配，显示它（通过整数索引到单元格 ID 的简单映射），并使用相当简单的 search 函数可以在其中找到我们词典中至少包含三个字母的所有单词。这将为我们提供一组如下所示的结果：
[
//...
{path: [9, 5, 6, 3], stuck: false, isWord: true},
{path: [9, 5, 6, 3, 2], stuck: true, isWord: false},
//...
]
对网格，
['L',' T',' P',' T',' O',' E',' N',' Y',' U',' T',' F',' O',' S',' H',' K',' I']
代表棋盘
+---+---+---+---+
| L | T | P | T |
+---+---+---+---+
| O | E | N | Y |
+---+---+---+---+
| U | T | F | O |
+---+---+---+---+
| S | H | K | I |
+---+---+---+---+
所以[9, 5, 6, 3]代表"TENT"而[9, 5, 6, 3, 2]代表"TENTP".
这里一个有趣的设计决定是在求解器中而不是在字典中将单词限制为三个或更多字母。它的效率稍低，但我认为可视化尝试一个和两个字母单词的算法更清晰。
现在我们有了这个表示，我们可以通过突出显示我们尝试过的每个测试用例的路径来演示它。请注意，当 trie 不包含最新字母时搜索器停止，因此我们没有指数数量的搜索路径。我假设这里的所有其他算法都做类似的事情。显示中没有特别有趣的代码。它只是一次一个地突出显示通过网格的路径，简要说明它是否是我们字典中的一个词，如果是一个，在将它添加到列表之前检查我们是否已经找到它找到的话。所有这些都是通过简单的 DOM 操作完成的。唯一有点棘手的是动画的时间安排。我们希望通过我们的文字快速移动，但希望文字的动画足够快以显示实际路径。我不确定我在这里取得了正确的平衡，但这并不可怕。
对此的一个可能的扩展涉及显示我们所显示的试验的进度条，或者使其成为可以停止、重新启动和逐步通过的东西。另一个非常有用的方法是用一条穿过所用方块的线来显示路径，而不仅仅是高亮颜色。但那些是另一天。
很多代码对于网格大小都是通用的，使用那个 getNeighbors 函数，我们可以很容易地把它的其余部分变成这样，除了一件事。我们在这里掷的骰子是为了模拟实际的 Boggle 骰子，而不是简单的随机选择。我不清楚如何为更大的网格更改它。
这是一件有趣的小事。虽然我希望它能对 OP 有所帮助，但我很高兴这样做只是为了我自己的娱乐。
这是我想出的：https://jsfiddle.net/Msiric/jwag86o2/3/
该解决方案的部分灵感来自 Scott 的建议，但由于我无法让它工作，我找到了另一种方法来指定动画 运行.[=13 时应执行的每个步骤=]
算法的主要变化：
const movements = (i, j) => [
{ row: i, column: j + 1, move: "RIGHT" },
{ row: i + 1, column: j + 1, move: "BOTTOM_RIGHT" },
{ row: i + 1, column: j, move: "BOTTOM" },
{ row: i + 1, column: j - 1, move: "BOTTOM_LEFT" },
{ row: i, column: j - 1, move: "LEFT" },
{ row: i - 1, column: j - 1, move: "TOP_LEFT" },
{ row: i - 1, column: j, move: "TOP" },
{ row: i - 1, column: j + 1, move: "TOP_RIGHT" },
];
const addStep = (() => {
let counter = 1;
return (i, j, matrix, isWord, action, steps) => {
steps.push({
x: i,
y: j,
c: matrix[i][j],
isWord,
action,
counter,
});
action === "remove" ? counter-- : counter++;
};
})();
const findWords = (matrix) => {
const words = [];
const map = {};
const steps = [];
const iterate = (i, j, word, visited) => {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
addStep(i, j, matrix, false, "add", steps);
if (trie.find(word).length) {
if (trie.contains(word) && !map[word]) {
words.push(word);
map[word] = true;
steps[steps.length - 1] = {
...steps[steps.length - 1],
isWord: true,
};
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
iterate(row, column, word, { ...visited });
}
addStep(i, j, matrix, false, "remove", steps);
} else {
addStep(i, j, matrix, false, "remove", steps);
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
iterate(i, j, "", {});
}
}
return { words, steps };
};
这是可视化函数：
const visualizeSteps = async (steps, inputs, spans, size) => {
for (let step of steps) {
const { x, y } = step;
const selection = y + size * x;
await delay(0);
if (spans[selection].innerHTML === "") {
spans[selection].innerHTML = step.counter;
}
inputs[selection].classList.add("highlight");
if (step.isWord) {
const highlights = document.getElementsByClassName("highlight");
for (let highlight of highlights) {
highlight.classList.add("success");
}
await delay(500);
for (let highlight of highlights) {
highlight.classList.remove("success");
}
} else {
if (step.action === "remove") {
await delay(0);
inputs[selection].classList.remove("highlight");
spans[selection].innerHTML = "";
}
}
}
};
我使用递归辅助函数构建了一个 boggle 求解器算法。 它使用 trie 数据结构来快速检查现有前缀是否在字典中有任何单词。 我想为算法的每一步制作动画，以显示如何在 HTML table 中找到每个单词，但无法使其正常工作。
算法如下：
const trie = '' // instantiated trie class (omitted for brevity)
const list = '' // imported dictionary (omitted for brevity)
// inputs are all the cells inside the table that hold the letters
const inputs = document.getElementsByClassName("input");
// size is the size of the table (ex. 4x4, 8x8, etc...)
const size = document.getElementById("size").valueAsNumber;
// populating the trie with every word in the dictionary
for (let item of list) {
trie.insert(item);
}
const movements = (i, j) => [
{ row: i, column: j + 1, move: "RIGHT" },
{ row: i + 1, column: j + 1, move: "BOTTOM_RIGHT" },
{ row: i + 1, column: j, move: "BOTTOM" },
{ row: i + 1, column: j - 1, move: "BOTTOM_LEFT" },
{ row: i, column: j - 1, move: "LEFT" },
{ row: i - 1, column: j - 1, move: "TOP_LEFT" },
{ row: i - 1, column: j, move: "TOP" },
{ row: i - 1, column: j + 1, move: "TOP_RIGHT" },
];
// takes a 2D array as input (ex. [['a', 'b', 'c', 'd'], ['e', 'f', 'g', 'h']])
export const findWords = (matrix) => {
const words = [];
const iterate = (i, j, word, visited) => {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
if (trie.find(word).length) {
if (trie.contains(word)) {
words.push(word);
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
iterate(row, column, word, { ...visited });
}
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
iterate(i, j, "", {});
}
}
return words;
};
可在此处找到可用的应用程序示例：https://jsfiddle.net/Msiric/24x765bn/
下面是使用生成器时的代码：
export const findWords = (matrix) => {
const words = [];
const iterate = function* (i, j, word, visited, color) {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
// highlighting the current cell here
inputs[j + size * i].classList.add(color);
if (trie.find(word).length) {
if (trie.contains(word)) {
words.push(word);
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
yield* iterate(
row,
column,
word,
{ ...visited },
column % 2 === 0 ? "blue" : "red"
);
// the cell should be unhighlighted once this cell is done
inputs[j + size * i].classList.remove(color);
}
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red").next();
}
}
return words;
};
这样做只会显示算法的最终状态，这不是我想要的。 我想显示每个单元格被突出显示或未突出显示，因为每个步骤都在执行并且每个单词都在被发现。 我还尝试包括 setTimeout 函数来延迟辅助函数的执行，但这也没有用。 它只是导致随机闪烁，因为单元格 highlighted/unhighlighted 乱序。
感谢任何帮助
在 javascript 中，您无法在同步函数执行期间渲染某些内容。任何尝试进行 DOM 更改的代码只会对这些更改进行排队，在运行时执行同步函数时无法绘制这些更改。
因此，你必须让你的函数异步，就像这个例子 https://jsfiddle.net/ep783cgw/2/
虽然我不确定你想如何形象化它，但我已经制作了一个 renderState 函数，你可以根据自己的喜好定义它。
// modify it as per your liking
const renderState = (anim,i,j,move) => {
const {row,column} = move
anim.innerText = `${i}_${j}-${row}_${column}-${move.move}`
}
// show noticable delay in animation
const delay = (ms) => new Promise(res => setTimeout(res, ms))
// make findWords async
const findWords = async (matrix) => {
const words = [];
const anim = document.querySelector('#result');
const iterate = async (i, j, word, visited) => {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
if (trie.find(word).length) {
if (trie.contains(word)) {
words.push(word);
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
// render the DOM
renderState(anim,i,j, move);
// wait for 200ms using await. Browser will draw the DOM in this time
await delay(200);
// iterate again using await
await iterate(row, column, word, { ...visited });
}
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
await iterate(i, j, "", {});
}
}
return words;
};
// make handleSubmit async
const handleSubmit = async (e) => {
e.preventDefault();
const inputs = document.querySelectorAll(".input");
const result = document.getElementById("result");
const size = document.getElementById("size").valueAsNumber;
const matrix = [];
for (let i = 0; i < size; i++) {
const row = [];
for (let j = 0; j < size; j++) {
row.push(inputs[j + size * i].value.toLowerCase());
}
matrix.push(row);
}
// use await to get output of findWords
const words = await findWords(matrix);
result.innerHTML = words;
};
要了解更多信息，请访问这些链接
- Event Loop Description | MDN
- A Whosebug answer on similar topic
编辑：我刚刚注意到您没有正确使用生成器函数。
为了更好地利用生成器函数，您应该创建一个生成器实例并对其调用 next() 以生成所有值。但是在你的代码中，你写了
iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red").next();
在每次 .next() 调用之前创建新实例的位置。因此，iterate 生成器不会生成所有值。
因此，上面的行应该是
const instance = iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red")
while(!instance.next().done)
您可以阅读生成器函数的示例here
代码太多了，我现在无法接受。但一般建议是您不要尝试将算法与显示混合使用。
在算法中，跟踪您测试的动作及其结果。在这里完全不用担心如何显示它。
完成后，进行测试，一次一个，突出显示网格。在这里使用 setInterval 或链式 setTimeout 很容易，因为您只是迭代尝试列表。每次你只需要取消设置当前突出显示，然后为路径上的单元格设置它，可能对路径的第一个和最后一个单元格有不同的显示，当你点击一个合法的单词时可能会有不同的东西（动画添加加入名单？）
让我们假设我们有一个部分看起来像这样的网格：
\ x
y \ 0 1 2 3
+---+---+---+---+
0 | · | · | O | · |
+---+---+---+---+
1 | · | O | F | · |
+---+---+---+---+
2 | Z | L | · | H |
+---+---+---+---+
3 | · | I | S | · |
+---+---+---+---+
也许每个测试都会产生类似
的结果{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'}],
stuck: false,
isWord: false
}
（假设“FOO”不在您的字典中。）
然后，因为你没有被卡住，你最终添加 {x: 1, y: 2, c: 'L'}，你将有 isWord: true ("FOOL") 和 stuck: false（因为 trie 说那里是 F-O-O-L).
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'},
{x: 1, y: 2, c: 'L'}],
stuck: false,
isWord: true
}
但是当你尝试添加 {x: 0, y: 2, c: 'Z'} 时，trie 告诉你没有单词开头 F-O-O-Z，你可以记录它不是单词，你被卡住了。
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'},
{x: 0, y: 2, c: 'Z'}],
stuck: true,
isWord: false
}
最终，您将尝试这个七个字母的单词：
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, c: 'O'},
{x: 1, y: 2, c: 'L'}, {x: 1, y: 3, c: 'I'}, {x: 2, y: 3, c: 'S'},
{x: 3, y: 2, c: 'H'}],
stuck: false,
isWord: true
}
请注意，这些可能是您的算法的唯一输出，因为从这些测试生成单词列表很简单：
.filter (t => t .isWord)
.map (({path}) => path .map (n => n .c) .join (''))
const uniqueWords = [... new Set (words)]
主要更新
自从我发布以上内容以来，我一直在断断续续地思考这个问题。这是一种尝试以接近这种方式的方式进行的尝试。 （如果您使用代码段的“全屏”选项，它可能看起来会更好。）：
// *************************
// Main function
// *************************
const run = () =>
Promise.resolve (showLoading())
.then (getDictionary)
.then (trie)
.then (buildPuzzle)
.then (tap (displayPuzzle))
.then (solvePuzzle)
// .then (tap (console .log))
.then (displaySolution)
.then (showWordCount)
// *************************
// Utility functions
// *************************
const tap = (fn) => (x) => (fn (x), x)
const range = (lo, hi) => [... Array (hi - lo)] .map ((_, i) => i + lo)
const last = (xs) => xs [xs .length - 1]
const titleCase = ([c, ...cs]) => c .toUpperCase() + cs.join('')
const showLoading = () => // not really a utility function, but no place better
document .getElementById ('word') .textContent ='Loading ...'
// *************************
// Dictionary handling -trie
// *************************
const getDictionary = () =>
//fetch ('http://fourwindssoft.com/scott/words/')
fetch ('https://norvig.com/ngrams/enable1.txt')
.then (s => s .text ())
.then (s => s .split ('\n'))
const trie = (words) =>
words .reduce (insertWord, {})
const insertWord = (trie, [c, ...cs]) =>
c ? {...trie, [c]: insertWord (trie [c] || {}, cs)} : {...trie, $: 1}
const find = (trie) => ([c = '', ...cs]) =>
trie && (cs .length == 0 ? trie [c] : find (trie[c]) (cs))
const contains = (trie) => (word) =>
'$' in (find (trie) (word) || {})
// *************************
// Board creation
// *************************
const buildPuzzle = (trie) => ({trie, letters: roll (dice)})
const dice =
'a|a|c|i|o|t, a|b|i|l|t|y, a|b|j|m|o|qu, a|c|d|e|m|p, a|c|e|l|r|s, a|d|e|n|v|z, a|h|m|o|r|s, b|i|f|o|r|x, d|e|n|o|s|w, d|k|n|o|t|u, e|e|f|h|i|y, e|g|k|l|u|y, e|g|i|n|t|v, e|h|i|n|p|s, e|l|p|s|t|u, g|i|l|r|u|w'
.split (', ') .map (d => d.split ('|'))
const roll = (dice) => shuffle (dice) .map (pickOne)
const shuffle = (xs, i = Math .floor (Math .random () * xs .length)) =>
xs .length == 0
? []
: [xs[i], ... shuffle ([... xs .slice (0, i), ... xs .slice (i + 1)])]
const pickOne = (xs) => xs [Math .floor (Math .random () * xs .length)]
// *************************
// Initial display
// *************************
const displayPuzzle = ({letters}) =>
letters .forEach ((l, i) => document .getElementById (`c${i}`) .textContent = titleCase (l))
// *************************
// Solving puzzle
// *************************
const solvePuzzle = ({trie, letters}) =>
({letters, tests: search (letters, neighbors, trie)})
// see https://link.fourwindssoft.com/30 for derivation or other grid sizes
const neighbors =
[[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]]
const search = (letters, neighbors, words, path = []) =>
path .length == 0
? letters .flatMap ((l, i) => search (letters, neighbors, find (words) (l) || {}, [i]))
: [
{path, isWord : words ? '$' in words && path.length > 2 : false, stuck: !words},
... neighbors [last (path)]
.filter ((i) => ! path .includes (i))
.flatMap ((i) => words
? search (letters, neighbors, find (words) (letters [i]), [...path, i])
: []
)
]
// *************************
// Display algorithm process
// *************************
const displaySolution = ({letters, tests}) =>
showPaths (letters) (tests)
const showPaths = (letters) => ([t, ...ts]) =>
t == undefined
? Promise.resolve(true)
: showPath (letters) (t) .then (() => showPaths (letters) (ts))
const showPath = (letters) => (t) => {
document .getElementById ('word') .textContent = t.path .map (n => letters [n]) .join('')
return highlightPath (50) (t.path)
.then (() => {
if (t.isWord) {
document.getElementById ('board') .classList .add ('match')
} else if (t.stuck) {
document.getElementById ('board') .classList .add ('stuck')
}
})
.then (delay (t.isWord ? 1500: 500) (clearHighlighting))
.then (handleWord (t, letters))
.then (() => {
const classList = document.getElementById ('board') .classList
classList .remove ('stuck')
classList .remove ('match')
})
}
const highlightPath = (t) => (path) => seq (
path .map ((n) => delay (t) (highlightCell (n)))
)
const seq = (promGens) =>
promGens .reduce ((c, n) => c .then (n), Promise.resolve(true))
const delay = (time) => (thunk) => () =>
new Promise ((res) => {setTimeout (() => {thunk(); res()}, time)})
const highlightCell = (n) => () =>
document .getElementById (`c${n}`) .classList .add ('highlighted')
const clearHighlighting = () =>
document .querySelectorAll ('#board td') .forEach ((node) => node .classList .remove ('highlighted'))
const handleWord = (t, letters) => {
if (t.isWord) {
const text = t.path .map (p => letters [p]) .join('')
const match = [...document .querySelectorAll ('#found li')] .find (node => node .textContent == text)
if (match) {
match .scrollIntoView ()
match .classList .add ('item-used')
setTimeout (() => match .classList .remove ('item-used'), 6000) // uggh, 6000 should match css animation!
} else {
const li = document .createElement ('li')
li. appendChild (document .createTextNode(text))
document .getElementById('found') .appendChild (li)
li .scrollIntoView ()
li .classList .add ('item-highlight')
setTimeout (() => li .classList .remove ('item-highlight'), 6000)
}
}
return t
}
const showWordCount = () => // ugly to use the DOM for this info, but too much refactoring to fix
document .getElementById ('word') .textContent = `${document.querySelectorAll('#found li') .length} words`
// *************************
// Start everything
// *************************
run ()
table {background: #999; padding: .25em; border: 1px solid black;}
td {border: 1px solid black; padding: .25em; background: white; text-align: center; width: 1em; height: 1em;}
td.highlighted {background: #ccc;}
table.stuck, table.stuck td.highlighted {background: #f99;}
table.match, table.match td.highlighted {background: #9f9;}
pre {width: 10em; text-align: center; color: #666;}
code {font-size: 2em;}
.container {display: flex; flex-direction: row;}
#results {height: 10em; width: 8em; margin-left: .5em; padding: .5em; background: #ddd; overflow: auto;}
#results ul {list-style: none; padding: 0; margin: 0em;}
@keyframes fadenew {from {background: #6f6} to {background: transparent;}}
li.item-highlight {animation: fadenew 6s;}
@keyframes fadeused {from {background: #f66} to {background: transparent;}}
li.item-used {animation: fadeused 6s;}
<div class="container">
<div id="demo">
<table id="board">
<tr><td id="c0">?</td><td id="c1">?</td><td id="c2">?</td><td id="c3">?</td></tr>
<tr><td id="c4">?</td><td id="c5">?</td><td id="c6">?</td><td id="c7">?</td></tr>
<tr><td id="c8">?</td><td id="c9">?</td><td id="c10">?</td><td id="c11">?</td></tr>
<tr><td id="c12">?</td><td id="c13">?</td><td id="c14">?</td><td id="c15">?</td></tr>
</table>
<pre><code id="word"></code></pre>
</div>
<div id="results">
<ul id ="found"></ul>
</div>
</div>
我确实对上面的建议稍作修改。路径只是整数列表，索引到作为网格的平面字母数组。每个索引的邻居列表是硬编码的，尽管最初，当摆弄不同的网格大小时，我 calculated them.
代码加载字典，这里是 Peter Norvig 的 enable1 list, turns it into a trie, with the fairly simple trie function. We randomly create a puzzle, using simulated dice，它应该与原始的 Boggle 字典非常匹配，显示它（通过整数索引到单元格 ID 的简单映射），并使用相当简单的 search 函数可以在其中找到我们词典中至少包含三个字母的所有单词。这将为我们提供一组如下所示的结果：
[
//...
{path: [9, 5, 6, 3], stuck: false, isWord: true},
{path: [9, 5, 6, 3, 2], stuck: true, isWord: false},
//...
]
对网格，
['L',' T',' P',' T',' O',' E',' N',' Y',' U',' T',' F',' O',' S',' H',' K',' I']
代表棋盘
+---+---+---+---+
| L | T | P | T |
+---+---+---+---+
| O | E | N | Y |
+---+---+---+---+
| U | T | F | O |
+---+---+---+---+
| S | H | K | I |
+---+---+---+---+
所以[9, 5, 6, 3]代表"TENT"而[9, 5, 6, 3, 2]代表"TENTP".
这里一个有趣的设计决定是在求解器中而不是在字典中将单词限制为三个或更多字母。它的效率稍低，但我认为可视化尝试一个和两个字母单词的算法更清晰。
现在我们有了这个表示，我们可以通过突出显示我们尝试过的每个测试用例的路径来演示它。请注意，当 trie 不包含最新字母时搜索器停止，因此我们没有指数数量的搜索路径。我假设这里的所有其他算法都做类似的事情。显示中没有特别有趣的代码。它只是一次一个地突出显示通过网格的路径，简要说明它是否是我们字典中的一个词，如果是一个，在将它添加到列表之前检查我们是否已经找到它找到的话。所有这些都是通过简单的 DOM 操作完成的。唯一有点棘手的是动画的时间安排。我们希望通过我们的文字快速移动，但希望文字的动画足够快以显示实际路径。我不确定我在这里取得了正确的平衡，但这并不可怕。
对此的一个可能的扩展涉及显示我们所显示的试验的进度条，或者使其成为可以停止、重新启动和逐步通过的东西。另一个非常有用的方法是用一条穿过所用方块的线来显示路径，而不仅仅是高亮颜色。但那些是另一天。
很多代码对于网格大小都是通用的，使用那个 getNeighbors 函数，我们可以很容易地把它的其余部分变成这样，除了一件事。我们在这里掷的骰子是为了模拟实际的 Boggle 骰子，而不是简单的随机选择。我不清楚如何为更大的网格更改它。
这是一件有趣的小事。虽然我希望它能对 OP 有所帮助，但我很高兴这样做只是为了我自己的娱乐。
这是我想出的：https://jsfiddle.net/Msiric/jwag86o2/3/
该解决方案的部分灵感来自 Scott 的建议，但由于我无法让它工作，我找到了另一种方法来指定动画 运行.[=13 时应执行的每个步骤=]
算法的主要变化：
const movements = (i, j) => [
{ row: i, column: j + 1, move: "RIGHT" },
{ row: i + 1, column: j + 1, move: "BOTTOM_RIGHT" },
{ row: i + 1, column: j, move: "BOTTOM" },
{ row: i + 1, column: j - 1, move: "BOTTOM_LEFT" },
{ row: i, column: j - 1, move: "LEFT" },
{ row: i - 1, column: j - 1, move: "TOP_LEFT" },
{ row: i - 1, column: j, move: "TOP" },
{ row: i - 1, column: j + 1, move: "TOP_RIGHT" },
];
const addStep = (() => {
let counter = 1;
return (i, j, matrix, isWord, action, steps) => {
steps.push({
x: i,
y: j,
c: matrix[i][j],
isWord,
action,
counter,
});
action === "remove" ? counter-- : counter++;
};
})();
const findWords = (matrix) => {
const words = [];
const map = {};
const steps = [];
const iterate = (i, j, word, visited) => {
if (matrix[i] && matrix[i][j]) {
if (!visited[`${i}_${j}`]) {
visited[`${i}_${j}`] = true;
word += matrix[i][j];
addStep(i, j, matrix, false, "add", steps);
if (trie.find(word).length) {
if (trie.contains(word) && !map[word]) {
words.push(word);
map[word] = true;
steps[steps.length - 1] = {
...steps[steps.length - 1],
isWord: true,
};
}
const moves = movements(i, j);
for (let move of moves) {
const { row, column } = move;
iterate(row, column, word, { ...visited });
}
addStep(i, j, matrix, false, "remove", steps);
} else {
addStep(i, j, matrix, false, "remove", steps);
}
}
}
};
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
iterate(i, j, "", {});
}
}
return { words, steps };
};
这是可视化函数：
const visualizeSteps = async (steps, inputs, spans, size) => {
for (let step of steps) {
const { x, y } = step;
const selection = y + size * x;
await delay(0);
if (spans[selection].innerHTML === "") {
spans[selection].innerHTML = step.counter;
}
inputs[selection].classList.add("highlight");
if (step.isWord) {
const highlights = document.getElementsByClassName("highlight");
for (let highlight of highlights) {
highlight.classList.add("success");
}
await delay(500);
for (let highlight of highlights) {
highlight.classList.remove("success");
}
} else {
if (step.action === "remove") {
await delay(0);
inputs[selection].classList.remove("highlight");
spans[selection].innerHTML = "";
}
}
}
};