469,271 Members | 1,481 Online

# searching a list of lists as a two-dimensional array?

Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks

Feb 12 '07 #1
16 3457 agent-s wrote:
Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks
This isn't very clear. What do you mean by "I have to search the

If piece is 1 and empty is 0 and piece is at ary[row][col]:

import operator
srch = [(i,j) for i in [-1,0,1] for j in [-1,0,1] if (i,j) != (0,0)]
is_adj = reduce(operator.or_, [ary[row+i][col+j] for (i,j) in srch]])
James
Feb 12 '07 #2
James Stroud <js*****@mbi.ucla.eduon Sun, 11 Feb 2007 16:53:16 -0800
didst step forth and proclaim thus:
agent-s wrote:
Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks

This isn't very clear. What do you mean by "I have to search the

If piece is 1 and empty is 0 and piece is at ary[row][col]:

import operator
srch = [(i,j) for i in [-1,0,1] for j in [-1,0,1] if (i,j) != (0,0)]
is_adj = reduce(operator.or_, [ary[row+i][col+j] for (i,j) in srch]])
Wow, maybe it's just me (I'm a pretty bad programmer) but this is
where list comprehensions begin to look unreadable to me. Here's a
C-like way to do it, (warning, untested in python):

for i in range(8):
for j in range(8):
for offset_i in range(-1,2):
for offset_j in range(-1, 2):
row = i + offset_i
col = j + offset_j
if (row < 0 or row 7) or (col < 0 or col 8) \
or ((row,col) == (i,j)):
continue
# else do something with board[row][col]

I realize this is gross and un-Pythonic and does the same thing the
above code does, but it's probably the way I'd choose to do it :).
Then again, I've been negatively influenced by doing a game of life in
C a few months back.

--
Sam Peterson
skpeterson At nospam ucdavis.edu
software would be much better" -- unknown
Feb 12 '07 #3
En Mon, 12 Feb 2007 02:24:54 -0300, Samuel Karl Peterson
James Stroud <js*****@mbi.ucla.eduon Sun, 11 Feb 2007 16:53:16 -0800
didst step forth and proclaim thus:
>agent-s wrote:
Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks
Wow, maybe it's just me (I'm a pretty bad programmer) but this is
where list comprehensions begin to look unreadable to me. Here's a
C-like way to do it, (warning, untested in python):
Just for fun, and to add one more way. This is a generator for adjacent
indexes, that can be used to search for occupied cells, for locating a
suitable next move, or whatever:

.... for ni in (i-1, i, i+1):
.... if ni not in range(8): continue
.... for nj in (j-1, j, j+1):
.... if nj not in range(8): continue
.... if ni!=i or nj!=j:
.... yield ni,nj
....
py>
[(3, 2), (3, 3), (3, 4), (4, 2), (4, 4), (5, 2), (5, 3), (5, 4
[(6, 2), (6, 3), (6, 4), (7, 2), (7, 4)]
[(3, 6), (3, 7), (4, 6), (5, 6), (5, 7)]
[(0, 6), (1, 6), (1, 7)]

--
Gabriel Genellina

Feb 12 '07 #4
En Mon, 12 Feb 2007 02:24:54 -0300, Samuel Karl Peterson
James Stroud <js*****@mbi.ucla.eduon Sun, 11 Feb 2007 16:53:16 -0800
didst step forth and proclaim thus:
>agent-s wrote:
Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks
Wow, maybe it's just me (I'm a pretty bad programmer) but this is
where list comprehensions begin to look unreadable to me. Here's a
C-like way to do it, (warning, untested in python):
Just for fun, and to add one more way. This is a generator for adjacent
indexes, that can be used to search for occupied cells, for locating a
suitable next move, or whatever:

.... for ni in (i-1, i, i+1):
.... if ni not in range(8): continue
.... for nj in (j-1, j, j+1):
.... if nj not in range(8): continue
.... if ni!=i or nj!=j:
.... yield ni,nj
....
py>
[(3, 2), (3, 3), (3, 4), (4, 2), (4, 4), (5, 2), (5, 3), (5, 4
[(6, 2), (6, 3), (6, 4), (7, 2), (7, 4)]
[(3, 6), (3, 7), (4, 6), (5, 6), (5, 7)]
[(0, 6), (1, 6), (1, 7)]

--
Gabriel Genellina

Feb 12 '07 #5
"agent-s" <sh*******@gmail.comwrites:
Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks
You're getting a bunch of Pythonic suggestions which are easy to
understand though not so efficient. If you're after efficiency you
might look at a book like Welsh and Baczynskyj "Computer Chess II" for
some techniques (warning, this is a rather old book though) and
program in a closer-to-the-metal language. One common approach these
days is "bit boards". Basically you represent the board state as a
bunch of 64-bit words, one bit per square. So for checking occupancy,
you'd have a word having the bits set for occupied squares. If you
only want to check adjacent squares (king moves), you could have a
bunch of bit masks (one for each square) with bits set only for the
adjacent squares (similarly for bishop moves, rook moves, etc.) Then
square, then AND it against the occupancy word. Normally you'd have
Feb 12 '07 #6
Paul Rubin wrote:
"agent-s" <sh*******@gmail.comwrites:
>>Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks

You're getting a bunch of Pythonic suggestions which are easy to
understand though not so efficient. If you're after efficiency you
might look at a book like Welsh and Baczynskyj "Computer Chess II" for
some techniques (warning, this is a rather old book though) and
program in a closer-to-the-metal language. One common approach these
days is "bit boards". Basically you represent the board state as a
bunch of 64-bit words, one bit per square. So for checking occupancy,
you'd have a word having the bits set for occupied squares. If you
only want to check adjacent squares (king moves), you could have a
bunch of bit masks (one for each square) with bits set only for the
adjacent squares (similarly for bishop moves, rook moves, etc.) Then
square, then AND it against the occupancy word. Normally you'd have
In defense of the less efficient suggestions, he did say he had to use a
list of lists. But what you describe is pretty cool.

James
Feb 12 '07 #7
James Stroud:
import operator
srch = [(i,j) for i in [-1,0,1] for j in [-1,0,1] if (i,j) != (0,0)]
is_adj = reduce(operator.or_, [ary[row+i][col+j] for (i,j) in srch]])
Or maybe (untested), Python V.2.5:

srch = [(i,j) for i in [-1,0,1] for j in [-1,0,1] if (i,j) != (0,0)]
is_adj = any(ary[row+i][col+j] for (i,j) in srch)

Or:

is_adj = any(ary[row+i][col+j] for i in [-1,0,1] for j in [-1,0,1] if
(i,j) != (0,0))

Bye,
bearophile

Feb 12 '07 #8
On Feb 12, 4:24 pm, Samuel Karl Peterson
C-like way to do it, (warning, untested in python):

for i in range(8):
for j in range(8):
for offset_i in range(-1,2):
for offset_j in range(-1, 2):
row = i + offset_i
col = j + offset_j
if (row < 0 or row 7) or (col < 0 or col 8) \
or ((row,col) == (i,j)):
continue
# else do something with board[row][col]

I realize this is gross and un-Pythonic and does the same thing
It's also just a little bit inefficient. Never mind the algorithm,
we'll talk about that later. Let's just improve the code a little:

side_range = range(8)
delta_range = range(-1, 2)
for i in side_range:
for offset_i in delta_range:
row = i + offset_i
if not (0 <= row <= 7): continue
for j in side_range:
for offset_j in delta_range:
if not offset_i and not offset_j: continue
col = j + offset_j
if not(0 <= col <= 7): continue
# *now* it's safe to do something
# with (row, col)

Such hoisting of code out of inner loops is done for you by a C
compiler -- Python assumes you know what you are doing :-)

Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list

Another approach that has been used is to have a 9 x 9 storage area;
the squares off the edge contain a value that is neither "empty" nor
any value that represents a piece. So with careful coding, they
automatically fail tests like "can I capture the piece on this
square" [no, it's not a piece] and "can I move here" [no, it's not
empty]. If the game is chess, you need 10 x 10 to cater for those
pesky knights.

Cheers,
John

Feb 12 '07 #9
On Sun, 11 Feb 2007 23:20:11 -0800, John Machin wrote:
Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list
Heh. Being a smart-alec is number 7 :-P

Seriously, this is Python. Are you *sure* bit-bashing is going to be
faster than the alternative? If this was C, or assembly, you'd almost
certainly be right. But Python is heavily object-oriented, and bit
manipulations are just methods, with all the overhead that entails.
>>import timeit
timeit.Timer("3 | 2", "").repeat()
[0.33678007125854492, 0.33447504043579102, 0.33331012725830078]
>>timeit.Timer("3 < 2", "").repeat()
[0.30328893661499023, 0.29070115089416504, 0.28839397430419922]

The problem with bit-bashing, masking etc. is that except for the most
simple cases it is quite obfuscated. If you aren't going to gain a serious
performance boost, why bother?

--
Steven D'Aprano

Feb 12 '07 #10
On 2007-02-12, James Stroud <js*****@mbi.ucla.eduwrote:
Paul Rubin wrote:
>"agent-s" <sh*******@gmail.comwrites:
>>>Basically I'm programming a board game and I have to use a
list of lists to represent the board (a list of 8 lists with 8
elements each). I have to search the adjacent cells for
existing pieces and I was wondering how I would go about doing
this efficiently. Thanks

You're getting a bunch of Pythonic suggestions which are easy
to understand though not so efficient. If you're after
efficiency you might look at a book like Welsh and Baczynskyj
"Computer Chess II" for some techniques (warning, this is a
rather old book though) and program in a closer-to-the-metal
language. One common approach these days is "bit boards".
Basically you represent the board state as a bunch of 64-bit
words, one bit per square. So for checking occupancy, you'd
have a word having the bits set for occupied squares. If you
only want to check adjacent squares (king moves), you could
have a bunch of bit masks (one for each square) with bits set
only for the adjacent squares (similarly for bishop moves,
appropriate bits for that square, then AND it against the
occupancy word. Normally you'd have separate occupancy words

In defense of the less efficient suggestions, he did say he had
to use a list of lists. But what you describe is pretty cool.
Precomputing and storing the adjecent indexes for each square
would be a possible hybrid solution. In effect every square would
contain pointers to all its neighbors.

--
Neil Cerutti
Feb 12 '07 #11

"John Machin" <sj******@lexicon.netwrote:
Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list
Thou shallt not bit - bash

What are the other five?

- Hendrik
Feb 13 '07 #12
On Feb 13, 4:57 pm, "Hendrik van Rooyen" <m...@microcorp.co.zawrote:
"John Machin" <sjmac...@lexicon.netwrote:
Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list

Thou shallt not bit - bash

What are the other five?
"""
.... regexes have their place, together with pointer arithmetic, bit
manipulations, reverse polish notation and goto. The problem is when
people use them inappropriately ...
"""

The sixth is never mentioned. Aliter: I can't count. Believe whichever
hypothesis you like :-)
Feb 13 '07 #13
"John Machin" <sjmac...@lexicon.netwrote:
On Feb 13, 4:57 pm, "Hendrik van Rooyen" <m...@microcorp.co.zawrote:
"John Machin" <sjmac...@lexicon.netwrote:
Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list
Thou shallt not bit - bash

What are the other five?

"""
... regexes have their place, together with pointer arithmetic, bit
manipulations, reverse polish notation and goto. The problem is when
people use them inappropriately ...
"""
I find this unsatisfactory - I was hoping for a five commandment
style of thing, setting out proper prohibitions against evil stuff.

It seems that I am a closet fundamentalist.

A sixth, btw is:

Thou shallt not use globals.

- Hendrik

Feb 13 '07 #14
Thanks for the help guys but I'm a newbie at this and from what I
understand from the code, it looks like you guys are using a two
dimensional array. I am not using a two dimensional array. Basically,
it looks like this:

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

above: a list of lists NOT a two-dimensional array

Feb 14 '07 #15
OK I just realized that a list of lists can be accessed in the same
way a 2d array would be accessed. Thanks anyways guys.

Feb 14 '07 #16
On Feb 12, 1:27 am, "agent-s" <shanek...@gmail.comwrote:
Basically I'm programming a board game and I have to use a list of
lists to represent the board (a list of 8 lists with 8 elements each).
I have to search the adjacent cells for existing pieces and I was
wondering how I would go about doing this efficiently. Thanks
def iter_grid(cols):
i=0
while True:
yield divmod(i,cols)
i += 1

gen = iter_grid(3)
for i in range(9):
x, y = gen.next()
if x == 1 and y ==1:
continue
else:
yield row - x + 1, col - y + 1

def make_grid_dict(rows, cols):
return dict( zip(iter_grid(cols), ['#'] * (rows*cols)) )

ret = []
for x, y in iter_adjacents(row, col):
if x -1 and y -1 and x < row_length and y < col_length:
ret.append((x,y))
return ret

grid = make_grid_dict(8, 8)
print '(%s, %s) - %s ' % (x, y, adjacents[x,y]
(0, 0) - [(1, 1), (1, 0), (0, 1)]
(0, 1) - [(1, 2), (1, 1), (1, 0), (0, 2), (0, 0)]
(0, 2) - [(1, 3), (1, 2), (1, 1), (0, 3), (0, 1)]
(0, 3) - [(1, 4), (1, 3), (1, 2), (0, 4), (0, 2)]
(0, 4) - [(1, 5), (1, 4), (1, 3), (0, 5), (0, 3)]
(0, 5) - [(1, 6), (1, 5), (1, 4), (0, 6), (0, 4)]
(0, 6) - [(1, 7), (1, 6), (1, 5), (0, 7), (0, 5)]
(0, 7) - [(1, 7), (1, 6), (0, 6)]
(1, 0) - [(2, 1), (2, 0), (1, 1), (0, 1), (0, 0)]
(1, 1) - [(2, 2), (2, 1), (2, 0), (1, 2), (1, 0), (0, 2), (0, 1), (0,
0)]
(1, 2) - [(2, 3), (2, 2), (2, 1), (1, 3), (1, 1), (0, 3), (0, 2), (0,
1)]
(1, 3) - [(2, 4), (2, 3), (2, 2), (1, 4), (1, 2), (0, 4), (0, 3), (0,
2)]
(1, 4) - [(2, 5), (2, 4), (2, 3), (1, 5), (1, 3), (0, 5), (0, 4), (0,
3)]
(1, 5) - [(2, 6), (2, 5), (2, 4), (1, 6), (1, 4), (0, 6), (0, 5), (0,
4)]
(1, 6) - [(2, 7), (2, 6), (2, 5), (1, 7), (1, 5), (0, 7), (0, 6), (0,
5)]
(1, 7) - [(2, 7), (2, 6), (1, 6), (0, 7), (0, 6)]
(2, 0) - [(3, 1), (3, 0), (2, 1), (1, 1), (1, 0)]
(2, 1) - [(3, 2), (3, 1), (3, 0), (2, 2), (2, 0), (1, 2), (1, 1), (1,
0)]
(2, 2) - [(3, 3), (3, 2), (3, 1), (2, 3), (2, 1), (1, 3), (1, 2), (1,
1)]
(2, 3) - [(3, 4), (3, 3), (3, 2), (2, 4), (2, 2), (1, 4), (1, 3), (1,
2)]
(2, 4) - [(3, 5), (3, 4), (3, 3), (2, 5), (2, 3), (1, 5), (1, 4), (1,
3)]
(2, 5) - [(3, 6), (3, 5), (3, 4), (2, 6), (2, 4), (1, 6), (1, 5), (1,
4)]
(2, 6) - [(3, 7), (3, 6), (3, 5), (2, 7), (2, 5), (1, 7), (1, 6), (1,
5)]
(2, 7) - [(3, 7), (3, 6), (2, 6), (1, 7), (1, 6)]
(3, 0) - [(4, 1), (4, 0), (3, 1), (2, 1), (2, 0)]
(3, 1) - [(4, 2), (4, 1), (4, 0), (3, 2), (3, 0), (2, 2), (2, 1), (2,
0)]
(3, 2) - [(4, 3), (4, 2), (4, 1), (3, 3), (3, 1), (2, 3), (2, 2), (2,
1)]
(3, 3) - [(4, 4), (4, 3), (4, 2), (3, 4), (3, 2), (2, 4), (2, 3), (2,
2)]
(3, 4) - [(4, 5), (4, 4), (4, 3), (3, 5), (3, 3), (2, 5), (2, 4), (2,
3)]
(3, 5) - [(4, 6), (4, 5), (4, 4), (3, 6), (3, 4), (2, 6), (2, 5), (2,
4)]
(3, 6) - [(4, 7), (4, 6), (4, 5), (3, 7), (3, 5), (2, 7), (2, 6), (2,
5)]
(3, 7) - [(4, 7), (4, 6), (3, 6), (2, 7), (2, 6)]
(4, 0) - [(5, 1), (5, 0), (4, 1), (3, 1), (3, 0)]
(4, 1) - [(5, 2), (5, 1), (5, 0), (4, 2), (4, 0), (3, 2), (3, 1), (3,
0)]
(4, 2) - [(5, 3), (5, 2), (5, 1), (4, 3), (4, 1), (3, 3), (3, 2), (3,
1)]
(4, 3) - [(5, 4), (5, 3), (5, 2), (4, 4), (4, 2), (3, 4), (3, 3), (3,
2)]
(4, 4) - [(5, 5), (5, 4), (5, 3), (4, 5), (4, 3), (3, 5), (3, 4), (3,
3)]
(4, 5) - [(5, 6), (5, 5), (5, 4), (4, 6), (4, 4), (3, 6), (3, 5), (3,
4)]
(4, 6) - [(5, 7), (5, 6), (5, 5), (4, 7), (4, 5), (3, 7), (3, 6), (3,
5)]
(4, 7) - [(5, 7), (5, 6), (4, 6), (3, 7), (3, 6)]
(5, 0) - [(6, 1), (6, 0), (5, 1), (4, 1), (4, 0)]
(5, 1) - [(6, 2), (6, 1), (6, 0), (5, 2), (5, 0), (4, 2), (4, 1), (4,
0)]
(5, 2) - [(6, 3), (6, 2), (6, 1), (5, 3), (5, 1), (4, 3), (4, 2), (4,
1)]
(5, 3) - [(6, 4), (6, 3), (6, 2), (5, 4), (5, 2), (4, 4), (4, 3), (4,
2)]
(5, 4) - [(6, 5), (6, 4), (6, 3), (5, 5), (5, 3), (4, 5), (4, 4), (4,
3)]
(5, 5) - [(6, 6), (6, 5), (6, 4), (5, 6), (5, 4), (4, 6), (4, 5), (4,
4)]
(5, 6) - [(6, 7), (6, 6), (6, 5), (5, 7), (5, 5), (4, 7), (4, 6), (4,
5)]
(5, 7) - [(6, 7), (6, 6), (5, 6), (4, 7), (4, 6)]
(6, 0) - [(7, 1), (7, 0), (6, 1), (5, 1), (5, 0)]
(6, 1) - [(7, 2), (7, 1), (7, 0), (6, 2), (6, 0), (5, 2), (5, 1), (5,
0)]
(6, 2) - [(7, 3), (7, 2), (7, 1), (6, 3), (6, 1), (5, 3), (5, 2), (5,
1)]
(6, 3) - [(7, 4), (7, 3), (7, 2), (6, 4), (6, 2), (5, 4), (5, 3), (5,
2)]
(6, 4) - [(7, 5), (7, 4), (7, 3), (6, 5), (6, 3), (5, 5), (5, 4), (5,
3)]
(6, 5) - [(7, 6), (7, 5), (7, 4), (6, 6), (6, 4), (5, 6), (5, 5), (5,
4)]
(6, 6) - [(7, 7), (7, 6), (7, 5), (6, 7), (6, 5), (5, 7), (5, 6), (5,
5)]
(6, 7) - [(7, 7), (7, 6), (6, 6), (5, 7), (5, 6)]
(7, 0) - [(7, 1), (6, 1), (6, 0)]
(7, 1) - [(7, 2), (7, 0), (6, 2), (6, 1), (6, 0)]
(7, 2) - [(7, 3), (7, 1), (6, 3), (6, 2), (6, 1)]
(7, 3) - [(7, 4), (7, 2), (6, 4), (6, 3), (6, 2)]
(7, 4) - [(7, 5), (7, 3), (6, 5), (6, 4), (6, 3)]
(7, 5) - [(7, 6), (7, 4), (6, 6), (6, 5), (6, 4)]
(7, 6) - [(7, 7), (7, 5), (6, 7), (6, 6), (6, 5)]
(7, 7) - [(7, 6), (6, 7), (6, 6)]

Feb 14 '07 #17

### This discussion thread is closed

Replies have been disabled for this discussion.