# How related are two relatives?

The coefficient of relationship refers to how much DNA two persons have in common. A parent has 50% common DNA with their child (unless the parents are related), so to calculate it we have to find all pairs of directed disjoint paths starting at same node (common ancestor) and ending at each of the two siblings, and sum 2^-(m+n) for all pairs of paths of length m and n.

Your program should accept a list of pairs of numbers (or names if you prefer) representing parent-child relations followed by another pair of number for which it should output the coefficient of relationship (either as a fraction, a decimal number, or a percentage).

For example:

Format: [list of parent-child relations] pair of relatives we want to compare -> expected output
-----------------------------------------------
[(1,2)] (1, 2) -> 50% (parent-child)
[(1,2), (2, 3), (3, 4)] (2, 3) -> 50% (still parent-child, make sure your path pairs are disjoint)
[(1,3), (2, 3)] (1, 2) -> 0% (not related, make sure your paths are directed)
[(1, 2), (2, 3)] (1, 3) -> 25% (grandparent-child)
[(1, 3), (1, 4), (2, 3), (2, 4)] (3, 4) -> 50% (siblings)
[(1, 2), (1, 3)] (2, 3) -> 25% (half-siblings)
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 5)] (4, 5) -> 25% (aunt/uncle-nephew/niece)
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (4, 6)] (5, 6) -> 12.5% (cousins)
[(1, 3), (1, 4), (2, 3), (2, 4), (5, 7), (5, 8), (6, 7), (6, 8), (3, 9), (7, 9), (4, 10), (8, 10)] (9, 10) -> 25% (double cousins)
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (4, 5)] (3, 5) -> 75% (parent-(child-with-sibling) incest)
[(1, 2), (1, 3), (2, 3)] (1, 3) -> 75% ((parent-and-grandparent)-(child-with-child) incest)


No person will have more than two parents and there will be no cycles in it. You can also assume that the number is the order in which they were born (so a < b in all (a, b)).

• Can you clarify the task and what exactly m and n represent? If you would give a more concrete formula or something, it would be fine. What exactly do the pairs in the input represent? Aug 12, 2017 at 7:53
• @Mr.Xcoder: The lengths of the paths to both siblings.
– user23125
Aug 12, 2017 at 7:54
• Also, can you have one example of input and an explanation (with steps) on how you obtained that output? Aug 12, 2017 at 7:58
• @isaacg: Yes, (a, b) represents "a is the parent of b", so there will be no (directed) cycles and no person with over 2 parents.
– user23125
Aug 12, 2017 at 15:05
• The half-siblings example (i.e [(1, 3), (2, 3)] (3, 4)) seems to be missing a pairing: either (1, 4) or (2, 4). Aug 13, 2017 at 2:19

# Python 3, 259247 226 bytes

lambda l,a,b:sum(2**-len({*m}^{*n})for v in{*sum(l,())}for m in p(v,a,l)for n in p(v,b,l)if not{*zip(m,m[1:])}&{*zip(n,n[1:])})
p=lambda i,j,l:sum([[[r+[i]for r in p(y,j,l)],[[y,x]]][j==y]for x,y in l if i==x],[])+[[i]]*(i==j)


Try it online!

This can probably be golfed down quite a bit, but for now I'm just happy it works.

# Python3, 206 bytes:

lambda l,a:(a in l)/2+sum(2**-len((x|y)-(x&y))for x in f(a,l,a)for y in f(a,l,a)if x&y)
def f(n,l,o,p=[],K=1):
for a,b in l:
if(b==n)&(K:=[a,b]!=o):yield from f(a,l,o,p+[b]);K=0
if K:yield{*p+[n]}


Try it online!

• 206 May 28, 2022 at 22:13

# Wolfram Language (Mathematica), 188166 154 bytes

e_~h~f_:=4Tr[2^-Tr[Length/@#]&/@Select[Flatten[Tuples[i@r_:=If[#==r,{{r}},FindPath[g,#,r,∞,All]];i/@f]&/@VertexList[g=Rule@@@e],1],DisjointQ@@Rest/@#&]]


Try it online!