444,100 Members | 2,495 Online
Need help? Post your question and get tips & solutions from a community of 444,100 IT Pros & Developers. It's quick & easy.

# RFC - n-puzzle.py

 P: n/a 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 Replies

 P: n/a On May 18, 4:15 pm, Phoe6

 P: n/a On May 19, 2:23 pm, Raymond Hettinger 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 May 19 '07 #3

 P: n/a Steve Holden wrote: Phoe6 wrote: >On May 19, 2:23 pm, Raymond Hettinger >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 ifstatements.I had used count method, to signify the meaning that, if the leastdistance 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

 P: n/a Peter Otten wrote: Steve Holden wrote: >Phoe6 wrote: >>On May 19, 2:23 pm, Raymond Hettinger

 P: n/a 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 May 19 '07 #7

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

Browse more Python Questions on Bytes