This is one of several challenges left for the community by Calvin's Hobbies.
Take a "family tree describing" file with lines of the form:
[ID] [mother ID] [father ID] [gender] [full name]
such as this which describes the first family tree at http://en.wikipedia.org/wiki/Cousin:
1 ? ? M Adam 2 ? ? F Agatha 3 ? ? M Bill 4 2 1 F Betty 5 2 1 M Charles 6 ? ? F Corinda 7 3 4 M David 8 6 5 F Emma
Write a program or function that takes in the file name and two IDs and outputs how those people are blood-related in simplest terms, using the common English names for relations. Input may be via STDIN, ARGV or function arguments but output should be to STDOUT.
- IDs are positive integers.
?is used when parentage is not known.
- Assume the graph will be connected and has no cycles.
- You may not assume that each person's parents are listed before that person (so a person's parent ID could be greater than their own ID).
- Assume everyone is either male or female and everyone has exactly one mother and exactly one father (of correct gender), although they might be unknown.
- Assume names are unique.
- Names can have spaces in them.
The following definitions of relationships R determine if person A is the R or person B. If two variants of R are listed, the first is for female A and the second for male A. All of these need to be implemented. If multiple definitions match, the earlier one is to be used. Terms in parentheses are gender-neutral terms, which do not need to be implemented but will be reused in further definitions. In definitions involving N and M, assume N > 1 and M > 0.
- daughter/son: A lists B as either parent.
- mother/father (parent): B lists A as either parent.
- sister/brother (sibling): A and B list the same mother and father.
- half-sister/half-brother (sibling): A and B list the same mother or the same father.
- niece/nephew: A lists a parent who is the sibling of B.
- aunt/uncle: B is A's niece or nephew.
- granddaughter/grandson (grandchild): A lists a parent who lists B as their parent.
- grandmother/grandfather (grandparent): B is A's grandchild.
- great-niece/great-nephew: A is the grandchild of C who is the sibling of B.
- great-aunt/great-uncle: B is A's great-niece or great-nephew.
- great-granddaughter/son (1st great-grandchild): A is a grandchild of C who lists B as their parent.
- great-grandmother/father (1st great-grandparent): B is A's 1st great-grandchild.
- Nth great-granddaughter/son (Nth great-grandchild): A is an (N-1)th grandchild of C who lists B as their parent.
- Nth great-grandmother/father (Nth great-grandparent): B is A's Nth great-grandchild.
- Nth great-niece/nephew: A is the (N-1)th great-grandchild of C who is the sibling of B.
- Nth great-aunt/uncle: B is A's Nth great-niece of Nth great-nephew.
- cousin: A is the grandchild of C who is the grandparent of B.
- Nth cousin: A is the (N-1)th grandchild of C who is the (N-1)th grandparent of B.
- cousin, M times removed: A is the grandchild of C who is the Mth grandparent of B or A is the Mth grandchild of C who is the grandparent of B .
- Nth cousin, M times removed: A is the Pth great-grandchild of C who is the Qth great-grandparent of B, where
N = min(P,Q) + 1and
M = |P-Q|.
M times, write
5 times etc.
Assume the following file is used (you don't have to be able to deal with multiple spaces, but I added them for legibility):
1 ? ? F Agatha 2 ? ? M Adam 3 ? ? F Betty 4 1 2 M Bertrand 5 1 2 F Charlotte 6 ? ? M Carl 7 ? ? F Daisy 8 3 4 M David 9 5 6 F Emma 10 ? ? M Edward 11 ? ? F Freya 12 7 8 M Fred 13 9 10 F Grace 14 ? ? M Gerald 15 ? ? F Hillary 16 11 12 M Herbert 17 13 14 F Jane 18 ? ? M James 19 15 16 F Kate 20 17 18 M Larry 21 ? 18 F Mary
Then input IDs should map to outputs as follows:
1 2 --> Agatha is not a blood relative to Adam. 8 3 --> David is the son of Betty. 9 13 --> Emma is the mother of Grace. 4 5 --> Bertrand is the brother of Charlotte. 9 4 --> Emma is the niece of Bertrand. 5 8 --> Charlotte is the aunt of David. 16 7 --> Herbert is the grandson of Daisy. 1 9 --> Agatha is the grandmother Emma. 12 5 --> Fred is the great-nephew of Charlotte. 4 13 --> Bertrand is the great-uncle of Grace. 16 3 --> Herbert is the great-grandson of Betty. 6 17 --> Carl is the great-grandfather of Jane. 19 2 --> Kate is the 3rd great-granddaughter of Adam. 1 17 --> Agatha is the 2nd great-grandmother of Jane. 20 4 --> Larry is the 3rd great-nephew of Bertrand. 5 16 --> Charlotte is the 2nd great-aunt of Herbert. 8 9 --> David is the cousin of Emma. 19 20 --> Kate is the 4th cousin of Larry. 16 9 --> Herbert is the cousin, twice removed, of Emma. 12 17 --> Fred is the 2nd cousin, once removed, of Jane. 21 20 --> Mary is the half-sister of Larry.
I wrote those up by hand so let me know if you spot any mistakes.
Another set of test data (provided by Scott Leadley, any errors are mine and not Martin's)
Ptolemy family tree
The picture is illustrative; the data below comes from the Wikipedia article "Ptolemaic dynasty".
1 ? ? F Berenice I of Egypt 2 ? ? M Ptolemy I Soter 41 1 2 F Arsinoe II of Egypt 3 1 2 M Ptolemy II Philadelphus 4 ? ? F Arsinoe I of Egypt 5 ? ? M Philip 6 4 3 M Ptolemy III Euergetes 7 1 5 F Magas of Cyrene 8 7 ? F Berenice II 9 8 6 M Ptolemy IV Philopator 10 8 6 F Arsinoe III of Egypt 11 10 9 M Ptolemy V Epiphanes 12 ? ? F Cleopatra I of Egypt 13 12 11 M Ptolemy VI Philometor 14 12 11 F Cleopatra II 15 12 11 M Ptolemy VIII Physcon 19 ? ? F Eirene 16 14 13 M Ptolemy VII Neos Philopator 17 14 13 F Cleopatra III 18 14 15 M Ptolemy Memphites 20 19 15 M Ptolemy Apion 21 17 15 F Cleopatra IV 22 17 15 M Ptolemy IX Lathyros 23 17 15 F Cleopatra Selene I 24 17 15 M Ptolemy X Alexander I 25 23 22 F Berenice III of Egypt 26 23 24 M Ptolemy XI Alexander II 27 21 22 M Ptolemy XII Auletes 28 25 24 F Cleopatra V of Egypt 29 28 27 F Cleopatra VI of Egypt 30 28 27 F Berenice IV of Egypt 31 28 27 M Ptolemy XIII Theos Philopator 32 28 27 F Cleopatra VII Thea Philopator 33 28 27 M Ptolemy XIV 34 28 27 F Arsinoe IV of Egypt 35 ? ? M Julius Caesar 37 32 35 M Ptolemy XV Caesarion 36 ? ? M Mark Anthony 38 32 36 M Alexander Helios 39 32 36 M Ptolemy XVI Philadelphus 40 32 36 F Cleopatra Selene II