Compare shapeless lists

Question

Let's have a ragged list containing no values, only more lists. For example:

[[[],[[]],[],[]],[],[[],[],[]],[]]

And the list will be finite, meaning that eventually every path terminates in an empty list [].

It's simple enough to determine if two of these are structurally equal. Check each element in order for equality and recurse. However what if we don't care about the order of the lists for equality? What if we only care that they have the same elements?

We can define this shapeless equality like so:

Two lists \$A\$, and \$B\$ are shapeless equal if for every element in \$A\$ there are as many elements in \$A\$ shapeless equal to it as there are in \$B\$, and vice-versa for the elements of \$B\$.

Your task will be to take two ragged lists and determine if they are "shapeless equal" to each other. If they are you should output some consistent value, if they are not you should output some distinct consistent value.

This is code-golf so answers will be scored in bytes with fewer bytes being the goal.

Testcases

[] [] -> 1
[[],[[]]] [[[]],[]] -> 1
[[],[[],[[]]]] [[],[[[]],[]]] -> 1
[[],[[],[[]]]] [[[[]],[]],[]] -> 1
[[]] [] -> 0
[[],[]] [[[]]] -> 0
[[],[]] [[]] -> 0
[[[],[],[]],[[]]] [[[],[]],[[],[]]] -> 0
[[],[],[[]]] [[],[[]],[[]]] -> 0

Answer 1

Brachylog, 3 bytes

p↰ᵐ

Try it online!

Explanation

This takes the first list as the input variable, and the second list as the output variable. The interpreter then prints true. if it is possible to satisfy this predicate with these variables, and false. otherwise.

p     The output is a permutation of the input
 ↰ᵐ   Recursively call this predicate on each element of the input

Answer 2

Python 3, 49 bytes

lambda x,y:g(x)==g(y)
g=lambda a:sorted(map(g,a))

Try it online!

Answer 3

JavaScript (ES6), 41 bytes

Expects (a)(b). Returns a Boolean value.

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

Try it online!

How?

We can't compare nested arrays in JS by simply coercing them to strings because everything is flatten and empty arrays are turned into empty strings. (Basically, only commas would remain with the arrays we're dealing with in this challenge.)

We could use JSON.stringify:

a=>JSON.stringify(a.map(g).sort())

but this is a bit lengthy.

Instead, we do a custom conversion to a string by prepending a 1 at the beginning of each call and appending a 0 at the end.

For an already sorted array, this effectively replaces opening brackets with 0's and closing brackets with 1's, while leaving commas unchanged.

For instance:

 [[],[[],[[]]]]
"110,110,110000"

Answer 4

Jelly, 7 bytes

߀Ṣ
Ç€E

A monadic Link accepting a list of the two ragged lists that yields 1 if they are "shapeless equal".

Try it online!

How?

Recursively sort the containers of any nested lists and compare the results for equality.

߀Ṣ - Helper Link, recursively sort container lists and their content: List, X
 €  - for each element in X:
ß   -   call this Link
  Ṣ - sort

Ç€E - Link, the main function: List, A
 €  - for each of the two lists in A:
Ç   -   call the Helper Link
  E - all equal?

Answer 5

Ruby, 38 bytes

->l,m{g=->a{a.sort.map &g};g[l]==g[m]}

Try it online!

(Stolen from hyper neutrino's python answer)

Answer 6

Wolfram Language (Mathematica), 16 bytes

SameQ@@Sort//@#&

Try it online!

Input [{A, B}].

Answer 7

05AB1E, 11 bytes

"®δ.V{"©.VË

Port of @JonathanAllan's Jelly answer, but without having access to recursive functions.

Input as a pair of nested lists.

Try it online or verify all test cases.

Explanation:

"..."      # Push the 'recursive' string explained below
     ©     # Store it in variable `®` (without popping)
      .V   # Execute it as 05AB1E code
           # (using the implicit input-pair in the first call)
        Ë  # Check if both lists in the pair are now equal
           # (after which the result is output implicitly)

 δ         # Map over each inner list:
® .V       #  Do a recursive call by executing string `®` as 05AB1E code
    {      # Then sort each inner list

Answer 8

Stax, 14 bytes

ü╙ûÆ╙X○Γfó¡↓↓▄

Run and debug it

Sort arrays till the lowest depth and compare for equality. G might be usable here, but a reusable recursive function feels shorter (recursive will probably prove me wrong). (I proved myself wrong. -1)

Answer 9

Python3, 78 bytes:

s=sorted
l=len
f=lambda a,b:l(a)==l(b)and all(f(j,k)for j,k in zip(s(a),s(b)))

Try it online!

Answer 10

Charcoal, 47 bytes

⊞υθ⊞υηＦυＦι⊞υκＷυ«≔⊟υι≔⟦⟧ζＷι⊞ζ⊟ιＷ⁻ζιＦ№ζ⌊κ⊞ι⌊κ»⁼θη

Try it online! Link is to verbose version of code. Not easy due to lack of recursion or sorting primitives. Explanation:

⊞υθ⊞υηＦυＦι⊞υκ

Get all of the lists and sublists from the input.

Ｗυ«≔⊟υι

Process them in reverse order.

≔⟦⟧ζＷι⊞ζ⊟ι

Move the elements of this (sub)list into a temporary list.

Ｗ⁻ζιＦ№ζ⌊κ⊞ι⌊κ

Put them back but in sorted order.

»⁼θη

Now that the input lists have been sorted in-place, we can just compare them directly.

Answer 11

Retina 0.8.2, 116 bytes

+`(?=(((\[)|(?<-3>])|,)+(?(3)^)),(?!\1)(((\[)|(?<-6>])|,)+(?(6)^))(.*))(.*)\[.*(?=\4\7$)\8].*(?=\7$)
$4,$1
^(.+) \1$

Try it online! Link includes test cases. Explanation:

+`

Repeat until no more lists need exchanging.

(?=(((\[)|(?<-3>])|,)+(?(3)^)),(?!\1)(((\[)|(?<-6>])|,)+(?(6)^))(.*))

Look ahead to capture two balanced lists and the tail of the string.

(.*)\[.*(?=\4\7$)\8].*(?=\7$)

Check whether the second list should precede the first list. The lookaheads ensure that we only compare the two lists captured above. Note that this could inefficiently swap two lists back and forth before it's finished sorting their sublists, but once all of the sublists are sorted the lists will eventually sort stably.

$4,$1

If so then exchange the two lists.

^(.+) \1$

Now that the input lists have been sorted, just compare them directly.

Answer 12

Pari/GP, 56 bytes

f(a,b)=s=vecsort;#a==#b&&prod(i=1,#a,f(s(a)[i],s(b)[i]))

Try it online!

Answer 13

Perl 5, 59 bytes

sub f{@_>1?f(pop)eq f(pop):"(@{[sort map{f($_)}@{pop()}]}"}

Try it online!