Problem 2: Old email groups in a new world.
Background:
Macrophage Inc.'s old email system "Overlook" allows users to set up
aliases for groups of email recipients. Two files are used to maintain
the system. The first "addr" file associates a name with each individual
email address in the system. The second "alias" file contains sequences of
entries, each of which
associates a group name with zero or more other names. The other names
may be group names or names associated with email addresses. In this
system, when an email group name is to be expanded into a list of email
recipients, the process is to go through the alias file in order. when
the given group name is found it is replaced by the list of associate names
and thereafter when any of those names are found they are expanded, etc.
The final list of names is then used to look up actual addresses in the addr file.
Names which are not associated with an actual address are simply ignored.
This system requires the user to be sure that an alias which references
other aliases appears before those other aliases in the file. For example
consider
bowling-buddies: swat-team jerry
jerry: jerry-home jerry-office
swat-team: tom jerry-office mary bowling-buddies
Bowling-buddies would expand to "tom jerry-office mary bowling-buddies jerry-home jerry-office" and then
presumably only tom, mary, and the jerrys would be found in the addr file.
Micromush's new email system "Outtake" is designed to allow aliases to
reference other aliases which appear earlier in the alias file as well.
This is fine
except that examples like that above could lead to an infinite loop of expansions.
Task
The purpose here is twofold:
-
Loops are detected and dealt with. The final expanded list should only contain
names which are reachable by expansion but are not group aliases, that is they
do not appear anywhere in the alias file followed by a ":"
- Duplication of names in the final list is avoided. Thus in the example
above the final list should be (in some order)
"tom jerry-office mary jerry-home".
Input:
The (standard) input will be the alias file. It consists of a sequence of
entries which are a name followed by a colon followed by zero or more names.
White space separates names within an entry and also separates entries. While
usually entries are on one line, this is not always the case and in fact
multiple entries may be on one line.
The final name followed by a semi-colon
is the name to be expanded.
Names are strings of up to 20 characters not
containing white space or colon or semicolon.
Output:
The list, without duplication, of address names reachable by alias expansion.
By definition an address name is any name which is not an alias group name
with a defining entry in the alias file.
Sample Input:
a: b c d h
f: g a script
b: a b c a
h i d: f
e: f fort
h: j: k l m z
b;
Sample Output:
c g i script