Phoe6 said:
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]
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