RFC - n-puzzle.py

[Peter Otten]

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