• # Better Way to Calculate Score?

## Question related to mission Family Gifts

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:
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,),