Compsci 201, Spring 2012, Boggle^®

Genesis of Assignment

(As is usual, the genesis and related links isn't necessary to complete the assignment, but it's full of useful and applied material.)

Prof. Astrachan fondly recalls neighborhood Boggle^® games from his now long-ago childhood and was re-introduced to it on Sun Unix workstations as a grad student in the mid 80's. We used Boggle^® for a Compsci 108 assignment at Duke in 1996. Boggle is in the Nifty Assignments Archive and the current instantiation of the assignment is a combination of efforts from professors at Duke, Stanford, and UCSD.

The Wikipedia entry on Boggle provides some background. Reviewing the rules on the Wikipedia site will help in understanding the play-of-the-game, but you'll be looking at implementation trade-offs that are independent of game-playing. You can play games based on words that are similar to Boggle like Yahoo! Word Racer.

Theoretical and practical approaches to word games have formed the basis for The World's Fastest Scrabble Program (Appel and Jacobson) for recognizing Genomic Signatures in DeBruijn Chains (Heath and Pati) and for An efficient interface between continuous speech recognition and language understanding (Oerder and Ney). In particular you'll be examining alternate implementations of a lexicon (word source). You'll work on a Trie implementation and a compressed Trie that's similar to a Radix Trie, but simpler to implement. Tries are the data structure behind the predictive text algorithms used in cell-phone texting, e.g., in T9 Text Input and have formed the basis for Internet Protocol routing, e.g., Keith Sklower's Tree-Based Packet Routing Table for Berkeley Unix.

You'll use different lexicons. Apparently there's a controversy as to what the "best" lexicon is for playing word games like Scrabble® and Boggle®

What You Will Do

You'll code one class to find a specific word on a Boggle® board and you'll implement two hierarchies of classes (one for Lexicons, one for Computer ("Auto") players of the game). Each hierarchy will be a group of classes that implement a common interface and allow you to reason empirically about trade-offs in implementation techniques.

1. Find Words On Board

   You'll design and code a class GoodWordOnBoardFinder that implements the IWordOnBoardFinder interface to find a word on a Boggle board. You'll use this class in implementing one of the auto-player classes and in determining where a word appears on a board when you or another (human) player plays the game.

2. Implement and benchmark lexicons

   You'll write classes that implement the ILexicon interface. Each lexicon implementation provides methods for looking up a word or a possible prefix of a word. The classes differ in how efficiently they support these operations and in how much memory they use.

3. Implement one AutoPlayer that finds all words quickly

   You'll write one class BoardFirstAutoPlayer that implements the IAutoPlayer interface. You're given a class that implements the interface, LexiconFirstAutoPlayer. Each class facilitates playing a game of Boggle by finding every possible word on a given Boggle board. These classes use the lexicons from the previous hierarchy.

4. Empirical Analyses

   You'll make conclusions based on empirical, runtime analyses of the classes you write to determine which of several methods is "best", and to reason in general about the trade-offs in different implementations. Please put this analysis in a file called Analysis.pdf.

Detailed instructions are given in the howto pages.

Grading

Your Analysis.pdf file should list your testing/analysis results.

Your readme should contain all the people with whom you collaborated, and the TAs/UTAs you consulted with. You should include an estimate of how long you spent on the program and what your thoughts are about the assignment.

Submit your README and all of your source code using Eclipse with assignment name boggle.