Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for What Is Wrong With This Family? by maybe
def is_family(tree):
# we want one connected tree, containing Mike.
# sufficient: 1 root + edges 1 less than nodes + all sons reachable from root
from collections import deque
fathers=set(t[0] for t in tree)
sons = set (t[1] for t in tree)
if len(fathers - sons)!= 1: return False
if len(tree) != len(fathers|sons) -1: return False
decendents, seen = deque([(fathers-sons).pop()]), set()
while decendents:
father = decendents.popleft()
if father in seen: return False # cycle
seen.add(father)
my_sons = [t[1] for t in tree if t[0]==father]
decendents.extend(my_sons)
sons.difference_update(my_sons)
return not sons # all sons covered?
if __name__ == "__main__":
#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 for your father?'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Jack']
]) == False, 'Can you be a father for your brather?'
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. 5, 2020
Comments:
