9
\$\begingroup\$

{}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.

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ Can a language with a nestable set type just check equality? \$\endgroup\$
    – xnor
    Jun 15, 2016 at 1:58
  • \$\begingroup\$ @xnor Built-ins should be fair game, yes \$\endgroup\$
    – Liam
    Jun 15, 2016 at 1:59
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Liam
    Jun 15, 2016 at 4:11
  • 1
    \$\begingroup\$ I'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.). \$\endgroup\$
    – Dennis
    Jun 15, 2016 at 4:30
  • 8
    \$\begingroup\$ 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 \$\endgroup\$
    – cat
    Jun 15, 2016 at 12:37

16 Answers 16

Reset to default
4
\$\begingroup\$

CJam, 11 bytes

q']/"]$"*~=

Try it here.

CJam, 13 bytes

q~L{{j}%$}j:=

Try it here.

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

Jelly, 6 bytes

߀Ṣ
ÇE

Try it online! or verify all test cases.

How it works

ÇE   Main link. Argument: [s, t] (pair of set arrays)

Ç    Apply the helper link to [s, t].
 E   Check if the elements of the resulting pair are equal.


߀Ṣ  Helper link. Argument: u (set array)

߀   Recursively map this link over u.
  Ṣ  Sort the result.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 8 bytes

{p:1a.}.

This expects brackets in Input and Output.

For example: 

?- run_from_atom('{p:1a.}.', [[]:[[]]], [[[]]:[]]).
true .

Explanation

{     }.   True if the predicate inside brackets is true with input Input and output Output

 p          Unify an implicit variable with a permutation of Input
  :1a       Apply this same predicate to each element of that implicit variable
     .      True if Output can be unified with the resulting list
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

APL (NARS2000), 4 bytes

≡⍦

⍦ is the multiset operator, which modifies functions to treat their arguments as sets instead of lists
≡ is the equivalence function, which returns a Boolean indicating if the arguments are completely equivalent in value and shape

Regarding the additional rule: Note that this answer does not use any unordered set datatype, but just normal lists (which may contain multiple identical elements). It just treats them as sets.

The byte count is 4 because NARS2000 uses UCS-2 exclusively.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Pyth, 9 bytes

LSyMbqyEy

Input format: use [] instead of {}.

Test suite

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 16 bytes

Equal@@Sort//@#&

An unnamed function which expects a list containing both sets, e.g.

Equal@@Sort//@#& @ {{{}, {{}}}, {{{}}, {}}}

We use //@ (MapAll) to sort the sets at every level and then assert at the results are equal.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 42 bytes

f=(a,b,g=a=>0+a.map(g).sort()+1)=>g(a)==g(b)

Accepts input using []s e.g. f([[],[[]]],[[[]],[]]). Works by converting the arrays to strings and then sorting them from the inside out. 0 and 1 are used because they're shorter than '[' and ']', so for example g([[[]],[]]) is 001,00111 which represents [[],[[]]].

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ You don't use recursion, so you can make it anonym \$\endgroup\$
    – Bálint
    Jun 15, 2016 at 22:14
  • \$\begingroup\$ Why is that 0+ there? \$\endgroup\$
    – Bálint
    Jun 15, 2016 at 22:23
  • \$\begingroup\$ @Bálint Because without the 0+ and +1 all I'd get is commas. \$\endgroup\$
    – Neil
    Jun 15, 2016 at 23:08
  • \$\begingroup\$ @Bálint I don't know why I forgot to remove the f=, I didn't include it in the byte count and I'm too lazy to edit the post just for that. \$\endgroup\$
    – Neil
    Jun 15, 2016 at 23:10
2
\$\begingroup\$

Python 2, 49 bytes

f=lambda x:sorted(map(f,x))
lambda a,b:f(a)==f(b)

For example, calling the anonymous function g:

>>> g( [[],[[]]] , [[[]],[]] )
True
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ g([[],[[],[]],[[],[[]]],[[]],[[[]]]], [[[],[]],[[[]],[]],[[]],[[[]]],[]]) returns False, but the sets are equal. That should be fixed by mapping before sorting. \$\endgroup\$
    – Dennis
    Jun 15, 2016 at 0:03
2
\$\begingroup\$

Prolog (SWI), 37 bytes

X+Y:-permutation(X,Z),maplist(+,Z,Y).

Try it online!

Takes input as nested lists, i.e. with square brackets instead of braces. Originally, this was X+Y:-sort(X,M),sort(Y,N),maplist(+,M,N)., but then I tried translating Fatalize's Brachylog v1 answer and it turned out 3 bytes shorter.

X+Y :-                    X+Y succeeds when
    permutation(X, Z),    for some permutation Z of X
    maplist(+, Z, Y).     + succeeds for every pair in Z zipped with Y.
                          (where maplist will succeed without the recursive call to + for
                          two empty lists, and fail if the lists have different lengths)

It actually can handle curly braces instead, for 23 more bytes:

Prolog (SWI), 60 bytes

{A}*C:-A=..[,|B],sort(B,C).
X+Y:-X=Y;X*M,Y*N,maplist(+,M,N).

Try it online!

* here converts a (nonempty, hence the X=Y;) brace term on its right side to a list of the term's elements then sorts it to its left side.

{A}*C :-            X*C succeeds when X is the brace term containing A
    A =.. [,|B],    where A is a comma-tuple and B is a list of its elements,
    sort(B, C).     and C is B sorted.

Since both arguments to + are going through * already, putting a sort in * saves 7 bytes over using permutation in +.

And finally, here's a version which handles the input lists possibly having duplicate elements, which is what inspired me to write a solution in Prolog to begin with:

Prolog (SWI), 57 bytes

X+Y:-X/Y,Y/X.
X/Y:-maplist(-(Y),X).
Y-E:-member(F,Y),E+F.

Try it online!

X+Y :-                   X+Y succeeds when
    X/Y, Y/X.            X/Y and Y/X succeed.
X/Y :-                   X/Y succeeds when
    maplist(-(Y), X).    for every element E of X, Y-E succeeds
                         (or when X is empty).
Y-E :-                   Y-E succeeds when
    member(F, Y),        there exists some element F of Y
    E+F.                 such that E+F succeeds.

Essentially, X/Y declares that X is a subset of Y, by declaring that for every element of X, there's an equal element of Y, so X/Y,Y/X declares that X and Y are equal sets.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ And now I need sleep \$\endgroup\$
    – Unrelated String
    May 11, 2019 at 10:37
1
\$\begingroup\$

Julia, 36 35 32 bytes

u*v=(sort(u.*v)...)
s%t=s*s==t*t

Input is a nested array either either the (deprecated) {} syntax or Any[].

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

SETL, 1 byte

=

Takes sets as left and right arguments.

Note that this does NOT adhere the added rule which prohibits unordered set datatypes.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Brachylog v2, 3 bytes

p↰ᵐ

Try it online!

Takes one set through the input variable and the other set through the output variable. Succeeds if the sets are equal and fails if they aren't.

Like my main Prolog answer, a translation of Fatalize's Brachylog v1 answer (which I think could be golfed down to p:0a?).

       The input
p      can be re-ordered so that
 ↰     when this predicate is applied again to
  ᵐ    all of its elements,
       it is the output.
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 7 chars / 9 bytes

ѨƾꞨî,Ꞩí

Try it here (ES6 browsers only).

Explanation

         // implicit: î=input1,í=input2
  Ꞩî,Ꞩí // apply the Set method to both inputs
Ѩƾ      // check if the Sets are equal
        // implicit output
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Haskell, 77 bytes

import Data.List
data S=L[S]deriving(Eq,Ord)
f(L x)=L$sort$f<$>x
a!b=f a==f b
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Out of interest, why did you need to define your own list type here? (Are == and < not defined by default for lists?) \$\endgroup\$
    – user62131
    Jun 19, 2017 at 0:21
  • 1
    \$\begingroup\$ the datatype is recursive: I define S as a (wrapped-in-L) list of Ses. Haskell has no built-in type that can represent lists of lists of lists of … \$\endgroup\$
    – Lynn
    Jun 19, 2017 at 14:50
0
\$\begingroup\$

Perl 6, 55 bytes

my&f=->\a,\b {a==b&&all map {f(|$_)},(a.sort Z,b.sort)}

Takes input with [].

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Some things: you don't need the space after the arguments to the code block, it's often shorter to use the $^ syntax instead, and I don't think the [] input works, since all of [[]],[[[]]],[[[[]]]] etc evaluate to [] \$\endgroup\$
    – Jo King ♦
    May 12, 2019 at 3:29
0
\$\begingroup\$

Wolfram Language (Mathematica), 20 bytes

Sort//@#==Sort//@#2&

Try it online!

Pure function that takes each set as an argument.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.