You will write a parallel solver for a word game. In the game, you will be given a grid consisting of letters from an alphabet, along with a dictionary that defines what sequences of letters constitute words. Your solver will attempt to find paths in the grid such that the letters in the path constitute a word in the dictionary. The longer the word, the more points you get. No paths are allowed to intersect (i.e., share letters) and no path can overlap with itself; if this happens, you will lose points for those paths. Your solver will be given 2 GB of heap space and a fixed time budget (of at least 100 ms, but sometimes much more, depending on the test) to complete, so your goal is to maximize your score within the given time frame.
The design of your algorithm is up to you. You may implement any new classes you like, and even download classes you find on-line, as long as you submit the source code and attribute proper credit to them in the code and in the design document. You must complete the implementation of the GridSolver class, in particular its solve method. The following classes are provided, and should not be changed:
Your code will be tested as follows:
The public tests we provide have several small sample grids and dictionaries. You will probably want to make a program to generate your own grids that are larger, for testing purposes. The secret tests will use larger grids and different, larger dictionaries. Note that we will only use dictionaries involving the 52 upper- and lower-case alphabetic characters.
This class is provided for you, and should not be changed. The Grid class has a factory method makeGrid that takes a filename as an argument and returns a Grid object. For example, the file public_grid_1.txt is provided to you, and has the following contents:
XXXTXXXXXX XXACXXXXXX XXXXXXXXXX XXXXMOXXXX XXXXSUXXXX XXXXEXXXXX XDXGXXXXXX XXOXXXXXXXCalling Grid.makeGrid("public_grid_1.txt") will return a Grid representing the above. Grids also have a number of helper methods; for example: numRows and numCols return the number of rows and columns in the grid, respectively, while get(r,c) returns the character stored at row r and column c in the grid. It also has methods for computing the score of a given Solution when using a particular Dictionary and for plotting a grid and its solution graphically.
This class is provided for you, and should not be changed. A dictionary is simply a list of words. For example, we have provided the file dict_animals.txt to you, whose contents are the following:
AARDVARK ALLIGATOR ANT ANTEATER ANTELOPE APE ARMADILLO BADGER BAT BEAR ...Such a file can be converted to Dictionary object using the Dictionary.makeDict factory method. This class also has a number of helper methods, e.g., for determining whether a word is contained in the dictionary, and the score a word has. This score is determined by the word's length, and the distribution of word lengths in the dictionary; for example, if 5-character words are particularly uncommon, then one will be almost worth the same as a 6-character word; whereas if 5-character words are very common, they will be worth little more than a 4-character word. See constructor code, which sets up the scoring for a dictionary, to understand the details.
This class represents a point on the grid; it is provided for you and should not be changed. All points are non-negative, as enforced by the constructor. Position (0,0) is in the upper left, and the first coordinate is the row, and the second is the column. So for the example grid above, (1,2) is A and (3,4) is M. The isAdjacent method takes another point as an argument and returns true if these two points are adjacent, which is defined having the absolute value of the row and column differences of the point being no greater than 1; in other words, points that are diagonally arranged are considered adjacent.
This interface represents a directed path through the grid, which is simply a list of adjacent points (i.e., elements of the Point class). Ultimately you will create paths that correspond to words. For example, in the Grid given above you can see there are paths corresponding to the words MOUSE, CAT, and DOG.
This interface represents a solution to the problem, which is a list of (legal) paths whose letters correspond to (legal) words in the dictionary. A solution is only valid if all of its paths in fact correspond to legal words, and none of these paths overlap one another (i.e., share common points). Self-overlapping paths are also disallowed.
This class provides a static method, solve, which takes three arguments: a Grid, a Dictionary, and a timeout, in milliseconds. You must provide a multithreaded implementation for this method. You can implement it however you like, and may implement any new classes that you need.
This is a single-threaded implementation of the Grid solving algorithm. It is used by the public tests for comparison purposes, to see whether your multi-threaded algorithm does better.
Begin by downloading the project zip file here: Skeleton Eclipse project (or just the code). The directory structure of the zipped folder should allow the existing code to be directly imported into the Eclipse IDE. Note that all code is part of the cmsc433.p3 package, and you should preserve this package structure even if not using an IDE. After downloading the source, familiarize yourself with the above requirements while looking at the skeleton code, and the javadocs found here (and also in the zip file): API Specification.
You can use freely available code to implement data structures to help your solution as long as (a) you include its source in your project so that we build it from scratch, and (b) you properly attribute where it came from in your design document.
The file Test.java implements a graphical presentation of the Grid and the solving algorithm. You can set the time limit using the slider, and you can decide whether or not it will depict a single-threaded solution, along with your multi-threaded one. To change the grid and dictionary used you need to change the GRIDNAME and DICTNAME constants at the top of the Test class. Beware: it runs rather slowly with large grids (e.g., of size 200x200 or more).
As mentioned above, we recommend that you write files to generate grids to test with, so you can try out your code on larger files. You should also test on a machine with multiple processors. The linuxlab machines typically have four cores, so they are good candidates. On these machines, Java 7 is the default, and it contains the fork/join framework. Java 8 is also available but you have to configure it to be in your path; cf. the Linuxlab FAQ.
In general, you can assume that you will be given at least 100 ms for each test, and at least four processors to work with.
Every file you submit should have your name and UID. To enforce academic integrity, Code WILL BE CHECKED for similarity to other submissions. Each student should make his or her own individual submission.
Submit your code on the Department's Submit Server. Contact the TA if you have any troubles submitting.
You are also required to submit a short "design document" describing the design choices you made in your algorithm. Explain the basic structure of how you break down the overall task into units of work and how you organize that work to involve multiple threads.
For this project, due to the freedom we've given you with design, your design document should also include a comprehensive test plan. The test plan should describe how you tested each piece of functionality in your code. You may also include any tests that you've written and instructions on how to run these tests.