Task 4. Inheritance

Available Marks: 14

The system of inheritance that applied to most families with land or a title in England until recent times was called entailment. It was designed to keep the family estate intact as far as possible, by passing ownership to one (generally male) person at a time. Instead of all children, or even just all sons, inheriting the estate on the death of an owner, the eldest surviving son inherits the lot. This rule then applies recursively to his sons. Thus all his male descendents are ahead of his younger brothers, his brothers are ahead of his uncles, and so on.

If all male descendents of the original owner are deceased, surviving females are next in line to inherit, but under these conditions:

• The inheritance rules still follow the eldest male line in order to rank females, and
• Sisters inherit equally (thus potentially breaking up the estate, which would be transferred to other families on marriage).

Example

The family tree below shows all the descendents of the original owner, M0. M0 and his eldest son M1 are deceased, and M1's eldest son is the present owner. The numbers in parentheses record the order of inheritance that would apply when M4 dies.

First in line is M4's brother M5 (because M4 has no male heirs), then M5's first son, his grandson, etc. Following all 10 surviving males, the same rules apply to females, starting with M4's daughters, who are jointly 10th in line. In practice males are assigned on a pre-order traversal of the male-line tree and females on a post-order traversal of the male-line tree, which is why F6 inherits ahead of F1.

Note that the structure doesn't depend on who's still alive: although dead people can't inherit, their living descendents can.

Your task

Write a program that analyses a family tree and prints the order of inheritance. Input consists of one line for each male, listing his children in descending order of age. The first input line is the number of males. Each person is identified by gender (M or F) and a non-negative integer, unique to that gender. The original owner is always M0, other numbers can be assigned in any order, but without gaps.

For each line the patriarch's ID is followed by an optional symbol and a colon, then the IDs of the children. The symbol is either

• x, indicating the person is deceased, or
• *, indicating the present owner.

Output is the present owner and the order of inheritance in one line, separated by spaces.

Sample data

This describes the tree above. It's already sufficiently complex to fully exercise your program.

12
M0x: M1 F1 M2 M3
M1x: M4 M5 F2 M6 F3
M3:
M4*: F4 F5
M5: M8 M9
M10:
M8: M11
M6: M10
M7: F6
M2: M7
M9:
M11:

M4 M5 M8 M11 M9 M6 M10 M2 M7 M3 F4+F5 F2+F3 F6 F1

Test data

Test your program using the following two test cases.

Test 1:

11
M0*: M3 M6
M1: M5
M2: M1
M3:
M4: M10 M2
M5:
M6: M7 M9
M7:
M8:
M9: M8 M4
M10:

Test 2:

17
M0x: M3 M14 M11
M4:
M8x: F2 M4 M15 M5
M12: M8 M10
M16:
M5:
M14x: F3 M12 F5
M3*:
M9:
M6: M13 F4
M10: M9 M6 M2
M2x:
M13x:
M11: M16 F1 M1
M1:
M15: M7
M7:

Assessment

• 5 marks for Test 1
• 9 marks for Test 2

You may submit multiple times. Only your most recent submission for each question will be marked.

Reference: Background information and example are from
Churchyard, Henry (2004-2011). Pride and Prejudice -- Notes on Education, Marriage, Status of Women, etc. Republic of Pemberley.

Image: talentenbank