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.

\$\endgroup\$
  • \$\begingroup\$ Can a language with a nestable set type just check equality? \$\endgroup\$ – xnor Jun 15 '16 at 1:58
  • \$\begingroup\$ @xnor Built-ins should be fair game, yes \$\endgroup\$ – Liam Jun 15 '16 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 '16 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 '16 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 '16 at 12:37

16 Answers 16

4
\$\begingroup\$

CJam, 11 bytes

q']/"]$"*~=

Try it here.

CJam, 13 bytes

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

Try it here.

\$\endgroup\$
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.
\$\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
\$\endgroup\$
2
\$\begingroup\$

Pyth, 9 bytes

LSyMbqyEy

Input format: use [] instead of {}.

Test suite

\$\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.

\$\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 [[],[[]]].

\$\endgroup\$
  • \$\begingroup\$ You don't use recursion, so you can make it anonym \$\endgroup\$ – Bálint Jun 15 '16 at 22:14
  • \$\begingroup\$ Why is that 0+ there? \$\endgroup\$ – Bálint Jun 15 '16 at 22:23
  • \$\begingroup\$ @Bálint Because without the 0+ and +1 all I'd get is commas. \$\endgroup\$ – Neil Jun 15 '16 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 '16 at 23:10
2
\$\begingroup\$

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.

\$\endgroup\$
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
\$\endgroup\$
  • \$\begingroup\$ g([[],[[],[]],[[],[[]]],[[]],[[[]]]], [[[],[]],[[[]],[]],[[]],[[[]]],[]]) returns False, but the sets are equal. That should be fixed by mapping before sorting. \$\endgroup\$ – Dennis Jun 15 '16 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.

\$\endgroup\$
  • \$\begingroup\$ And now I need sleep \$\endgroup\$ – Unrelated String May 11 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!

\$\endgroup\$
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.

\$\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.
\$\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
\$\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
\$\endgroup\$
  • \$\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 '17 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 '17 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!

\$\endgroup\$
  • \$\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 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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