9
1
{}is the empty set. You may use () or [] if you choose.
We aren't going to rigorously define "set", but sets all satisfy the following properties:
Sets follow the usual mathematical structure. Here are some important points:
- Sets are not ordered.
- No set contains itself.
- Elements are either in a set or not, this is boolean. Therefore set elements cannot have multiplicities (i.e. an element cannot be in a set multiple times.)
- Elements of a set are also sets and
{}is the only primitive element.
Task
Write a program/function that determines whether two sets are equal.
Input
Two valid sets via stdin or function argument. The input format is loose within reason.
Some valid inputs are:
{} {{}}
{{},{{}}} {{{{{},{{}}}}}}
{{},{{},{{}}}} {{{},{{}}},{{{{{},{{}}}}}}}
Invalid inputs:
{{} {} Brackets will always be balanced.
{{},{}} {} Set contains the same element twice
Output
A truthy value if the inputs are equal, falsy otherwise.
Test cases
Your submission should answer correctly for all valid inputs, not just for the test cases. These may be updated at any point.
Truthy:
{} {}
{{},{{}}} {{{}},{}}
{{},{{},{{{}},{}}}} {{{{},{{}}},{}},{}}
Falsy:
{} {{}}
{{},{{},{{{}},{}}}} {{{{}}},{},{{}}}
{{},{{}},{{{}}},{{},{{}}}} {}
Scoring
Additional Rules
An additional rule has been added banning unordered iterable types altogether. They are too common and trivialize this challenge far too much. Feel free to leave answers that violate this in place, please just make an indication that they were made before the rule change.
Liam
Posted 2016-06-14T22:57:35.987
Reputation: 3 035
Can a language with a nestable set type just check equality? – xnor – 2016-06-15T01:58:14.853
@xnor Built-ins should be fair game, yes – Liam – 2016-06-15T01:59:22.660
Does that mean I can write a function that accepts two sets as input? That seems to defeat the purpose of the challenge since
{{},{{}}}and{{{}},{}}are literally the same set. – Dennis – 2016-06-15T04:01:41.9671@Dennis well, even though this is a "balanced-string" challenge, I never really thought of it as a parsing challenge. But, now that I think about it, by assuming that all input is valid, I've kind of made it a parsing challenge. So I think you're right. Enough languages probably have the idea of a an un-ordered list that would trivialize this. – Liam – 2016-06-15T04:11:21.580
1I'll be fine with whatever decision you make. Personally, while I think that using sets somehow can still be creative without trivializing the challenge (like my Julia answer, which recursively converts a nested array into a nested set), allowing nested sets as input makes the whole thing a bit too simple (
==in Julia, 2 bytes;frozenset.__eq__in Python, 16 bytes; etc.). – Dennis – 2016-06-15T04:30:35.257@Dennis My original solution used recursion, which is why I thought it might be interesting, so I think using similar built-in type equality checks shouldn't be allowed (despite what I said to xnor). – Liam – 2016-06-15T05:06:26.837
OK, rolling back my Julia answer. The cleanest approach would probably be to ban unordered iterable types altogether. For example, converting two sets to lists and comparing the results technically doesn't use a set equality test. – Dennis – 2016-06-15T05:24:58.327
8
See the comments for an explanation.Please don't do this. Comments are volatile and go away very easily, so important sutff goes in the post body – cat – 2016-06-15T12:37:15.517@cat the rule is the important part, and that is in the text body. I felt that the explanation was too cumbersome (because it was really a conversation) to put in the text body. If you think it is truly necessary, I will ask Dennis to move the conversation to chat and link that from the body. As it stands, I have added a brief summary to the body and removed the reference to the comments (which is what I should have done in the first place, whoops!). – Liam – 2016-06-15T21:23:51.393