Velocity Reviews > nested lists as arrays

# nested lists as arrays

naturalborncyborg
Guest
Posts: n/a

 02-14-2005
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

Fredrik Lundh
Guest
Posts: n/a

 02-14-2005
"naturalborncyborg" <(E-Mail Removed)> 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

(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>

Michael Spencer
Guest
Posts: n/a

 02-14-2005
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]]
>>>

Michael

benjamin.cordes@blawrc.de
Guest
Posts: n/a

 02-14-2005
Allright. What difference in runtime and space would it make using

Do you have a pointer for me concerning runtime of standard
manipulations in Pythons?

Thanks for tip.

benjamin.cordes@blawrc.de
Guest
Posts: n/a

 02-14-2005
Allright. What difference in runtime and space would it make using

Do you have a pointer for me concerning runtime of standard
manipulations in Pythons?

Thanks for the tip.

Fredrik Lundh
Guest
Posts: n/a

 02-14-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> Allright. What difference in runtime and space would it make using

is this for an interactive game? if so, the answer is "none at all".

(on my machine, you can make about 6000000 dict[x,y] accesses per
second, compared to 7500000 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>