473,781 Members | 2,335 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

RFC - n-puzzle.py

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.ph...=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

May 18 '07 #1
6 2577
On May 18, 4:15 pm, Phoe6 <orsent...@gmai l.comwrote:
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.app end(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(sh ort_path) 1:
write:
short_path = mdists[0]
if short_path in mdists[1:]:

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

May 19 '07 #2
On May 19, 2:23 pm, Raymond Hettinger <pyt...@rcn.com wrote:
On May 18, 4:15 pm, Phoe6 <orsent...@gmai l.comwrote:
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

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(sh ort_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. :-)

--
Senthil

http://uthcode.sarovar.org

May 19 '07 #3
Phoe6 wrote:
On May 19, 2:23 pm, Raymond Hettinger <pyt...@rcn.com wrote:
>On May 18, 4:15 pm, Phoe6 <orsent...@gmai l.comwrote:
>>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
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(sh ort_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.
>
>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.
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.blogs pot.com squidoo.com/pythonology
tagged items: del.icio.us/steve.holden/python
All these services currently offer free registration!
-------------- Thank You for Reading ----------------

May 19 '07 #4
Steve Holden wrote:
Phoe6 wrote:
>On May 19, 2:23 pm, Raymond Hettinger <pyt...@rcn.com wrote:
>>Instead of:
short_path = mdists[0]
if mdists.count(sh ort_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
May 19 '07 #5
Peter Otten wrote:
Steve Holden wrote:
>Phoe6 wrote:
>>On May 19, 2:23 pm, Raymond Hettinger <pyt...@rcn.com wrote:
Instead of:
short_path = mdists[0]
if mdists.count(sh ort_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.blogs pot.com squidoo.com/pythonology
tagged items: del.icio.us/steve.holden/python
All these services currently offer free registration!
-------------- Thank You for Reading ----------------

May 19 '07 #6
Phoe6 wrote:
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_s tate(self, st):
It's heuristics, not huristics.

# Choose a random item from exp_sts among those with minimal
# manhattan_dista nce()
exp_sts = self.expand(st)
mdists = []
for st in exp_sts:
mdists.append(s elf.manhattan_d istance(st))
mdists.sort()
short_path = mdists[0]
if mdists.count(sh ort_path) 1:
least_paths = []
for st in exp_sts:
if self.manhattan_ distance(st) == short_path:
least_paths.app end(st)
return random.choice(l east_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.manhat tan_distance)
least_paths = [s for s in exp_sts
if self.manhattan_ distance(s) == short_path]
return random.choice(l east_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(m inima(self.expa nd(st), key=self.manhat tan_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(ke y(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

May 19 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
2027
by: xavier vazquez | last post by:
have a problem with a program that does not working properly...when the program run is suppose to generate a cross word puzzle , when the outcome show the letter of the words overlap one intop of the other....how i can fix this this run the random words for the program import javax.swing.JOptionPane; import java.util.ArrayList; import java.util.Random; public class CrossWordPuzzleTester {
0
9636
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10306
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10139
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
9931
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
8961
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7485
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5504
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4037
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
3632
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.