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
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 = "";
}
}
}
};