Battleships.py

'''
The algorithm works as follows:
It simply checks all positions, with positions being marked with None (unknown) x (part of a ship) or o (no ship)

Because the description says that ships can't touch (including diagonally) you know for sure that if a position
has the part of a ship that the positions diagonal to it don't, like so:
o.o
.x.
o.o

This is the only tactic that my program uses, although it does check the inner square first 
(with a border of 1 position around it) to increase the chance that positions marked as 
being empty don't fall outside the board
'''
import sys
board = []
TOTAL_SHIPPARTS = 4+2*3+3*2+4*1
hits = 0
LETTERS = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

for x in xrange(10):
	board.append([])
	for y in xrange(10):
		board[x].append(None)

def printBoard():
	print "!"
	for y in xrange(10):
		for x in xrange(10):
			if board[x][y] is "x":
				sys.stdout.write("x")
			else:
				sys.stdout.write("o")
		if y < 9:
			sys.stdout.write("\n")
	sys.exit(0)

def processSquare(x, y):
	global hits
	if board[x][y] is not None:
		return
	sys.stdout.write(LETTERS[x] + str(9-y)+"\n")
	sys.stdout.flush()
	
	answer = raw_input()
	if answer[0] is "x":
		board[x][y] = "x"
		if not (x-1 < 0):
			if not (y-1 < 0):
				board[x-1][y-1] = "o"
			if not (y+1 > 9):
				board[x-1][y+1] = "o"
		
		if not (x+1 > 9):
			if not (y-1 < 0):
				board[x+1][y-1] = "o"
			if not (y+1 > 9):
				board[x+1][y+1] = "o"
		hits = hits + 1
		if hits >= TOTAL_SHIPPARTS:
			printBoard()
	else:
		board[x][y] = "o"
		
for y in xrange(1,9):
	for x in xrange(1,9):
		processSquare(x, y)
for y in xrange(10):
	for x in xrange(10):
		processSquare(x, y)

printBoard()