Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
FamilyTree iter() solution in Clear category for What Is Wrong With This Family? by r.bathoorn
from collections import deque
from collections import defaultdict
class FamilyTree():
def __init__(self, tree):
# create two sets fathers and sons
fathers, sons = map(set, zip(*tree))
self.fathers = fathers
# create a lookup list of sons for each father in the tree
self.sons = defaultdict(list)
for father, son in tree:
self.sons[father].append(son)
# root of the tree is the father that is not a son
self.roots = fathers - sons
# determine the size of the family
# fathers that are also sons are counted only once by using intersect
self.size = len(fathers | sons)
def __getitem__(self, f):
return self.sons[f]
@property
def root(self):
# can only have one root of the tree otherwise there are unrelated families in there
if len(self.roots) != 1:
return []
else:
return self.roots
def __iter__(self):
# iterate family using BFS to trace a tree
q = deque(self.root)
while q:
# node is first element of q
node = q.popleft()
if node in self.sons: q.extend(self.sons[node])
yield node
def is_family(self):
seen = set() # visited nodes
for node in iter(self):
# found loop in tree so result is False
if node in seen: return False
# add node to seen list, used for loop detection
seen.add(node)
return len(seen) == self.size # reached the end of family and have seen all relatives
def is_family(tree):
family = FamilyTree(tree)
return family.is_family()
if __name__ == "__main__":
assert is_family([["Jack","Mike"],["Logan","Mike"],["Logan","Jack"]]) == False, 'Looks like Mike has two fathers'
#These "asserts" using only for self-checking and not necessary for auto-testing
assert is_family([
['Logan', 'Mike']
]) == True, 'One father, one son'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack']
]) == True, 'Two sons'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Alexander']
]) == True, 'Grandfather'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Logan']
]) == False, 'Can you be a father to your father?'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Jack']
]) == False, 'Can you be a father to your brother?'
assert is_family([
['Logan', 'William'],
['Logan', 'Jack'],
['Mike', 'Alexander']
]) == False, 'Looks like Mike is stranger in Logan\'s family'
print("Looks like you know everything. It is time for 'Check'!")
Feb. 24, 2021
Comments:
