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.31108Im 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 divisionimport numpyimport operatorimport commandsimport randomimport sysimport osfrom time import sleepfrom 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)            sys.stdout.write(header)        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 startLocationdef checkRoadBlocks(attackerGridClass,defenderFleetClass,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.blockedCoordListdef 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.attackListdef 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    returndef 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        attackerGridClass.blockedCoordList=checkRoadBlocks(attackerGridClass,defenderFleetClass,startLocation)        ########################################################################################################        #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)            #Alert message... saying skipping cause road block in the way    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 turnListdef 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 OVERdef 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 \ndef 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=Yif 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    msg=How about Global Thermonuclear War?......    #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    msg=Please be patient as battle tatics and anaylsis are loaded\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\nelse:    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=Nif 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=gridSizeelse:    #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 gridmyGridClass=grid('USA',xGrid,yGrid)if numberOfPlayers==0:    enemyGridClass=grid(random.choice(countryList),xGrid,yGrid)else:    enemyGridClass=grid(enemy,xGrid,yGrid)#################################################################################################Initalize our fleetmyFleetClass=fleet()myFleetClass.maxShipSize=myFleetClass.determineMaxShipSize()myFleetClass.minShipSize=myFleetClass.determineMinShipSize()enemyFleetClass=fleet()enemyFleetClass.maxShipSize=enemyFleetClass.determineMaxShipSize()enemyFleetClass.minShipSize=enemyFleetClass.determineMinShipSize()#################################################################################################Set up grid valuesenemyGridValues=enemyGridClass.gridValuesenemyGridClass.searchList=enemyGridClass.defineSearchList(myFleetClass.maxShipSize,enemyGridClass.attackNumber)myGridValues=myGridClass.gridValuesmyGridClass.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 shipsif 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.pyclass 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 minShipSizegrid.py# -*- coding: utf-8 -*-import sysimport refrom time import sleep#Color codes#http://www.siafoo.net/snippet/88class 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        header=        numElements= len(self.displayGridDict)        x=0        while x<numElements:            #Horzintal label            header+=[%s]%self.alphList[x]            x+=1        numElements=len(self.displayGridDict)        for key in sorted(self.displayGridDict.iterkeys()):            value=self.displayGridDict[key]            if row==0:                if numElements>9:                    displayStr=  %s\n%(header)                else:                    displayStr= %s\n%(header)                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        header=        numElements= len(self.displayEnemyGridDict)        x=0        while x<numElements:            header+=[%s]%self.alphList[x]            x+=1        numElements=len(self.displayEnemyGridDict)        for key in sorted(self.displayEnemyGridDict.iterkeys()):            value=self.displayEnemyGridDict[key]            if row==0:                if numElements>9:                    displayStr=  %s\n%(header)                else:                    displayStr= %s\n%(header)                sys.stdout.write(displayStr)                displayStr=            displayStr+=%s%key            for cell in value:                displayStr+=%s%cell            displayStr+=\n            sys.stdout.write(displayStr)            displayStr=            row+=1
Battleship algorithm
python;algorithm;game