One of the most exciting things about learning foreign languages is the fact that some words cannot be translated literally. Simply because they have no direct counterpart in our own language. After all, how on earth would you ever translate the fourteen different words the Inuit use for snow? Or the Swedish word lagom, which means something like "not too much and not too little".

The Swedish language itself has no words that are equivalent to grandmother or grandfather. When naming their ancestors, Swedes indeed always indicate if they refer to the descent along the maternal or paternal lineage. Mother is translated in Swedish as mor and father as far. Your maternal grandmother becomes mormor (literally: your mother's mother) and your paternal grandmother becomes farmor (literally: your father's mother). Analogously, they translate the maternal grandfather as morfar and the paternal grandfather as farfar. If we would take over the same naming scheme in English, we would end up with something like mama, mafa, fama and fafa. That would sound really crazy, no?

Swedes extend this naming scheme to refer to their great-grandparents, great-great-grandparents and more distant ancestors. As such, morfarfar is your mother's father's father and farmorfarmor is your father's mother's father's mother.

The Swedish way to describe ancestors sometimes results in quite complex situations. Ancestors are indeed addressed in different ways by their offspring, even though they are of the same generation. If a grandmother has grandchildren of both her daughters and her sons, they will be shouting both farmor and mormor all day long. Meanwhile, grandfather will be confused whether his first response should go to morfar or farfar.

Assignment

We'll work with family trees that have been constructed according to a simplified model, which assumes the following conditions to be fulfilled:

• each person has a unique name that does not contain spaces

• each person has children with at most one partner (of the other sex)

• each child always has one mother and one father; parents are not necessarily included in the family tree, but if one of the parents is included, so does the other

• each person has a unique path to all its ancestors in the family tree

The illustration below shows an example of such a family tree, where women are shown in pink and men in blue. Couples having children are connected by a thick horizontal line. The other relationships should be read from top to bottom, with mother and father on top and their children on the next line. The last condition we have imposed on the family trees means that there's no incest within the family (for example, we can find no children resulting from a relationship between a father and his daughter, nor from relationships between cousins).

The relationships in a family tree are stored in a text file with UTF-8¹ character encoding, whose lines each contain three or more space-separated names. The first name is that of a mother, the second name that of a father and the remaining names are from their children. This way, the example file given below corresponds to the relationships as depicted in the illustration above.

Alana Ronan Beatrice August
Beatrice Clarence Ramiro Regan
Alexandra Ramiro Carlos Luciana Ciara
Regan Damari Alberto Natalee
Amira August Drake Eric Rosa Jadon
Rosa Jovanni Kole Sincere Emmy Gabriella Xzavier
Teresa Jadon Cadence Gavyn Aryana

Note that there is no imposed order in which the lines are listed in the text file. Your task:

• Write a function family_members that takes the location (str) of a text file containing information about the relationships in family tree, formatted as described above. The function must return a dictionary (dict) that maps the names (str) of all member of the family tree onto a dictionary (dict) that may contain the following keys:

• mother: mapped onto the name (str) of the mother of the family member

• father: mapped onto the name (str) of the father of the family member

• children: mapped onto a set containing the names (str) of all children of the family member

Only the keys that correspond to relationships that can be derived from the given text file may be included in the dictionary.

• Write a function ancestor that takes three arguments: i) the name (str) of a family member, ii) the Swedish description (str) of an ancestor and iii) a dictionary (dict) containing relationships in a family tree (formatted as the dictionaries returned by the function family_members). The function must return the name (str) of the ancestor of the given family member that is referred to by the given Swedish description, taking into account the given family tree relationships. The function may assume that the give name of the family member occurs as a key in the given dictionary, and that the Swedish description of the ancestor is a string (str) composed of the substrings mor and far, without the need to check this explicitly. In case the given family tree does no contain an ancestor of the given family member that is referred to by the given description, an AssertionError must be raised with the message unknown ancestor.

• Write a function descendants that takes three arguments: i) the name (str) of a family member, ii) an integer $$n \in \mathbb{N}_0$$ (int) and iii) a dictionary (dict) containing relationships in a family tree (formatted as the dictionaries returned by the function family_members). The function must return a dictionary (dict) whose keys are all Swedish descriptions (str) the given family member is referred to by his or her $$n$$-th generation of ancestors in the given family tree. The dictionary must map each of these descriptions onto a set of names (str) of all descendants in the family tree that refer to the given family member by this description. The function may assume that the give name of the family member occurs as a key in the given dictionary, without the need to check this explicitly. The generations of ancestors are determined relatively to the given family member: the first generation are the children of the family member, the second generation are the grandchildren, the third generation are the great-grandchildren, and so on.

Example

In the following interactive session, we assume the text file data.txt² to be located in the current directory. This is the text file that corresponds to the family tree that is used as an example in the description of this assignment.

>>> relationships = family_members('data.txt3')
>>> relationships['Sincere']
{'father': 'Jovanni', 'mother': 'Rosa'}
>>> relationships['August']
{'father': 'Ronan', 'mother': 'Alana', 'children': {'Eric', 'Drake', 'Jadon', 'Rosa'}}
>>> relationships['Ronan']
{'children': {'Beatrice', 'August'}}

>>> ancestor('Drake', 'mor', relationships)
'Amira'
>>> ancestor('Rosa', 'farmor', relationships)
'Alana'
>>> ancestor('Sincere', 'morfarfar', relationships)
'Ronan'
>>> ancestor('Luciana', 'morfarmor', relationships)
Traceback (most recent call last):
AssertionError: unknown ancestor

>>> descendants('Ronan', 1, relationships)
{'far': {'Beatrice', 'August'}}
>>> descendants('Ronan', 2, relationships)
{'morfar': {'Regan', 'Ramiro'}, 'farfar': {'Rosa', 'Eric', 'Jadon', 'Drake'}}
>>> descendants('Ronan', 3, relationships)
{'farmorfar': {'Carlos', 'Luciana', 'Ciara'}, 'farfarfar': {'Gavyn', 'Cadence', 'Aryana'}, 'mormorfar': {'Alberto', 'Natalee'}, 'morfarfar': {'Kole', 'Emmy', 'Sincere', 'Xzavier', 'Gabriella'}}