CheckIO是國外的編程網站，游戲畫風，通過編程完成任務，解鎖新的島嶼和建築物。在提交通過後，還可以查看獲得評分最高的答案，學習別人的思路。唯一缺點就是全英文。。。
最近問哥在逛國外的網站CheckIO時，發現一些有趣的題目，今天和大家分享一例：
Michael always knew that there was something wrong with his family. Many strangers were introduced to him as part of it.
麥克老是覺得家裡有點不對勁，總是有許多陌生人自稱是他的家人。
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.
麥克想要搞清楚，於是他花了將近一個月的時間分析家庭檔案，並把所有的父子關系都梳理出來，放在一起。
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.
有了這些數據，麥克就能很快找出誰是陌生人。也許。。。這個家裡唯一的陌生人就是麥克自己？（細思極恐）讓我們看看吧。
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.
你有一份父子關系的清單。此列表中的每個元素都有兩個元素。第一個是父親的名字，第二個是兒子的名字。家譜上所有名字都是唯一的。你的任務是檢查這份家譜是否正確：家譜中有沒有陌生人、並且所有關系都是正常的。
Input: list of lists. Each element has two strings. The list has at least one element
輸入：二維列表。每個元素含有兩個字符串。列表保證至少有一個元素（字符串對）。
Output: bool. Is the family tree correct.
輸出：布爾值。判斷家譜是否正確。
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
# 兒子不可能是父親的父親
is_family([['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Jack']]) == False
# 不可能成為親兄弟的父親
is_family([['Logan', 'William'], ['Logan', 'Jack'], ['Mike', 'Alexander']]) == False
# 看來麥克才是陌生人給出的二維列表裡的每一個元素都是一對父子的名字，父親的名字在前，兒子的名字在後，比如[['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Alexander']]裡，Logan是Mike的父親，也是Jack的父親，而Mike又有個兒子叫Alexander。所以我們可以根據列表畫出一張族譜：
正常的族譜應該就是上面這個樣子。而所謂的陌生人，在這個例子裡，就是和家庭裡任何一人都沒有父子關系的人。比如根據另一個列表[['Logan', 'William'], ['Logan', 'Jack'], ['Mike', 'Alexander']]可以畫出的族譜如下：
這張族譜裡，Mike和Alexander雖然是父子關系，但他們和Logan一家沒有任何聯系，所以，相對於Logon一家，Mike和Alexander就是陌生人。由此可見，我們想要完成判斷的第一個任務：沒有陌生人，就是確認給出的列表裡是否只有一個家族。而完成這個任務的方法就是，順著所有的“兒子”往上找，如果最終只找到一個“祖先”，那就證明這些人都屬於同一個家族，即沒有陌生人。
另外，我們還要完成第二個判斷任務：家譜是正確的。題目中也給出了例子，比如“兒子”不可能是“父親”的“父親”——不能出現循環：
也不可能成為“親兄弟”的“父親”——每個人都只有一個父親：
所以，最直接的辦法就是，先根據列表把家譜畫出來，然後再遍歷每個“兒子”，找到他們的“祖先”，看看是不是同一個人。
CheckIO網站上如果代碼提交通過，就可以看到其他人的優秀答案。所以問哥先按照自己的思路提交通過了一份代碼，然後就可以看到很多優秀的答案，得以學習他人的優秀思路。
按照問哥最樸素的想法：先把族譜畫出來。所以問哥的第一個念頭就是：先創建一個字典。但是用“父親”做鍵，還是“兒子”做鍵呢？
由於一個“父親”可以有多個“兒子”，而每個“兒子”都只有一個“父親”。後面我們還要遍歷每個“兒子”，去尋找“祖先”。所以很顯然，把“兒子”作為鍵更合適，因為可以通過字典方便地找到“兒子”的“父親”是誰。
於是第一步根據二維列表創建族譜字典，問哥寫下代碼：
def is_family(tree):
family = {j:i for i, j in tree}局部變量tree就是傳進來的表面父子關系的二維列表，遍歷每一對父子，然後將“兒子”作為鍵，“父親”作為值，創建一個字典family。
但是這樣會有一個問題，就是當某個“兒子”有多個“父親”的時候，比如：
[['Logan', 'Mike'], ['Logan', 'Jack'], ['Mike', 'Jack']]Jack的“父親”是Logan和Mike，這顯然是錯誤的。但是在創建字典的時候，Jack這個鍵的“父親”值會被最後一次賦值所覆蓋掉，從而忽略了這個錯誤。
檢查這個錯誤也很簡單：如果有多個“父親”，或者說存在覆蓋情況的話，那最終的字典的鍵的數量肯定要少於傳進來的父子列表對。於是，我們可以檢查字典family和原始二維列表tree的長度，如果長度變少了，就說明出現了重復的情況，從而可以直接返回False。只要加一條語句就好：
if len(family.keys())<len(tree):return False如此，我們便創建好一個族譜的字典，名叫family。但這個字典中依然存在錯誤的可能，比如循環情況沒有解決，Mike的父親是Logan，Logan的父親是Mike，這兩對關系都可以同時存在字典中。這種錯誤可以在第二步“溯源”中排除。
第二步我們就可以遍歷字典，檢查每個“兒子”的“祖先”。首先創建一個名叫anscestor的集合變量（注意：創建空集合是用set()），用來保存每次遍歷到的“祖先”的名字，同時，如果遍歷到的“祖先”是同一人的話，集合在添加新元素的時候會自動去重，只保留一個值。其次，我們需要一個for循環，遍歷字典中的每一個父子對。而for循環的裡面，我們還需要一個while循環，用於檢查“父親”的“父親”，一直到某位“父親”在字典裡沒有“父親”的時候，那他就是這個家族的“祖先”了。於是，我們可以這樣寫：
anscestor = set()
for i in family.keys():
while family.get(i):
i=family.get(i)
anscestor.add(i)就是不斷從字典裡查詢“兒子”的“父親”，直到字典裡沒有記錄的時候，就把當前的“父親”添加到“祖先”列表anscestor裡。
但是由於存在我們剛才說過的循環情況，while循環會有成為死循環的可能。
於是我們需要檢查當前查詢的這位“父親”，是不是已經查詢過了。而如果已經查詢過，現在又要查詢，就說明出現了循環。比如我們查詢Mike，得知他的父親是Logan，而我們查詢Logan的時候，字典告訴我們他的父親是Mike，而Mike已經被查詢過，說明這裡出現了循環，從而直接返回False。同樣，如果給到的列表父子均為同一人，也可以通過這種檢查排除掉。
代碼實現如下：
checked = []
while family.get(i):
i=family.get(i)
if i in checked:return False
checked.append(i)最後當遍歷完所有父子對後，如果集合anscestor裡的元素大於1，也就是有2個以上的“祖先”，自然就說明這個家族是有陌生人的。於是，可以直接返回判斷結果：
return len(anscestor)==1最後提交通過的完整代碼如下：
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)==1當代碼提交通過後，再過一段時間（想立即看就得花錢買會員），就可以看到其他人投票產生的幾個最佳答案了。關於這道題，大家的方法其實都差不多，不過很多人引用了一些標准庫裡的函數，有些是問哥之前很少用到的，所以也是學到了新的知識。
比如下面這個得票率第一的方法就是用了collections模塊裡的defaultdict()函數。
代碼實現的基本思想是一樣的，先建立一個族譜的字典anscestor，“兒子”作為鍵，“父親”以及“父親”的“父親”合並在一起成為一個集合，再把這個集合作為族譜字典anscestor的值。
完整代碼如下：
from collections import defaultdict
def is_family(tree):
anscestor = defaultdict(set)
for father, son in tree:
if father == son: return False # 如果父子是同一人，顯然是錯的
if son in anscestor[father]: return False # 如果兒子是父親的祖先，顯然是錯的
if anscestor[son]: return False # 如果同一個兒子有多個父親，顯然是錯的
anscestor[son] |= {father} | anscestor[father] # 兒子的祖先等於父親加上父親的祖先的並集
adam = [person for person in anscestor if not anscestor[person]]
return len(adam) == 1這裡代碼調用了collections模塊裡的defaultdict()函數，創建了一個特殊的字典。這個函數的作用就是，如果字典裡沒有某個鍵的記錄，那在第一次調用它的時候，給它創建一個默認值。而這個默認值並不是具體的某個值，而是一個由defaultdict()函數裡指定的數據類型的空值。
比較以下運行結果：
a = defaultdict(int)
a['b']
0 # 整數類型的空值是0
a
defaultdict(<class 'int'>, {'b': 0})
a = defaultdict(str)
a['b']
'' # 字符串類型的空值是空字符串
a
defaultdict(<class 'str'>, {'b': ''})
a = defaultdict(list)
a['b']
[] # 列表類型的空值是空列表
a
defaultdict(<class 'list'>, {'b': []})
a = defaultdict(set)
a['b']
set() # 集合類型的空值是空集合
a
defaultdict(<class 'set'>, {'b': set()})
a = defaultdict(dict)
a
defaultdict(<class 'dict'>, {})
a['b']
{} # 字典類型的空值是空字典
a
defaultdict(<class 'dict'>, {'b': {}})所以本例中，根據二維列表建立族譜字典後，只要檢查這個字典裡值為空集合的鍵，就可以得到家族裡的第一個人（沒有“父親”的人），如果這個“第一人”不止一個，就說明有陌生人（家族）了。
今天的分享就到這裡，謝謝大家，我們下次再見！
