How to find friends
Sophiaのドローンは、魂のない愚かなドローンではありません。彼らは友達を作ったり持つことができます。 実際、彼らは既にドローンのための彼ら自身のソーシャルネットワークが動いています! Sophiaはドローン達の間のつながりに関するデータを受け取って、彼らの間の関係について知りたいと思います。
我々はドローン達の間の直接のつながりの配列を持っています。 各々のつながりはハイフンで区切られた友達の二つの名前をもつ文字列で表現されています。 例えば: "dr101-mr99"はdr101とmr99が友達であることを意味しています。 あなたはドローン達の間のもっと複雑な関係を決定できるような関数を書かなくてはいけません。 さらに、あなたには二つの名前が与えられます。 任意の深さの共通のかかわりを介して彼らが関係しているかどうか決定してみましょう。 例えば: 二つのドローンが共通の友人をもつかどうか、もしくは友達がさらに共通の友人をもつか等です。
network
例を見てみましょう:
scout2とscout3は共通の友人scout1を持っているので彼らには関係があります。 superとscout2はsscout、scout4、scout1を経由して関係があります。 しかしdr101とsscoutは関係がありません。
入力: 三つの入力変数: 友達に関する情報、文字列のタプル; 一つ目の名前、文字列; 二つ目の名前、文字列
出力: これらのドローン達に関係があるかどうか、ブール値
例:
check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"scout2", "scout3") == True
check_connection(
("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
"scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
"dr101", "sscout") == False
どのように使われるか: このコンセプトは結合ネットワークの構築であまり明確でない関係を発見するのに役に立つでしょう。 そしてどのようにソーシャルネットワークが働くかについても。
事前条件: len(network) ≤ 45
if "name1-name2" in network, then "name2-name1" not in network
3 ≤ len(drone_name) ≤ 6
first_name and second_name in network.
network = list(network) network = '-'.join(network) network = network.split('-') network_set = set(network)
ネットワークは相互的だから、ひたすらに集合に入れればいいのかと思った。しかし、これは一応は動くんだけど、テストの３つ目（異なるネットワークがある場合）にはうまく機能しない。
わからんから、答えみて考える。
def check_connection(network, first, second): setlist = [] for connection in network: s = ab = set(connection.split('-')) # unify all set related to a, b for t in setlist[:]: # we need to use copy if t & ab: # check t include a, b s |= t setlist.remove(t) setlist.append(s) # only s include a, b return any(set([first, second]) <= s for s in setlist) <200b> <200b> <200b> if __name__ == '__main__': #These "asserts" using only for self-checking and not necessary for auto-testing assert check_connection( ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2", "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"), "scout2", "scout3") == True, "Scout Brotherhood" assert check_connection( ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2", "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"), "super", "scout2") == True, "Super Scout" assert check_connection( ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2", "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"), "dr101", "sscout") == False, "I don't know any scouts."
まず、split('-')によって、ネットワークのそれぞれのノードをもったリストをつくる。そして、それを更に集合へと変換している。
これを変数ｓとabにセットする。
次のfor文はsetlistの浅いコピーを作ってこれを操作しているのだけれど、一度目はsetlistの要素数は0なのでとりあえず。先にすすむ。
setlistにsplit('-')で作られたノードの集合を追加する。これでsetlistの中身ができた。
さっき飛ばしたfor文に再び戻ってきた。浅いコピーを作って、そのあとどうしているのだろうか。
t & ab とあるこの&とはなにか。
tとabのどちらの集合にも含まれている要素だけを返す。論理演算子だ。
次に s |= t
s = s | t と等しい式。 ｜ とは集合sと集合tの少なくともどちらか一方に含まれている要素の集合を返す。
そのあとsetlistから集合ｔを削除している。
つまり、ノードのつながりがある巨大な集合をつくっているのだ。
最後にfirstとsecondを受け取って、さきほど作った集合の中にfirstとsecondがあればfirstとsecondの間にネットワークがあるとわかる。
ただ、この方法ってネットワークが２つまでの場合にしか対応できないような。３つ以上ではうまく探せないのではないか。
def check_connection(edges, first, last): path = {first} check = 0 # All points who can be acceseed from "first" # are put in path set. # At the end end "last" is checked if is in path set. while(len(path) > check): check = len(path) # this part can be easily optimized to avoid # iterating through edges already accepted in path set. # I skipped this to keep my solution # clear and easy to understand for edge in edges: one, two = edge.split("-") if one in path or two in path: path.add(one) path.add(two) else: return last in path
他の人の解答。これ、すごいきれい。
