|title:||Predicting the Outcome of Scrabble Games|
|topics:||Algorithms and Data Structures , Case studies and Applications|
WordFeud cheat apps essentially let you look up words on the basis of limited information about the letters in that word. Given a dictionary, this is essentially a search algorithm, but the complexity of the task requires that you pick a suitable data structure.
The "limited information" may be given in any of a number of ways:
- Known placed letters (a pattern W-R- allows WORD, WARS, etc)
- Known unplaced letters (the letters WR also allow WREN, BREW etc)
- Forbidden letters
- Regular expressions (which in fact encompass all of the above)
In this assignment you will investigate the most suitable data structure for this purpose, using as strong a specification mechanism as you can achieve. A good candidate for such a data structure is Multiple-Valued Decision Diagrams.
To carry out the assignment well you must implement and experiment with candidate data structures, in a language of your choice. Optionally, you can make the resulting program available as a web service or app.