3 ms·
Semi offtopic: Can anybody tell me about an appropriate data structure for computing Scrabble (or any crossword) short of full-out walking a 2d grid? I've rea
by jewbacca 16y ago
Semi offtopic:
Can anybody tell me about an appropriate data structure for computing Scrabble (or any crossword) short of full-out walking a 2d grid? I've read a bit about Tries and Directed Acyclic Word Graphs, but those seem to just be for optimizing dictionary matching, and don't seem to account at all for the actual structure of the board (especially not the possibility of colliding with other branches when adding new words).
I'm 90% certain it'll come back right back to needing a global and explicit a 2d grid when I try to build in a board with static score multipliers, but ignoring this for now and just trying to lay out letters: is there a masochistically-functional way to compute Scrabble/crosswords without working on an explicit 2d grid?
- btmorex 16y agoHave to ask... what would the motivation be to use anything other than a 2d grid to represent something that, in the real world, is a 2d grid?
- jewbacca 16y agoWell, finding the best word for a given tile rack played on a given position can be expressed staggeringly simply in Haskell. I'm just wondering if there's some clever way to store and search a whole board without getting into something messy and halfway-imperative. Something that can be expressed as mostly a composition of simple library functions. Plus, I've always had issues with multidimensional structures -- I can never quite settle on what's the most intuitive way to express them.