Back to University of Twente portal
| author: | Thomas Brus |
| title: | Predicting the Outcome of Scrabble Games |
| keywords: | |
| topics: | Algorithms and Data Structures , Case studies and Applications |
| committee: | Arend Rensink |
| end: | January 2015 |
Description
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.