RFC - n-puzzle.py

[Phoe6]

Hi All,
I would like to request a code and design review of one of my program.
n-puzzle.py
http://sarovar.org/snippet/detail.php?type=snippet&id=83
Its a N-puzzle problem solver ( Wikipedia page and http://norvig.com/ltd/test/n-puzzle.lisp
)

I have used OO Python for the above program and would like comments on
my approach as I am just starting with OOP.

Thanks
Senthil

 

[Raymond Hettinger]

Hi All,
I would like to request a code and design review of one of my program.
n-puzzle.pyhttp://sarovar.org/snippet/detail.php?type=snippet&id=83
Its a N-puzzle problem solver ( Wikipedia page andhttp://norvig.com/ltd/test/n-puzzle.lisp
)

I have used OO Python for the above program and would like comments on
my approach as I am just starting with OOP.

Thanks
Senthil

Nice job, this doesn't look like a beginner program at all.

For feedback, here's a few nits:

Instead of:
if key + x in range(0, self.tsize):
write:
if 0 <= key + x < self.tsize:


Instead of:
mdist = mdist + jumps + steps
write:
mdist += jumps + steps


Instead of:
least_paths = []
for st in exp_sts:
if self.manhattan_distance(st) == short_path:
least_paths.append(st)
write:
least_paths = [st for st in exp_sts if self.manhattan_distance(st)
== short_path]

Instead of:
short_path = mdists[0]
if mdists.count(short_path) > 1:
write:
short_path = mdists[0]
if short_path in mdists[1:]:

Instead of:
if node != 0:
write:
if node:


Raymond

 

[Phoe6]

Nice job, this doesn't look like a beginner program at all.

Thanks Raymond.

For feedback, here's a few nits:

Yes, I made changes in them all. Thanks for the list comprehension
pointer, I missed it.

Instead of:
short_path = mdists[0]
if mdists.count(short_path) > 1:
write:
short_path = mdists[0]
if short_path in mdists[1:]:

I would like to understand the difference between the two if
statements.
I had used count method, to signify the meaning that, if the least
distance occurs more then proceed with block.
How is 'in' with list[1:] an advantage? If it is.

Instead of:
if node != 0:
write:
if node:

Here again, I went by the meaning of non-zero value nodes and made
comparision with node != 0. Just in case, the n-states were
represented by '0', '1', '2', '3', I would have gone for node != '0'
sticking to the meaning. I think, I should aid it with a comment,
otherwise might get confused in the future.

Thanks a lot, Raymond.

 

[Steve Holden]

Nice job, this doesn't look like a beginner program at all.

Thanks Raymond.

For feedback, here's a few nits:

Yes, I made changes in them all. Thanks for the list comprehension
pointer, I missed it.

Instead of:
short_path = mdists[0]
if mdists.count(short_path) > 1:
write:
short_path = mdists[0]
if short_path in mdists[1:]:

I would like to understand the difference between the two if
statements.
I had used count method, to signify the meaning that, if the least
distance occurs more then proceed with block.
How is 'in' with list[1:] an advantage? If it is.

Because it can stop as soon as short_path is found, whereas the count
method must examine all elements to determine whether they should
increment the count beyond one.

Here again, I went by the meaning of non-zero value nodes and made
comparision with node != 0. Just in case, the n-states were
represented by '0', '1', '2', '3', I would have gone for node != '0'
sticking to the meaning. I think, I should aid it with a comment,
otherwise might get confused in the future.

This is a standard Python idiom. If you had used strings then the test
*would* have had to explicitly compare against '0', but when evaluating
for a test Python treats zeros, the empty string, the empty list, set or
dictionary, None (and various other possibilties) as false.

It's not a big deal, but it will be just a tad faster.

Thanks a lot, Raymond.

Channeling Raymond, he says you're welcome.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
------------------ Asciimercial ---------------------
Get on the web: Blog, lens and tag your way to fame!!
holdenweb.blogspot.com squidoo.com/pythonology
tagged items: del.icio.us/steve.holden/python
All these services currently offer free registration!
-------------- Thank You for Reading ----------------

 

[Peter Otten]

Instead of:
short_path = mdists[0]
if mdists.count(short_path) > 1:
write:
short_path = mdists[0]
if short_path in mdists[1:]:

I would like to understand the difference between the two if
statements.
I had used count method, to signify the meaning that, if the least
distance occurs more then proceed with block.
How is 'in' with list[1:] an advantage? If it is.

Because it can stop as soon as short_path is found, whereas the count
method must examine all elements to determine whether they should
increment the count beyond one.

It's a trade-off. You check only half (on average) of the items in the
original list, but in exchange copy all but one into a new list.
The idiom Raymond recommended only makes sense because comparison is "slow"
and slicing is "fast" in Python.

If the original list were large in comparison to the available RAM the
following idiom might be preferrable:

it = iter(mdists)
short_path = it.next()
if short_path in it:
# ...

Peter

 

[Steve Holden]

Instead of:
short_path = mdists[0]
if mdists.count(short_path) > 1:
write:
short_path = mdists[0]
if short_path in mdists[1:]:
I would like to understand the difference between the two if
statements.
I had used count method, to signify the meaning that, if the least
distance occurs more then proceed with block.
How is 'in' with list[1:] an advantage? If it is.

Because it can stop as soon as short_path is found, whereas the count
method must examine all elements to determine whether they should
increment the count beyond one.

It's a trade-off. You check only half (on average) of the items in the
original list, but in exchange copy all but one into a new list.
The idiom Raymond recommended only makes sense because comparison is "slow"
and slicing is "fast" in Python.

That's true.

If the original list were large in comparison to the available RAM the
following idiom might be preferrable:

it = iter(mdists)
short_path = it.next()
if short_path in it:
# ...

Yes, that would nail it. Though of course it loses the obviousness which
both original solutions have. I suppose that's often the nature of
optimizations, though.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
------------------ Asciimercial ---------------------
Get on the web: Blog, lens and tag your way to fame!!
holdenweb.blogspot.com squidoo.com/pythonology
tagged items: del.icio.us/steve.holden/python
All these services currently offer free registration!
-------------- Thank You for Reading ----------------

 

[Peter Otten]

I would like to request a code and design review of one of my program.
n-puzzle.py

I have used OO Python for the above program and would like comments on
my approach as I am just starting with OOP.

[The following has nothing to do with OOP, I just read Raymond's post and
got interested in the context]

class State:

def huristic_next_state(self, st):

It's heuristics, not huristics.

# Choose a random item from exp_sts among those with minimal
# manhattan_distance()

exp_sts = self.expand(st)
mdists = []
for st in exp_sts:
mdists.append(self.manhattan_distance(st))
mdists.sort()
short_path = mdists[0]
if mdists.count(short_path) > 1:
least_paths = []
for st in exp_sts:
if self.manhattan_distance(st) == short_path:
least_paths.append(st)
return random.choice(least_paths)
else:
for st in exp_sts:
if self.manhattan_distance(st) == short_path:
return st

Looks like you do not need the count() method call at all as the branch for
multiple nearest items works with a length-one list, too. As a consequence,
there's no need to keep a list of distances, just the minimum:

# all untested
exp_sts = self.expand(st)
short_path = min(exp_sts, key=self.manhattan_distance)
least_paths = [s for s in exp_sts
if self.manhattan_distance(s) == short_path]
return random.choice(least_paths)

Calling random.choice() on a list with only one item is predictable but will
do no harm if the code is not time-critical.

By the way, you could write a helper function that finds all minima
according to some criterion

minima([1, 2, -1, 1.0, 3], key=abs)

[1, -1, 1.0]

With such a function the method body would become

return random.choice(minima(self.expand(st), key=self.manhattan_distance))

Almost self-documenting, I'd say

Here's a quick and dirty implementation:

def minima(values, key=lambda x: x):
d = {}
for v in values:
d.setdefault(key(v), []).append(v)
return d[min(d)]

The advantage of this approach is that you

- iterate over the list just once
- call the key() function once per list item
- can test the function independently from your State class

The memory overhead for the extra lists can be avoided by a better
implementation.

Peter