I built a boggle solver algorithm utilizing a recursive helper function. It uses a trie data structure to quickly check if the existing prefix has any words in the dictionary or not. I would like to animate every step of the algorithm to display how every word is being found in the HTML table, but cannot get it to work correctly.
Here is the algorithm:
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;
};
A working app example can be found here: https://jsfiddle.net/Msiric/24x765bn/
Here is what the code looks like when using a generator:
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;
};
Doing this just displays the final state of the algorithm which is not what I want. I'd like to display each cell being highlighted or unhighlighted as every step is being executed and each word is being found. I also tried including setTimeout functions to delay the execution of the helper function, but that didn't work either. It just caused random flickering since cells were being highlighted/unhighlighted out of order.
Any help is appreciated
CodePudding user response：
In javascript, you cannot render something while in the mid of a synchronous function. Any code which attempts to make DOM changes will only queue those changes, which cannot be drawn while the runtime is executing your synchronous function.
Hence, you have to make your function asynchronous, like in this example https://jsfiddle.net/ep783cgw/2/
While I wasn't sure how you want to visualize it, I've made a renderState function which you can define to your liking.
// 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;
};
To learn more, follow these links
EDIT: I just noticed that you aren't using generator function correctly.
To better utilize the generator function, you should create a single generator instance and call next() on it to yield all values. But in your code, you've written
iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red").next();
where you're creating a new instance before every .next() call. Hence, the iterate generator won't yield all values.
The above line should therefore be
const instance = iterate(i, j, "", {}, j % 2 === 0 ? "blue" : "red")
while(!instance.next().done)
You can read an example of generator functions here
CodePudding user response：
There's a bit too much code for me to take in now. But a general suggestion would be that you don't try to mix the algorithm with the display.
In the algorithm, keep track of the motions you test and their results. Don't worry at all here about how you will display this.
After you've finished, take the test and one at a time, highlight the grid. Here it's easy with either setInterval or chained setTimeouts, as you are simply iterating over a list of attempts. Each time you would just need to unset current highlighting, and then set it for cells on the path, perhaps with a different display for the first and last cells of the path, and perhaps something different when you hit a legitimate word (animate the add to the list?)
Let's imagine we had a grid that in part looked something like this:
\ x
y \ 0 1 2 3
--- --- --- ---
0 | · | · | O | · |
--- --- --- ---
1 | · | O | F | · |
--- --- --- ---
2 | Z | L | · | H |
--- --- --- ---
3 | · | I | S | · |
--- --- --- ---
Perhaps each test would yield something like
{
path: [{x: 2, y: 1, c: 'F'}, {x: 2, y: 0, c: 'O'}, {x: 1, y: 1, 'c': 'O'}],
stuck: false,
isWord: false
}
(assuming "FOO" is not in your dictionary.)
Then when, because you're not stuck, you eventually add {x: 1, y: 2, c: 'L'}, you will have isWord: true ("FOOL") and stuck: false (because the trie says that there are nodes under 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
}
But when you try instead to add {x: 0, y: 2, c: 'Z'}, and the trie tells you there are no words beginning F-O-O-Z, you can record that it's not a word and you are stuck.
{
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
}
Eventually, you will try this this seven-letter word:
{
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
}
Note that these can be the only output from your algorithm, because it's trivial to generate the word list from these tests:
.filter (t => t .isWord)
.map (({path}) => path .map (n => n .c) .join (''))
const uniqueWords = [... new Set (words)]
CodePudding user response：
This is what I came up with: https://jsfiddle.net/Msiric/jwag86o2/3/
The solution is partially inspired by Scott's suggestion, but since I couldn't get it to work, I found another way of specifying each step that should be performed when the animation is running.
Main changes to the algorithm:
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 };
};
And here is the visualization function:
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 = "";
}
}
}
};