4

Let's say that I am trying to make a BattleShip game in Python. I have a list of lists called board. Each list in board is a list of the spaces in that row of the board, for this example, it will be 5x5:

[['clear', 'clear', 'clear', 'clear', 'clear'],
['clear', 'clear', 'clear', 'clear', 'clear'],
['clear', 'clear', 'clear', 'clear', 'clear'],
['clear', 'clear', 'clear', 'clear', 'clear'],
['clear', 'clear', 'clear', 'clear', 'clear']]

I want to create a function to return a random clear space in the board.

def pl_point(board):
    place = [randrange(0,5),randrange(0,5)] #heh, found out these aren't inclusive.
    if board[place[0]][place[1]] == "clear": return place
    else:
        return pl_point() #calls itself until a clear place is found

Here are my questions: Is it inefficient to have a function call itself until it gets the value it wants (even if the board is almost entirely filled)? Is there a better way I should do this instead?

I couldn't figure out how to use a while statement with this because the statement would always reference 'place' before it was assigned, and I couldn't think of any value for place that wouldn't reference an out-of-range or unassigned 'board' value.

My apologies if this is a duplicate topic, I tried to find a similar one but couldn't. This is also my first time using this site to ask a question instead of answer one.

Improve this question
9
  • 2
    Why not keep track of positions already considered and exclude them from your random guesses? Commented Aug 15, 2014 at 1:12
  • @inspectorG4dget: Yeah, that would remove the infinite worst-case behavior (and therefore the potential recursion error, unless his board's area is close to 1000); the average-case behavior is much less important here. So that might be the simplest way to tackle it… Commented Aug 15, 2014 at 1:26
  • One more thing: your board at the top is invalid; you need commas between the rows. And you might as well edit the randranges to use 5 to avoid there being any irrelevant problems here. (But I don't want to nitpick without pointing out that this is impressive for a first-time question. I don't know whether you pored over the help section, or just have good instincts for what's important to put into a question, but either way, nice job.) Commented Aug 15, 2014 at 1:32
  • the term you are looking for is "recursion" or "recursive function" Commented Aug 15, 2014 at 1:33
  • @abarnert Yeah, I found out randrange isn't inclusive like I somehow thought. And in my program I used "for i in board: print i" while I was working to bug-fix and such, the extra first and last square brackets were an afterthought when making this post. I added commas. Thanks for nitpicking, honestly. Commented Aug 15, 2014 at 1:39

3 Answers 3

Reset to default
5

Is it inefficient to have a function call itself until it gets the value it wants (even if the board is almost entirely filled)? Is there a better way I should do this instead?

Yes and yes. But it's not really the inefficiency that's the issue, so much as the fact that if you get unlucky enough to need to try 1000 times, your program will fail with a recursion error.

I couldn't figure out how to use a while statement with this because the statement would always reference 'place' before it was assigned, and I couldn't think of any value for place that wouldn't reference an out-of-range or unassigned 'board' value.

Just use while True:, and you can break or return to get out of the loop:

while True:
    place = [randrange(0,4),randrange(0,4)] #randrange is inclusive
    if board[place[0]][place[1]] == "clear":
        return place

As a side note, as inspectorG4dget points out in the comments, randrange is not inclusive; this will only return the numbers 0, 1, 2, and 3.

Also, putting the x and y coordinates into a list just so you can use [0] and [1] repeatedly makes things a bit harder to read. Just use x, y = [randrange(5), randrange(5)] (fixing the other problem as well), then board[x][y], and return x, y.

If this is too slow, then yes, there is a more optimal way to do it. First make a list of all of the clear slots, then pick one at random:

clearslots = [(x, y) for x in range(5) for y in range(5) if board[x][y] == "clear"]
return random.choice(clearslots)

That will probably be slower when the board is mostly empty, but it won't get any worse as the board fills up. Also, unlike your method, it has guaranteed worst-case constant time; instead of being incredibly unlikely for the routine to take years, it's impossible.

If you don't understand that list comprehension, let me write it out more explicitly:

clearslots = []
for x in range(5):
    for y in range(5):
        if board[x][y] == "clear":
            clearslots.append((x, y))
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

randrange is inclusive <- are you sure? From the docs: Choose a random item from range(start, stop[, step]). This fixes the problem with randint() which includes the endpoint; in Python this is usually not what you want.
@inspectorG4dget: I've just copied his original code to show him how to wrap a while True: loop around it; I didn't try to fix any other problems with it.
Oops! Sorry about that. Didn't notice the copy-paste
@inspectorG4dget: That's OK; I upvoted your comment, and edited it into the answer, because he obviously does need to know that. I'm just pointing out that I didn't have much idea of whether the code actually worked or not, except for the while True: loop, which I'm pretty sure I got right. :)
@SirChimi: This is one of the reasons it's better to iterate over lists instead of ranges, use functions like choice instead of randrange, etc.; you don't have to remember what is or isn't inclusive, worry about off-by-one errors, etc.
|
1

Sure there's a better way. Try this:

def pl_point(board):
    for y,row in enumerate(board):
        for x,col in row:
            if col == 'clear':
                return (x,y)

Is there a reason it has to be random? If so...

def pl_point_random(board):
    places = {(x,y) for x in range(len(board)) for y in range(len(board[0]))}
    # the above is a set comprehension of every spot on the board
    #   (assuming the board is rectangular...)
    while True:
        point = random.choice(places)
        # choose a random spot in places
        x,y = point
        if board[x][y] != 'clear':
            return point
        else:
            places.remove(point)

Or even better:

def pl_point_random_v2(board):
    places = [(x,y) for y,row in enumerate(board) for x,col in rows if col=='clear']
    return random.choice(places)
Improve this answer

9 Comments

Your method isn't very random: I want to create a function to return a random clear space in the board
I am not trying to return the first clear point, I want a random one.
So the 'places' set comprehension basically lowers the chances of this being unlucky and choosing the same occupied space multiple times?
Alright, I see. I'm not exactly sure how to use for statements with two variables like you have in there, but I will look that up and learn about it. Thank you for your help. Minor fix: in pl_point_random_v2, the last line should say 'places' instead of 'place'
@SirChimi: If you get an exception from a comprehension and don't know how to debug it, unroll it into an explicit for loop (see the example at the end of my answer) that makes it a lot easier to step through in the debugger, or add print calls, or however else you like to figure out what's going on.
|
0

Generators are a pretty Pythonic tool which can allow you to solve your problem. Essentially you want to go over a set of randomized clear spaces, returning one item at a time, correct?

You create a function which gets a single list of all the clear spaces first, like some answers already provided and return a random choice from that list. However, then you keep getting choices as needed by calling next() on the function you create.

import random

def board_randomizer():
    clear_spaces = [...] # list comprehension or your method of choosing
    while clear_spaces:
           coord = random.choice(clear_spaces)
           clear_spaces.remove(coord)
           yield coord # returns a random location, one item at a time

clear_positions = board_randomizer() # initialize a generator
# keeps picking random locations until a StopIteration error is raised
clear_positions.next()
clear_positions.next()
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.