nested lists as arrays

Discussion in 'Python' started by naturalborncyborg, Feb 14, 2005.

  1. 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] == -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
     
    naturalborncyborg, Feb 14, 2005
    #1
    1. Advertising

  2. "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 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>
     
    Fredrik Lundh, Feb 14, 2005
    #2
    1. Advertising

  3. 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
     
    Michael Spencer, Feb 14, 2005
    #3
  4. naturalborncyborg

    Guest

    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.
     
    , Feb 14, 2005
    #4
  5. naturalborncyborg

    Guest

    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.
     
    , Feb 14, 2005
    #5
  6. 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 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>
     
    Fredrik Lundh, Feb 14, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JustSomeGuy

    Sorting lists of lists...

    JustSomeGuy, Jun 17, 2004, in forum: C++
    Replies:
    0
    Views:
    329
    JustSomeGuy
    Jun 17, 2004
  2. Replies:
    2
    Views:
    351
    Terry Reedy
    Feb 14, 2005
  3. nested lists as arrays

    , Feb 14, 2005, in forum: Python
    Replies:
    9
    Views:
    412
  4. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    413
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  5. Philipp
    Replies:
    21
    Views:
    1,139
    Philipp
    Jan 20, 2009
Loading...

Share This Page