CheckIO It is a foreign programming website , Game painting style , Complete the task by programming , Unlock new islands and buildings . After the traffic , You can also view the answers with the highest scores , Learn other people's ideas . The only drawback is that it is all in English ...
Recently, I asked my brother about visiting foreign websites CheckIO when , Find some interesting topics , Today I would like to share an example with you ：
Michael always knew that there was something wrong with his family. Many strangers were introduced to him as part of it.
Mike always thinks something's wrong at home , There are always many strangers who claim to be his family .
Michael should figure this out. He's spent almost a month parsing the family archives. He has all father-son connections of his entire family collected in one place.
Mike wants to find out , So he spent nearly a month analyzing his family files , And sort out all the father son relationships , Put together .
With all that data Michael can easily understand who the strangers are. Or maybe the only stranger in this family is Michael? Let's see.
With that data , Mike can quickly find out who the stranger is . Maybe ... The only stranger in the family is Mike himself ？（ Consider very fear ） Let's see .
You have a list of family ties between father and son. Each element on this list has two elements. The first is the father's name, the second is the son's name. All names in the family are unique. Check if the family tree is correct. There are no strangers in the family tree. All connections in the family are natural.
You have a list of father son relationships . Each element in this list has two elements . The first is the father's name , The second is the son's name . All the names on the family tree are unique . Your task is to check whether this genealogy is correct ： Are there any strangers in the family tree 、 And all relationships are normal .
Input: list of lists. Each element has two strings. The list has at least one element
Input ： 2 d list . Each element contains two strings . The list is guaranteed to have at least one element （ String pair ）.
Output: bool. Is the family tree correct.
Output ： Boolean value . Judge whether the genealogy is correct .
Example:
Example ：
is_family([['Logan', 'Mike']]) == True
is_family([['Logan', 'Mike'], ['Logan', 'Jack']]) == True
is_family([['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Alexander']]) == True
is_family([['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Logan']]) == False
# A son cannot be the father of a father
is_family([['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Jack']]) == False
# You can't be the father of your own brother
is_family([['Logan', 'William'], ['Logan', 'Jack'], ['Mike', 'Alexander']]) == False
# It seems that Mike is a stranger Each element in the given two-dimensional list is a parent-child name , Father's name comes first , The son's name comes after , such as [['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Alexander']] in ,Logan yes Mike Father , It's also Jack Father , and Mike There is another son named Alexander. So we can draw a family tree according to the list ：
A normal genealogy should look like this . And the so-called strangers , In this case , Is a person who has no father son relationship with anyone in the family . For example, according to another list [['Logan', 'William'], ['Logan', 'Jack'], ['Mike', 'Alexander']] The genealogy that can be drawn is as follows ：
In this genealogy ,Mike and Alexander Although it's a father son relationship , But they and Logan There is no contact with the family , therefore , be relative to Logon a ,Mike and Alexander A stranger . thus it can be seen , We want to complete the first task of judgment ： No strangers , It's confirmation Is there only one family in the given list . And the way to accomplish this task is , Follow all the “ son ” Look up , If you finally find only one “ The ancestors ”, That proves that these people belong to the same family , There are no strangers .
in addition , We still have to complete the second judgment task ： The genealogy is correct . Examples are also given in the title , such as “ son ” It can't be “ father ” Of “ father ”—— There can't be a cycle ：
Nor can it be “ Brother ” Of “ father ”—— Everyone has only one father ：
therefore , The most direct way is , First draw the family tree according to the list , Then traverse each “ son ”, Find them “ The ancestors ”, See if it's the same person .
CheckIO If the code submitted on the website passes , You can see other people's excellent answers . So I submitted a code according to my own ideas , Then you can see many excellent answers , To learn from others' excellent ideas .
According to brother Wen's most simple idea ： First draw the genealogy . So my first thought is ： First create a dictionary . But with “ father ” Make the key , still “ son ” Making keys ？
Due to a “ father ” There can be multiple “ son ”, And each “ son ” There is only one “ father ”. We'll go through each later “ son ”, Go looking for “ The ancestors ”. So obviously , hold “ son ” As a key is more appropriate , Because you can find it easily in a dictionary “ son ” Of “ father ” Who is it? .
So the first step is to create a genealogy dictionary according to the two-dimensional list , Ask brother to write down the code ：
def is_family(tree):
family = {j:i for i, j in tree}local variable tree It is a two-dimensional list of apparent parent-child relationships , Traverse every parent and son , And then “ son ” As key ,“ father ” As value , Create a dictionary family.
But there is a problem , Is when someone “ son ” There are many. “ father ” When , such as ：
[['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Jack']]Jack Of “ father ” yes Logan and Mike, This is obviously wrong . But when creating a dictionary ,Jack This key is “ father ” The value will be overwritten by the last assignment , Thus ignoring this error .
Checking for this error is also simple ： If there are more than one “ father ”, Or if there is coverage , The number of keys in the final dictionary must be less than that in the parent-child list . therefore , We can check the dictionary family And the original 2D list tree The length of , If the length decreases , It means that there is repetition , So you can directly return to False. Just add a statement ：
if len(family.keys())<len(tree):return Falsesuch , We will create a dictionary of genealogy , named family. But there is still the possibility of mistakes in this dictionary , For example, the circulation problem is not solved ,Mike His father is Logan,Logan His father is Mike, These two pairs of relations can be stored in the dictionary at the same time . Such mistakes can be made in the second step “ Tracing to the source ” Exclude from .
In the second step, we can traverse the dictionary , Check each “ son ” Of “ The ancestors ”. First create a file called anscestor Set variables for （ Be careful ： To create an empty collection, use set()）, It is used to save the “ The ancestors ” Name , meanwhile , If I traverse to “ The ancestors ” It's the same person , The collection will be automatically de duplicated when adding new elements , Keep only one value . secondly , We need a for loop , Traverse every parent-child pair in the dictionary . and for Inside the loop , We need one more while loop , Used for inspection “ father ” Of “ father ”, Until someone “ father ” Not in the dictionary “ father ” When , Then he belongs to this family “ The ancestors ” 了 . therefore , We can write this way ：
anscestor = set()
for i in family.keys():
while family.get(i):
i=family.get(i)
anscestor.add(i)Is to constantly look it up in the dictionary “ son ” Of “ father ”, Until there is no record in the dictionary , Just put the current “ father ” Add to “ The ancestors ” list anscestor in .
But because of the existence of the cycle we just mentioned ,while The loop may become an endless loop .
So we need to check the current query “ father ”, Has it been checked . And if you have already inquired , Now we have to query , It means that there is a cycle . For example, we query Mike, Learned that his father was Logan, And we query Logan When , The dictionary tells us that his father is Mike, and Mike Has been inquired , It means that there is a cycle , To return directly to False. Again , If the father and son of the given list are the same , It can also be ruled out by this check .
The code implementation is as follows ：
checked = []
while family.get(i):
i=family.get(i)
if i in checked:return False
checked.append(i)Finally, after traversing all parent-child pairs , If the collection anscestor The element in is greater than 1, There is a 2 More than one “ The ancestors ”, Naturally, there are strangers in this family . therefore , You can directly return the judgment result ：
return len(anscestor)==1Finally, the complete code submitted for approval is as follows ：
def is_family(tree):
family = {j:i for i,j in tree}
if len(family.keys())<len(tree):return False
anscestor = set()
for i in family.keys():
checked = []
while family.get(i):
i=family.get(i)
if i in checked:return False
checked.append(i)
anscestor.add(i)
return len(anscestor)==1When the code mentions the traffic , In a while （ If you want to see it immediately, you have to pay for the membership ）, You can see some of the best answers voted by others . About this question , In fact, everyone's methods are similar , However, many people refer to some functions in the standard library , Some are rarely used before asking brother , So I also learned new knowledge .
For example, the following method with the highest vote rate is used collections In the module defaultdict() function .
The basic idea of code implementation is the same , First build a dictionary of genealogy anscestor,“ son ” As key ,“ father ” as well as “ father ” Of “ father ” Merge together to form a set , Take this set as a genealogical dictionary anscestor Value .
The complete code is as follows ：
from collections import defaultdict
def is_family(tree):
anscestor = defaultdict(set)
for father, son in tree:
if father == son: return False # If the father and son are the same , Obviously wrong
if son in anscestor[father]: return False # If the son is the father's ancestor , Obviously wrong
if anscestor[son]: return False # If the same son has more than one father , Obviously wrong
anscestor[son] |= {father} | anscestor[father] # The son's ancestor is equal to the father plus the father's ancestor
adam = [person for person in anscestor if not anscestor[person]]
return len(adam) == 1Here the code calls collections In the module defaultdict() function , Created a special dictionary . The function is , If there is no record of a key in the dictionary , That's when you call it for the first time , Create a default value for it . The default value is not a specific value , It's a matter of defaultdict() The null value of the data type specified in the function .
Compare the following run results ：
a = defaultdict(int)
a['b']
0 # The null value of integer type is 0
a
defaultdict(<class 'int'>, {'b': 0})
a = defaultdict(str)
a['b']
'' # A null value of a string type is an empty string
a
defaultdict(<class 'str'>, {'b': ''})
a = defaultdict(list)
a['b']
[] # A null value of a list type is an empty list
a
defaultdict(<class 'list'>, {'b': []})
a = defaultdict(set)
a['b']
set() # The null value of a collection type is an empty collection
a
defaultdict(<class 'set'>, {'b': set()})
a = defaultdict(dict)
a
defaultdict(<class 'dict'>, {})
a['b']
{} # A null value of a dictionary type is an empty dictionary
a
defaultdict(<class 'dict'>, {'b': {}})So in this case , After building a genealogy dictionary according to the two-dimensional list , Just check the key of the empty set in the dictionary , You can get the first person in the family （ No, “ father ” People who ）, If this “ The first person ” More than one , It means there are strangers （ family ） 了 .
Today's sharing is here , Thank you. , See you next time ！
