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.
Notes
- 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.
Blood relations
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) + 1
andM = |P-Q|
.
For Nth
, write 2nd
, 3rd
, 4th
, 5th
etc.
For M times
, write once
, twice
, thrice
, 4 times
, 5 times
etc.
Examples
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