Compsci 100, Fall 2011, Boggle®

You should snarf assignment boggle from http://www.cs.duke.edu/courses/fall11/cps100/snarf or browse the code directory for code files provided. See the Boggle howto file for help and more instructions.

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.)

wikipedia jpg
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 Compsci educators at Duke, Stanford, and UCSD. This version emphasizes empirical analyses of tradeoffs in different implementations.

The Wikipedia Boggle entry explains the game in detail including popular culture references to Boggle. 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 online, e.g., Yahoo! Word Racer is related and Facebook used to have a game called Scramble that is related to Boggle.

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).

Analyzing alternative implementations and algorithms will help inform a better understanding of both work and play, what a great way to build a foundation in understanding how to turn data into information.

In particular you'll be examining alternate implementations of a lexicon or word source. You'll work on a Trie implementation and a compressed Trie that's similar to a Radix Trie/Patricia Trie, but simpler to implement. Tries are the data structure behind predictive text used in cell-phone texting, e.g., in T9 Text Input and have formed the basis for IP-routing, e.g., see Keith Sklower's Tree-Based Packet Routing Table for Berkeley Unix although changes to IPv6 may change the utility of tries as described here: Scalable high speed IP routing lookups (Waldvogel, Varghese, Turner, Plattner).

You'll use different word-sources or 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. You'll run code/experiments to reason about the classes you write.

  1. Find Words On Board

    You'll design and code one 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 facilitates 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.

More information is given in the howto pages.

Grading

This assignment is weighted by a factor of 2. There are correctness/algorithm points for the functionality of GoodWordOnBoardFinder, BinarySearchLexicon, and extra credit for the CompressedTrieLexicon. There are also correctness/algorithm points for the autoplayer code. There are engineering points for how the game is played with all lexicons and autoplayers. There are analysis points for the analysis of lexicons and generating statistics for high-scoring boards.

Your README file should list your testing results, all the people with whom you collaborated, and the TAs/UTAs you consulted with. You may want to include your testing and analysis results in a separate analysis document.

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.