21
\$\begingroup\$

A family of sets is called laminar if for any two sets \$A\$ and \$B\$ in the family one of the following is true:

  • \$ A \subseteq B \$
  • \$ A \supseteq B \$
  • \$ A \cap B = \emptyset \$

Or less mathematical:

A laminar set is a list of lists that satisfies the following condition: If two elements of the top level list have at least one element in common, one of them has to be completely contained in the other one.

Examples:

laminar:
{} 
{{1,2,3},{1,2},{1},{}}
{{1,2,3,4},{1,2,3},{1,2},{3},{4}}
{{1,2,3,4},{1,2},{3,4},{1},{3}}
{{1,2,3,4},{1,3},{2,4},{1},{2},{3},{4},{}}
{{1,2,3},{4,5},{7,8},{3},{5},{7}}

not laminar:

{{1,2},{2,3}}
{{1,2,3,4},{1,2,3},{1,2},{3,4}}
{{1,2,3,4},{1,2},{3,4},{2,3},{1},{2},{3},{4}}
{{1,2,3,4,5},{1,2,3},{4,5,6}}

Your goal is to write a program of function that takes a set of set as input and returns truthy if the set is laminar and falsey if is it not laminar.

Rules:

  • You can take lists instead of sets as Input
  • If you use lists as input you can assume that the lists (top-level and/or sub-lists) are sorted (in any convenient order) and each element appear only once
  • Your solution should be able to handle Inputs lists with at least 250 distinct element values
  • You are allowed to use any type to represent the elements of the list (as long as it has enough distinct values)
  • This is the shortest solution (per language) wins.
\$\endgroup\$
1
  • \$\begingroup\$ Can the assumed sort be something other than lexicographic in the case of a top-level sort? e.g. descending by length? \$\endgroup\$ Aug 3, 2023 at 8:29

18 Answers 18

12
\$\begingroup\$

Python, 50 bytes

lambda c:all(a&b in(a,b,a-a)for a in c for b in c)

Attempt This Online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I am thoroughly confused as to why a-a works, but not 0. \$\endgroup\$
    – SanguineL
    Aug 2, 2023 at 18:34
  • 4
    \$\begingroup\$ @SanguineL Probably because 0 is not a set. At least not in Python. \$\endgroup\$
    – loopy walt
    Aug 2, 2023 at 18:40
  • 5
    \$\begingroup\$ @SanguineL Since a is a set and not a number, a-a also creates a set, in this case the empty set. set() works but is longer. {} unfortunately makes a dict and not a set. \$\endgroup\$
    – mousetail
    Aug 2, 2023 at 18:44
  • 1
    \$\begingroup\$ Ah, I see. That does make sense. \$\endgroup\$
    – SanguineL
    Aug 2, 2023 at 19:23
10
\$\begingroup\$

Rust, 63 bytes

Port of mousetail's python answer.

|s|s.iter().all(|a|s.iter().all(|b|a&b==*a||a&b==*b||a&b==a-a))

Rust explorer

\$\endgroup\$
1
  • 9
    \$\begingroup\$ Two things I love the most: 1: Rust, 2: Mention of my name (I'm narcissistic) \$\endgroup\$
    – mousetail
    Aug 2, 2023 at 18:46
8
\$\begingroup\$

Nekomata + -e, 8 bytes

ᵒ{ᵋ∩?Ø?=

Attempt This Online!

ᵒ{ᵋ∩?Ø?=
ᵒ{          For each pair of elements A, B in the input, check that:
  ᵋ∩        Intersection of A and B
    ?Ø?     Any of A, B, or the empty set
       =    Are they equal?
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 69 bytes

Expects a list of lists. Returns false for laminar, or true for not laminar.

Not the right tool for the job.

a=>a.some(x=>a.some(y=>(b=x.filter(v=>y.includes(v))+'')&&b!=x&b!=y))

Try it online!

41 bytes (ES11)

As one would expect, converting each sub-list to a BigInt bit-mask and applying bitwise logic is longer.

a=>(a=a.map(b=>b.map(v=>m|=1n<<v,m=0n)&&m)).some(x=>a.some(y=>y^(y&=x)&&x^y&&y))

Try it online! (80 bytes)

But if we can take the list of sets directly as a list of bit-masks (as suggested by @Cubic), then we can just do:

a=>a.some(x=>a.some(y=>y^(y&=x)&&x^y&&y))

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ I don't think you need to convert in your second solution, according to the spec a list of "sets" is a valid input, and I'd say a bitset is a set. But I don't think JS supports 250+ bit integers, which the question requires. \$\endgroup\$
    – Cubic
    Aug 3, 2023 at 11:43
  • \$\begingroup\$ @Cubic JS has native BigInts since ES2020. \$\endgroup\$
    – Arnauld
    Aug 3, 2023 at 11:48
  • \$\begingroup\$ @Cubic Also, thanks for reminding me that we have to support 250+ distinct elements. I've fixed the 75-byte version (now 80). \$\endgroup\$
    – Arnauld
    Aug 3, 2023 at 12:05
4
\$\begingroup\$

05AB1E, 11 bytes

ãε¯ªy`Ã.å}P

Try it online or verify all test cases.

Explanation:

ã        # Cartesian product to get all pairs of the (implicit) input-list
 ε       # Map over each pair of lists:
  ¯ª     #  Append an empty list to the pair
  y`     #  Push the lists of the pair separately to the stack
    Ã    #  Pop both, and push a list with values that occurred in both lists
     .å  #  Non-vectorized check if this list is in the earlier triplet of lists
 }P      # After the map: check if all are truthy
         # (after which the result is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Raku, 47 bytes

{all cross @^a,@a,:with{$^x∩$^y≡∅|$x|$y}}

Try it online!

(The ageing version of Perl 6 on TIO does not understand the operator, added in 2020. I replaced it there with eqv for one additional byte.)

This anonymous function takes as input a list of sets in the variable @^a/@a. It computes the cross product of all of those sets with each other using the anonymous function in braces following :with. For each pair, that function returns a truthy value if the intersection () of the two sets is identical to () one of those sets or to the empty set (). The final result is a truthy value indicating whether all of those pairwise values are truthy.

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

JavaScript (Node.js), 88 bytes

x=>x.some(a=>x.some(b=>g(a,b)&g(b,a)))
g=(a,b)=>/0,1|1,0/.test(a.map(i=>+b.includes(i)))

Try it online!

Return inversed

\$\endgroup\$
3
\$\begingroup\$

Factor + math.unicode sets.extras, 52 bytes

[ dup '[ _ [ diffs f like and and ] with ∃ ] ∃ ]

Attempt This Online!

Output is inverted: outputs f for laminar and t for not laminar.

  • alias for any? that is 1 byte shorter
  • dup '[ _ [ ... ] with ∃ ] ∃ Is there any pair of sets in the input that is true when [ ... ] is applied to them?
  • diffs A lovely word that takes two sets as inputs and returns three outputs: the set difference between input 1 and input 2, the set difference between input 2 and input 1, and the intersection between input 1 and input 2. This word converts empty sets to f except for the intersection.
  • f like Convert the intersection to f if it is empty; leave alone otherwise.
  • and and Take the logical and of the three results.
\$\endgroup\$
3
\$\begingroup\$

Haskell, 68 63 bytes

Unfortunately \\ is not in Prelude, and I couldn't figure out how to write it shorter without the Data.List functions (without the import it's 51 bytes).

(Shaved off 5 bytes by switching to list comprehension from nested all)

import Data.List
l s=and[a\\b==[]||b\\a==[]||a\\b==a|a<-s,b<-s]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 59 with inverted output. Hell, it still ties non-inverted if you slap a not$ on there. \$\endgroup\$ Aug 3, 2023 at 11:14
3
\$\begingroup\$

Jelly, 8 bytes

iƇⱮFf\€Ƒ

Try it online!

Relies on the whole family being sorted descending by length, incidentally coinciding with how the testcases are displayed.

  ⱮF        For each element of any of the sets,
iƇ          filter the family to only sets containing it.
      €Ƒ    Is every one of those sub-families unchanged by
    f\      cumulative intersection?

Jelly, 10 9 bytes

fpḟpḟ@ðþF

Try it online!

-1 remembering that I already made the link dyadic

Outputs an empty list iff laminar. If output can't have reversed truthiness, slap a on the end.

      ðþ     For every pair (dyadically) of sets:
 p           Take the Cartesian product of
f            the intersection and 
  ḟ          the difference one way
   p         and
    ḟ@       the difference the other way.
        F    Flatten.

Jelly, 10 bytes

Œcµḟṭif/)P

Try it online!

Direct approach everyone else is using.

Œcµ     )P    For every pair (as a list) of sets:
    ṭ         Append
   ḟ          the empty list;
     i        does that contain
      f/      the intersection?
\$\endgroup\$
3
\$\begingroup\$

Scala, 79 bytes

Port of @corvus_192's Rust answer in Scala.


Golfed version. Try it online!

s=>{s.forall(a=>{s.forall(b=>{var z=a intersect b;z==a||z==b||z==a.diff(a)})})}

Ungollfed version. Try it online!

import scala.collection.immutable.HashSet

object Main extends App {
  
  def f(s: Seq[HashSet[Int]]): Boolean = {
    s.forall(a => {
      s.forall(b => {
        a.intersect(b) == a || a.intersect(b) == b || a.intersect(b) == a.diff(a)
      })
    })
  }
  
  assert(f(Seq.empty[HashSet[Int]]))
  assert(f(Seq(
    HashSet(1, 2, 3),
    HashSet(1, 2),
    HashSet(1),
    HashSet.empty[Int]
  )))
  assert(f(Seq(
    HashSet(1, 2, 3, 4),
    HashSet(1, 3),
    HashSet(2, 4),
    HashSet(1),
    HashSet(2),
    HashSet(3),
    HashSet(4),
    HashSet.empty[Int]
  )))

  assert(!f(Seq(HashSet(1, 2), HashSet(2, 3))))
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I don't know Scala but I think you can replace z==a.diff(a) with z.size==0 (it works for the test-cases) \$\endgroup\$
    – bsoelch
    Aug 4, 2023 at 8:25
3
\$\begingroup\$

R, 64 bytes

\(x,`?`=all)?Map(\(A)?Map(\(B)any(?(p=A%in%B),?B%in%A,?!p),x),x)

Attempt This Online!

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

Charcoal, 15 bytes

⬤θ⬤θ№⟦ιλυ⟧⁻ι⁻ιλ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for laminar, nothing if not. Explanation: Charcoal has no set intersection function, otherwise this would be a direct port of @mousetail's latest Python answer, but emulating list intersection using list difference does mean I get to use the predefined variable for an empty list.

 θ              Input list
⬤               All elements satisfy
   θ            Input list
  ⬤             All elements satisfy
      ι         Outer element
       λ        Inner element
        υ       Empty list
    №⟦   ⟧      Includes
           ι    Outer element
          ⁻     List difference
             ι  Outer element
            ⁻   List difference
              λ Inner element
\$\endgroup\$
2
\$\begingroup\$

Pyth, 13 bytes

.Am}@Fd+d.{Y*

Attempt This Online!

Explanation

.Am}@Fd+d.{Y*QQ    # implicitly add QQ
                   # implicitly assign Q = eval(input())
            *QQ    # cartesian product of Q and Q
  m                # map over lambda d
    @Fd            #   intersection of the elements of d
   }               #   is in
       +d.{Y       #   d plus the empty set
.A                 # return whether all elements are true
\$\endgroup\$
2
\$\begingroup\$

Arturo, 56 bytes

$->x[some? x'a->some? x'b->¬∨∨a=a--b[]=a--b[]=b--a]

Try it!

Inverts the output; false for laminar and true for not laminar.

$->x[               ; a function taking a set of sets x
    some? x'a->     ; is there some set a in x that
        some? x'b-> ; is there some set b in x that
            []=b--a ; the empty set equals b diff a
            ∨       ; or
            []=a--b ; the empty set equals a diff b
            ∨       ; or
            a=a--b  ; a diff b is unchanged
            ¬       ; logical not (we have to do it this way to accommodate empty input)
]                   ; end function
\$\endgroup\$
2
\$\begingroup\$

C (GCC), 199 197 bytes

#define T int
#define A(p,z)*v){T b=0,i=0;for(;y;++i)b|=p;return b?z:!z;}
#define y v[i]
C(T x,T A(x==y,1)P(T z,T*s,T A(z-C(y,s),1)X(T*a,T*A(P(1,a,y)&P(1,y,a)&(P(0,a,y)|P(0,y,a)),0)f(T*A(!X(y,v),1)

Attempt This Online!

Takes input as a double pointer to int (int **) which is zero terminated on both levels (hence 0 cannot be used as an element).

Note that the solution is in C, while the full snippet is in C++ because I used vectors to store the data after parsing.


ungolfed solution (in C++)

\$\endgroup\$
3
  • \$\begingroup\$ Macros so horrifying they wrap around to beautiful! Can shave four bytes off with #define A(p,z)*v){T b=0;for(T i=0;y;++i)b|=p;return z^b;}. \$\endgroup\$ Aug 7, 2023 at 5:16
  • 1
    \$\begingroup\$ @UnrelatedString unfortunately it doesn't work as it is because p assumes values >1 to indicate truthy, and hence z^b does not correspond to logic xor \$\endgroup\$
    – matteo_c
    Aug 7, 2023 at 9:44
  • 1
    \$\begingroup\$ Ah, I read the test case outputs wrong. Glad to see it's salvageable \$\endgroup\$ Aug 7, 2023 at 9:48
2
\$\begingroup\$

Julia 1.0, 43 bytes

~x=all(A⊆B||B⊆A||A∩B==[] for A=x,B=x)

Try it online!

-2 bytes thanks to MarcMush: square brackets aren't needed for an array comprehension that is passed to a function

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

Ruby, 45 43 bytes

->a{a.all?{|x|a.all?{|y|[[],x,y].any?x&y}}}

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Replace index x&y with any?x&y for -2. \$\endgroup\$
    – Value Ink
    Sep 1, 2023 at 3:54

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.