Weekly Problem #14

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement

You are writing software to help someone understand their very complicated family. Your task is to determine all aunts and uncles of a given person. An aunt or uncle of a person is defined as a sibling of that person's parent. Two people are siblings if they have one or more parents in common.

Create a class AuntUncle that contains a method list which receives a tvector<string>, with each element containing a record of a person's birth - in the form of "PARENT1 PARENT2 CHILD" (quotes for clarity only), and a single String with the target person's name, and returns a tvector<string> of all aunts and uncles for that target person, sorted alphabetically.

Definition

Class: AuntUncle
Method: list
Parameters: tvector<string>, string
Returns: tvector<string>
Method signature (see below, be sure your method is public):

Class

#include<string> using namespace std; #include "tvector.h" class AuntUncle { public: tvector<string> list(const tvector<string>& parents, const string& target) { // fill in code here } };

Notes

Gender of the people is not to be considered. In other words, parents A and B could have a child together, as could parents A and C, as well as parents B and C - even though this would be impossible normally, since at least one of those pairings would result in two people of the same gender.
Under no circumstances will the correct answer include the target.
Under no circumstances will the correct answer include either of the actual parents of the target.

Constraints

Inputs are valid (you don't need to check) if all of the following criteria are met:

parents will contain between 1 and 50 elements, inclusive.
Each element in parents will be in the form of "parent1 parent2 child" (quotes for clarity).
Each element in parents will not contain leading/trailing spaces.
Each item in each element of (parent1, parent2, and child) will be at least 1 character, and at most 10 characters, in length.
Each item in each element of parents (parent1, parent2, and child) will contain only capital letters ('A'-'Z').
Each item in each element of parents (parent1, parent2, and child) will be separated by exactly one space.
Each element in parents will not contain repeated names. That is, parent1, parent2, and child will all be different names.
No ancestral loops will occur in parents. In other words, someone cannot be both a descendant and an ancestor of the same person.
No one will be listed as a child in more than one element in parents. A person can only have one pair of parents.
String target will contain only capital letters ('A'-'Z').
String target will be between 1 and 10 characters in length, inclusive.
String target will be contained as an item (either parent1, parent2, or child) in at least one element of parents.

Examples

In each of these examples, quotes ('"'), commas (','), and curly braces ('{' and '}') are included for clarity only. They are never part of the input or output.

```
parents = {"JOE JANE ROB"}
target = "ROB"
```
Returns: {}
Target "ROB"'s parents do not have parents, let alone siblings. "ROB" has no uncles or aunts.
```
    
parents = {"JOE MARY FRANK", "BOB JANE MARTHA", "FRANK MARTHA ROB", 
           "BOB AMANDA TROY"}
target = "ROB"
```
Returns: {"TROY"}
Target "ROB"'s parent "MARTHA" has a parent "BOB" who has a child other than either of "ROB"'s parents. This child is named "TROY", and must be "ROB"'s Uncle (or Aunt).
```
parents = {"HECTOR DANA ROB", "ROB MARY JOE", "JOE MARY FRANK"}
target = "FRANK"
```
Returns:{}
Target "FRANK"'s parent "MARY" is also his parent "JOE"'s parent. Be careful you don't think "FRANK" is his own Uncle (or Aunt).

parents = {"A B E", "C D F", "E F G", "A P Z", "B P Y", "C P X", "D P W", 
           "A B V", "B C U", "A C T", "B D S", "A D R", "B C Q"}
target = "G"

return: {"Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"}

Note that the answer is sorted alphabetically.

Owen L. Astrachan

Last modified: Wed Jul 23 10:30:05 EDT 2003