| Bytes | Lang | Time | Link |
|---|---|---|---|
| 725 | Scala 3 | 240603T034849Z | 138 Aspe |
| 278 | Python 2 | 191125T113728Z | Dead Pos |
| 033 | Jelly | 191122T095024Z | Nick Ken |
Scala 3, 725 bytes
A port of @Dead Possum's Python 2 answer in Scala.
725 bytes, it can be golfed much more.
Golfed version. Attempt This Online!
def COI(I: List[List[String]], Z: String): Double = {
val P = mutable.Map[String, ListBuffer[String]]()
for (R <- I; r <- R.take(2)) {
if (!P.contains(r)) P(r) = ListBuffer[String]()
P(r) ++= R.drop(2)
}
def fP(c: String, p: List[String], r: ListBuffer[List[String]]): ListBuffer[List[String]] = {
if (c == Z) r += p
else if (P.contains(c)) for (z <- P(c)) fP(z, p :+ z, r)
r
}
var rS = 0.0
for (k <- P.keys) {
val paths = fP(k, List(), ListBuffer())
val pC = paths.combinations(2)
for (c <- pC) {
val a = c(0)
val b = c(1)
val cL = (a ++ b).size
if (cL - 1 == (a ++ b).toSet.size&& a.init.last != b.init.last) rS += math.pow(0.5, cL - 2)
}
}
rS
}
Ungolfed version. Attempt This Online!
import scala.collection.mutable
import scala.collection.mutable.ListBuffer
object Main {
def main(args: Array[String]): Unit = {
// Defining the input list of lists
val I = List(
List("Philip I", "Joanna", "Charles V", "Ferdinand I", "Isabella 2"),
List("Isabella 1", "Charles V", "Maria", "Philip II"),
List("Ferdinand I", "Anna 1", "Maximillian II", "Charles IIa", "Anna 2"),
List("Isabella 2", "Christian II", "Christina"),
List("Maria", "Maximillian II", "Anna 3"),
List("Anna 2", "Albert V", "Maria Anna 1", "William V"),
List("Christina", "Francis I", "Renata"),
List("Philip II", "Anna 3", "Philip III"),
List("Charles IIa", "Maria Anna 1", "Margaret", "Ferdinand II"),
List("William V", "Renata", "Maria Anna 2"),
List("Philip III", "Margaret", "Philip IV", "Maria Anna 3"),
List("Ferdinand II", "Maria Anna 2", "Ferdinand III"),
List("Maria Anna 3", "Ferdinand III", "Mariana"),
List("Philip IV", "Mariana", "Charles IIb")
)
val Z = "Charles IIb" // Target element
val result = CoefficientOfInbreeding(I, Z)
println(result)
}
def CoefficientOfInbreeding(I: List[List[String]], Z: String): Double = {
// Dictionary to store the relationships
val P = mutable.Map[String, ListBuffer[String]]()
// Populating the dictionary P with relationships from list I
for (R <- I) {
for (r <- R.take(2)) { // Iterate over the first two elements of each sublist in I
if (!P.contains(r)) {
P(r) = ListBuffer[String]()
}
P(r) ++= R.drop(2) // Add the rest of the elements in the sublist as relationships
}
}
// Function to recursively find paths from c to Z
def findPaths(
c: String,
path: List[String],
result: ListBuffer[List[String]]
): ListBuffer[List[String]] = {
if (c == Z) {
result += path
} else if (P.contains(c)) {
for (z <- P(c)) {
findPaths(z, path :+ z, result)
}
}
result
}
// Finding all combinations of paths and calculating the desired sum
var resultSum = 0.0
for (k <- P.keys) {
val paths = findPaths(k, List(), ListBuffer[List[String]]())
// Get all combinations of paths
val pathCombinations = paths.combinations(2)
for (comb <- pathCombinations) {
val a = comb(0)
val b = comb(1)
val combinedLength = (a ++ b).length
val uniqueElementsLength = (a ++ b).toSet.size
if (
combinedLength - 1 == uniqueElementsLength && a.init.last != b.init.last
) {
resultSum += math.pow(0.5, combinedLength - 2)
}
}
}
resultSum
}
}
Python 2, 304 294 293 278 bytes
Takes as input: list of lists of relatives; name of person to calculate coefficient.
P={}
I,Z=input()
for R in I:
for r in R[:2]:P[r]=P.get(r,[])+R[2:]
l=lambda c,p,X:c==Z and X.append(p)or c in P and[l(z,p*1+[z],X)for z in P[c]]and X
print sum(pow(.5,len(a+b)-2)for k in P for a in l(k,[],[])for b in l(k,[],[])if~-len(a+b)==len(set(a+b))if a>b if a[-2]!=b[-2])
Python 2, 274 bytes
If input is allowed as single list of lists, where last list contains name of person to calculate coefficient, some bytes can be saves, using leaked variable from for loop.
P={}
for Z in input():
for r in Z[:2]:P[r]=P.get(r,[])+Z[2:]
l=lambda c,p,X:c==Z[0]and X.append(p)or c in P and[l(z,p*1+[z],X)for z in P[c]]and X
print sum(pow(.5,len(a+b)-2)for k in P for a in l(k,[],[])for b in l(k,[],[])if~-len(a+b)==len(set(a+b))if a>b if a[-2]!=b[-2])
Some explanation
# Converts input lists into dictionary, where keys - each parent
# and values - list of its children
# In this task we don't care about direct relations between any parents
P={}
for R in I:
# for parents in cells [0] and [1] add cells [2:]
for r in R[:2]:
P[r] = P.get(r, []) + R[2:]
# Lambda collects all paths from node c to the person of interest
# It's recursive function, which stores all paths in argument X and then returns it
# Each paths is guarantied to have person of interest as last element
# and one of its parents as previous to last element
l=lambda c,p,X: c==Z and X.append(p) or c in P and [l(z, p*1+[z], X) for z in P[c]] and X
# For each node with children:
# calculate all paths to person of interest
# get all pairs of this paths
for k in P
for a in l(k,[],[])for b in l(k,[],[])
# filters out dublicates
if a>b
# if paths from pair have unique items
# (except only 1 same item, that each path have - person of interest)
# and if previous to last elements are different
# (i.e. paths through different parents)
if ~-len(a+b)==len(set(a+b)) and a[-2]!=b[-2]
# This pair of paths forms simple inbreed path, so add up to result
sum(pow(.5,len(a+b)-2) .. )
Note, that algorithm also covers cases when one of parents is ancestor to other one, as node of elder parent will produce similar paths, that will add up to result sum.
Jelly, 43 33 bytes
ịW€;Ɱ0ịịɗ¥€Ẏ¥ƬẎ¥€ŒpṪ€E$ƇF€QƑƇẈ.*S
A dyadic link taking the individual as the left argument and the pedigree as the right. The pedigree is a list of lists where each (possibly empty) list represents the parents of the person at that index. Returns a floating point number.
Explanation
ị | Index into pedigree to find parents of desired individual
W€ | Wrap each in a list
¥€ | For each parent:
¥Ƭ | - Do the following as a dyad, keeping intermediate results:
¥€ | - Do the following as a dyad for each member of the list
;Ɱ ɗ | - Concatenate the following (as a dyad) to the end of the list:
0ị | - Last member of the list
ị | - Indexed into pedigree to find parents
Ẏ | - Remove one level of lists (concatenating outer sublists together)
Ẏ | - Remove one level of lists (concatenating outer sublists together)
Œp | Cartesian product of the two lists of possible chains of ancestors for each parent
$Ƈ | Keep those where:
Ṫ€ | - The tail of each chain (removing from the chain in the process)
E | - Is equal
F€ | Flatten each
Ƈ | Keep those where:
Ƒ | - The list is invariant when:
Q | - Uniquified
Ẉ | Lengths of each list
.* | 0.5 to the power of the lengths
S | Sum