7
\$\begingroup\$

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)).

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Mr. Xcoder Aug 12 '17 at 7:53
  • \$\begingroup\$ @Mr.Xcoder: The lengths of the paths to both siblings. \$\endgroup\$ – user23125 Aug 12 '17 at 7:54
  • 2
    \$\begingroup\$ Also, can you have one example of input and an explanation (with steps) on how you obtained that output? \$\endgroup\$ – Mr. Xcoder Aug 12 '17 at 7:58
  • \$\begingroup\$ 50% seems awfully high for cousins. By my calculation, that should be 12.5%, since 1 and 2 each have path lengths of 2 to 5 and 6, so they should contribute 1/16th each, for a total of 1/8th. \$\endgroup\$ – isaacg Aug 12 '17 at 8:00
  • \$\begingroup\$ @isaacg: Fixed it, I forgot to change the number after copy-pasting. \$\endgroup\$ – user23125 Aug 12 '17 at 8:01
1
\$\begingroup\$

Python 3, 259 247 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy