text: Better Way to Calculate Score?
   
  The code below works until the system runs out of memory. My guess is that a state's score is not drawing good states quickly enough to the top of the heap The __lt__ method is inversed so that higher scores are favored. States get a higher score for longer chains but are penalized for the most common shared person that people can give to. The __eq__ and __hash__ methods are designed to avoid duplicate states.
  Can anyone recommend a better way of calculating the score for a state?
  from collections import Counter from heapq import heappop, heappush from itertools import chain, tee def find_chains(family, couples): "Return the longest list of gift chains as a list of lists." target = TABLE[Z(family), Z(map(Z, couples))] if not target: return () return tuple(map(list, Machine(family, couples, target).search())) def pairwise(iterable): a, b = tee(iterable) next(b, None) return zip(a, b) class Machine: def __init__(self, family, couples, target): self.family = family self.couples = couples self.target = target self.options = {name: family - {name} for name in family} for a, b in couples: self.options[a].remove(b) self.options[b].remove(a) self.state = State((), self.options) def search(self): heap, skip = [self.state], {self.state} while heap: state = heappop(heap) for child in state.children: if len(child.chain) == self.target: return child.chain if child not in skip: skip.add(child) heappush(heap, child) return () class State: def __init__(self, chain, options): self.chain = chain self.options = options def __lt__(self, other): return self.score > other.score @property def score(self): score = len(self.chain) score -= Counter(chain(*self.options.values())).most_common(1)[0][1] return score def __eq__(self, other): return set(self.chain) == set(other.chain) def __hash__(self): return hash(frozenset(self.chain)) @property def children(self): for chain in self.combinations_with_refinement(min(self.options)): yield type(self)(self.chain + (chain,), {start: self.options [start] - {stop} for start, stop in pairwise(chain + (chain[0],))}) def combinations_with_refinement(self, primer): yield from self._cwr((primer,), primer, primer, 1, len(self.options)) def _cwr(self, chain, head, tail, size, goal): size += 1 if size < goal: for option in self.options[tail]: if option not in chain: yield from self._cwr(chain + (option,), head, option, size, goal) else: for option in self.options[tail]: if option not in chain and head in self.options[option]: yield chain + (option,)
  Created at: June 19, 2015, 3:02 p.m.; Updated at: June 22, 2015, 12:31 p.m.