[long] nested lists as arrays

[bruno modulix]

benjamin.cordes at blawrc.de 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__() method ?
We can't use the dict.items() method since dicts are not ordered. But we 
can recompute the keys... What about :

def __str__(self):
   s = []
   for row in self.range:
     for col in self.range:
       s.append("%d\t" % self.elements[(row, col)])
     s.append('\n')
   return ''.join(s)

Was not so difficult, finally. Now the compare() has to be rewritten too:

def compare(self, other):
   if (self.dim != other.dim):
     return 0

   for row in self.range:
     for col in self.range:
       if self.elements[(row,col)] != other.elements[(row,col)]:
         return False
   # no difference
   return True

Err... Wait a minute... What are we doing here ? Comparing 2 dicts ? 
Wait, wait, let's check something...

 >>> '__eq__' in dir(dict)
True

Haha ! Our good'ole dict already has an 'equality' special method... Now 
is this a 'value' or 'identity' equality ?

 >>> d1 = {1:1, 2:2}
 >>> d2 = {2:2, 1:1}
 >>> d1 == d2
True

Bingo ! Play it again, sam :

def compare(self, other):
   return self.elements == other.elements

Hehehe. Less code, better code, as grand'ma used to say !-)

Now the fine part : let's make it move. What was it like ?

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)

This won't work since our swapElements() method now expects 2 tuples. 
Let's look closer. The first pair is always the same, it's the actually 
the empty slot. Quite sensible. We just have to create the second tuple 
from the first. And BTW, I don't like the if/elif neither. What about 
using a dict again ? :

def performMove(self, direction):
   slot = self.getEmptySlot()
   to_slot = {'up'   : lambda (row, col): (row-1, col),
              'down' : lambda (row, col): (row+1, col),
              'left' : lambda (row, col): (row, col-1),
              'right': lambda (row, col): (row, col+1)}
   self.swapElements(slot, to_slot[direction](slot))

Better, but not quite ok: it's silly to recreate the to_slot dict each 
time. Let's put it in the __init__ :

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

   self.to_slot = {'up'   : lambda (row, col): (row-1, col),
        	          'down' : lambda (row, col): (row+1, col),
                   'left' : lambda (row, col): (row, col-1),
                   'right': lambda (row, col): (row, col+1)}


and now our performMove() method become:

def performMove(self, direction):
   slot = self.getEmptySlot()
   self.swapElements(slot, self.to_slot[direction](slot))


Begins to look better, isn't it ? Ok, your turn to play !-)
Just two more things :

1/
getPossibleMoves(self):
   emptySlot = self.getEmptySlot()
   y = emptySlot[1]
   x = emptySlot[0]
   (...)

could benefit from being rewritten as:

getPossibleMoves(self):
   row, col = self.getEmptySlot()
   (...)

(Yes, Python will automagically 'unpack' the tuple !-)

2/
     def getChildren(self):
         moves = self.getPossibleMoves()
         self.children = []
         for eachMove in moves:
             newchild = copy.copy(self.performMove(eachMove))

performMove() doesn't explicitly return anything, so it implicitly 
returns None. This may not give you what you want !-)

If the idea is to 'capture' the state of the puzzle object, you may want 
to have performMove() returning self. *But* remember that the state of 
the puzzle object is affected by performMove(), so this may not behave 
as expected either, since after each move, the possible moves change.

So the solution would be to 'clone' self *before* each performMove(), 
call the performMove() on each clone and store the clone.

(BTW, the name of the method may be somewhat misleading, and I'm not 
sure this method really belongs to the Puzzle class. )

and finally (pun intend !-) :

             try:
                 self.children.append(newchild)
             except:
                 print "Exception: " + str(len(self.children))

This is the only place where you handle exceptions. But there is no 
particular reason to expect an exception here. So your try/except block 
is useless. Worse, it's badly coded, since you don't specify which 
exception you want to catch. This may put you into troubles (probably 
not here, but... I recently had hard time to debug some code that had 
many 'catch-all' except clauses.)

Well... You seem to like puzzles, so I leave it up to you to finish that 
one.

*warning* : this 100% untested code. You should write some unit tests to 
make sure every method woks as expected.

HTH
Bruno