RFC - n-puzzle.py

Discussion in 'Python' started by Phoe6, May 19, 2007.

  1. Phoe6

    Phoe6 Guest

    Phoe6, May 19, 2007
    #1
    1. Advertising

  2. On May 18, 4:15 pm, Phoe6 <> wrote:
    > 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
     
    Raymond Hettinger, May 19, 2007
    #2
    1. Advertising

  3. Phoe6

    Phoe6 Guest

    On May 19, 2:23 pm, Raymond Hettinger <> wrote:
    > On May 18, 4:15 pm, Phoe6 <> wrote:
    > > 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(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. :)

    --
    Senthil

    http://uthcode.sarovar.org
     
    Phoe6, May 19, 2007
    #3
  4. Phoe6

    Steve Holden Guest

    Phoe6 wrote:
    > On May 19, 2:23 pm, Raymond Hettinger <> wrote:
    >> On May 18, 4:15 pm, Phoe6 <> wrote:
    >>> 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(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.

    >
    >> 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.blogspot.com squidoo.com/pythonology
    tagged items: del.icio.us/steve.holden/python
    All these services currently offer free registration!
    -------------- Thank You for Reading ----------------
     
    Steve Holden, May 19, 2007
    #4
  5. Phoe6

    Peter Otten Guest

    Steve Holden wrote:

    > Phoe6 wrote:
    >> On May 19, 2:23 pm, Raymond Hettinger <> wrote:
    >>> 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
     
    Peter Otten, May 19, 2007
    #5
  6. Phoe6

    Steve Holden Guest

    Peter Otten wrote:
    > Steve Holden wrote:
    >
    >> Phoe6 wrote:
    >>> On May 19, 2:23 pm, Raymond Hettinger <> wrote:
    >>>> 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 ----------------
     
    Steve Holden, May 19, 2007
    #6
  7. Phoe6

    Peter Otten Guest

    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_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
     
    Peter Otten, May 19, 2007
    #7
    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. Marco Gazerro

    RFC: New module Business::GestPayCrypt

    Marco Gazerro, May 14, 2004, in forum: Perl
    Replies:
    0
    Views:
    441
    Marco Gazerro
    May 14, 2004
  2. John Timney \(Microsoft MVP\)

    Re: More efficient RFC 1867 uploads?

    John Timney \(Microsoft MVP\), Jul 11, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    457
    David Waz...
    Jul 11, 2003
  3. Richard K Bethell

    Re: More efficient RFC 1867 uploads?

    Richard K Bethell, Jul 14, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    374
    Richard K Bethell
    Jul 14, 2003
  4. Chris Welch
    Replies:
    1
    Views:
    335
    S. Justin Gengo
    Nov 25, 2003
  5. Ivan Shmakov
    Replies:
    3
    Views:
    1,200
    Kari Hurtta
    Feb 13, 2012
Loading...

Share This Page