-
It is possible to diminish this code's run time?
Family GiftsAfter trying to get this program to run faster and use less memory, it is unclear to me what more can be done to have this code complete the challenge in a timely fashion.
"""\
Every Christmas in my family, each of us gives a present to only one other
person. To organize who should offer a gift to whom (I call it the chain of
presents), we introduced a few rules:
- There should be a single chain where every person in the family is present,
- Couples should not give to one another,
- Every person should give a gift to a different person than they had in
previous years
So the problem would be to find and list the longest list of chains of
presents. For example in a family {a,b,c,d} with couples=({a,b},{c,d}):
[[a,c,b,d],[a,d,b,c]].
You are given a set of family member names and a list of couples in this
family. Find the maximum number of chains with all family members. Gift chains
should be represented as a list of names where i-th gives a present to i+1-th
and the last person in the list to the first.
Input: Names of family members as a set of strings. Couple list as a
tuple of sets with two strings in each.
Output: The longest list of gift chains as a list/tuple of lists/tuples
with strings.
Precondition: len(couples) <= 7"""
from operator import itemgetter
from pprint import pprint
Z = frozenset
TABLE = {(Z({'Hollie', 'Gary', 'Jeanette'}),
Z({Z({'Gary', 'Jeanette'})})): 0,
(Z({'Javier', 'Rachel', 'Curtis', 'Lee'}),
Z({Z({'Curtis', 'Lee'}), Z({'Javier', 'Rachel'})})): 2,
(Z({'Mary', 'Selena', 'Phyllis', 'Philip', 'Eric', 'Sondra'}),
Z({Z({'Mary', 'Eric'}), Z({'Philip', 'Sondra'})})): 4,
(Z({'Eugene', 'Delores', 'Delia', 'Ricardo', 'Ella', 'Kurt'}),
Z({Z({'Ella', 'Eugene'}), Z({'Delores', 'Kurt'}),
Z({'Delia', 'Ricardo'})})): 4,
(Z({'Nelson', 'Kaitlin', 'Amelia', 'Jack'}),
Z({Z({'Nelson', 'Amelia'}), Z({'Kaitlin', 'Jack'})})): 2,
(Z({'Eugenia', 'Alex', 'Monique', 'Kitty', 'Robert', 'Tamika', 'Rene',
'Tim', 'Maggie', 'Joseph'}),
Z({Z({'Tim', 'Tamika'}), Z({'Robert', 'Kitty'}),
Z({'Eugenia', 'Alex'}), Z({'Monique', 'Rene'}),
Z({'Maggie', 'Joseph'})})): 8,
(Z({'Melisa', 'Annmarie', 'Dee', 'Rafael', 'Gerald'}),
Z({Z({'Melisa', 'Gerald'}), Z({'Annmarie', 'Rafael'})})): 2,
(Z({'Lula', 'Bill', 'Irene', 'Vincent', 'Dorothea', 'Paulette',
'Virginia'}),
Z()): 6,
(Z({'Tabitha', 'Esperanza', 'Delores', 'Carl', 'Erin', 'Samuel',
'Fred', 'Erica', 'Amber', 'Dixie'}),
Z({Z({'Fred', 'Delores'}), Z({'Erica', 'Carl'})})): 7,
(Z({'Herminia', 'Louis', 'David', 'Sondra', 'Herbert', 'Jane',
'Jeannie', 'Alexandria', 'Theodore', 'Meghan', 'Nettie',
'Eleanor', 'Autumn', 'Jeffery', 'Fay', 'June', 'Lynnette'}),
Z({Z({'Theodore', 'Meghan'}), Z({'David', 'Nettie'}),
Z({'Louis', 'Autumn'}), Z({'Herbert', 'Eleanor'}),
Z({'Fay', 'Jeffery'})})): 14,
(Z({'Fred', 'Yolanda', 'Doreen'}),
Z({Z({'Fred', 'Doreen'})})): 0,
(Z({'Jacklyn', 'Maurice', 'Lela', 'Stella', 'Winnie', 'Barbra',
'Lavonne', 'Estela', 'Gordon'}),
Z({Z({'Maurice', 'Lela'})})): 7,
(Z({'Russell', 'Maryanne', 'Benjamin', 'Matthew', 'Loraine', 'Penny',
'Todd', 'Jenifer', 'Leah'}),
Z({Z({'Jenifer', 'Todd'}), Z({'Benjamin', 'Loraine'}),
Z({'Leah', 'Matthew'})})): 6,
(Z({'Kelly', 'Allison', 'Bobbie', 'Curtis', 'Petra', 'Robin'}),
Z({Z({'Robin', 'Kelly'}), Z({'Curtis', 'Allison'})})): 4}
def main():
"Test the find_chains function with several cases to see if it breaks."
assert checker(find_chains,
{'Gary', 'Jeanette', 'Hollie'},
({'Gary', 'Jeanette'},),
0), "Three of us"
assert checker(find_chains,
{'Curtis', 'Lee', 'Rachel', 'Javier'},
({'Rachel', 'Javier'}, {'Curtis', 'Lee'}),
2), "Pairs"
assert checker(find_chains,
{'Philip', 'Sondra', 'Mary', 'Selena', 'Eric', 'Phyllis'},
({'Philip', 'Sondra'}, {'Eric', 'Mary'}),
4), "Pairs and Singles"
for (family, couples), total in sorted(TABLE.items(), key=itemgetter(1)):
print('total =', total)
assert checker(find_chains, set(family), couples, total), 'Full Test'
def checker(function, family, couples, total):
"Check the function with family and couples to see if it works correctly."
user_result = function(family.copy(), tuple(c.copy() for c in couples))
pprint(user_result)
if (not isinstance(user_result, (list, tuple)) or
any(not isinstance(chain, (list, tuple)) for chain in user_result)):
return False
if len(user_result) < total:
return False
gifted = set()
for chain in user_result:
if set(chain) != family or len(chain) != len(family):
return False
for f, s in zip(chain, chain[1:] + [chain[0]]):
if {f, s} in couples:
return False
if (f, s) in gifted:
return False
gifted.add((f, s))
return True
################################################################################
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:
__slots__ = 'family', 'couples', 'target', 'options', 'state'
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:
__slots__ = 'chain', 'options'
def __init__(self, chain, options):
self.chain = chain
self.options = options
def __lt__(self, other):
return self.score > other.score
def __eq__(self, other):
return set(self.chain) == set(other.chain)
def __hash__(self):
return hash(Z(self.chain))
@property
def score(self):
score = len(self.chain)
score -= Counter(chain(*self.options.values())).most_common(1)[0][1]
return score
@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,)
@property
def score(self):
return len(self.chain)
@property
def children(self):
for chain in self.combinations_with_refinement(min(self.options)):
yield type(self)(self.chain + (chain,), self.options)
def combinations_with_refinement(self, primer):
options = self.options
for chain in self.chain:
options = {start: options[start] - {stop} for start, stop in
pairwise(chain + (chain[0],))}
yield from self._cwr((primer,), primer, primer, 1, len(options),
options)
@classmethod
def _cwr(cls, chain, head, tail, size, goal, options):
size += 1
if size < goal:
for option in options[tail]:
if option not in chain:
yield from cls._cwr(chain + (option,), head, option, size,
goal, options)
else:
for option in options[tail]:
if option not in chain and head in options[option]:
yield chain + (option,)
if __name__ == '__main__':
main()
