Write a Java program that reads in a text file containing the coordinates of two battleships.

Implement three different strategies (using the strategy design pattern) for locating the battleships. How to submit: All homework for this course must be submitted to D2L.

Detailed Description:

Create a data structure that represents a 25X25 grid. You will use this grid to place the two battleships and to track the progress of your search for the battleships.

Read in Coordinates Coordinates are stored in a file named input.txt. Each line represents ONE game so the following sample represents three different runs of the game. For each game there is one carrier and one submarine. The carrier occupies 5 cells represented by the first five coordinates in the line (below), and the submarine represents the remaining three coordinates. See example below:

Create a 25X25 grid and place the carrier and submarine onto the grid.

(0,0)(0,1)(0,2)(0,3)(0,4)(4,15)(4,16)(4,17) (5,9)(5,10)(5,11)(5,12)(5,13)(20,5)(20,6)(20,7) (15,3)(16,3)(17,3)(18,3)(19,3)(24,6)(24,7)(24,8)

Create a BattleshipSearch class This class is responsible for searching the grid for both the carrier and the submarine. (Note: Just reading the results from the input file and omitting the search step will SIGNIFICANTLY REDUCE your grade). You need to read in the coordinates, place the ships, and then independently search for them! You must use a search strategy and will output the text shown at the bottom of the page to the console for each game (with example coordinates from first row of text file). For each game you will systematically use each of the following three search strategies.

Create a family of search strategies. Make sure that you implement the strategy design pattern here.

Horizontal Sweep Strategy: Start at 0,0 and perform a systematic line-by-line sweep through the grid until you have found both ships.

Random Search Strategy: Use the random number generator to randomly check coordinates until you have found both ships.

Strategic Search: Figure out a more efficient search strategy and implement it as the third strategy. See how efficient your approach can be. (Hint: A vertical sweep strategy would be equally as inefficient as (a) so try to think of something better!)

Your battleship search class must systematically use each of the search strategies. While the answer will be the same in each case, the number of cells searched will differ.

Game 1: Strategy: Horizontal Sweep

Number of cells searched: 117 Carrier found: (0,0) to (0,4) Submarine found: (4,15) to (4,17) Strategy: Random Search Number of Cells searched: 490 Carrier found: (0,0) to (0,4) Submarine found: (4,15) to (4,17) Strategy: Strategic Search Number of Cells searched: 82 Carrier found: (0,0) to (0,4) Submarine found: (4,15) to (4,17)