Battleship Chronicles, Part I

The 2009-2010 academic year was quickly ending, so I needed a worthy activity to wrap up my club/elective/academic team thingy, Computer Team (CompTeam), with a bang. Following the steps of Dr. Nevard, who assigned my Data Structures class an interactive 5-card draw program. Each person in the class had to write an AI to play that game by communicating with a `dealer' (or host) program. Originally, Sam and I planned to do Blackjack with the students, but the activity was brainstormed at the last minute, so we scrapped it. We then looked on TopCoder for more interesting interactive programs and decided on Battleship. Sam wrote up the problem statement, replicated below:

Your task is to implement a program to play the game Battleship. Here is a sample grid:

Carrier    | length 5
Battleship | length 4
Cruiser    | length 3
Submarine  | length 3
Destroyer  | length 2

 |1|2|3|4|5|6|7|8|9|10|
-+-+-+-+-+-+-+-+-+-+--+
A| | | |4| | |3|3|3|  |
-+-+-+-+-+-+-+-+-+-+--+
B| | | |4| | | | | |  |
-+-+-+-+-+-+-+-+-+-+--+
C| | | |4| | | | | |  |
-+-+-+-+-+-+-+-+-+-+--+
D| | | | | | | | | |  |
-+-+-+-+-+-+-+-+-+-+--+
E| | | |2|2|2|2| | |  |
-+-+-+-+-+-+-+-+-+-+--+
F| | | | | | | | |1|  |
-+-+-+-+-+-+-+-+-+-+--+
G| | | | | | | | |1|  |
-+-+-+-+-+-+-+-+-+-+--+
H| | | |5|5| | | |1|  |
-+-+-+-+-+-+-+-+-+-+--+
I| | | | | | | | |1|  |
-+-+-+-+-+-+-+-+-+-+--+
J| | | | | | | | |1|  |
-+-+-+-+-+-+-+-+-+-+--+

You do not know the location of your opponent's ships. Every turn, you will output a location to fire at, and you will be told whether your shot was a hit or a miss, and if it was a hit, which of your opponent's ships you have hit. The first person to sink all of their opponent's ships wins.


Scoring:

There will be a round-robin tournament, where every program will play all other programs k times, for some integer k to be decided. Programs will be awarded 1 point for each victory and 0 points for each loss and will be ranked on how many points they receive. If neither program has won after each program has had 200 calls to fire, no points will be given to either program. 


Implementation:

If you are writing your code in Java, then your files should all be contained in one package which is not the default. If you are writing your code in another language, then compile your code to an .exe file. It is ok if your program requires other files in the same directory. 

Each program will be placed in its own folder, and no program should try to access files in another folder. Programs may create or modify files in their own folder if desired.

You should implement the following pseudocode in your main function:

init()
while (true)
 command = readLine() // Standard input
 if(command = "name")
  printName()
 else if(command = "place")
  placeShips()
 else if(command = "fire")
  fire()
 else if(command = "hits")
  n = readLine()
  processHits(n)
 else if(command = "exit")
  exit(0)

init()
 Initializes your program. 

printName()
 Prints the name of your program to standard output and flushes the buffer.

placeShips()
 Prints a string which represents the locations of your ships and flushes the buffer. Your string will consist of 5 pairs of points which describe the endpoints of each ship, in order. For example, the grid above would be represented by "F9 J9 E4 E7 A4 C4 A7 A9 H4 H5". Ships must be placed horizontal or vertical, must be completely on the grid, cannot overlap, and must have lengths consistent with the table in order. Failure to do so will result in a forfeit for that match. Extra spaces in the output string will be ignored by the parser. 

fire()
 Prints a string which represents where you would like to fire and flushes the buffer. The string will be of the form (row)(column), just like above. For example, to fire at B4, print the string "B4". An incorrectly formatted output or out of bounds output will result in a forfeit. Extra spaces in the output string will be ignored by the parser.

processHits(n)
 n will be a number representing the index of the hit ship in the above table, or 0 if no ship was hit. For example, if n = 2, then you hit your opponent's battleship. Your program should process this data however it likes.


Other Information:

- After every call to fire, there will be a call to hits, even if your program has already won. After this, if a program has won, both programs will be told to exit. 
- Your program cannot get a hit on a square multiple times. If your program fires on a square more than once, it will always be a miss. 
- Please test your code before you send in your final version. 

The competitors seemed pretty excited about it. I also opened it to anyone remotely interested (aka people on my mailing list). For the first few classes, I let them work on their programs. As expected, they got a bit bored on the second or third class.