Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Depth firs analisys solution in Clear category for What Is Wrong With This Family? by kudinov.feodor
from collections import defaultdict
def is_family(tree):
# normalize for better lookup
# {"parent1": ["son1", "son2", ...], ...}
tree_dict = defaultdict(list)
sons = []
for parent, son in tree:
tree_dict[parent].append(son)
sons.append(son)
# define root to start with
roots = set(tree_dict) - set(sons)
if len(roots) != 1:
return False
root = next(iter(roots))
# recursive depth first tree analisys
def children_not_in_visited(parent):
visited.append(parent)
children = tree_dict.pop(parent, [])
for child in children:
if child in visited or not children_not_in_visited(child):
return False
return True
visited = []
if children_not_in_visited(root):
return not bool(tree_dict) # some one left, tree is fragile
return False
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 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'!")
June 21, 2020