# Battleship algorithm

Im looking to improve my search algorithm in my battleship game. Code is not perfect but would appreciate any suggestions or recommendations.

Running the simulation using a 100x100 grid (10,000 possible locations) Im averaging ~30% accuracy.

Games played 500 Average = 0.31108

Im using a forward and backwards diagonal search approach. The search diagonal locations by moving forward and backwards by the using the maxShipSize that is still active. As a ship is sunk the maxShipSize changes.

If a ship is hit i check a cross pattern (left,up,right and down). When a ship is hit more then once a sequential pattern search occurs.

battleship.py

# -*- coding: utf-8 -*-
from __future__ import division
import numpy
import operator
import commands
import random
import sys
import os
from time import sleep
from grid import grid
from fleet import fleet

#setupNavy
#Purpos: To place our ships on the grid
#Receives: setupSelection- either manual or random
#          gridClass
#          sortedShipList
#Return:
def setupNavy(setupSelection,gridClass,sortedShipList):
used="no"
shipCoordList=[]
for shipData in sortedShipList:
shipName=shipData[0]
shipSize=shipData[1]
if setupSelection=="manual":
header= "Ship placement: %s size is: %s\n"%(shipName,shipSize)
con="yes"
while con=="yes":
if setupSelection=="manual":
start=raw_input("Enter start point: ")
else:
randomX=random.randrange(0,gridClass.xGridSize)
randomY=random.randrange(0,gridClass.yGridSize)
xLetter=gridClass.alphDict[randomX]
start="%s%d"%(xLetter,randomY)
coordStatus=gridClass.checkDataPointValue(start)
if coordStatus=="E":
con="no"
if setupSelection=="manual":
placement=raw_input("Place Vertical (V) or Horizontal (H): ")
else:
placement=random.choice("VH")
end=gridClass.determineEndPoint(start,shipSize,placement)
if end=="F":
if setupSelection=="manual":
error= "Datapoint: %s will place %s off the grid \n"% (start,shipName)
sys.stdout.write(error)
used="yes"
else:
shipCoordList=gridClass.determineFullLocation(start,end)
gridClass.shipLocationDict[shipName]=shipCoordList
for coord in shipCoordList:
coordList=coord.split(',')
dataPoint="%s%s"%(gridClass.alphDict[int(coordList[0])],coordList[1])
coordStatus=gridClass.checkDataPointValue(dataPoint)
if coordStatus=='T':
if setupSelection=="manual":
error= "Datapoint: %s is already used \n"% dataPoint
sys.stdout.write(error)
used="yes"
if used=="no":
gridClass.gridValuesUsed+=shipCoordList
else:
if setupSelection=="manual":
error= "Datapoint: %s is already used \n"% dataPoint
sys.stdout.write(error)
con="yes"
if used=="yes":
con="yes"
used="no"

os.system('clear; history -c')

gridClass.shipPlacement(start,end,shipCoordList)
gridDict=gridClass.populateGrid()
if setupSelection=="manual":
gridClass.displayGrid()

sleep(0.25)
os.system('clear; history -c')
return

def determineNextAttackInSeq (attackerGridClass):
startLocation="";xHitList=[];yHitList=[]
for hit in attackerGridClass.hitList:
hitCoordList=hit.split(',')
xHitList.append(hitCoordList[0])
yHitList.append(hitCoordList[1])
if len(set(xHitList))>1:
nextY=yHitList[0]
xHitList=sorted(xHitList)
nextBegX=int(xHitList[0])-1
nextEndX=int(xHitList[len(xHitList)-1])+1
begCoord="%s,%s"%(nextBegX,nextY)
lastCoord="%s,%s"%(nextEndX,nextY)
if begCoord in attackerGridClass.attackList:
startLocation=begCoord
elif lastCoord in attackerGridClass.attackList:
startLocation=lastCoord
#Vertical order
elif len(set(yHitList))>1:
nextX=xHitList[0]
yHitList=sorted(yHitList)
nextBegY=int(yHitList[0])-1
nextEndY=int(yHitList[len(yHitList)-1])+1
begCoord="%s,%s"%(nextX,nextBegY)
lastCoord="%s,%s"%(nextX,nextEndY)
if begCoord in attackerGridClass.attackList:
startLocation=begCoord
elif lastCoord in attackerGridClass.attackList:
startLocation=lastCoord
return startLocation

startList=startLocation.split(',')
xValue=int(startList[0])
yValue=int(startList[1])
#Convert to alpha numeric for display purposes
#ie. 2,13 is C13
start="%s%s"%(attackerGridClass.alphDict[xValue],yValue)
possVertLocList=[]
possHorzLocList=[]
maxGridSize=attackerGridClass.xGridSize
minShipSize=defenderFleetClass.minShipSize
possVertLocList.append(startLocation)
possHorzLocList.append(startLocation)
iteratorSeq=0
startX=xValue
startY=yValue
while iteratorSeq < minShipSize:
iteratorSeq=iteratorSeq+1
#Veritcal locations
possY=int(startY)+iteratorSeq
if possY<maxGridSize and possY>=0:
possVertLocBelow="%s,%s"%(startX,possY)
possVertLocList.append(possVertLocBelow)
possY=int(startY)-iteratorSeq
if possY<maxGridSize and possY>=0:
possVertLocAbove="%s,%s"%(startX,possY)
possVertLocList.append(possVertLocAbove)
#Horziontal locations
possX=int(startX)+iteratorSeq
if possX<maxGridSize and possX>=0:
possHorzLocRight="%s,%s"%(possX,startY)
possHorzLocList.append(possHorzLocRight)
possX=int(startX)-iteratorSeq
if possX<maxGridSize and possX>=0:
possHorzLocLeft="%s,%s"%(possX,startY)
possHorzLocList.append(possHorzLocLeft)
for coord in attackerGridClass.missedList:
if coord in possVertLocList:
possVertLocList.remove(coord)
elif coord in possHorzLocList:
possHorzLocList.remove(coord)

possVertLocList= sorted(possVertLocList)

ySList=[]
for coordS in possVertLocList:
xySlist=coordS.split(',')
ySList.append(xySlist[1])
ySList.sort(key=int)
numSeq=0
prev=-1
count=0
ySeqList=[]
for ySValue in ySList:
ySValue=int(ySValue)
if prev==ySValue:
numSeq=numSeq+1
prev=prev+1
else:
prev=int(ySValue)+1
numSeq=1
ySeqList.append(numSeq)

possHorzLocList=sorted(possHorzLocList)
xSList=[]
for coordS in possHorzLocList:
xySlist=coordS.split(',')
xSList.append(xySlist[0])
xSList.sort(key=int)
numSeq=0
prev=-1
count=0
xSeqList=[]
for xSValue in xSList:
xSValue=int(xSValue)
if prev==xSValue:
numSeq=numSeq+1
prev=prev+1
else:
prev=int(xSValue)+1
numSeq=1
xSeqList.append(numSeq)

if minShipSize not in xSeqList and minShipSize not in ySeqList:
attackerGridClass.blockedCoordList.append(startLocation)
return attackerGridClass.blockedCoordList

def findAroundCoords(attackerGridClass,startLocation):
startList=startLocation.split(',')
xValue=int(startList[0])
yValue=int(startList[1])
left=xValue-1
below=yValue-1
right=xValue+1
above=yValue+1

if left>=0:
leftValue="%s,%s"%(left,yValue)
leftLetter="%s%s"%(attackerGridClass.alphDict[left],yValue)
if leftValue not in attackerGridClass.attackList and leftValue not in attackerGridClass.hitList and leftValue not in attackerGridClass.missedList:
attackerGridClass.attackList.append(leftValue)
if below>=0:
belowValue="%s,%s"%(xValue,below)
belowLetter="%s%s"%(attackerGridClass.alphDict[xValue],below)
if belowValue not in attackerGridClass.attackList and belowValue not in attackerGridClass.hitList and belowValue not in attackerGridClass.missedList:
attackerGridClass.attackList.append(belowValue)
if right<=(attackerGridClass.xGridSize-1):
rightValue="%s,%s"%(right,yValue)
rightLetter="%s%s"%(attackerGridClass.alphDict[right],yValue)
if rightValue not in attackerGridClass.attackList and rightValue not in attackerGridClass.hitList and rightValue not in attackerGridClass.missedList:
attackerGridClass.attackList.append(rightValue)
if above<=(attackerGridClass.yGridSize-1) or above==attackerGridClass.yGridSize-1:
aboveValue="%s,%s"%(xValue,above)
aboveLetter="%s%s"%(attackerGridClass.alphDict[xValue],above)
if aboveValue not in attackerGridClass.attackList and aboveValue not in attackerGridClass.hitList and aboveValue not in attackerGridClass.missedList:
attackerGridClass.attackList.append(aboveValue)
return  attackerGridClass.attackList

def checkShipStatus(attackerGridClass,defenderGridClass,defenderFleetClass):
#Determine if the attacked ship is sunk.
for ship, locationList in defenderGridClass.shipLocationDict.iteritems():
hitsTaken=0
shipSize=defenderFleetClass.shipFleetDict[ship]
if defenderFleetClass.shipStatusDict[ship]=="active":
for location in locationList:
if location in attackerGridClass.attackedCoordList:
hitsTaken+=1
if hitsTaken==shipSize:
print "%s sunk a %s"%(whosTurn,ship)
sleep(1.25)
attackerGridClass.blockedCoordList=[]
defenderFleetClass.shipStatusDict[ship]="sunk"
defenderFleetClass.numberSunkShips+=1
attackerGridClass.attackNumber=0
defenderFleetClass.minShipSize=defenderFleetClass.determineMinShipSize()
if len(attackerGridClass.hitList)>shipSize:
attackerGridClass.attackList=[]
tmpHitList=sorted(attackerGridClass.hitList)
firstCoord=tmpHitList[0]
findAroundCoords(attackerGridClass,firstCoord)
lastCoord=tmpHitList[len(tmpHitList)-1]
findAroundCoords(attackerGridClass,lastCoord)
attackerGridClass.hitList=[]

else:
attackerGridClass.attackList=[]
attackerGridClass.hitList=[]
#Empty attackList... Possiable problem!!!
#print "*************************"
#for extraCoord in attackerGridClass.attackList:
#goodCoord=determineNextAttackInSeq(attackerGridClass)
#print goodCoord
#print attackerGridClass.attackList
return

def attackShip(whosTurn,attackerGridClass,defenderGridClass,defenderFleetClass):
newAttack="Y"
numShipsInFleet=len(defenderFleetClass.shipStatusDict)
while newAttack=="Y":
#Person vs computer. We prompt for location to attack
if whosTurn=="player":
attackCoords=raw_input("Input attack coordinates (ex B2): ")
xLetter=attackCoords[:1]
xValue=defenderGridClass.alphList.index(xLetter)
yValue=int(attackCoords[1:])
startLocation="%s,%s"%(xValue,yValue)
else:
#If we already have a planned attacked list then get the next one
#The attackList is a educated guess where we should attack next
#based on previous attacks.
print attackerGridClass.attackList
if len(attackerGridClass.attackList)!=0:
attackerGridClass.attackList=sorted(attackerGridClass.attackList)

################################################################
# If we have a hit we want to check what the next sequitnal order would be
startLocation=determineNextAttackInSeq (attackerGridClass)

if startLocation=="":
#Get first location in attack list
print "nexxxxt"
startLocation=attackerGridClass.attackList[0]
print startLocation
################################################################
end=''
else:
searchListEmpty="T"
while searchListEmpty=="T":
#If we dont have a searchList then lets build one.
#The searchList is some logical search. We built that in defineSearchList
if len(attackerGridClass.searchList)==0:
#Get the max size of active ships.
#The maxShipSize is used in our search algorithm
defenderFleetClass.maxShipSize=defenderFleetClass.determineMaxShipSize()
#defineSearchList is a digonal search
attackerGridClass.searchList=attackerGridClass.defineSearchList(defenderFleetClass.maxShipSize,attackerGridClass.attackNumber)
attackerGridClass.attackNumber+=1
#Remove location if we have already missed/hit that spot
attackerGridClass.searchList=list(set(attackerGridClass.searchList) - set(attackerGridClass.missedList))
attackerGridClass.searchList=list(set(attackerGridClass.searchList) - set(attackerGridClass.hitList))

if len(attackerGridClass.searchList)>0:
startLocation=random.choice(attackerGridClass.searchList)
else:
startLocation=random.choice(attackerGridClass.validPoints)
else:
searchListEmpty="F"
startLocation=random.choice(attackerGridClass.searchList)
#Randomly select a valid point from our searchList
#startLocation=random.choice(attackerGridClass.searchList)

#######################################################################################################
#We have our Attack location at this point.
startList=startLocation.split(',')
xValue=int(startList[0])
yValue=int(startList[1])
#Convert to alpha numeric for display purposes
#ie. 2,13 is C13
start="%s%s"%(attackerGridClass.alphDict[xValue],yValue)
########################################################################################################
#BREAKING
########################################################################################################

#Cleanup some of our lists.
#Remove our attack from our validPoint
#Remove our attack from our attacklist
if startLocation in attackerGridClass.attackList:
attackerGridClass.attackList.remove(startLocation)
#Remove our attack from our search list
if startLocation in attackerGridClass.searchList:
attackerGridClass.searchList.remove(startLocation)

#if startLocation not in attackerGridClass.attackedCoordList and startLocation not in atta
if startLocation in attackerGridClass.blockedCoordList:
pass
elif startLocation not in attackerGridClass.attackedCoordList:
attackerGridClass.attackedCoordList.append(startLocation)
newAttack="N"
#if attack location is in the defenders values used then its a hit
if startLocation in defenderGridClass.gridValuesUsed:
print "Attacking at %s (%s)" %(start,startLocation)
print "BOOM!! Direct Hit"
print attackerGridClass.attackList
sleep(1.25)
os.system('clear; history -c')
hit='\033[1;31m×\033[1;m'
defenderHit='\033[1;31m×\033[1;m'

#Displays when a enemys ship is hit.
attackerGridClass.gridValuesAttacked[xValue][yValue]="[%s]"%hit
#Displays when a ship is hit. shows an x in the place of the ship
defenderGridClass.gridValues[xValue][yValue]="[%s]"%defenderHit

#Add or attack locatio to our hit list
attackerGridClass.hitList.append(startLocation)
findAroundCoords(attackerGridClass,startLocation)
if startLocation in attackerGridClass.validPoints:
attackerGridClass.validPoints.remove(startLocation)

#############################################################################

#############################################################################
#Determine if the attacked ship is sunk.
checkShipStatus(attackerGridClass,defenderGridClass,defenderFleetClass)

#############################################################################
attackerGridClass.blockedCoordList=[]

else:
print "Attacking at %s (%s)" %(start,startLocation)
attackerGridClass.missedList.append(startLocation)
attackerGridClass.attackedCoordList.append(startLocation)
if startLocation in attackerGridClass.validPoints:
attackerGridClass.validPoints.remove(startLocation)
newAttack="N"
print "Missed....."

sleep(1.25)
os.system('clear; history -c')
#attackResult="[M]"
#miss='ø'
miss='\033[1;30mø\033[1;m'
attackResult="[%s]"%miss
attackerGridClass.gridValuesAttacked[xValue][yValue]="[%s]"%miss
attackerGridClass.blockedCoordList=[]

else:
hitOrMiss="Miss"
if startLocation in attackerGridClass.hitList:
hitOrMiss="HIT"
if whosTurn=="player":
print "You already attacked %s%d which was a %s "%(xLetter,yValue,hitOrMiss)
if defenderFleetClass.numberSunkShips==numShipsInFleet:
gameOver(attackerGridClass.gridName)
displayGameStats(xGrid)
sys.exit()
return
return

def determineMaxMoves(xGrid,yGrid,player):
i=0;turnList=[]
maxTurns=(xGrid*yGrid)*2
while i < maxTurns:
if i%2==0:
turnList.append(player)
else:
turnList.append('Joshua')
i+=1
return turnList

def gameOver(winner):
if winner=="USA":
print "\n******** %s WINS******** \n" %winner
#print u'{:─^10}'.format(u'')

print """
____________________________________________
|* * * * * * * * * * |_______________________|
|* * * * * * * * * * |_______________________|
|* * * * * * * * * * |_______________________|
|* * * * * * * * * * |_______________________|
|* * * * * * * * * * |_______________________|
|____________________________________________|
|____________________________________________|
|____________________________________________|
|____________________________________________|
|____________________________________________|
"""
else:
print "Better luck next time..  %s WINS \n" %winner
print "GAME OVER"

def displayGameStats(xsize):
print "      Results  \n"

print "%s BATTLEFIELD"% enemyGridClass.gridName
enemyGridClass.populateGrid()
enemyGridClass.displayGrid()
print "\n"
for shipName,shipStatus in enemyFleetClass.shipStatusDict.iteritems():
print shipName,shipStatus
print "\n"

print "%s BATTLEFIELD"% myGridClass.gridName
myGridClass.populateGrid()
myGridClass.displayGrid()

print "\n"
for shipName,shipStatus in myFleetClass.shipStatusDict.iteritems():
print shipName,shipStatus
print "\n"
possiableAttacks=xsize * xsize
percentage=enemyGridClass.attackCounter/possiableAttacks
print "Total Number of locations: %s"%possiableAttacks
print "Number of attacks: %s"%enemyGridClass.attackCounter

print "Percent of accuracy: %s"%percentage
print "\n"

def displayMessage(msg):
for letter in msg:
sys.stdout.write(letter)
sys.stdout.flush()
sleep(.085)

######################################################################################
#Display welcome message... Start of game. Meaningless messages just for fun.
user=commands.getoutput("whoami")
msg= "Greetings %s  my name is Joshua.. Shall we play a game? " % user
#displayMessage(msg)
#playGame=raw_input("Y or N ")
playGame="Y"
if playGame.upper()=="Y":
msg="Number of players 0 or 1:"
#displayMessage(msg)

#Determine number of players.
#0 Computer vs Computer
#1 Person vs Computer
#numberOfPlayers=int(raw_input(" "))
numberOfPlayers=0
if numberOfPlayers==0:
player="Professor Flakner"
else:
player=user
#displayMessage(msg)
#sleep(2.0)
msg="My apologies.\nThat game has been removed from my system. Lets play BattleShip\n\n"
#displayMessage(msg)
countryList=['China','Russia','SouthKorea','India','France','Mexico','Taiwan','Turkey','NorthKorea']
if numberOfPlayers==1:
msg="Which country would you like to play?\n"
displayMessage(msg)
for country in countryList:
msg="%s \n"%country
displayMessage(msg)
enemy=raw_input(": ")
msg="Very well.\n"
#displayMessage(msg)
#for i in range(21):
#    sys.stdout.write('\r')
#    sys.stdout.write("[%-20s] %d%%" % ('='*i, 5*i))
#    sys.stdout.flush()
#    sleep(0.25)
#print "\n\n"
else:
msg="A Strange Game.\nThe only winning move is not to play..\nHow about a nice game of chess.."
displayMessage(msg)
sys.exit()

################################################################################################
## Define the size of the Grid

#gridSelection=raw_input("Would you like to define the size of of the grid ('Y' or 'N')? " )
gridSelection="N"
if gridSelection.upper()=="Y":
inputValuesValid="False"
while inputValuesValid=="False":
gridSize=int(raw_input("Input size of X and Y axis (Min:6  Max:17576)? " ))
if gridSize <6:
print "Biggest ship is 6 units.. Will not fit on grid."
if gridSize >17576:
print "Nah dude..Max x and y xis size is 26  "
#If the grid size is in range then lets proceed
if gridSize >6  or gridSize <= 17576:
inputValuesValid="True"
xGrid=gridSize
yGrid=gridSize
else:
#Default Grid size
xGrid=16
yGrid=16

################################################################################################
#Built a list of "whos turn it is".
#For example
#['Professor Flakner','Joshua', 'Professor Flakner', 'Joshua']
turnList=determineMaxMoves(xGrid,yGrid,player)
################################################################################################
#Initalize our grid

myGridClass=grid('USA',xGrid,yGrid)
if numberOfPlayers==0:
enemyGridClass=grid(random.choice(countryList),xGrid,yGrid)
else:
enemyGridClass=grid(enemy,xGrid,yGrid)

################################################################################################
#Initalize our fleet

myFleetClass=fleet()
myFleetClass.maxShipSize=myFleetClass.determineMaxShipSize()
myFleetClass.minShipSize=myFleetClass.determineMinShipSize()

enemyFleetClass=fleet()
enemyFleetClass.maxShipSize=enemyFleetClass.determineMaxShipSize()
enemyFleetClass.minShipSize=enemyFleetClass.determineMinShipSize()
################################################################################################

#Set up grid values
enemyGridValues=enemyGridClass.gridValues
enemyGridClass.searchList=enemyGridClass.defineSearchList(myFleetClass.maxShipSize,enemyGridClass.attackNumber)

myGridValues=myGridClass.gridValues
myGridClass.searchList=myGridClass.defineSearchList(enemyFleetClass.maxShipSize,myGridClass.attackNumber)
################################################################################################

#Sort our ships by size.
sortedShipList=sorted(myFleetClass.shipFleetDict.iteritems(), key=operator.itemgetter(1),reverse=True)

################################################################################################
#Setup the layout of our ships.

#Populate Computer/Enemy grid.
#Randomly place our ships
setupNavy('random',enemyGridClass,sortedShipList)
#setupNavy('manual',enemyGridClass,sortedShipList)
enemyGridClass.populateGrid()

#Prompt if we want to manually place our ships.
if numberOfPlayers==1:
choiceForSetup=raw_input("Would you like to manually place your ships ('Y' or 'N')?" )
else:
choiceForSetup="N"
#Manually setup our ships
if choiceForSetup.upper()=='Y':
#Display an empty grid
myGridClass.populateGrid()
myGridClass.displayGrid()
#Manually setup our ships
setupNavy('manual',myGridClass,sortedShipList)
myGridClass.populateGrid()
else:
#Randomly setup or ships.
setup='Y'
while setup=="Y":
setupNavy('random',myGridClass,sortedShipList)
#setupNavy('manual',myGridClass,sortedShipList)
#Display our random fleet location
myGridClass.populateGrid()
myGridClass.displayGrid()
#If person is playing computer, prompt if they like the fleet setup
if numberOfPlayers==1:
con=raw_input("Are you satisfied with your location of your ships ('Y' or 'N')? ")
else:
con="Y"
#Setup is good so we change our conditional statement
if con.upper()=="Y":
setup="N"
else:
#Setup is NOT goodd so lets reset our grid and randomly setup another fleet
myGridClass.gridValuesUsed=[]
myGridValues=myGridClass.resetGridValues()
################################################################################################
#All necessary setup requirements have been met so lets get this party started.
for whosTurn in turnList:
print "\n%s turn"%whosTurn
if whosTurn!="Joshua":
#If person is playing computer then we send in a flag "player"
#This allows us to pick a attack location rather then the computer
if int(numberOfPlayers) ==1:
whosTurn='player'
attackShip(whosTurn,myGridClass,enemyGridClass,enemyFleetClass)
myGridClass.attackCounter+=1
else:
attackShip(whosTurn,enemyGridClass,myGridClass,myFleetClass)
enemyGridClass.attackCounter+=1

print "\n    MY BATTLEFIELD"
myGridClass.populateGrid()
myGridClass.displayGrid()

print "\n    MY ATTACKS"
myGridClass.populateEnemyGrid()
myGridClass.displayEnemyGrid()


fleet.py

class fleet:
def __init__(self):
#List of current ships of the United States Navy
#Ship name         |           Size
#--------------------------------------
#airCraftCarrier               6
#battleShip                    5
#submarine                     4
#cruiser                       3
#destroyer                     2

#self.shipFleetDict={'airCraftCarrier':6}

self.shipFleetDict={'airCraftCarrier':5,
'battleship':4,
'submarine':3,
'cruiser':3,
'destroyer':2}

self.shipStatusDict={'airCraftCarrier':'active',
'battleship':'active',
'submarine':'active',
'cruiser':'active',
'destroyer':'active'}

self.numberSunkShips=0
self.maxShipSize=0
self.minShipSize=0

def determineMaxShipSize(self):
maxShipSize=0
for ship,state in self.shipStatusDict.iteritems():
if state=='active':
if self.shipFleetDict[ship]>maxShipSize:
maxShipSize=self.shipFleetDict[ship]
return maxShipSize

def determineMinShipSize(self):
from time import sleep
minShipSize=1000
for ship,state in self.shipStatusDict.iteritems():
if state=='active':
if self.shipFleetDict[ship]<minShipSize:
minShipSize=self.shipFleetDict[ship]
return minShipSize


grid.py

# -*- coding: utf-8 -*-
import sys
import re
from time import sleep

#Color codes
#http://www.siafoo.net/snippet/88

class grid:
def __init__(self,name,xSize,ySize):
self.gridName =name
self.attackCounter=0
self.digCount=0
self.hitList=[]
self.attackedCoordList=[]
self.blockedCoordList=[]
self.missedList=[]
self.gridValuesUsed=[]
self.attackList=[]
self.displayGridDict={}
self.displayEnemyGridDict={}
self.shipLocationDict={}
self.xGridSize=xSize
self.yGridSize=ySize
self.gridValues=[ [ '\033[1;44m[ ]\033[1;m' for i in range(self.yGridSize) ] for j in range(self.xGridSize) ]
self.gridValuesAttacked=[ [ '\033[1;44m[ ]\033[1;m' for i in range(self.yGridSize) ] for j in range(self.xGridSize) ]
self.validPoints=self.defineValidPoints()
self.alphList=self.defineAlphList()
self.alphDict=self.generateDict()
self.searchList=[]
self.maxCharLen=self.determineMaxChars()
self.attackNumber=1

def determineMaxChars(self):
maxCharLen=len(self.alphList[self.xGridSize])
return maxCharLen

def defineAlphList(self):
import itertools
alphaString=''.join(map(chr, range(65,91)))
alpha=26
maxDict={}
maxList=[]
#FROM A to ZZZ
chosen=100
x=0
y=0
overloop=0
while x < chosen:
mod=x%alpha
if x!=0 and mod==0:
overloop+=1
maxList+=[''.join(i) for i in itertools.product(alphaString,repeat=overloop)]
x+=1
return maxList

def get_rows(self,grid):
return [[cell for cell in row] for row in grid]

def get_cols(self,grid):
cols = [[] for col in grid[0]]
for row in grid:
for col_index, cell in enumerate(row):
cols[col_index].append(cell)
return cols

def get_forward_diagonals(self,grid,maxShipSize):
buff = ['X']*(len(grid[0])+1)
buff_grid = []
for row_index, row in enumerate(self.get_rows(grid)):
buff_grid.append( buff[row_index:] + row + buff[:row_index+maxShipSize] )
cols = self.get_cols(buff_grid)[2:-1]
for col in cols:
while 'X' in col:
col.remove('X')
return cols

def get_cols_backward(self,grid):
cols = [[] for col in grid[len(grid)-1]]
for row in grid:
for col_index, cell in enumerate(row):
cols[col_index].append(cell)
return cols

def get_backward_diagonals(self,grid,maxShipSize):
buff = ['X']*(len(grid[0])+1)
buff_grid = []
for row_index, row in enumerate(self.get_rows(grid)):
buff_grid.append( buff[:row_index+1] + row + buff[row_index-maxShipSize:] )
cols = self.get_cols_backward(buff_grid)[1:-2]
for col in cols:
while 'X' in col:
col.remove('X')
return cols

def get_digonals_maxSize(self,allList,maxShipSize):
iterator=0
searchList=[]
allList = [x for x in allList if x != []]
middle=int(round(float(len(allList)/2)))
while middle>0:
searchList.append(allList[middle])
middle-=maxShipSize
middleHigh=int(round(float(len(allList)/2)))
while middleHigh<len(allList)-1:
searchList.append(allList[middleHigh])
middleHigh+=maxShipSize
searchList=sorted(searchList)
#remove duplicate lists
searchList=[searchList[i] for i in range(len(searchList)) if i == 0 or searchList[i] != searchList[i-1]]
return searchList

def get_digonals_maxSize_backward(self,allList,maxShipSize):
searchList=[]
allList = [x for x in allList if x != []]
middle=int(round(float(len(allList)/2)))
while middle>0:
searchList.append(allList[middle])
middle-=maxShipSize
middleHigh=int(round(float(len(allList)/2)))
while middleHigh<len(allList)-1:
searchList.append(allList[middleHigh])
middleHigh+=maxShipSize
#searchList=sorted(searchList)
#remove duplicate lists
searchList=[searchList[i] for i in range(len(searchList)) if i == 0 or searchList[i] != searchList[i-1]]
return searchList

def defineCoords(self):
maxGrid=self.yGridSize
coordsList=[]
grid=[ [ '[]' for i in range(maxGrid) ] for j in range(maxGrid) ]
for i in range(maxGrid):
searchList=[]
for j in range(maxGrid):
coords="%s,%s"%(i,j)
searchList.append(coords)
coordsList.append(searchList)
return coordsList

def defineSearchListForwardList(self,maxShipSize,attackNumber):
coordsList=self.defineCoords()
allList= self.get_forward_diagonals(coordsList,maxShipSize)
searchList=self.get_digonals_maxSize(allList,maxShipSize)
what="%s %s "% (attackNumber-1,len(searchList))
if attackNumber-1<len(searchList):
return searchList[attackNumber-1]
else:
return self.validPoints

def defineSearchList(self,maxShipSize,attackNumber):
coordsList=self.defineCoords()
allListForward= self.get_forward_diagonals(coordsList,maxShipSize)
searchListForward=self.get_digonals_maxSize(allListForward,maxShipSize)
searchListForward=sorted(searchListForward, key=len,reverse=True)
allListBackward= self.get_backward_diagonals(coordsList,maxShipSize)
searchListBackward=self.get_digonals_maxSize_backward(allListBackward,maxShipSize)
searchListBackward=sorted(searchListBackward, key=len,reverse=True)

searchList=searchListForward+searchListBackward
searchList=[searchList[i] for i in range(len(searchList)) if i == 0 or searchList[i] != searchList[i-1]]
searchList=sorted(searchList, key=len,reverse=True)
if self.digCount < len(searchList):
searchListToReturn=searchList[self.digCount]
self.digCount+=1
return searchListToReturn
else:
return self.validPoints

def defineValidPoints(self):
validPoints=[]
x=0
while x < self.xGridSize:
y=0
while y < self.yGridSize:
validPoints.append("%s,%s"%(x,y))
y+=1
x+=1
return validPoints

def generateDict(self):
alphDict={}
i=0
for i in range(0, len(self.alphList)):
#alphDict[(ord(self.alphList[i])%32)-1] = self.alphList[i]
alphDict[i] = self.alphList[i]

return alphDict

def resetGridValues(self):
#sam
self.gridValues=[ [ '[ ]' for i in range(self.yGridSize) ] for j in range(self.xGridSize) ]
return self.gridValues

def checkDataPointValue(self,dataPoint):
m=re.search('([A-Z]*)([0-9]*)',dataPoint)
xValue=m.group(1)
yValue=m.group(2)

xValue=self.alphList.index(xValue)
coords="%s,%s"%(xValue,yValue)
if coords in self.gridValuesUsed:
return "T"
else:
return "E"

def determineEndPoint(self,start,size,placement):
startValues=re.search('([A-Z]*)([0-9]*)',start)
x=startValues.group(1)
y=startValues.group(2)
if placement.upper()=='V':
yEnd=(int(y)+size)-1
if yEnd > self.yGridSize-1: return "F"
endPoint="%s%s"%(x,str(yEnd))
else:
xValueNumber=self.alphList.index(x)
xEnd=xValueNumber+size-1
if xEnd > self.xGridSize-1: return "F"
endPoint="%s%s"%(self.alphList[xEnd],y)
return endPoint

def determineFullLocation(self,start,end):
startValues=re.search('([A-Z]*)([0-9]*)',start)
xValueStart=startValues.group(1)
yValueStart=int(startValues.group(2))

endValues=re.search('([A-Z]*)([0-9]*)',end)
xValueEnd=endValues.group(1)
yValueEnd=int(endValues.group(2))

shipCoordList=[]
if xValueStart==xValueEnd: #placing vertical
xValueNumber=self.alphList.index(xValueStart)
i=yValueStart
while i <= yValueEnd:
shipCoordList.append('%s,%s'%(xValueNumber,i))
i+=1
else:
xValueStart=self.alphList.index(xValueStart)
xValueEnd=self.alphList.index(xValueEnd)
i=xValueStart
while i <= xValueEnd:
shipCoordList.append('%s,%s'%(i,yValueStart))
i+=1
return shipCoordList

def shipPlacement(self,start,end,shipCoordList):
startValues=re.search('([A-Z]*)([0-9]*)',start)
xValueStart=startValues.group(2)
xValueEnd=startValues.group(1)
block='■'
if xValueStart==xValueEnd: #placing vertical
for coord in shipCoordList:
coordList=coord.split(',')
xValue=int(coordList[0])
yValue=int(coordList[1])
displayVal="\033[1;44m[%s]\033[1;44m"%block
self.gridValues[xValue][yValue]=displayVal
else: #placing horizontal
i=1
size=len(shipCoordList)
for coord in shipCoordList:
coordList=coord.split(',')
xValue=int(coordList[0])
yValue=int(coordList[1])
if i ==1:
displayVal="[%s "%block
elif i==size:
displayVal=" %s]"%block
else:
displayVal=" %s "%block
self.gridValues[xValue][yValue]=displayVal
i+=1
return

def populateGrid(self):
y=0
#gridDict={}
numElements=len(self.gridValues)
while y < self.yGridSize:
values=[]
x=0
while x < self.xGridSize:
values.append(self.gridValues[x][y])
x+=1
if numElements>9:
yDisplay="%02d" % (y,)
self.displayGridDict[yDisplay]=values
else:
self.displayGridDict[y]=values
values=[]
y+=1
return

def displayGrid(self):
row=0
numElements= len(self.displayGridDict)
x=0
while x<numElements:
#Horzintal label
x+=1
numElements=len(self.displayGridDict)
for key in sorted(self.displayGridDict.iterkeys()):
value=self.displayGridDict[key]
if row==0:
if numElements>9:
else:
sys.stdout.write(displayStr)
displayStr=""
#Vertical Label
displayStr+="%s"%key

for cell in value:
displayStr+="%s"%cell
displayStr+="\n"
sys.stdout.write(displayStr)
displayStr=""
row+=1

def populateEnemyGrid(self):
y=0
#gridDict={}
numElements=len(self.gridValuesAttacked)
while y < self.yGridSize:
values=[]
x=0
while x < self.xGridSize:
values.append(self.gridValuesAttacked[x][y])
x+=1
if numElements>9:
yDisplay="%02d" % (y,)
self.displayEnemyGridDict[yDisplay]=values
else:
self.displayEnemyGridDict[y]=values
values=[]
y+=1
return

def displayEnemyGrid(self):
row=0
numElements= len(self.displayEnemyGridDict)
x=0
while x<numElements:
x+=1
numElements=len(self.displayEnemyGridDict)
for key in sorted(self.displayEnemyGridDict.iterkeys()):
value=self.displayEnemyGridDict[key]
if row==0:
if numElements>9:
else:
sys.stdout.write(displayStr)
displayStr=""
displayStr+="%s"%key

for cell in value:
displayStr+="%s"%cell
displayStr+="\n"
sys.stdout.write(displayStr)
displayStr=""
row+=1

• I'm putting this as a comment since I'm not confident in it as an answer, but why are you starting with the largest size? If you start at the largest, you'll eventually need to backtrack and then do the smaller ones anyway. My guess is that the opposite is faster, but I'm ready to be proven totally wrong about it. Sep 7 '15 at 13:28
• I used to confuse the computer by putting a battleship and a destroyer end-to-end. Often the computer would destroy the battleship and one cell of the destroyer and think it had hit my aircraft-carrier. You should always take one step further once you think you've destroyed a ship. Sep 7 '15 at 13:56
• @SuperBiasedMan When placing ships, the largest has the least amount of possible places. Doing that first makes placement easier.
– Mast
Sep 7 '15 at 14:55
• @Mast You're talking about placement but the OP is using it to try find ships to attack. Sep 7 '15 at 15:00
• @SuperBiasedMan thank for your suggestion. I originally started off with that a approach (checkerboard attack) and the percent of accuracy was a lot lower. :) Sep 7 '15 at 15:18

Some general style suggestions; incomplete due to lack of time, but they should give you some things to think about.

Upgrade to Python 3 if possible. You appear to only be using stdlib code, so this should be reasonable painless.

You have a lot of java-esque naming conventions. Python style (see especially PEP 8) prefers methods and variables to be named like_this rather than likeThis. Names of classes should be capitalised, so Grid instead of grid. You have some of your methods named according to this style already - you should generally try to pick one style and stick with it; preferably follow the conventions in PEP 8 unless there's a compelling reason not to.

You use strings as flags a lot - eg,

used="no"
con="yes"
while con=="yes":


Python supports booleans, so you can do

used = False
con = True
while con:


#setupNavy
#Purpos: To place our ships on the grid
#Receives: setupSelection- either manual or random
#          gridClass
#          sortedShipList
#Return:


Should be docstrings - basically, make it an unassigned string literal, and put it directly inside the function definition.

The first argument to setup_navy is another string-as-flag. Use a bool instead, and all it automatic_placement. But even better, split this into two functions. The one that does it automatically could actually be a method of Grid called place_ships, and document it as placing them randomly. The one that places them manually does belong out in the main flow of your program, since it continually does IO. This will simplify your code greatly.

The second argument is called gridClass but actually expects a Grid instance. Just call it grid.

sortedShipList could just be called ships. If you want to document its structure (which isn't a bad idea), you can do better than giving it a clunky name that only documents some of it's structure - in your docstring, do this:

def place_ships(self, ships):
'''
Randomly place the given ships on the grid.

ships: a sorted list of tuples (name, type)
'''


Consider using a namedtuple for the ships, so then this loop:

for shipData in sortedShipList:
shipName=shipData[0]
shipSize=shipData[1]


can become just:

for ship in ships:


and you can immediately work with ship.name and ship.data.

shipCoordList=gridClass.determineFullLocation(start,end)
gridClass.shipLocationDict[shipName]=shipCoordList


It seems odd to ask gridClass to work something out for you, and then immediately assign exactly that result back to an attribute on gridClass. It would make more sense if you could come up with a flow that the grid can modify it's own attributes appropriately. I think it might make sense for grid to have a method to place a single ship at a particular start location, and going in a particular direction - perhaps raising an exception if it would go past the end (possibly taking a flag to say that that's ok sometimes). It looks like you already have a method called grid.shipPlacement - why aren't you using it here?

Your coordinates here are strings. Instead, leave them as (x, y) tuples so you don't have to keep parsing them every time you want to do stuff with them.

Drop the word "determine" from various method names. It's just noise. We know that a function either does something or calculates something - ie, functions usually (although there are occasionally good reasons to have exceptions) follow the principle of command-query separation. So if its name is a noun phrase, we already know that it must calculate whatever that phrase refers to. You might consider making some of them into propertys so that you can use them as attributes.

• Thank you for the suggestions. I really like the boolen idea using named tuples. I will also use docstrings. Your suggestions will help clean up the code for easier readability. The function "checkDataPointValue" verifies that a ship can fit on the board. Adding proper docstrings with each function will help clarify stuff like this. :) I will also work on better naming conventions. I typically put the type of data structure in the variable name for quickly knowing what type it is. ie shipCoordList or shipLocationDict. Is that not a good idea? Sep 7 '15 at 15:37

You don't need to have a large sprawling comment like this and then have a dictionary that mimics the table data anyway.

    #List of current ships of the United States Navy
#Ship name         |           Size
#--------------------------------------
#airCraftCarrier               6
#battleShip                    5
#submarine                     4
#cruiser                       3
#destroyer                     2

#self.shipFleetDict={'airCraftCarrier':6}

self.shipFleetDict={'airCraftCarrier':5,
'battleship':4,
'submarine':3,
'cruiser':3,
'destroyer':2}


If you rename shipFleetDict to ship_fleet_sizes then you make it obvious what the dictionary is for even without adding a comment. Also generally speaking using the datatype in the name is redundant since it's clear in the code anyway that you're defining a dictionary. It's extra bad though that you define the size of the ships differently in the comment and the dictionary itself. Comments should be accurate and up to date to avoid confusion.

In your next dictionary for ship status, I would again remove Dict from the name and switch to using True and False rather than 'active'. It's a faster check, and more Pythonic. It would allow you to do this:

if fleet.ship_status['airCraftCarrier']:


Also why not call your two ship size functions in init?

    self.max_ship = self.min_ship_size()
self.min_ship = self.max_ship_size()


Speaking of those methods, you should be combining the if statements rather than doing 2 separate ones.

max = 0
for ship,active in self.shipStatusDict.iteritems():
if (active and self.ship_fleet[ship] > max):


I recommend not mimicking the names of the class attributes, it's liable to cause confusion and look like you just forgot to include self. before it. max is clear enough to use on these few lines.

And you left in a useless import in determineMinShipSize. If you're no longer using this, clean it out.

from time import sleep

• I really like your idea of using a true,false boolean instead of active or sunk. if fleet.ship_status['airCraftCarrier']: is really nice and a lot nicer then checking its value. Sep 7 '15 at 15:40
• @SamSanchez The reason is that it makes variable names extra long and harder to follow. Generally it should be obvious what type something is from how you use it. fleet.ship_size['cruiser'] is quite clear because you know that collection objects (lists, dictionaries etc.) are accessed with [] and dictionaries are the usual collection object that takes a key to access the values. If it was a more unusual data type that might be mistaken for another (like a Counter), then it could be worth including it in the name. Sep 7 '15 at 15:45