Re: [long] nested lists as arrays
great thanks -- http://mail.python.org/mailman/listinfo/python-list
Problem with nested lists as arrays
Hello, For a class modeling the block puzzle I use nested lists as arrays. Within this class there is a method for swaping elements. I have lots of trouble with that method but can't figure it out. It has probably to do with my unuseful approach to nested lists, but I don't want to write the code again. As I am a python newbie any other comments on the code will be appreciated. Thanks for any help. # Puzzle.py # class for a sliding block puzzle # an starting state of a 8-puzzle could look like the following: # # | 7 2 4 | # | | # | 5 X 6 | # | | # | 8 3 1 | # # the goal is to reach this state: # # | X 1 2 | # | | # | 3 4 5 | # | | # | 6 7 8 | # import copy class Puzzle: def __init__(self, dim): self.dim = dim self.elements = [[0 for column in range(dim)] for row in range(dim) ] def getEmptySlot(self): i = 0 j = 0 while i = self.dim-1: while j = self.dim-1: if self.elements[j][i] == -1: return [j, i] j = j+1 j = 0 i = i + 1 def performMove(self, direction): slot = self.getEmptySlot() if (direction == up): self.swapElements(slot[1], slot[0], slot[1]+1, slot[0]) elif (direction == down): self.swapElements(slot[1], slot[0], slot[1]-1, slot[0]) elif direction == left: self.swapElements(slot[1], slot[0], slot[1], slot[0]-1) elif (direction == right): self.swapElements(slot[1], slot[0], slot[1], slot[0]+1) def swapElements(self, fromx, fromy, tox, toy): dummy = self.elements[toy][tox] self.elements[toy][tox] = self.elements[fromy][fromx] self.elements[fromy][fromx] = dummy def getPossibleMoves(self): emptySlot = self.getEmptySlot() y = emptySlot[1] x = emptySlot[0] north = (y == 0) south = (y == (self.dim-1)) west = (x == 0) east = (x == (self.dim-1)) middle = not(north or south or west or east) northwest = north and west northeast = north and east southwest = south and west southeast = south and east # orientation has to be distinct # save original values orignorth = north origsouth = south # original north or south orignors = north or south north = north and not (west or east) south = south and not (west or east) west = west and not (orignors) east = east and not (orignors) if middle: return [up, down, left, right] elif north: return [up, left, right] elif south: return [down, left, right] elif west: return [up, down, left] elif east: return [up, down, right] elif northwest: return [up, left] elif northeast: return [up, right] elif southwest: return [down, left] elif southeast: return [down, right] # ~Puzzle.py -- http://mail.python.org/mailman/listinfo/python-list
Re: Problem with nested lists as arrays
Some general remarks: def getEmptySlot(self): i = 0 j = 0 while i = self.dim-1: while j = self.dim-1: if self.elements[j][i] == -1: return [j, i] j = j+1 j = 0 i = i + 1 make this: def getEmptySlot(self): for i in xrange(self.dim): for j in xrange(self.dim): if self.elements[i][j] == -1: return (i,j) def getPossibleMoves(self): emptySlot = self.getEmptySlot() y = emptySlot[1] x = emptySlot[0] make this: x,y = self.getEmptySlot() -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
[EMAIL PROTECTED] wrote: Hi, why can't I do this: dummy = self.elements[toy][tox] self.elements[toy][tox] = self.elements[fromy][fromx] self.elements[fromy][fromx] = dummy after initialising my nested list like this: self.elements = [[0 for column in range(dim)] for row in range(dim) ] Works for me: dim = 10 elements = [[0 for column in xrange(dim)] for row in xrange(dim) ] toy, tox = (2,5) fromy, fromx = (7,5) dummy =elements[toy][tox] elements[toy][tox] = elements[fromy][fromx] elements[fromy][fromx] = dummy And use xrange instead of range. -- Regards, Diez B. Roggisch -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
[EMAIL PROTECTED] wrote:
Hi,
why can't I do this:
dummy = self.elements[toy][tox]
self.elements[toy][tox] = self.elements[fromy][fromx]
self.elements[fromy][fromx] = dummy
after initialising my nested list like this:
self.elements = [[0 for column in range(dim)] for row in
range(dim) ]
Sorry, I'm not psychic enough to guess what is exactly your problem:
- what do you mean can't do ? You have a traceback ? please post it.
You have unexpected results ? please describe.
- what are self, dim, toy, tox, fromy, fromx ?
- is all that code in the same method ?
- etc etc
So please post more informations if you expect us to help you.
Note that the following code is correct:
l = [[0 for i in range(3)] for y in range(3)]
l
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
l[0][0] = 1
l
[[1, 0, 0], [0, 0, 0], [0, 0, 0]]
l[0][0], l[0][1] = l[0][1], l[0][0]
l
[[0, 1, 0], [0, 0, 0], [0, 0, 0]]
So I guess that your problem has nothing to do with nested lists.
(Also note BTW that, thanks to the magic of multiple assignement, you
don't need the dummy stuff. The pythonic idiom for swapping 2 bindings is
a, b = b, a)
--
bruno desthuilliers
python -c print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in '[EMAIL PROTECTED]'.split('@')])
--
http://mail.python.org/mailman/listinfo/python-list
nested lists as arrays
Hi, I'm using nested lists as arrays and having some problems with that approach. In my puzzle class there is a swapelement method which doesn't work out. Any help and comments on the code will be appreciated. Thanks. # Puzzle.py # class for a sliding block puzzle # an starting state of a 8-puzzle could look like the following: # where X is an empty space and the move up in the example would move 6 to X # X is represented as -1 in the array # # | 7 2 4 | # | | # | 5 X 6 | # | | # | 8 3 1 | # # the goal is to reach this state: # # | X 1 2 | # | | # | 3 4 5 | # | | # | 6 7 8 | # import copy class Puzzle: def __init__(self, dim): self.dim = dim self.elements = [[0 for column in range(dim)] for row in range(dim) ] def getEmptySlot(self): i = 0 j = 0 while i = self.dim-1: while j = self.dim-1: if self.elements[j][i] == -1: return [j, i] j = j+1 j = 0 i = i + 1 def performMove(self, direction): slot = self.getEmptySlot() if (direction == up): self.swapElements(slot[1], slot[0], slot[1]+1, slot[0]) elif (direction == down): self.swapElements(slot[1], slot[0], slot[1]-1, slot[0]) elif direction == left: self.swapElements(slot[1], slot[0], slot[1], slot[0]-1) elif (direction == right): self.swapElements(slot[1], slot[0], slot[1], slot[0]+1) def swapElements(self, fromx, fromy, tox, toy): dummy = self.elements[toy][tox] self.elements[toy][tox] = self.elements[fromy][fromx] self.elements[fromy][fromx] = dummy def getPossibleMoves(self): emptySlot = self.getEmptySlot() y = emptySlot[1] x = emptySlot[0] north = (y == 0) south = (y == (self.dim-1)) west = (x == 0) east = (x == (self.dim-1)) middle = not(north or south or west or east) northwest = north and west northeast = north and east southwest = south and west southeast = south and east # orientation has to be distinct # save original values orignorth = north origsouth = south # original north or south orignors = north or south north = north and not (west or east) south = south and not (west or east) west = west and not (orignors) east = east and not (orignors) if middle: return [up, down, left, right] elif north: return [up, left, right] elif south: return [down, left, right] elif west: return [up, down, left] elif east: return [up, down, right] elif northwest: return [up, left] elif northeast: return [up, right] elif southwest: return [down, left] elif southeast: return [down, right] # ~Puzzle.py -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
Diez B. Roggisch wrote: [EMAIL PROTECTED] wrote: Hi, why can't I do this: dummy = self.elements[toy][tox] self.elements[toy][tox] = self.elements[fromy][fromx] self.elements[fromy][fromx] = dummy after initialising my nested list like this: self.elements = [[0 for column in range(dim)] for row in range(dim) ] Works for me: dim = 10 elements = [[0 for column in xrange(dim)] for row in xrange(dim) ] toy, tox = (2,5) fromy, fromx = (7,5) dummy =elements[toy][tox] elements[toy][tox] = elements[fromy][fromx] elements[fromy][fromx] = dummy And use xrange instead of range. -- Regards, Diez B. Roggisch thanks so far, and sorry for posting the topic now 3 times. -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
naturalborncyborg [EMAIL PROTECTED] wrote:
Hi, I'm using nested lists as arrays and having some problems with
that approach. In my puzzle class there is a swapelement method which
doesn't work out.
what happens, and what do you expect?
Any help and comments on the code will be appreciated.
is it elements[y][x] or elements[x][y]? both variants seem to be used
in your code.
(fwiw, in this case, using a dictionary might be a lot easier. store cells
as elements[x, y], use elements.get((x, y)) is None to check for empty
cells, use elements[x, y] = None or del elements[x, y] to empty a cell,
use elements = {} to clear all cells, etc).
/F
--
http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
naturalborncyborg wrote: Hi, I'm using nested lists as arrays and having some problems with that approach. In my puzzle class there is a swapelement method which doesn't work out. What doesn't work out? On casual inspection that method seems to work: p = Puzzle(2) p.elements[0][0] = 1 p.elements[1][1] = 2 p.elements [[1, 0], [0, 2]] p.swapElements(0,0,1,1) p.elements [[2, 0], [0, 1]] What should it do instead? Michael -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
Thanks for the code.
What I want to do is this:
I want to solve the block puzzle problem. The problem is as follows:
You have a nxn Array of Numbers and one empty space. Now you there are
up to four possible moves: up, right, down and left, so that each
neighbour of the empty slot can be moved there.
The method getEmptySlot is for getting the empty slot. The method
getPossibleMoves returns the possible moves. Perfoming a move is
swaping one element with the empty slot marked as -1.
The full executable code is appended.
The expected behaviour is that when the move is performed the
appropiate elements should be swaped. But for some reason every now and
then it swaps the wrong elements.
# Puzzle.py
# class for a sliding block puzzle
# an starting state of a 8-puzzle could look like the following:
#
# | 7 2 4 |
# | |
# | 5 X 6 |
# | |
# | 8 3 1 |
#
# the goal is to reach this state:
#
# | X 1 2 |
# | |
# | 3 4 5 |
# | |
# | 6 7 8 |
#
import random
import copy
class Puzzle:
def __init__(self, dim):
self.dim = dim
# self.elements = {}
# for column in range(dim):
# for row in range(dim):
# elements[(column, row)] = 0
self.elements = [[0 for column in range(dim)] for row in
range(dim) ]
def __str__(self):
s =
i = 0
j = 0
while i = self.dim-1:
while j = self.dim-1:
s = s + str(self.elements[j][i])
j=j+1
s = s + \t
i=i+1
j = 0
s = s + \n
return s
def compare(self, compareTo):
if (self.dim != compareTo.dim):
return 0
i = 0
j = 0
equal = 1
while i = self.dim-1:
while j = self.dim-1:
if self.elements[j][i] != compareTo.elements[j][i]:
equal = 0
j = j+1
i = i+1
return equal
def setAsGoalState(self):
# create elements of puzzle
i = 0
j = 0
while i = self.dim-1:
while j = self.dim-1:
self.elements[j][i] = i*3+j
j=j+1
j=0
i=i+1
# create empty element seperately
self.elements[0][0] = -1
def setRandomState(self):
# container for the elements to pick from
container = [1,2,3,4,5,6,7,8,-1]
# create elements of puzzle randomly
i = 0
j = 0
while i = self.dim-1:
while j = self.dim-1:
if len(container) 0:
randomindex = random.randint(0,len(container)-1)
self.elements[j][i] = container[randomindex]
del container[randomindex]
j=j+1
else:
break
j=0
i=i+1
def getEmptySlot(self):
i = 0
j = 0
while i = self.dim-1:
while j = self.dim-1:
if self.elements[j][i] == -1:
return [j, i]
j = j+1
j = 0
i = i + 1
def performMove(self, direction):
slot = self.getEmptySlot()
if (direction == up):
self.swapElements(slot[1], slot[0], slot[1]+1, slot[0])
elif (direction == down):
self.swapElements(slot[1], slot[0], slot[1]-1, slot[0])
elif direction == left:
self.swapElements(slot[1], slot[0], slot[1], slot[0]-1)
elif (direction == right):
self.swapElements(slot[1], slot[0], slot[1], slot[0]+1)
def swapElements(self, fromx, fromy, tox, toy):
dummy = self.elements[toy][tox]
self.elements[toy][tox] = self.elements[fromy][fromx]
self.elements[fromy][fromx] = dummy
def getChildren(self):
moves = self.getPossibleMoves()
self.children = []
for eachMove in moves:
newchild = copy.copy(self.performMove(eachMove))
try:
self.children.append(newchild)
except:
print Exception: + str(len(self.children))
def getPossibleMoves(self):
emptySlot = self.getEmptySlot()
y = emptySlot[1]
x = emptySlot[0]
north = (y == 0)
south = (y == (self.dim-1))
west = (x == 0)
east = (x == (self.dim-1))
middle = not(north or south or west or east)
northwest = north and west
northeast = north and east
southwest = south and west
southeast = south and east
# orientation has to be distinct
# save original values
orignorth = north
origsouth = south
# original north or south
orignors = north or south
north = north and not (west or east)
south = south and not (west or east)
west = west and not (orignors)
east =
Re: Problem with nested lists as arrays
[EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] 'Having trouble' is too vague to figure out. However, I would delete this: def getEmptySlot(self): i = 0 j = 0 while i = self.dim-1: while j = self.dim-1: if self.elements[j][i] == -1: return [j, i] j = j+1 j = 0 i = i + 1 and maintain an .empty attribute, which is trivially updated in def swapElements(self, fromx, fromy, tox, toy): dummy = self.elements[toy][tox] self.elements[toy][tox] = self.elements[fromy][fromx] self.elements[fromy][fromx] = dummy as (fromy,fromx). Note that there is no need to pass tox, toy to this routine. Indeed, I would include the last two lines in your move routine. Since dummy is always the same object, I would also just keep it as self._dummy instead of looking it up each time. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
Diez B. Roggisch [EMAIL PROTECTED] wrote in message And use xrange instead of range. For small dimensions like 3,4,5, xrange is way overkill and perhaps takes both more space and time. Since dim is a constant for a given puzzle, I would set self._range = range(dim) in __init__() and use that to iterate. And, as I said in another response, I would not iterate to make a move. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
Allright. What difference in runtime and space would it make using dictionaries instead? Do you have a pointer for me concerning runtime of standard manipulations in Pythons? Thanks for tip. -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
Allright. What difference in runtime and space would it make using dictionaries instead? Do you have a pointer for me concerning runtime of standard manipulations in Pythons? Thanks for the tip. -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
[EMAIL PROTECTED] wrote: Allright. What difference in runtime and space would it make using dictionaries instead? is this for an interactive game? if so, the answer is none at all. (on my machine, you can make about 600 dict[x,y] accesses per second, compared to 750 list[x][y] accesses... assuming that your algorithm needs to check each cell on the board 10 times per move, and you want the moves to appear instantly, the slower solution should be fast enough for a 250x250 board, compared to a 270x270 board for the faster solution...). /F -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
[EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] def setRandomState(self): # container for the elements to pick from container = [1,2,3,4,5,6,7,8,-1] # create elements of puzzle randomly i = 0 j = 0 while i = self.dim-1: while j = self.dim-1: if len(container) 0: randomindex = random.randint(0,len(container)-1) self.elements[j][i] = container[randomindex] del container[randomindex] j=j+1 else: break j=0 i=i+1 Without reading closely, I believe that the above can generate any possible position. Are you aware that half are unsolvable? If that matters, you need to either find a book or site that explains the parity test for solvability or generate the start position from the goal position by a series of random moves. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: nested lists as arrays
Terry Reedy wrote: [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] def setRandomState(self): # container for the elements to pick from container = [1,2,3,4,5,6,7,8,-1] # create elements of puzzle randomly i = 0 j = 0 while i = self.dim-1: while j = self.dim-1: if len(container) 0: randomindex = random.randint(0,len(container)-1) self.elements[j][i] = container[randomindex] del container[randomindex] j=j+1 else: break j=0 i=i+1 Without reading closely, I believe that the above can generate any possible position. Are you aware that half are unsolvable? If that matters, you need to either find a book or site that explains the parity test for solvability or generate the start position from the goal position by a series of random moves. Terry J. Reedy This covers the test for solvability - enjoy ;-): http://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-24.pdf BTW, just because your puzzle looks like a grid doesn't neceesarily mean that representing the data as nested arrays is easiest. A flat list might be just as good here. It simplifies some of the operations (creating a random ordering becomes a one-liner), at the expense of a little more complexity in some others: import random class n2grid(object): A grid for the n squared puzzle def __init__(self,dim = 4): self.cells = range(dim*dim) self.dim = dim self.pos = (0,0) def shuffle(self): random.shuffle(self.cells) self.pos = divmod(self.cells.index(0),self.dim) def show(self): for row in self._asarray(): print .join([%2s] % (cell or ) for cell in row) def _move(self,dy,dx): dim = self.dim cells = self.cells oldy, oldx = self.pos newy, newx = oldy + dy, oldx + dx if 0 = newx dim and 0 = newy dim: ix = newy * dim + newx ox = oldy * dim + oldx cells[ix], cells[ox] = cells[ox], cells[ix] self.pos = newy,newx else: raise Exception, Illegal move to: (%s,%s) % (newy, newx) def move(self, dx, dy): try: self._move(dx,dy) self.show() except: pass def _asarray(self): #create the array representation when needed cells = iter(self.cells) dim = self.dim return [[cells.next() for j in range(dim)] for i in range(dim)] def __repr__(self): return repr(self._asarray()) p = n2grid() p.show() ... [ ][ 1][ 2][ 3] [ 4][ 5][ 6][ 7] [ 8][ 9][10][11] [12][13][14][15] p.shuffle() p.show() [ 3][15][ 6][ 7] [10][ ][12][ 5] [ 4][ 1][14][ 8] [ 2][11][13][ 9] p.move(1,1) [ 3][15][ 6][ 7] [10][14][12][ 5] [ 4][ 1][ ][ 8] [ 2][11][13][ 9] p.move(1,0) [ 3][15][ 6][ 7] [10][14][12][ 5] [ 4][ 1][13][ 8] [ 2][11][ ][ 9] p.move(1,0) # illegal (does nothing) Cheers Michael -- http://mail.python.org/mailman/listinfo/python-list
Re: [long] nested lists as arrays
[EMAIL PROTECTED] a écrit :
Thanks for the code.
What I want to do is this:
I want to solve the block puzzle problem. The problem is as follows:
You have a nxn Array of Numbers and one empty space. Now you there are
up to four possible moves: up, right, down and left, so that each
neighbour of the empty slot can be moved there.
The method getEmptySlot is for getting the empty slot. The method
getPossibleMoves returns the possible moves. Perfoming a move is
swaping one element with the empty slot marked as -1.
The full executable code is appended.
s/executable/source/ !-)
The expected behaviour is that when the move is performed the
appropiate elements should be swaped. But for some reason every now and
then it swaps the wrong elements.
So the problem is not that you can't swap 2 elements, but that there
seems to be some logical bug(s) in your code.
# Puzzle.py
# class for a sliding block puzzle
(snip)
import random
import copy
class Puzzle:
def __init__(self, dim):
self.dim = dim
self.elements = [[0 for column in range(dim)] for row in
range(dim) ]
So at this stage you've got 3 rows of 3 colums:
[
['row 0 - col 0', 'row 0 - col 1', 'row 0 - col 2'],
['row 1 - col 0', 'row 1 - col 1', 'row 1 - col 2'],
['row 2 - col 0', 'row 2 - col 1', 'row 2 - col 2']
]
Is that right ?
def __str__(self):
s =
i = 0
j = 0
while i = self.dim-1:
ok, looping on rows
while j = self.dim-1:
and now looping on columns in current row...
s = s + str(self.elements[j][i])
oops ! Looks like you're addressing row[j] column[i] instead of row[i]
column[j] !-)
j=j+1
s = s + \t
i=i+1
j = 0
s = s + \n
return s
(snip the rest of the code)
Ok, let's try with a slightly more pythonic (and thus more readable)
version of this code (I used another method name so we can compare both
versions):
def to_string(self):
s = []
for row in self.elements:
for col in row:
s.append('%d\t' % col)
s.append('\n')
return ''.join(s)
For testing purpose, let's modify the __init__ a bit (this will break
the code but what, it's just to check something, we can get back to
original code later):
def __init__(self, dim):
self.dim = dim
self.range = range(self.dim)
#self.elements = [[0 for column in self.range] for row in self.range]
self.elements = [[int('%d%d' % (row, column)) for column in
self.range] for row in self.range]
# check we have a correct layout, remove me when fixed:
print %s % self.elements
and now let's try:
p = Puzzle(3)
[[0, 1, 2], [10, 11, 12], [20, 21, 22]]
so far, so good, we have 3 rows of 3 columns each.
let's continue:
print p.to_string()
0 1 2
10 11 12
20 21 22
Ok, so our new to_string() method is ok. Now the real test:
print p
0 10 20
1 11 21
2 12 22
Remember ?
oops ! Looks like you're addressing row[j] column[i] instead of row[i]
column[j]
Looks like we found one bug...
Let's continue and rewrite some more code:
def compare(self, other):
if (self.dim != other.dim):
return False
for self_row, other_row in zip(self.elements, other.elements):
for self_col, other_col in zip(self_row, other_row):
if self_col != other_col:
return False
return True
Ok, that one was easy. Let's try with another one
def getEmptySlot(self):
for row in self.elements:
for cell in row:
if cell == -1:
return ???
Mmmm... won't work. Seems we need indices here, let's try again:
def getEmptySlot(self):
for row in self.range:
for col in self.range:
if self.elements[row][col] == -1:
return (row, col)
Ok, not so clean but still readable (notice how using explicit names
like 'row' and 'col' helps understanding the code...).
Now let's do the swap:
def swapElements(self, from_cell, to_cell):
from_row, from_col = from_cell
to_row, to_col = to_cell
elts = self.elements
elts[to_row][to_col], elts[from_row][from_col] =
elements[from_row][from_col], elts[to_row][to_col]
Mmmm... this begins to smell. I don't like having to split the coords
like this. I'd prefer something like:
def swapElements(self, from_cell, to_cell):
self.elements[from_cell], self.elements[to_cell] \
= self.elements[to_cell], self.elements[from_cell]
This could be possible if we used another data structure. Something like
a dict of coords:value pairs. We could build it like this:
def __init__(self, dim):
self.dim = dim
self.range = range(self.dim)
self.elements = {}
for row in self.range:
for col in self.range:
self.elements[(row,col)] = 0
and then the search for the empty slot:
def getEmptySlot(self):
for coords, value in self.elements.items():
if value == -1:
return coords
assert(False) # shouldn't be here anyway !
Hey, that looks nicer, isn't it ? But what with the __str__()
