First clear solution for What Is Wrong With This Family? by Sim0000 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

First solution in Clear category for What Is Wrong With This Family? by Sim0000

from collections import defaultdict

def is_family(tree):
    anscestor = defaultdict(set)
    for father, son in tree:
        if father == son: return False
        if father in anscestor[son]: return False
        if son in anscestor[father]: return False
        if anscestor[father] & anscestor[son]: return False
        anscestor[son] |= {father} | anscestor[father]
    adam = [person for person in anscestor if not anscestor[person]]
    return len(adam) == 1



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, 'grant father'
    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'!")

Oct. 5, 2016

Comments:

Thenbacker on Oct. 6, 2016, 3:10 a.m.
Cool solution, love the use defaultdicts with sets in this solution!

przemyslaw.daniel on Sept. 2, 2017, 3:35 p.m.
This is beautiful algorithm. When iterating we have to check if father with his ancestors has nothing in common with son and son's ancestors. Family head must be one. This code can be just a bit <a href="https://py.checkio.org/mission/wrong-family/publications/przemyslaw.daniel/python-3/7-liner/?ordering=most_voted&filtering=all">simplified</a>

Sim0000 on Sept. 3, 2017, 2:47 a.m.
Thank you!

quesneljoseph on Oct. 29, 2017, 5:42 a.m.
mannn this is some sweet code. how does defaultdict work here? it looks critical to the code but even after checking documentation i do not understand why exactly. I understand how the sets work. Is it just because there is no default set notation or is there some special purpose?

Sim0000 on Oct. 29, 2017, 6:13 a.m.
If key does not exist, I want to return set(). There are several way to achieve this. One way is <pre class='brush: python'>d[key] if key in d else set() </pre> Another way is <pre class='brush: python'>d.get(key, set()) </pre> The third way is using defaultdict I used in this solution. <pre class='brush: python'>d = defaultdict(set) </pre> The defaultdict have class name as argument. When d[key] and key does not exist in d, C() is called as default value, where C is class name. It is same as d.get(key, C()). For the purpose of simplicity of source code, we use defaultdict. I feel above two way is rather messy. I hope this may help you :-)

Robert_Li on May 19, 2018, 12:21 a.m.
U're really cool man

r_tchaik on July 2, 2020, 3:30 a.m.
Simple and elegant. Very nice!

r.bathoorn on Feb. 10, 2021, 9:59 a.m.
Did they add more test cases? The solution did not work for me. It failed on the check with two fathers I had to add the following check in the tree loop: if anscestor[son]: return False # 'Can you have two fathers?'

Sim0000 on Feb. 10, 2021, 11:25 a.m.
I agree with you. I am working on <a href="https://py.checkio.org/mission/wrong-family/publications/Sim0000/python-3/traverse-tree-from-root/">a new solution</a> that solves the problem. Please take a look.

wayne_sun on May 22, 2022, 5:34 a.m.
You're right, this code doesn't work now, and you doesn't need another two <pre class='brush: python'> #if father in anscestor[son]: return False #if anscestor[father] & anscestor[son]: return False if anscestor[son]: return False </pre>

luke.smith22 on Sept. 24, 2021, 1:45 p.m.
Just so I'm clear. When running through the for loop, the fathers are treated as the keys and the sons are treated as values?

smalcom on Aug. 30, 2023, 7:23 p.m.
<blockquote> assert is_family([["Jack", "Mike"], ["Logan", "Mike"], ["Logan", "Jack"]]) == False AssertionError </blockquote>

Look up in the Dict()

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.