CSC 122: Computer Science II, Spring 2005

Project 2

Sorting and Searching - Word Search

Deadline: Friday, March 4, 5:00 p.m.

Overview:

You are to write a program that solves word search puzzles by listing all of the words that can be found in a grid (forwards, backwards, up, down, or diagonally) that are also in a large (around 100,000 words) list of English words. You have been provided with a Grid class that can either generate a random grid or read one from a text file (using the same Infile class from Project 1). You are to write a word list class to read in the dictionary from a text file, sort it, and support efficient searching. You will also write a driver class which creates a grid and a word list, then prints out the grid followed by all of the dictionary words that were found in the grid. You do not need to mark where the words were found in the grid.

Specification:

Here is an excerpt from the JavaDoc for the provided Grid class:

---

public class Grid

Stores a two-dimensional grid of characters for use in a word search game. The grid may be generated randomly or read from a file.

Author:

bhoward

---

Constructor Summary

Grid(Infile in)           Construct a Grid by reading lines from a text file.

Grid(int rows, int cols)           Construct a randomly-generated Grid of the given size.

 

Method Summary
java.lang.String	chars(int row, int col, int dir)           Extract characters from this Grid starting at the given row and column and heading in the given direction: 0 is right, 1 is down-right, 2 is down, 3 is down-left, 4 is left, 5 is up-left, 6 is up, and 7 is up-right.
int	cols()           Get the number of columns in this Grid.
void	display()           Print this Grid on the system console.
int	rows()           Get the number of rows in this Grid.

 

Constructor Detail

Grid

public Grid(Infile in)

Construct a Grid by reading lines from a text file.

Parameters:

in - The Infile from which to read. The number of rows will be the number of lines read from the file; the number of columns will be the number of characters in the shortest line (longer lines will be truncated).

---

Grid

public Grid(int rows,
            int cols)

Construct a randomly-generated Grid of the given size.

Parameters:

rows -

cols -

Method Detail

chars

public java.lang.String chars(int row,
                              int col,
                              int dir)

Extract characters from this Grid starting at the given row and column and heading in the given direction: 0 is right, 1 is down-right, 2 is down, 3 is down-left, 4 is left, 5 is up-left, 6 is up, and 7 is up-right.

Parameters:

row - The starting row (0 .. rows()-1)

col - The starting column (0 .. cols()-1)

dir - The direction (0 .. 7)

Returns:

The string of characters from the starting position to an edge of the grid.

---

cols

public int cols()

Get the number of columns in this Grid.

---

display

public void display()

Print this Grid on the system console.

---

rows

public int rows()

Get the number of rows in this Grid.

---

Word list format:

• The filename is words.txt (in the same directory as the project).
• Each line in the file gives one english word, using only the letters 'a' through 'z' (no spaces, no upper-case, no punctuation).
• The word list is not initially sorted; it is derived from the work of the SCOWL (Spell Checking Oriented Word Lists) project: http://wordlist.sourceforge.net/, which provides a variety of word lists (American, British, and Canadian variants, plus a common English core) over a range of levels (starting from a small list of the 5000 most common words up to the "insane" list of more than 600,000). The word list we are using is a concatenation of 16 of these lists (so the file is actually made up of 16 sorted blocks of varying sizes), with about 112,000 words (including American variants); it has been processed to remove words shorter than four letters (since there would be too many matches for the shortest words in a letter grid), as well as words with apostrophes or accented characters.

The suggested algorithm:

• Initialize the grid, either randomly or from a text file.
• Display the grid on the console.
• Read the word list, then sort it (with over 100,000 strings, you will not want to use a quadratic sort).
• For each letter in the grid, and for each of the eight directions you can head from that letter, use the chars method of the Grid object to extract all of the characters in that direction.
• Now, for each prefix of that string of letters (use the substring method), check whether it is a word in the word list (again, with the sizes involved, you will not want to use a linear search). If it is, print it out on the console.
• If this algorithm is implemented correctly, your program should be able to find all of the words in a 100-by-100 grid in only a few seconds. If not, you'll need to go out for coffee -- perhaps in Indianapolis.

The Project and Getting Started:

The WordSearch project:

• The project should consist of four classes – Driver, WordList, Grid, and Infile.
• Driver (client) – Creates instances of Infile, WordList, and Grid and invokes appropriate methods from each.
• WordList (server) – Initializes the list of words, loads the words from the input file, sorts the list, supports efficient searching of the list.
• Grid (server) - This class will be given to you in the WordSearch project, and is described above.
• Infile (server) – This class will be given to you in the WordSearch project.
• The project can be copied from I:\csc122\public\WordSearch
• Implement the project using the test driven implementation strategy: first build a test system and stubbed implementation of each class.
• Test on the grid stored in the project file, testgrid.txt (which was constructed using a tool at http://www.armoredpenguin.com/wordsearch/, using words from the chapter headings of the textbook). If my model solution is correct (and I believe it is), you should find 341 words (some will be duplicates, since a word such as "noon" will be found twice, and several words actually occur several times at different places in the grid).
• Here is an example 20-by-20 random grid, and what the output might look like (compressed here for easier reading):

  pecnyscdgbaeeelvokfe
  aetiylgneeageioorpml
  selhfdoiniciursniriv
  tmmdromngrengdcaevgh
  etirzbieeatennnhrgio
  hxitntphsnsempqihrdh
  agaeyetrsetcfseidrio
  raeihwlcvbsruoypoers
  pabratbhognasrlnnatv
  coohaentolssaonzddsn
  srutomsitbcnacsrpklk
  ietrretealdlnastseei
  strevekmfaavnvlasnul
  oeaulsttihvveneeaius
  idnnbsceiayncawrtiue
  aancyrescorlnerbeegs
  dnjacibtmmcnsinlsegg
  esnaiincrogailgnrhat
  rnyiuttrmhsplraereun
  hronlirenzleoiondvse
  
  
  past   paste  sync   lone   nine   gigs   arris  viol   rite   zoon   eaten  
  enol   nide   herm   ohos   harp   ends   dirt   tend   tends  dies   read   
  bots   ours   your   yours  ordo   pour   brat   bout   sang   rand   outran 
  hues   slot   rete   toms   tret   mare   stob   blah   nary   scan   tels   
  rete   rete   read   teal   slew   stre   else   vest   ever   evert  asks   
  sate   sates  seem   test   earl   ewes   ates   sues   deter  tass   ewes   
  etas   gere   cite   come   nape   silo   seta   nays   glia   tahr   homo   
  soms   earl   rear   lire   linn   
                         
  

  One potential enhancement is to collect the list of found words and sort it before printing it out, but this is not required (though it should be easy to reuse the WordList class for this purpose).

Standards:

Your project should be well-written, neatly-formatted, modular, and well-documented.

Grading:

• Reading the list of words (10 pts)
• Sorting the list of words efficiently (25 points)
• Searching for words correctly (20 points)
• Processing the grid correctly (20 points)
• Printing the grid and list of found words (10 points)
• Documentation and style (15 points)

DePauw University, Computer Science Department, Spring 2005
Maintained by Brian Howard (bhoward@depauw.edu). Last updated