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)]
Major Update
I've been thinking about this on and off since I posted the above. Here is an attempt to do it in something close to that fashion. (It will probably look better if you use the "Full Screen" option of the snippet.):
// *************************
// 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>
I did change slightly from my suggestion above. The paths are just list of integers, indices into a flat array of letters that is the grid. The list of neighbors of each index is hard-coded, although originally, when fiddling with different grid sizes, I calculated them.
The code loads a dictionary, here Peter Norvig's enable1 list, turns it into a trie, with the fairly simple trie function. We randomly create a puzzle, using simulated dice that should be a close match to the original Boggle ones, display it (through the simple mapping of integer indices to cell ids), and use the fairly simple search function to find in it all the words that are in our dictionary and have at least three letters. This will give us an array of results that look like this:
[
//...
{path: [9, 5, 6, 3], stuck: false, isWord: true},
{path: [9, 5, 6, 3, 2], stuck: true, isWord: false},
//...
]
against the grid,
['L',' T',' P',' T',' O',' E',' N',' Y',' U',' T',' F',' O',' S',' H',' K',' I']
which represents the board
+---+---+---+---+
| L | T | P | T |
+---+---+---+---+
| O | E | N | Y |
+---+---+---+---+
| U | T | F | O |
+---+---+---+---+
| S | H | K | I |
+---+---+---+---+
So [9, 5, 6, 3] represents "TENT" and [9, 5, 6, 3, 2] represents "TENTP".
One interesting design decision here is to restrict the words to three or more letters in the solver rather than in the dictionary. It is slightly less efficient, but I think visualizing the algorithm trying one and two letter words is clearer.
Now that we have this representation, we can demonstrate it by highlighting the path through each test case that we tried. Note that the searcher stops when the trie does not contain the latest letter, so we don't have an exponential number of paths to search. I assume all the other algorithms here do something similar. There is no particularly interesting code in the display. It simply, one at a time, highlights a path through the grid, briefly notes whether or not it's a word in our dictionary, and if it is one, checks to see whether we've already found it before adding it to a list of found words. All this is done with plain DOM manipulation. The only slight trickiness is in the timings of the animation. We want to move quickly through our words, but want the animation of the words to be quick enough to show the actual path. I'm not sure I've struck the right balance here, but it's not horrible.
One possible extension to this involves showing a progress bar of the trials we've displayed, or making it something that can be stopped, restarted and stepped through. Another, very useful one would be to show the path with a line through the squares used and not just the highlight color. But those are for another day.
A lot of the code is generic as to grid size, and using that getNeighbors function, we could easily make the rest of it so, except for one thing. The dice we roll here are meant to simulate actual Boggle dice and not simple random selections. It's not clear to me how to change that for larger grids.
This was a fun little thing to do. While I hope it might help the OP, I was glad to do it just for my own amusement.
