TopCoder problem "SetComparison" used in CRPF Charity Finals (Division I Level Three)

Problem Statement

    When studying set theory, the line between elements and sets is often blurred. Using the following definitions, you are going to write a function that will help students in a set theory class make such distinctions.

An atom is something that is not a set. In this problem atoms will be strings of lowercase letters.

A set is a collection of elements. The elements can be other sets, or atoms. In this problem, sets will be represented as comma-delimited lists of elements, the whole of which is enclosed in curly brackets ( '{' and '}' ). A set may be empty, and is thus denoted as "{}". This notation convention will be used throughout the rest of the problem statement.

x is a member of a set B if B contains x. For example, a, {b}, and {c,{a}} are all members of {a,{b},{c,{a}}}. b and {} are not members of this set.

Two sets are equivalent if and only if they contain exactly the same elements. Worded differently, two sets are NOT equivalent if there is an element contained by one that isn't contained by the other. For example, {a,{b},c}, {a,c,{b}}, and {a,a,{b},c} are all equivalent since they contain the same elements. The set {a,{b},c,b} is not equivalent to the previous three since none of them contain the element b. Note that duplication of elements does not affect a set.

A set A is a subset of a set B if and only if B contains every element that A contains and possibly others as well. For example, {}, {a,a,b}, {a,{c},b}, and {{c},a,b,c} are all subsets of {{c},a,c,b}. Note that {a,a,b} contains elements a and b, which are both contained in {{c},a,c,b}.

A set A is a proper subset of a set B if and only if A is a subset of B and they are not equivalent.

A set A is the powerset of a set B if and only if A contains every possible subset of B and nothing else. For example, {{a},{b},{a,b},{}} is the powerset of {a,b}. {a,{a},{}} is not the powerset of {a}.

A set A is equipotent to a set B if and only if A and B contain the same number of distinct elements. The word distinct here is only used for added emphasis. For example, {a,b,c}, {aa,bb,cc}, and {d,{e},f,f} are all equipotent to each other because they each contain 3 distinct elements. {a,a,a}, {a,b,c,{}} and {a,a,b} are not equipotent to the previous three.

Given 2 Strings a and b representing sets, your function will return a String[] containing each of the following that holds true for a and b:

"MEMBER" : if a is a member of b

"EQUIVALENT" : if a and b are equivalent

"SUBSET" : if a is a subset of b

"PROPER SUBSET" : if a is a proper subset of b

"POWERSET" : if a is the powerset of b

"EQUIPOTENT" : if a and b are equipotent

The returned String[] should be sorted in lexicographic ('A'-'Z') order.



Parameters:String, String
Method signature:String[] relation(String a, String b)
(be sure your method is public)


-a must contain between 2 and 50 characters inclusive
-b must contain between 2 and 50 characters inclusive
-Both a and b must adhere to the following grammar:

VALID = "{" LIST "}" | "{}"



ATOM = positive length lowercase string
-Both a and b will only contain lowercase letters ('a'-'z'), brackets ('{' and '}'), and commas (',')


Returns: { "PROPER SUBSET",  "SUBSET" }
The empty set is always a subset of any set. Since a and b do not represent equivalent sets, it is a proper subset as well.
Returns: { "POWERSET" }
Here the set represented by a contains every possible subset of the set represented by b.
Only difference is repeated elements.
Returns: { "MEMBER",  "PROPER SUBSET",  "SUBSET" }
Returns: { "MEMBER" }
Returns: { "POWERSET" }
Returns: { }

Problem url:

Problem stats url:




lbackstrom , schveiguy

Problem categories:

String Parsing