Program | TREES.C, TREES.CPP, TREES.PAS |
Given a sequence of child-parent pairs, where a pair consists of the child's
name followed by the (single) parent's name, and a list of query pairs also
expressed as two names, you are to write a program to determine whether the
query pairs are related. If the names comprising a query pair are related the
program should determine what the relationship is. Consider academic advisees
and advisors as exemplars of such a single parent genealogy (we assume a single
advisor, i.e., no co-advisors).
In this problem the child-parent pair p q denotes that p is the child of q.
In determining relationships between names we use the following definitions:
The Input
The input consists of parent-child pairs of names, one pair per line. Each
name in a pair consists of lower-case alphabetic characters or periods (used
to separate first and last names, for example). Child names are separated from
parent names by one or more spaces. Parent-child pairs are terminated by a pair
whose first component is the string ``no.child''. Such a pair is NOT to be considered
as a parent-child pair, but only as a delimiter to separate the parent-child
pairs from the query pairs. There will be no circular relationships, i.e., no
name p can be both an ancestor and a descendent of the same name q.
The parent-child pairs are followed by a sequence of query pairs in the same
format as the parent-child pairs, i.e., each name in a query pair is a sequence
of lower-case alphabetic characters and periods, and names are separated by
one or more spaces. Query pairs are terminated by end-of-file.
There will be a maximum of 300 different names overall (parent-child and query
pairs). All names will be fewer than 31 characters in length. There will be
no more than 100 query pairs.
The Output
For each query-pair p q of names the output should indicate the relationship
p is-the-relative-of q by the appropriate string of the form
If an m-cousin is removed 0 times then only m cousin should be printed, i.e.,
removed 0 should NOT be printed. Do not print st, nd, rd, th
after the numbers.
Sample Input
alonzo.church oswald.veblen
stephen.kleene alonzo.church
dana.scott alonzo.church
martin.davis alonzo.church
pat.fischer hartley.rogers
mike.paterson david.park
dennis.ritchie pat.fischer
hartley.rogers alonzo.church
les.valiant mike.paterson
bob.constable stephen.kleene
david.park hartley.rogers
no.child no.parent
stephen.kleene bob.constable
hartley.rogers stephen.kleene
les.valiant alonzo.church
les.valiant dennis.ritchie
dennis.ritchie les.valiant
pat.fischer michael.rabin
Sample Output
parent
sibling
great great grand child
1 cousin removed 1
1 cousin removed 1
no relation