
#!/usr/bin/env python
#
# BattleShip


import random


#--------------------------Fields------------------------------

emptyField = [ "  _A_B_C_D_E_F_G_H_I_J_",
               " 1|_|_|_|_|_|_|_|_|_|_|",
               " 2|_|_|_|_|_|_|_|_|_|_|",
               " 3|_|_|_|_|_|_|_|_|_|_|",
               " 4|_|_|_|_|_|_|_|_|_|_|",
               " 5|_|_|_|_|_|_|_|_|_|_|",
               " 6|_|_|_|_|_|_|_|_|_|_|",
               " 7|_|_|_|_|_|_|_|_|_|_|",
               " 8|_|_|_|_|_|_|_|_|_|_|",
               " 9|_|_|_|_|_|_|_|_|_|_|",
               "10|_|_|_|_|_|_|_|_|_|_|" ]

TESTcompsField = [ "  _A_B_C_D_E_F_G_H_I_J_",
               " 1|_|_|_|o|_|_|o|_|_|_|",
               " 2|_|_|_|o|_|_|o|_|_|o|",
               " 3|_|o|_|o|_|_|o|_|_|_|",
               " 4|_|_|_|o|_|_|_|_|_|_|",
               " 5|_|_|_|_|_|_|_|_|_|o|",
               " 6|_|_|_|_|_|o|o|o|_|_|",
               " 7|o|_|_|_|_|_|_|_|_|_|",
               " 8|_|_|_|_|_|_|_|_|_|_|",
               " 9|_|_|o|o|_|_|_|o|_|_|",
               "10|_|_|_|_|_|_|_|o|_|_|" ]

TESTyourField  = [ "  _A_B_C_D_E_F_G_H_I_J_",
               " 1|_|o|_|_|_|_|_|o|_|_|",
               " 2|_|_|_|_|_|_|_|_|_|o|",
               " 3|_|_|_|o|o|o|o|_|_|_|",
               " 4|_|_|_|_|_|_|_|_|_|_|",
               " 5|_|o|o|o|_|_|_|_|_|o|",
               " 6|_|_|_|_|_|_|_|_|_|o|",
               " 7|o|_|_|_|_|_|_|_|_|_|",
               " 8|o|_|_|o|_|_|_|o|_|_|",
               " 9|_|_|_|_|_|_|_|o|_|_|",
               "10|_|o|o|_|_|_|_|o|_|_|" ]

compsField = [ "  _A_B_C_D_E_F_G_H_I_J_",
               " 1|_|_|_|_|_|_|_|_|_|_|",
               " 2|_|_|_|_|_|_|_|_|_|_|",
               " 3|_|_|_|_|_|_|_|_|_|_|",
               " 4|_|_|_|_|_|_|_|_|_|_|",
               " 5|_|_|_|_|_|_|_|_|_|_|",
               " 6|_|_|_|_|_|_|_|_|_|_|",
               " 7|_|_|_|_|_|_|_|_|_|_|",
               " 8|_|_|_|_|_|_|_|_|_|_|",
               " 9|_|_|_|_|_|_|_|_|_|_|",
               "10|_|_|_|_|_|_|_|_|_|_|" ]

yourField  = [ "  _A_B_C_D_E_F_G_H_I_J_",
               " 1|_|_|_|_|_|_|_|_|_|_|",
               " 2|_|_|_|_|_|_|_|_|_|_|",
               " 3|_|_|_|_|_|_|_|_|_|_|",
               " 4|_|_|_|_|_|_|_|_|_|_|",
               " 5|_|_|_|_|_|_|_|_|_|_|",
               " 6|_|_|_|_|_|_|_|_|_|_|",
               " 7|_|_|_|_|_|_|_|_|_|_|",
               " 8|_|_|_|_|_|_|_|_|_|_|",
               " 9|_|_|_|_|_|_|_|_|_|_|",
               "10|_|_|_|_|_|_|_|_|_|_|" ]

yourShots =  [ "  _A_B_C_D_E_F_G_H_I_J_",
               " 1|_|_|_|_|_|_|_|_|_|_|",
               " 2|_|_|_|_|_|_|_|_|_|_|",
               " 3|_|_|_|_|_|_|_|_|_|_|",
               " 4|_|_|_|_|_|_|_|_|_|_|",
               " 5|_|_|_|_|_|_|_|_|_|_|",
               " 6|_|_|_|_|_|_|_|_|_|_|",
               " 7|_|_|_|_|_|_|_|_|_|_|",
               " 8|_|_|_|_|_|_|_|_|_|_|",
               " 9|_|_|_|_|_|_|_|_|_|_|",
               "10|_|_|_|_|_|_|_|_|_|_|" ]



#-----------------------Other Variables---------------------

totalSpots = 20
compsSpots = totalSpots
usersSpots = totalSpots
turn = "user"
sunk = 0
target = ""
possibleShots = []

#-------------------------Functions-------------------------

def printField( field ):
	for line in field:
		print line



def getVertical( shot ):
	if( len(shot) == 3 ):
		return 10
	else:
		return ord(shot[1]) - ord('0')


def getHorizontal( shot ):
	return 3 + (ord(shot[0]) - ord('a'))*2



def isShot( shot ):
	if( len(shot) < 2 ):
		return 0
	if( len(shot) > 2 ):
		if( len(shot) == 3 ):
			if( shot[0] >= 'a' and shot[0] <= 'j' and shot[1] == '1' and shot[2] == '0' ):
				return 1
			elif( shot[2] >= 'a' and shot[2] <= 'j' and shot[0] == '1' and shot[1] == '0' ):
				return 1
			else:
				return 0
		else:
			return 0
	if( ( ((shot[0] < '1' and shot[0] > '9') and (shot[0] < 'a' and shot[0] > 'j')) ) and  ((shot[1] < '1' and shot[1] > '9') and (shot[1] < 'a' and shot[1] > 'j')) ):
		return 0
	else:
		return 1

def formatShot( shot ):					#precondition: isShot(shot) == 1
	if( shot[0] >= 'a' and shot[0] <= 'j' ):
		return shot
	if( len(shot) == 2 ):
		shot = "" + shot[1] + shot[0]
		return shot
	shot = "" + shot[2] + shot[0] + shot[1]
	return shot

def askForShot():
	print "Your move, tough guy!: "
	shot = raw_input()
	while( isShot(shot) == 0 ):
		print "Invalid. Try again: "
		shot = raw_input()
	return shot



#returns 1 if a ship is hit
#returns 0 if an empty spot is hit
#returns -1 if the spot has already been shot at
def processShot( shot, field ):
	h_index = getHorizontal( shot )
	v_index = getVertical( shot )
	spot = field[v_index][h_index]
	if( spot == 'o' ):
		field[v_index] = field[v_index][:h_index] + "X" + field[v_index][h_index+1:]
		return 1
	if( spot == '.' ):
		return -1
	if( spot == '_' ):
		return 0



#returns 1 if a ship is hit
#returns 0 if an empty spot is hit
#returns -1 if the spot has already been shot at
def checkShot( shot, field ):
	h_index = getHorizontal( shot )
	v_index = getVertical( shot )
	spot = field[v_index][h_index]
	if( spot == 'o' ):
		return 1
	if( spot == '.' or spot == 'X' ):
		return -1
	if( spot == '_' ):
		return 0



def generateShot():
	v = random.randint( 1, 10 )
	h = chr( ord('a') + random.randint( 1, 10 ) - 1 )
	return "" + h + str(v)



def shootSameShip( shot, field ):
	v = getVertical( shot )
	h = getHorizontal( shot )
	directions = []
	global possibleShots
	l_shot = getShotInDir(shot,"l")
	r_shot = getShotInDir(shot,"r")
	u_shot = getShotInDir(shot,"u")
	d_shot = getShotInDir(shot,"d")
	if( isShot(l_shot) == 1 and checkShot(l_shot, field) != -1 ):	directions.append("l")
	if( isShot(r_shot) == 1 and checkShot(r_shot, field) != -1 ):	directions.append("r")
	if( isShot(u_shot) == 1 and checkShot(u_shot, field) != -1 ):	directions.append("u")
	if( isShot(d_shot) == 1 and checkShot(d_shot, field) != -1 ):	directions.append("d")
	if((isShot(l_shot) == 1 and getSpot(l_shot,field) == "X" ) or ( isShot(r_shot) == 1 and  getSpot(r_shot,field) == "X" )):
		if( "u" in directions ):	directions.remove("u")
		if( "d" in directions ):	directions.remove("d")

	if((isShot(u_shot) == 1 and getSpot(u_shot,field) == "X" ) or ( isShot(d_shot) == 1 and  getSpot(d_shot,field) == "X" )):
		if( "l" in directions ):	directions.remove("l")
		if( "r" in directions ):	directions.remove("r")

	for dir in directions:
		newShot = getShotInDir(shot, dir)
		if( isShot(newShot) == 1 and checkShot(newShot,field) != -1 and newShot not in possibleShots ):
			possibleShots.append( newShot )

	for s in possibleShots:
		if(getSpot(s,field) == "."):	possibleShots.remove(s)
	ind = random.randint(0, len(possibleShots)-1)
	shot = possibleShots[ind]
	possibleShots.remove(shot)
	return shot



def getShotInDir( shot, direction ):
	h = shot[0]
	v = getVertical( shot )

	if( direction == "r" ):
		if( h >= 'j' ):
			return ""
		else:
			return "" + chr(ord(h)+1) + str(v)
	if( direction == "l" ):
		if( h <= 'a' ):
			return ""
		else:
			return "" + chr(ord(h)-1) + str(v)
	if( direction == "u" ):
		if( v <= 1 ):
			return ""
		else:
			return "" + h + str(v-1)
	if( direction == "d" ):
		if( v >= 10 ):
			return ""
		else:
			return "" + h + str(v+1)



def getSpot( shot, field ):
	v = getVertical( shot )
	h = getHorizontal( shot )
	return "" + field[v][h]


#returns 1 if the ship is sinks
#returns 0 otherwise
def checkIfSunk( shot, field ):
	right = 1
	left = 1
	up = 1
	down = 1
	h = getHorizontal( shot )
	v = getVertical( shot )

	if( h < 21 and field[v][h + 2] == 'o' ):
		return 0
	if( field[v][h - 2] == 'o' ):
		return 0
	if( v < 10 and field[v+1][h] == 'o' ):
		return 0
	if( field[v-1][h] == 'o' ):
		return 0

	if( h < 21 and field[v][h+2] == 'X' ):
		right = checkIfSunkDir( getShotInDir( shot, "r" ), field, "r" )
	if( h > 3 and field[v][h-2] == 'X' ):
		left = checkIfSunkDir( getShotInDir( shot, "l" ), field, "l" )
	if( v > 1 and field[v-1][h] == 'X' ):
		up = checkIfSunkDir( getShotInDir( shot, "u" ), field, "u" )
	if( v < 10 and field[v+1][h] == 'X' ):
		down = checkIfSunkDir( getShotInDir( shot, "d" ), field, "d" )
	return right*left*up*down


#used by CheckIfSunk, this method is recursive
def checkIfSunkDir( shot, field, direction ):
	h = getHorizontal( shot )
	v = getVertical( shot )

	newShot = getShotInDir( shot, direction )
	if( isShot(getShotInDir(newShot, direction)) == 1 and getSpot( newShot, field ) == 'X' ):
		return checkIfSunkDir( newShot, field, direction )
	elif( getSpot( newShot, field ) == 'o' ):
		return 0
	else:
		return 1


def dotDiagnal( shot, field ):
	v_index = getVertical( shot )
	h_index = getHorizontal( shot )
	if( v_index < 10 and h_index < 21 ):
		field[v_index+1] = field[v_index+1][:h_index+2] + "." + field[v_index+1][h_index+3:]
	if( v_index < 10 and h_index > 3 ):
		field[v_index+1] = field[v_index+1][:h_index-2] + "." + field[v_index+1][h_index-1:]
	if( v_index > 1 and h_index < 21 ):
		field[v_index-1] = field[v_index-1][:h_index+2] + "." + field[v_index-1][h_index+3:]
	if( v_index > 1 and h_index > 3 ):
		field[v_index-1] = field[v_index-1][:h_index-2] + "." + field[v_index-1][h_index-1:]



def dotAcross( shot, field ):
	v_index = getVertical( shot )
	h_index = getHorizontal( shot )
	if( v_index < 10 and field[v_index+1][h_index] == "_" ):
		field[v_index+1] = field[v_index+1][:h_index] + "." + field[v_index+1][h_index+1:]
	if( v_index > 1 and field[v_index-1][h_index] == "_" ):
		field[v_index-1] = field[v_index-1][:h_index] + "." + field[v_index-1][h_index+1:]
	if( h_index < 21 and field[v_index][h_index+2] == "_" ):
		field[v_index] = field[v_index][:h_index+2] + "." + field[v_index][h_index+3:]
	if( h_index > 3 and field[v_index][h_index-2] == "_" ):
		field[v_index] = field[v_index][:h_index-2] + "." + field[v_index][h_index-1:]


def dotAlong( shot, field ):
	directions = ["r", "l", "u", "d"]
	for dir in directions:
		s = getShotInDir( shot, dir )
		if( isShot( s ) == 1 ):
			if( getSpot(s, field) == "X" ):
				dotAlongDir( s, field, dir )
			elif( getSpot(s, field) == "_" ):
				addToField( ".", s,  field )



#takes shot as the place to dot or go in direction dir=20
#(not as the place from which to start and go in the direction)
def dotAlongDir( shot, field, dir ):
	if( isShot(shot) == 0 ):
		return
	if( getSpot(shot, field) == "X" ):
		dotAlongDir( getShotInDir(shot,dir), field, dir )
	elif( getSpot(shot, field) == "_"):
		addToField( ".", shot, field )


def addToField( mark, shot, field ):
	v_index = getVertical( shot )
	h_index = getHorizontal( shot )
	field[v_index] = field[v_index][:h_index] + mark + field[v_index][h_index+1:]



#returns a random direction - "r","l","u","d"
def randDir():
	dir = ["r","l","u","d"]
	i = random.randint(0,3)
	return dir[i]



def generateField( field ):
	ships = { "4.1":["","","",""], "3.1":["","",""], "3.2":["","",""], "2.1":["",""], "2.2":["",""], "2.3":["",""], "1.1":[""], "1.2":[""], "1.3":[""], "1.4":[""] }
	shot = ""
	dir = ""
	ind = 1
	for ship in ships.keys():
		ok = 0
		while( ok == 0 ):
			shot = generateShot()
			dir = randDir()
			pos = placeShipDir( len(ships[ship]), shot, dir, field )
			if( len(pos) > 0 ):
				ships[ship] = pos
				ok = 1
		for s in ships[ship]:
			addToField("X", s, field)
			dotDiagnal( s, field )
		dotAlong( s, field )

	y = 0
	while( y < len(field) ):
		x = 0
		while( x < len(field[y]) ):
			if( field[y][x] == '.' ):
				field[y] = field[y][:x] + "_" + field[y][x+1:]
			elif( field[y][x] == "X" ):
				field[y] = field[y][:x] + "o" + field[y][x+1:]
			x = x+1
		y = y+1



def manuallyMakeField( field ):
	ships = { "4.1":["","","",""], "3.1":["","",""], "3.2":["","",""], "2.1":["",""], "2.2":["",""], "2.3":["",""], "1.1":[""], "1.2":[""], "1.3":[""], "1.4":[""] }
	shot = ""
	dir = ""
	ind = 1
	for ship in ships.keys():
		ok = 0
		while( ok == 0 ):
			shot = raw_input( "Place ship of length " + str(len(ships[ship])) + " here: " )
			shot = formatShot( shot )
			if( len(ships[ship]) == 1 ):	dir = randDir()
			else:				dir = raw_input( "In direction: " )
			pos = placeShipDir( len(ships[ship]), shot, dir, field )
			if( len(pos) > 0 ):
				ships[ship] = pos
				ok = 1
		for s in ships[ship]:
			addToField("X", s, field)
			dotDiagnal( s, field )
		dotAlong( s, field )
		printField( field )

	y = 0
	while( y < len(field) ):
		x = 0
		while( x < len(field[y]) ):
			if( field[y][x] == '.' ):
				field[y] = field[y][:x] + "_" + field[y][x+1:]
			elif( field[y][x] == "X" ):
				field[y] = field[y][:x] + "o" + field[y][x+1:]
			x = x+1
		y = y+1



#head = location of beginning of the ship in the form of a shot
def placeShipDir( length, head, dir, field ):
	position = []
	while( length > 0 ):
		if( isShot(head) == 1 and getSpot(head, field) == "_" ):
			position.append( head )
			head = getShotInDir( head, dir )
			length = length-1
		else:	return []
	return position



#----------------------Test---------------------------





#----------------------Main---------------------------

generateField( compsField )
ans = raw_input("Would you like to place your ships mannually? (y/n): ")
if( ans == "y" or ans == "Y" ):
	print "Aye, aye, captain! Let us position our armada!"
	manuallyMakeField( yourField )
else:
	print "Aye, aye, captain! The ships will be placed as we planned before!"
	generateField( yourField )

print "\n\n\n   --Computer's field--"
for line in yourShots:
	print line
print "\n   -----Your Field-----"
for line in yourField:
	print line


while( usersSpots > 0 and compsSpots > 0 ):
	while( turn == "user" ):
		shot = askForShot()
		if (shot == "qq"):
			shot = "a1"
			usersSpots = 0
			turn = "computer"
		shot = formatShot(shot)
		hit = processShot(shot, compsField)
		if( hit != 0 ):
			if( hit == 1 ):
				compsSpots = compsSpots - 1
				addToField( "X", shot, yourShots )
				print "Nicely done!"
				sunk = checkIfSunk( shot, compsField )
				if( sunk == 1 ):
					print "Down she goes!"
					dotAcross( shot, compsField )
					dotDiagnal( shot, compsField )
					dotAcross( shot, yourShots )
					dotDiagnal( shot, yourShots )
					dotAlong( shot, compsField )
					dotAlong( shot, yourShots )
				else:
					print "Let us use this confusion and fire again!"
					dotDiagnal( shot, compsField )
			if( hit == -1):
				print "No need to fire there, capt'n! Ye know better than that!"
		else:
			addToField( ".", shot, yourShots )
			addToField( ".", shot, compsField )
			turn = "computer"
		printField( yourShots )

	while( turn == "computer" ):
		if( target == "" ):	shot = generateShot()
		else:			shot = shootSameShip( target, yourField )
		hit = processShot( shot, yourField )
		if( hit == 1 ):
			print "Computer shoots: " + shot
			print "...and hits."
			target = shot
			usersSpots = usersSpots - 1
			addToField( "X", shot, yourField )
			sunk = checkIfSunk( shot, yourField )
			dotDiagnal( shot, yourField )
			if( sunk == 1 ):
				dotAcross( shot, yourField )
				dotAlong( shot, yourField )
				print "They got us!"
				target = ""
				possibleShots = []
			else:
				print "We're on fire, capt'n!"
		elif( hit == 0 ):
			print "Computer shoots: " + shot
			print "...and misses!"
			addToField( ".", shot, yourField )
			turn = "user"
		printField( yourField )
		print "sunk: ", sunk
		raw_input("Press Enter")

