The simple game jawbreaker is often seen on Windows-CE based PDAs and mobile phones. It is a little like the game tetris in that the objective is to maximize your score by arranging (falling) items. While tetris requires you to arrange the falling items, jawbreaker requires you to select sets of adjacent, identically colored items to make them fall.

A number of items form a set, iff:

• each item has the same color,
• each item is adjacent to at least one other along the north, south, east, or west axes. Items are not adjacent (and thus not in the same set) if only next to each other on a diagonal.

The game proceeds as follows:

• The game commences by invoking the program from the command-line, optionally providing the number of rows and columns on which the game is to be played;

              jawbreaker [nrows ncolumns]
  

• Clicking on an item of any color, results in that item and all other items in that item's set, disappearing from the screen. All items above those items, then fall until they rest on another item or reach the bottom. Removing a set of n items scores n²-1 points.

• The game finishes when no items remain. The objective, of course, is to maximize your score by locating and removing maximal sets.

The directory http://www.cs.dartmouth.edu/~chris/cs23/jawbreaker/ contains some files to get you started - take a copy of all files.

1. Before you start any coding - design a list of tests that will enable you to extensively test an eventual implementation of jawbreaker.

2. [10 marks] Design and develop your own implementation of jawbreaker. You will only need to extend the file jawbreaker.c. In particular, you will not need to modify (nor understand) any of the Tcl/Tk GUI code, but you will call the provided functions to interact with the GUI.

   Complete your program by 12noon Wednesday 11th. and place a copy of it in your home directory with the following commands:

             cp  jawbreaker  ~/jawbreaker
             chmod  755  ~/jawbreaker
   

   this will enable other students to copy and execute your program, but they will not be able to see your source code. Testers should just run and test other students' programs, but should not look at the code.

   You may exprience some difficulties getting your application to display the graphical output, depending on where you're working and what software you have installed on you laptops. If sitting at a Linux machine in S.001, then you will need to compile and link your jawbreaker on a machine that has the Tcl/Tk libraries installed (e.g. moose.cs.dartmouth.edu). Login to moose with: ssh -X moose.cs.dartmouth.edu ....develop, compile and link your program (logged into moose) ./jawbreaker (logged into moose) If working on your own Linux or Macintosh laptop, the above command sequence should also work from anywhere on campus.

3. [10 marks] In your role as a tester, test another student's program against the tests that you previosuly developed.

   You should test the code of the student immediately after you from this list.

   Here, marks are not being awarded, or deducted, for the success or failure of the other student's program. Marks are awarded for your description of how their program performs against your tests.

   Write your test-report as a simple ASCII-text file, do not submit it as an MS-Word document nor as HTML.

4. [10 marks] A dictionary data structure is often used to provide a mapping between a word (a string) and its definition (another string). A hash table is often used to implement the dictionary, as it can provide (almost) constant speed lookups. At the core of the hash table is a hashing function, which is a many-to-one function mapping a string to an integer. An example of one such hashing function is:

       #include <stdlib.h>
   
       int hash(char *str)
       {
           int h = 0;
   
           while(*str) {
               h = h * 8 + *str ;
               ++str;
           }
           return( abs(h) );
       }
   

   Design and develop code to implement a dictionary using a hash table. We will need code to add new definitions, to determine if a requested definition exists, and to fetch a requested definition. For simplicity, assume that we'll never remove definitions. Firstly, test your implementation with some simple data such as:

             H <tab> hydrogen
             He <tab> helium
             Li <tab> lithium
             Be <tab> beryllium
   

   Then (and this is the main exercise) develop one or more sets of test data that thoroughly test your implementation. In a separate (plain text) file, explain how each of your chosen data sets tests your implementation.

5. [0 marks] Very difficult and not being assessed.

   Consider a text file of data consisting of a number of lines of four integers each. Each line contains the non-negative x, y, and z integer coordinates of a point in a rectangular prism (it is not necessarily a cube). Each line of 3 coordinates also contains a single data measurement taken at those coordinates - it could be the temperature, radiation intensity, or air pressure from inside a nuclear reactor. Any data points not explicitly provided are considered to have the value zero.

   The data has been captured by a device that flys around randomly in the 3D space, and so the data points "arrive" in any order. As such, you don't really know the bounds of the 3D space until you've finished reading all of the data. However, you only have time to read and record the data items once (as the reactor melts down!) so you'll need to build a 3D data structure "on the fly".

   Write a program which is able to read in all of the data points, dynamically growing a 3D data structure to hold the rectangular prism of data as necessary.

   This question is actually developing a 3-D version of our TSV library. Could we develop an N-D version?