14
\$\begingroup\$

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 so answers will be scored in bytes with fewer bytes being the goal.

Testcases

[] [] -> 1
[[],[[]]] [[[]],[]] -> 1
[[],[[],[[]]]] [[],[[[]],[]]] -> 1
[[],[[],[[]]]] [[[[]],[]],[]] -> 1
[[]] [] -> 0
[[],[]] [[[]]] -> 0
[[],[]] [[]] -> 0
[[[],[],[]],[[]]] [[[],[]],[[],[]]] -> 0
[[],[],[[]]] [[],[[]],[[]]] -> 0
\$\endgroup\$
1
  • \$\begingroup\$ Suggested falsy test case: [[],[[]],[[]]] [[],[[],[[]]]]. (All existing test cases would pass a simplified version of my solution where the trailing 0 is not inserted.) \$\endgroup\$
    – Arnauld
    Jan 11, 2022 at 1:56

13 Answers 13

15
\$\begingroup\$

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

Python 3, 49 bytes

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

Try it online!

\$\endgroup\$
0
6
\$\begingroup\$

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"
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Old Firefox (SpiderMonkey) has an uneval which is a bit shorter than JSON.stringify. Although still longer than current approach. \$\endgroup\$
    – tsh
    Jan 11, 2022 at 1:48
  • \$\begingroup\$ @tsh Interesting, thanks. I was suspecting either V8 or SpiderMonkey had such a feature but couldn't find it. \$\endgroup\$
    – Arnauld
    Jan 11, 2022 at 1:50
5
\$\begingroup\$

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?
\$\endgroup\$
4
\$\begingroup\$

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)

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 16 bytes

SameQ@@Sort//@#&

Try it online!

Input [{A, B}].

\$\endgroup\$
2
\$\begingroup\$

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

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)

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ You can cut out two bytes by removing the l=len line. It adds 6 to only save 4 later on \$\endgroup\$
    – thshea
    Jan 11, 2022 at 23:09
1
\$\begingroup\$

Charcoal, 47 bytes

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

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

⊞υθ⊞υηFυFι⊞υκ

Get all of the lists and sublists from the input.

Wυ«≔⊟υι

Process them in reverse order.

≔⟦⟧ζWι⊞ζ⊟ι

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

W⁻ζιF№ζ⌊κ⊞ι⌊κ

Put them back but in sorted order.

»⁼θη

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 59 bytes

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

Try it online!

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