CS 2110 Summer 2011: Assignment 2 — Boggle

CS 2110 Summer 2011: Assignment 2 -- Boggle

Due July 12 at 5pm

This assignment is to be done in pairs. Information about partners will be provided separately.

1 Playing Boggle1

In this assignment, we continue the theme of games. Unlike the last assignment, where the computer relied on deception to outplay its human opponent, in this assignment the computer will try to win using nothing more than clever algorithms and brute force computation.

You will design software to play a computer version of the board game Boggle. If you are unfamiliar with the game, here is a brief description. The board is a 4 x 4 grid onto which 16 dice are randomly placed. On the face of each die is a single letter (except for one face, which has the two letters "Qu"). The objective is to form words from sequentially adjacent cubes. (Two cubes are adjacent, or neighboring, if they lie next to each other horizontally, vertically, or diagonally. Cubes in the middle of the board have 8 neighbors; a cube at the corner of the board has only 3 neighbors.) In forming a word, each cube can be used only once. The objective to find as many words as possible in a given amount of time. In the traditional board game version, all players start at the same time, writing down as many words as they can find, and then comparing word lists when time is up. A player is awarded points for finding a word that no one else found, and more points are given for longer words. Additional details of the game are described on Wikipedia ().

Our computerized version has only a few modifications. We have two players: a human word finder and a computer word finder. The human goes first, and has 60 seconds to find as many words as possible. Then it is the computer's turn. As the screenshot suggests, the computer often trounces the human. In addition, in our version the size of the square grid is variable, and you can play either a 4 x 4 or a 5 x 5 board. On the smaller board, the computer is restricted to finding words of three or more letters; on the larger board, 4 or more letters.

1This assignment was adapted with permission from Owen Astrachan of Duke. His assignment is the result of a combination of efforts from computer science educators at Duke, Stanford, and UCSD.

1

Figure 1: A screenshot of the computer version of Boggle. Highlighted on the board is one of the 84 words that the computer found: "clothe." The primary goal of this assignment is to design and implement recursive algorithms. So that you can concentrate on these aspects, we provide code that manages the details of the game and displays the board graphically. (You will have a chance to code graphical user interfaces later this summer!)

Primary Learning Objectives ? Master recursion, particularly recursive backtracking algorithms (2(a) on syllabus). ? Practice the methodology of write unit tests (4(b) on syllabus). ? Use inheritance appropriately in software design (3(a,c) on syllabus).

2

2 The Assignment

You are asked to (a) implement three classes; (b) write unit tests for one of those classes; and (c) answer a few questions.

Classes to Implement ? Define and implement a new class called WordOnBoardFinder that implements the IWordOnBoardFinder interface. When the human player enters a word, this class can be used to verify that the word does in fact occur on the board. (Hint: it may also have other uses.) ? Define and implement two versions of the computer player. Each version of your computer player must implement the IAutoPlayer interface. Conceptually, the computer player is given a Boggle board and a lexicon (a list of words) and its job is to find every word that can be formed on the board under the rules of Boggle. In addition to code that manages the Boggle board, we also provide a Java class that manages the lexicon, called SimpleLexicon. ? The first version should be in a new class called LexiconFirstAutoPlayer. The strategy behind this version is to start with the lexicon: for each word that occurs in the lexicon, see if it occurs on the board. ? The second version should be in a new class called BoardFirstAutoPlayer. The strategy behind this version is to start with the board and try to form words by trying all possible paths on the board. For each path, check whether the word formed by the path occurs in the lexicon. As explained in Section 4.4, it should avoid "dead end" paths. The SimpleLexicon class offers useful features for recognizing dead ends.

Unit Tests In class called TestWordFinder, you should write at least 3 test cases that test your WordOnBoardFinder implementation. Each test case should test a distinct aspect of the class' functionality. (If you implement your WordOnBoardFinder class using test-driven development, each test will naturally examine a distinct aspect of your implementation.) Give each test a descriptive name and include a comment that describes what each particular test is testing. (Note: an example test is provided for you, you must implement 3 in addition to this one.) You are not required to submit tests for your IAutoPlayer implementations. Nevertheless we recommend that you test this code to make sure it works properly.

3

Questions 1. In BoardFirstAutoPlayer, record the number of times that your recursive helper method is called. The specific number may vary from game to game, but roughly how many times is it called? If the answer is around 12 million, then you may not be avoiding dead ends (see 4.4). 2. Describe how you dealt with the special case of the "Qu." 3. Briefly describe your experience working with a partner. For each method, who wrote the body of the method? When you were not the one typing, what were you doing to help your partner?

2.1 Grading guidelines

Carefully review the comments you received on assignment 1 and avoid similar mistakes this time. While for the first assignment, we did not deduct points for some mistakes such as poor style and incorrect .jar files, we will be deducting points for these mistakes on assignment 2. As with assignment 1, your code must adhere to the interfaces. Finally, be sure to include answers to the above questions.

2.2 Submission

Submissions should be handed in via CMS . You should submit a jar file called assignment2.jar containing:

? WordOnBoardFinder.java ? BoardFirstAutoPlayer.java ? LexiconFirstAutoPlayer.java ? TestWordFinder.java ? "answers.txt" containing the answers to the questions above. ? (Optional) BinarySearchLexicon.java Instructions for creating a .jar file were provided in assignment 1. Following the convention from the first assignment, your Java code should be in a package having the name id.assignment2 where netid is either your netid or your partners' netid (either is fine).

4

3 Extension (Optional)

Completing the following extensions will earn you karma points, as explained in the syllabus.

Good Test Cases Exceptionally good test cases will earn karma.

BinarySearchLexicon While conceptually a lexicon is just a set of words, the Java class that we provide for managing the lexicon, SimpleLexicon, does more than just maintain a set of words. In particular, it is possible to check not just whether a word is contained in the lexicon but also whether it is a prefix of a word in the lexicon. The SimpleLexicon implements the ILexicon interface. To complete this extension, write an alternative implementation of the ILexicon interface. Your implementation should be written in a class called BinarySearchLexicon. This class should store words in a sorted ArrayList. Sort the list after adding all the words to it using the Java built-in method Collections.sort. To determine the status of a word, implement a recursive binary search. We will discuss binary search in class, but perhaps not until near the deadline for this assignment. You can read about it in the book on p. 423. The key idea is to use binary search to find whether a given String is a word in the sorted lexicon. Or if the word is not there, a binary search can tell you where the word would be. Once you've found this location, checking for a prefix is fairly straightforward. You might find it helpful to use the startsWith method defined in the String class. When checking for a prefix, make sure you don't go off the end of the array of words in the lexicon. Write some test cases that demonstrate the correctness of your ILexicon implementation.

4 Tips

4.1 Getting Started

From CMS, download assignment2.jar and the two lists of words, bogwords.txt and ospd3.txt. The second list is a large list derived from the Official Scrabble Player's Dictionary and contains some rather unusual words (good for impressing friends). Following the same procedure as in assignment 1, import the jar into Eclipse. You should not modify any of these files except BoggleMain and AutoPlayerMain.

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download