9
\$\begingroup\$

inputs / outputs

your program/function/routine/... will be a predicate on two tuple sequences; call it relation . for the purpose of simplicity we use natural numbers:

  • the input will be two list of pairs of numbers from ℕ (including 0); call them Xs and Ys
  • the output will be a "truthy" value

specification

checks the sequences for equality up to permuting elements where the first elements u and u' don't match.

in other words compares lists with (u,v)s in it for equality. but it doesn't completely care about the order of elements (u,v)s. elements can be permuted by swapping; swaps of (u,v) and (u',v') are only allowed if u ≠ u'.

formally: write Xs ≡ Ys iff holds for Xs and Ys as inputs (the predicate is an equivalence relation hence symmetric):

  • [] ≡ []
  • if rest ≡ rest then [(u,v),*rest] ≡ [(u,v),*rest] (for any u, v)
  • if u ≠ u' and [(u,v),(u',v'),*rest] ≡ Ys then [(u',v'),(u,v),*rest] Ys

examples

[] [] → 1
[] [(0,1)] → 0
[(0,1)] [(0,1)] → 1
[(0,1)] [(1,0)] → 0
[(1,0)] [(1,0)] → 1
[(1,2),(1,3)] [(1,2),(1,3)] → 1
[(1,2),(1,3)] [(1,3),(1,2)] → 0
[(1,2),(1,3)] [(1,2),(1,3),(0,0)] → 0
[(0,1),(1,2),(2,3)] [(2,3),(1,2),(0,1)] → 1
[(1,1),(1,2),(2,3)] [(2,3),(1,2),(0,1)] → 0
[(1,2),(0,2),(2,3)] [(2,3),(1,2),(0,1)] → 0
[(1,2),(2,3),(0,2)] [(2,3),(1,2),(0,1)] → 0
[(1,1),(1,2),(1,3)] [(1,1),(1,2),(1,3)] → 1
[(3,1),(1,2),(1,3)] [(1,2),(1,3),(3,1)] → 1
[(3,1),(1,2),(1,3)] [(1,3),(1,2),(3,1)] → 0
[(2,1),(3,1),(1,1),(4,1)] [(3,1),(4,1),(1,1)] → 0
[(2,1),(4,1),(3,1),(1,1)] [(3,1),(1,1),(2,1),(4,1)] → 1
[(2,1),(3,1),(1,1),(4,1)] [(3,1),(2,1),(4,1),(1,1)] → 1

(keep in mind the relation is symmetric)

\$\endgroup\$
5
  • 3
    \$\begingroup\$ Welcome to Code Golf! I'd recommend using the sandbox for future challenges, although this looks like a pretty good first challenge. \$\endgroup\$ Dec 16, 2020 at 13:24
  • 3
    \$\begingroup\$ And we are going to call it the "Hamburger menu operator".. More seriously, you have the line [(0,1)] [(1,0)] → 0 duplicated, did you mean another test case and it's a typo? \$\endgroup\$
    – Kaddath
    Dec 16, 2020 at 13:39
  • 3
    \$\begingroup\$ To check that I understand, is this an equivalent way to specify the condtion? "For each number n, the pairs whose first element equals n within each list come in the same order." \$\endgroup\$
    – xnor
    Dec 16, 2020 at 13:39
  • \$\begingroup\$ @Kaddath fixed. \$\endgroup\$
    – 榨 菜
    Dec 16, 2020 at 13:42
  • \$\begingroup\$ @xnor: yes, this is equivalent! \$\endgroup\$
    – 榨 菜
    Dec 16, 2020 at 13:43

8 Answers 8

5
\$\begingroup\$

Husk, 4 bytes

¤=Ö←

Try it online! (header runs function on all test cases)

¤       # combin: applies one function to two values and combines the results
 =      # combining function: are they equal?
  Ö←    # function to apply: sort on first element 
        # values (implicit): inputs
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 47 bytes

Assumes that .sort() is stable, which is now guaranteed by the specification (today's version!).

a=>b=>(g=a=>a.sort(([a],[b])=>a-b))(a)+''==g(b)

Try it online!

\$\endgroup\$
3
+150
\$\begingroup\$

Haskell, 42 bytes

import Data.List
q=sortOn fst
a%b=q a==q b

Try it online!

Based on Arnauld's JS solution. Despite Haskell needing a lengthy import to access sorting, it's well worth the bytes. Note that sortOn, which sorts a list by a custom predicate, is stable. In fact, sortOn fst is used for the example in the documentation.


Haskell, 50 bytes

a%b|let q l=[t|u<-a++b,t<-l,fst t==fst u]=q a==q b

Try it online!

51 bytes

k?l=[x|(i,x)<-l,i==k]
a%b=and[k?a==k?b|(k,_)<-a++b]

Try it online!

Uses this characterization: For each number k, the pairs whose first element equals k within each list come in the same order."

The helper function ? in k?l takes a list of pairs l and selects for the second element x in each pair (k,x) with first element equal to k. The main function % then checks that this is the same on both input lists for each k present.

Note that we avoid using sorting, which Haskell doesn't have built-in without a lengthy import.

51 bytes

k?l=[t|t<-l,fst t==k]
a%b=and[k?a==k?b|(k,_)<-a++b]

Try it online!

51 bytes

(?)k=filter$(==k).fst
a%b=and[k?a==k?b|(k,_)<-a++b]

Try it online!

51 bytes

l?m=[x|(k,_)<-m,(i,x)<-l,i==k]
a%b|s<-a++b=a?s==b?s

Try it online!

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

Ruby 2.7, 41 bytes

->a,b{a.sort_by{_1[0]}==b.sort_by{_1[0]}}

No TIO link, as TIO uses an older version of Ruby.


Ruby, 45 bytes

->a,b{a.sort_by(&:first)==b.sort_by(&:first)}

Try it online!

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

K (ngn/k), 13 bytes

{~/x@'<'*''x}

Try it online!

Takes input as a single argument of two lists of lists.

  • x@'<'*''x sort each input by the first item of each-each input
  • ~/ do the two sorted lists match?
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 23 bytes

⬤⁺θη⁼Φθ⁼§λ⁰§ι⁰Φη⁼§λ⁰§ι⁰

Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. - for equivalent, nothing if not. Explanation:

  θ                     First list
 ⁺                      Concatenated with
   η                    Second list
⬤                       All pairs must satisfy
      θ                 First list
     Φ                  Filtered where
        §λ⁰             First element of inner pair
       ⁼                Equals
           §ι⁰          First element of outer pair
    ⁼                   Equals
               η        Second list
              Φ         Filtered where
                 §λ⁰    First element of inner pair
                ⁼       Equals
                    §ι⁰ First element of outer pair
                        Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 21 bytes

%O#`\d+,\d+
^(.+)¶\1$

Try it online! Assumes lists on separate lines but link includes header that splits the test cases for ease of use. Explanation:

%O#`\d+,\d+

Sort each list stably by the first element of each pair.

^(.+)¶\1$

Compare the two lists.

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

Jelly, 4 bytes

ṖÞ€E

A monadic Link accepting a list of the two lists which yields 1 (truthy) or 0 (falsey).

Try it online! Or see the test-suite.

How?

ṖÞ€E - Link: [a,b]
  €  - for each list, [t_1, t_2, ...], in [a,b]
 Þ   -   sort by:
Ṗ    -     pop (t_n with its tail removed)
   E - all equal?
\$\endgroup\$

Your Answer

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

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