An application for the Discord Game SpellCast. Spellcast is very similar to Boggle, where you try to find the best word possible
I saw some existing solutions out there and wanted to make a faster and cleaner solution. My application can support up to 4 substitions within a minute.
blue tile is the start of the word
red tile is a tile that needs to be substituted
Using a heap and priority prefix tree, where prefixes that lead to a higher word at the leaf are prioritized more, we can navigate through all the best words first. Afterwards, we will reach a point where the word in the heap, even with the double word multiplier and triple letter bonus, cannot beat the existing best solution. This is where we can halt.
In this diagram, we have a example of early stopping. There can be other heuristics added to this, where if we reach too small of a slope, we can stop the search.
For Backend:
cd spellCastSolverBackend
py -m uvicorn main:app
For Frontend:
cd spellCastUI
npm run dev
- Up to 4 substitions
- Very fast for competitive gameplay
- Clean and easy UI
- Can edit the margin of error for higher speed
- Has a higher average case time complexity than a bruteforce prefix tree search.
- Using Monte Carlo for determining if shuffle is optimal
- Accounting for gems and optimal gem collection