16
\$\begingroup\$

Two points pand q in a topological space can be separated if there are open sets U and V such that:

  1. p is an element of U and q is an element of V
  2. U and V do not have any elements in common

Your task is given a topology (a set of open sets) and two points p and q (p!=q) to output sets U and V satisfying the above conditions, or decide that such sets do not exist.

Examples:

{{},{0},{1},{0,1}} 0 1                             -> {0},{1}
{{},{0},{1,2},{0,1,2}} 0 1                         -> {0},{1,2}
{{},{0,1},{2,3},{2,3,4},{0,1,2,3},{0,1,2,3,4}} 1 2 -> {0,1},{2,3} or {0,1},{2,3,4}
{{},{1,2},{3,4},{5,6},{1,2,3,4},{1,2,5,6},{3,4,5,6},{1,2,3,4,5,6}} 1 3 -> {1,2},{3,4} or {1,2},{3,4,5,6} or {1,2,5,6},{3,4}
{{},{1,2},{3,4},{5,6},{1,2,3,4},{1,2,5,6},{3,4,5,6},{1,2,3,4,5,6}} 1 5 -> {1,2},{5,6} or {1,2,3,4},{5,6} or {1,2},{3,4,5,6}

{{},{0,1}} 0 1                                     -> "not separable"
{{},{1},{1,2}} 1 2                                 -> "not seperable"
{{},{1,2,3},{1,3},{2,3},{3}} 1 2                   -> "not seperable"
{{},{0},{1,2},{0,1,2}} 1 2                         -> "not separable"
{{},{1,2},{3,4},{5,6},{1,2,3,4},{1,2,5,6},{3,4,5,6},{1,2,3,4,5,6}} 1 2 -> "not separable"

Rules:

  • You can assume the the Input is valid (a set of sets, that defines a Topology1)
  • You may assume that the two given points are different and contained in at least one of the sets in the Topology
  • You may use lists instead of sets for input/output
  • If you use lists you can assume that the elements are unique and sorted in any convenient order
  • If there are multiple possibilities to separate the elements you may return any one of them
  • Outputting the complete list of all matches is not allowed
  • If the two points cannot be separated, you may output any value, as long as it cannot be mistaken for the output in a separable case
  • It is allowed to throw an exception to indicate the non-separable case
  • Your code should be able to handle sets with at least 31 distinct elements
  • This is the shortest solution (per language) wins

1 A set S of sets is a topology if:

  1. It contains the empty set and the set of all elements
  2. Any (finite) intersection of elements in S is an element of S
  3. Any union of elements in S is an element of S
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Suggest test cases: {{},{1,2,3},{1,3},{2,3},{3}} 1 2 (cannot satisfy condition 2) and {{},{1},{1,2}} 1 2 (can satisfy for p but not for q). \$\endgroup\$ Aug 9, 2023 at 12:26
  • \$\begingroup\$ Do we need to handle p==q? \$\endgroup\$
    – xnor
    Aug 9, 2023 at 20:44
  • 2
    \$\begingroup\$ Is it valid to output a list of all pairs? Some answers are doing that. \$\endgroup\$
    – xnor
    Aug 9, 2023 at 20:46
  • 2
    \$\begingroup\$ Can you consistently return an error for non-separable? \$\endgroup\$
    – Jonah
    Aug 10, 2023 at 1:43
  • \$\begingroup\$ @xnor p==q is excluded by the second rule \$\endgroup\$
    – bsoelch
    Aug 10, 2023 at 12:21

15 Answers 15

7
\$\begingroup\$

Python, 63 bytes

lambda l,*I:(O:=[min(l,key={c}.__xor__)for c in I])[0]&O[1]or O

Attempt This Online!

This expects a list of sets for the topology. The list shall be ordered by descending length as allowed per OP. (Actually, it suffices that the longest set comes first.)

How?

This depends on the specific implementation of min. It assumes that min works left to right and updates the current minimum whenever the next element is smaller than it. In particular, elements that cannot be compared to the current minimum are ignored. We use this to have min ignore exactly the subsets that contain c by starting off with the full set minus c. As this is the opposite of what we actually need we key min with ^{c}, so we can start with the full set and ignore all subsets not containing c.

Other than that it works like the other versions.

Python, 65 bytes

lambda l,*I:(O:=[min(l&{x|{c}for x in l})for c in I])[0]&O[1]or O

Attempt This Online!

This takes a set of frozensets for the topology.

Python, 66 bytes

lambda l,*I:(O:=[min(x for x in l if{c}&x)for c in I])[0]&O[1]or O

Attempt This Online!

Returns a disjoint pair of sets containing either point. Or a single set in case of failure.

Test harness stolen from @solid.py.

How?

Being a finite topology l contains the intersections of all sets containing p=I[0] and of all sets containing q=I[1]. We need only check these. To obtain the intersections we use the fact that they are minimal within the subset of subsets containing p (or q). Note that it does not matter that typically some subsets will not be comparable (both < and >= return False). For the min function to succeed it suffices that there is a minimum, i.e. one element that is comparable to and smaller than all the others.

\$\endgroup\$
5
\$\begingroup\$

R, 60 75 bytes

Edit: +15 bytes to fix bug

\(t,p,q){for(i in t)for(j in t)if(p%in%i&q%in%j&!any(i%in%j))F=list(i,j);F}

Attempt This Online!

Outputs a list of two separating sets, or FALSE if no separating sets can be found.

\$\endgroup\$
5
\$\begingroup\$

Python, 64 bytes

-8 bytes, -3 bytes and -2 bytes thanks to Value Ink, loopy walt and xnor respectively. Also, thanks to Neil and bsoelch for their suggestions.

Takes as input a list of sets, and returns a pair (tuples) of separated sets. In the not separable case it raises an exception.

lambda l,p,q:[(u,v)for u in l for v in l if{p}-u=={q}-v==u&v][0]

Attempt This Online!

\$\endgroup\$
7
  • 2
    \$\begingroup\$ (Also you can just write print(f(a,b,c) or 'not separable') in your test suite.) \$\endgroup\$
    – Neil
    Aug 9, 2023 at 18:35
  • 1
    \$\begingroup\$ if{p}-u|{q}-v|u&v==set() will also work, but you'll need to swap {} for set() in the test suite so it doesn't complain about the type mismatch between sets and dicts. \$\endgroup\$
    – Value Ink
    Aug 10, 2023 at 1:26
  • 1
    \$\begingroup\$ lambda l,p,q:[(u,v)for u in l for v in l if{p}-u|{q}-v|u&v<{0}] \$\endgroup\$
    – loopy walt
    Aug 10, 2023 at 10:25
  • 1
    \$\begingroup\$ ==set() can be replaced with <{0} saving three more bytes. A set is considered less than another only if it is a proper subset (so {0}<{0} is falsey and only set()<{0} will be truthy in this usage). \$\endgroup\$ Aug 10, 2023 at 11:08
  • 1
    \$\begingroup\$ Using exceptions it is possible in 66 bytes \$\endgroup\$
    – bsoelch
    Aug 10, 2023 at 17:59
4
\$\begingroup\$

05AB1E, 16 15 13 bytes

ãʒ`åyIδ嫘J₄-

Inputs in the order \$topology, [p,q]\$. Outputs all possible results, so an empty list for 'not separable'. (Although all given test cases have \$p<q\$, it'll also work if \$p>q\$.)

Try it online or verify all test cases.

Explanation:

ã         # Cartesian power of 2 to create all pairs of the first (implicit) input-list
          # of lists (including pairs of the same topology-sets)
 ʒ        # Filter this list of pairs of lists by:
  `å      #  Verify (the inverse of) rule 2:
  `       #   Pop and push both lists separated to the stack
   å      #   Check for each value in the second list whether it's in the first list
  yIδå    #  Verify (a portion of) rule 1:
  y       #   Push the current pair of lists again
   I      #   Push the second input-pair of integers
    δ     #   Pop both, and apply double-vectorized:
     å    #    Contains-check
  «˜J₄-   #  Combine the checks of the two rules:
  «       #   Merge the two lists together
   ˜J     #   Flatten and join it to a string
     ₄-   #   Subtract 1000, to verify whether the string is of the form "0...01001",
          #   where "0...0" comes from the check of rule 2
          #   and "1001" from the check of rule 1
          #   (only 1 is truthy in 05AB1E)
          # (after which the filtered list is output implicitly)
\$\endgroup\$
4
\$\begingroup\$

Ruby, 50 bytes

Returns nil if no pair exists.

->s,x,*y{s.product(s).find{[x]-_1|y-_2|_1&_2==[]}}

Attempt This Online!

->s,x,*y{                               # Anonymous lambda that takes three arguments
                                        #  (y is splatted to make it a one-element array)
         s.product(s)                   # Cartesian product of the topology against itself
          .find{                        # Find first pair that matches the following
                [x]-_1                  # Subtract elements of U (_1) from an array w/ only x
                                        #  (empty array if x is in U)
                      |y-_2             # intersect w/ subtraction of V (_2) from y
                                        #  (empty if y is in V)
                           |_1&_2       # intersect w/ union of U and V (empty if no overlap)
                                 ==[]   # If the intersection of these three is an empty array,
                                        #  the conditions have been met
                                     }  # End find call
                                      } # End lambda definition
\$\endgroup\$
2
  • \$\begingroup\$ You could pass both numbers as one-element arrays, avoid the splat and the un-splat for -3 bytes \$\endgroup\$
    – G B
    Aug 11, 2023 at 10:38
  • \$\begingroup\$ @GB Is that in the rules? I didn't see the option to input single-element sets for the target points within the rules. \$\endgroup\$
    – Value Ink
    Aug 11, 2023 at 17:10
2
\$\begingroup\$

Pyth, 13 bytes

f!+@FTs-VvzT*

Attempt This Online!

Returns a list of all possible separating pairs, [] if none exist.

Explanation

f!+@FTs-VvzT*QQ    # implicitly add QQ
                   # implicitly assign Q=eval(input()) z=input()
            *QQ    # cartesian product of Q and Q
f                  # filter on lambda T
       -VvzT       #   vectorize subtraction on eval(z) and T
      s            #   sum (empty set for valid pairs)
   @FT             #   fold T on intersection
  +                #   add (empty set for valid pairs)
 !                 #   not (true for empty set)
\$\endgroup\$
2
\$\begingroup\$

Retina, 99 bytes

~L$`(.)¶(.)$
,-5G`¶O$$`.$*($2).$*|.+¶$$1¶Lw$$m`^(.$*$1.$*)$$[\S\s]+^(.$*$2.$*)$$¶$$1,$$2¶A`(.).$*\1

Try it online! Uses strings as sets. Takes input on separate lines but test suite splits on commas for convenience. Outputs all possible results. Explanation: The program itself is only one stage, but works by generating a program to do the actual work and then using the ~ flag to run the resulting program. As an example, it generates the following code for the last test case:

,-5G`

Delete the two points leaving just the sets.

O$`.*(2).*|.+
$1

Sort the sets containing the second point to the end.

Lw$m`^(.*1.*)$[\S\s]+^(.*2.*)$
$1,$2

List most pairs of sets where the first set contains the first point and the second set contains the second point. (Some pairs where the first set contains both points are missed but they're not relevant anyway.)

A`(.).*\1

Delete pairs that have an element in common.

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

Factor + combinators.extras sets.extras, 77 bytes

Returns the first two separating sets found, or two f.

[| s x y | s s [| a b | a b disjoint? x a in? y b in? 3and ] cartesian-find ]

Attempt This Online!

  • [| s x y | ... ] A quotation (anonymous function) taking named inputs s (for the sets), x, and y.
  • s s [| a b | ... ] cartesian-find Find the first pair in s that is true when ... is run on it. Name the inputs (the two sets) to the quotation a and b.
  • a b disjoint? Is the intersection of a and b empty? (Leaves a boolean on the stack.)
  • x a in? Is x in a? (Leaves a boolean on the stack.)
  • y b in? Is y in b? (Leaves a boolean on the stack.)
  • 3and Take the logical and of three objects.
\$\endgroup\$
2
\$\begingroup\$

Jelly, 10 bytes

fƇⱮf/€Ṇf/¡

A dyadic Link that accepts the topology as a list of lists* on the left and the points as a list on the right and yields the smallest cardinality separating sets or 0 if no separating set is possible.

* Jelly has no sets.

Try it online! Or see the test-suite.

How?

fƇⱮf/€Ṇf/¡ - Link: Topology; Points
  Ɱ        - map across {Points} with:
 Ƈ         -   keep those Sets of {Topology} for which:
f          -     {Set} filter keep {Point}
     €     - for each of these two FilteredTopolgies:
    /      -   reduce by:
   f       -     filter keep
                   -> Intersection of the FilteredTopology
         ¡ - repeat...
        /  - ...times: reduce {Intersections} by:
       f   -             filter keep
                           N.B. [] is falsey so repeat zero times
                                other lists are truthy so repeat once
      Ṇ    - ...action: logical NOT
\$\endgroup\$
2
\$\begingroup\$

Haskell, 89 88 bytes

f t p q=head[x|x@[u,v]<-t#t,p%u&&q%v&&all(\[i,j]->i/=j)(u#v)];s#t=sequence[s,t];(%)=elem

Attempt This Online!

Note that head is redefined for testing purposes only. If you remove the header, function f returns the two open sets if they exists, otherwise throws the exception *** Exception: Prelude.head: empty list.

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

JavaScript (ES6), 79 bytes

-6 thanks to @l4m2

Expects (a,p,q) where a is a list of sets.

Returns either a pair of sets or [ undefined, undefined ].

(a,p,q)=>[a.find(U=>b=a.find(V=>U.has(p)&V.has(q)>[...V].some(v=>U.has(v)))),b]

Try it online!

Patiently waiting for new ECMAScript set methods ...

Commented

(a, p, q) => [         // a[] = list of sets, (p, q) = integers
  a.find(U =>          // look for some set U in a[]:
    b = a.find(V =>    //   and some other set V in a[], saved in b:
      U.has(p) &       //     such that p belongs to U,
      V.has(q) >       //     q belongs to V,
      [...V].some(v => //     and there's not any value v from V ...
        U.has(v)       //       ... that also belongs to U
      )                //     end of some()
    )                  //   end of inner find()
  ),                   // end of outer find()
  b                    // output the 2nd set
]                      // (if the 1st set is undefined, so is b)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 86 \$\endgroup\$
    – l4m2
    Aug 9, 2023 at 11:22
  • 1
    \$\begingroup\$ 79 \$\endgroup\$
    – l4m2
    Aug 10, 2023 at 8:19
1
\$\begingroup\$

Charcoal, 23 bytes

FθEΦθ∧№ιη∧№κζ⁼ι⁻ικ⭆¹⟦ικ

Try it online! Link is to verbose version of code. Uses lists as sets. Outputs all possible results. Explanation:

 θ                      List of lists
F                       Loop over elements
    θ                   List of lists
   Φ                    Filtered where
       ι                Outer list
      №                 Contains
        η               First point
     ∧                  Logical And
           κ            Inner list
          №             Contains
            ζ           Second point
         ∧              Logical And
              ι         First list
             ⁼          Equals
                ι       First list
               ⁻        Removing elements in
                 κ      Second list
  E                     Map over results
                  ⭆¹⟦ικ Pretty-print both lists
\$\endgroup\$
1
\$\begingroup\$

Scala 3, 89 bytes

(l,p,q)=>for{u<-l;v<-l;if u.contains(p)&&v.contains(q)&&u.intersect(v).isEmpty}yield(u,v)

Attempt This Online!

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

Arturo, 65 bytes

$[s m n][loop s'a->loop s'b->if∧∧a<>a--m b<>b--n a=a--b[a b]]

Try it!

Returns every valid pair.

$[s m n][           ; a function taking three arguments (s is sets)
    loop s'a->      ; loop over s, assign current elt to a
        loop s'b->  ; loop over s, assign current elt to b
            if∧∧    ; if the following 3 statements are true...
            a<>a--m ; m is in a
            b<>b--n ; n is in b
            a=a--b  ; a intersect b is empty
            [a b]   ; then return a and b
]                   ; end function
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 86 bytes

sub{($s,$p,$q)=@_;map{$u=$_;map[$u,$_],grep$p~~@$u&$q~~@$_&!(grep$_~~@$u,@$_),@$s}@$s}

Try it online!

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