Hello. I have 3 more files as well which are test data and a class we have to copy paste but this is not allowing me to do so. asmt2.pdf is the 7page assignment. The rest of the files are just copy paste and include the game code as well. There are three more files which I believe are test data but this is not allowing me to include this. I'm not sure what you mean by referencing style so I just chose the option "Other". Please include comments in the java code. Thank you
asmt2.dvi CS 2210 — Data Structures and Algorithms Assignment 2 Due Date: October 18 at 11:55 pm Total marks: 20 1 Overview For this assignment you have to write a Java program that plays the following board game. Two players take turns putting colored tiles on a rectangular gameboard of size R × C, where R is the number of rows and C is the number of columns. The goal is for a player to place a pre-specified number k of their tiles in adjacent positions of the same row, column, or diagonal of the board, similarly as in the game of tic tac toe. However, some positions on the board are marked as ”blocked” and player tiles cannot be placed there. The first player who places k of their tiles in adjacent positions of the same row, column, or diagonal wins the game. If no more empty positions remain on the board where player tiles can be placed and no player has won, then the game ends in a draw. Your program will play against a human opponent. The human player uses light blue tiles and the computer uses orange tiles. Empty positions on the board are green and blocked positions are dark blue. The computer randomly decides who makes the first move. Figure 1(a) shows a possible set of tiles on a board of size 3 × 4 where k = 3; in this figure the human player has won the game. In Figure 1(b) the game has ended in a draw. (a) (b) Figure 1: (a) The human player wins. (b) The game is a draw. You will be given code for displaying the gameboard on the screen and for playing the game. There are several Java classes that you need to implement as described in the next sections. If you are interested in knowing how the algorithm for playing the above game works additional information is in the file Additional.pdf. 2 Board Configurations A board configuration is the positioning of the tiles on the gameboard. Your program will represent a board configuration as a string as follows. A light blue tile is represented with the character ’b’, an orange tile with ’o’, a green empty space with ’g’, and a dark blue blocked position with ’d’. To form a string for a given board configuration we concatenate the characters corresponding to the tiles and empty positions on the board starting at the upper left position and moving top to bottom and left to right. For example, for the configurations in Figure 2, their string representations are “obbboobgg”, “obbboobod”, and “obbboobdo”. Each board configuration is assigned a score. The higher the score is the better the current state of the game is for the program. Conversely, the lower the score is the better the current state of the game is for the human player. The program will use the following four scores for board configurations: 9 (a) (b) (c) 1 1 12 2 23 3 3 4 5 6 7 8 9 4 5 6 7 8 9 4 5 6 7 8 Figure 2: Board configurations. 0: in the board configuration the human player wins 1: in the board configuration no player has won and the game is not a draw 2: in the board configuration the game is a draw 3: in the board configuration the computer wins the game. For example, the score for the gameboard shown in Figure 2(a) is 1. The score for the board displayed in Figure 2(b) is 2 and for the board in Figure 2(c) is 3. As mentioned above when playing the game the computer and human player will take turns placing tiles on the board. In each turn of the computer the program will consider all positions where it can place a tile and what the potential outcome is for putting it there; at the end it selects the best possible position to put its. Since there is a vary large number of possibilities that the program needs to consider, to speed it up the program will use a hash table to store board configurations that it has already processed; this way the program will not have to consider the same board configuration multiple times. 3 Classes to Implement You are to implement the following Java classes: Data.java, Dictionary.java, InexistentKeyException.java, DuplicatedKeyException, and Evaluate.java. You can implement more classes if you need to. You must write all the code yourself. You cannot use code from the textbook, the Internet, or any other sources. You cannot use Java’s Hashtable class or hashCode() method. 3.1 Class Data This class represents the records that will be stored in the objects of class Dictionary.java. An object of this class stores a string and two integers; therefore there will be three instance variables in this class. The string stored in an object of this class will be used as its key attribute. For this class, you must implement all and only the following public methods: public Data(String key, int score, int level): The constructor for the class. public String getKey(): Returns the string stored in this Data object. public int getScore(): Returns the first integer stored in this Data object. public int getLevel(): Returns the second integer stored in this Data object. You can implement any other methods that you want to in this class, but they must be declared as private methods. 2 3.2 Class Dictionary This class implements a dictionary using a hash table in which collisions are resolved using separate chaining. The hash table will store objects of the class Data. You will decide on the size of the table, keeping in mind that the size of the table must be a prime number. A table of size between 5000-10000, should work well. You must design your hash function so that it produces few collisions. A bad hash function that induces many collisions will result in a lower mark. You are encouraged to use a polynomial hash function. As mentioned above, you cannot use Java’s hashCode() method in your hash function. For this class, you must implement all the public methods in the following interface: public interface DictionaryADT { public int put(Data record) throws DuplicatedKeyException; public void remove(String key) throws InexistentKeyException; public Data get(String key); public int numDataItems(); } The descriptions of these methods follows: public int put(Data record) throws DuplicatedKeyException: Inserts the given Data object referenced by record in the dictionary. This method must throw a DuplicatedKeyException (see below) if the string stored in the object referenced by record is already in the dictionary. You are required to implement the dictionary using a hash table with separate chaining. To determine how good your design is, we will count the number of collisions produced by your hash function. Method put must return the value 1 if the insertion of the object referenced by record into the hash table produces a collision, and it must return the value 0 otherwise. In other words, if for example your hash function is h(key) and the name of your table is T , this method must return the value 1 if the list in entry T [h(record.getKey())] of the table already stores at least one element; it must return 0 if that list was empty before the insertion. public void remove(String key) throws InexistentKeyException: Removes the Data object containing string key from the dictionary. Must throw a InexistentKeyException (see below) if the hash table does not store any Data object with the given key value. public Data get(String key): A method which returns the Data object stored in the hash table containing the given key value, or null if no Data object stored in the hash table contains the given key value. public int numDataItems(): Returns the number of Data objects stored in the hash table. Since your Dictionary class must implement all the methods of the DictionaryADT interface, the declaration of your method should be as follows: public class Dictionary implements DictionaryADT You can download the file DictionaryADT.java from OWL. The only other public method that you can implement in the Dictionary class is the constructor method, which must be declared as follows public Dictionary(int size) this initializes a dictionary with an empty hash table of the specified size. You can implement any other methods that you want to in this class, but they must be declared as private methods (i.e. not accessible to other classes). 3 Hint. You might want to implement a class Node storing an object of the class Data to construct the linked lists associated to the entries of the hash table. You do not need to follow this suggestion. You can implement the lists associated with the entries of the table in any way you want. 3.3 Classes InexistentKeyException and DuplicatedKeyException These are just the classes implementing the types of exceptions thrown by the put and remove methods of class Dictionary. 3.4 Class Evaluate This class implements all the auxiliary methods needed by the algorithm that plays the above board game. For details on the algorithm that plays the board game, please read document Additional.pdf posted in OWL as part of this assignment. The constructor for this class must be as follows public Evaluate (int boardRows, int boardColumns, int tilesNeeded, int maxLevels) The first two parameters specify the size of the gameboard, the third parameter is the number of adjacent tiles needed to win the game, and the last parameter specifies the playing quality of the program (the higher this value is the better the program will play, but the slower it will be; when you test your program use values between 3 and 5 so the program plays OK and it is not too slow). This class must have an instance variable called gameBoard of type char[][] to store the game- board. This variable is initialized inside the constructor so that every entry of gameBoard stores the character ’g’ indicating that every position of the board is empty. As the game is played, every entry of gameBoard will store one of the characters ’b’, ’o’, ’d’, or ’g’. This class must also implement the following public methods. public Dictionary createDictionary(): returns an empty Dictionary of the size that you have selected. public Data repeatedConfig(Dictionary dict): This method first represents the content of the two dimensional array gameBoard as a string as described in Section 2; then it checks whether this string is in dict: If it is, this method returns the Data object that contains it; otherwise the method returns the value null. public void insertConfig(Dictionary dict, int score, int level): This method first represents the content of gameBoard as a string as described in Section 2, then it cre- ates an object of the class Data storing this string, score, and level; finally, this Data object is stored in dict. public void storePlay(int row, int col, char symbol): This method stores symbol in gameBoard[row][col]. public boolean squareIsEmpty (int row, int