5
\$\begingroup\$

Challenge

Premise

Euler diagrams consist of simple closed shapes in a 2-D plane that each depict a set or category. How or whether these shapes overlap demonstrates the relationships between the sets.

I'm a spoilt brat who thinks Euler diagrams are hard to draw. For any Euler diagram, I want to know the minimum number of points where the perimeters of two shapes intersect. Here's an example:

foo, bar outside foo, baz in foo, qux in baz, qux in fooNOTbaz, qux in bar

The Euler diagram drawn above represents a relationship where:

  • foo and bar are disjoint.
  • All baz are foo but not vice versa.
  • Some qux are baz; some qux are foo but not baz; and some qux are bar.
  • Not all baz are qux; not all non-baz foo are qux; and not all bar are qux.

In this particular example you can't do better than a whopping six crossings, but that's life.

Task

Input: a sequence of multiple integers as follows.

  • An integer, say \$A\$, which designates a set.
  • An integer, say \$m\$. This means 'the set designated by \$A\$ is a proper subset of the following \$m\$ sets'.*
  • \$m\$ integers (except if \$m=0\$), each designating a set.
  • An integer, say \$n\$. This means 'the set designated by \$A\$ is equivalent to the following \$n\$ sets'.*
  • \$n\$ integers (except if \$n=0\$), each designating a set.
  • An integer, say \$p\$. This means 'the set designated by \$A\$ is a proper superset of the following \$p\$ sets'.*
  • \$p\$ integers (except if \$p=0\$), each designating a set.*
  • An integer, say \$q\$. This means 'the set designated by \$A\$ contains part but not all of each of the following \$q\$ sets'.*
  • \$q\$ integers (except if \$q=0\$), each designating a set.
  • Repeat the above until the whole system is defined.

The input format isn't fixed. The Python dict or JS object, for example, would be just as good - in such cases, the starred (*) lines wouldn't be so necessary.

Please note that the input is guaranteed not to produce 'exclaves' (as in this image, namely 'Centaurs').

Output: the minimum number of crossings, of the perimeters of two shapes, in the Euler diagram.

Example 1

Input, with bracketed remarks for your benefit:

1 (Consider the set designated by 1.)
0   (It's not a proper subset of anything.)
0   (It's equivalent to no other set.)
1   (It's a proper superset of:)
3     (the set designated by 3.)
1   (It; the set designated by 1; contains part but not all of:)
4     (the set designated by 4.)
2 (Consider the set designated by 2.)
0   (It's not a proper subset of anything.)
0   (It's equivalent to no other set.)
0   (It's not a proper superset of anything.)
1   (It contains part but not all of:)
4     (the set designated by 4.)
3 (Consider the set designated by 3.)
1   (It's a proper subset of:)
1     (the set designated by 1.)
0   (It; the set designated by 3; is equivalent to no other set.)
0   (It's not a proper superset of anything.)
1   (It contains part but not all of:)
4     (the set designated by 4.)
4 (Consider the set designated by 4.)
0   (It's not a proper subset of anything.)
0   (It's equivalent to no other set.)
0   (It's not a proper superset of anything.)
3   (It contains part but not all of:)
1     (the set designated by 1,)
2     (the set designated by 2 and)
3     (the set designated by 3.)

Output: 6

This example exactly matches the one in the section 'Premise' (set 1 would be foo, 2 bar, 3 baz, 4 qux).

Suppose we want to have the input be like a JS object instead. A possibility is:

{
 1:[[],[],[3],[4]],
 2:[[],[],[],[4]],
 3:[[1],[],[],[4]],
 4:[[],[],[],[1,2,3]]
}

Example 2

Input: 1 0 0 1 2 1 3 2 1 1 0 0 1 3 3 0 0 0 2 1 2

Output: 4

Please see here.

Suppose we want to have the input be like a JS object instead. A possibility is:

{
 1:[[],[],[2],[3]],
 2:[[1],[],[],[3]],
 3:[[],[],[],[1,2]]
}

Remarks

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Q: You didn't say how to find the answer. How do I do it? A: Carefully. \$\endgroup\$ Apr 26 '20 at 8:17
  • 1
    \$\begingroup\$ Q: You didn't say how to find the answer. How do I do it? A: By yourself. \$\endgroup\$
    – user92069
    Apr 26 '20 at 8:29
  • 6
    \$\begingroup\$ Interesting problem! 1) Please consider relaxing the input format (e.g I might want to use a dictionary, where each set number is mapped with 4 lists of numbers). 2) More test cases would be greatly appreciated, especially in this problem where the algorithm is not obvious. \$\endgroup\$ Apr 26 '20 at 9:02
  • \$\begingroup\$ @SurculoseSputum Hope the latest edit (2020-04-26T09:34Z) helps. \$\endgroup\$ Apr 26 '20 at 9:36
  • 4
    \$\begingroup\$ @RGS The main difference between Venn and Euler diagrams is that a Venn diagram shows all possible logical relationships between sets, whilst an Euler diagram only shows existing relationships. denis1251.blogspot.com/2016/06/… \$\endgroup\$ Apr 26 '20 at 11:04
1
\$\begingroup\$

MATLAB - 109 Bytes

Try it online

function n=E(s)
i=2;k=1;n=0;while i<numel(s)
k=mod(k,4)+1;n=n+s(i)*((k==1)-(k==3)/2);i=i+s(i)+1+(k<2);end

ungolfed:

function n=E(s)             % function def, input 2 and output n
i=2;                        % sequence index
k=1;                        % 1=sub,2=equivalent,3=super,4=part
n=0;                        % initialized output
while i<numel(s)            % Loop through sequence
k=mod(k,4)+1;               % if k==4, then a new set has started, so back to 1.
n=n+s(i)*((k==1)-(k==3)/2); % s(i) represents n,m,p,q  
                            % If k==1, then s(i)=q, so add s(i) to n. 
                            % If k==3, s(i)=m, so subtract s(i)/2 from n.  
i=i+s(i)+1+(k<2);           % Advance index by (n,m,p,q) and 1 if k==1 (aka k<2) to skip set number definition. 
end                         % end

Explanation:

This may be a naive approach, but from what I see, the only way to have a perimter intersection is when you have a set as a part of another.

For super/subsets, there will be no perimeter intersections, since they will be concentric.

For sets that match exactly, there will only be one shape that represents two sets, so there are no perimeter crossings between them.

Therefore, the only time you can have an overlap is for parts. From there it is simple: every crossing includes two points, since by the nature of overlapping rectangles, there will be two and only two intersections of the perimeters. And since the sets that contain parts of another must reference each other (i.e. if set 1 and 2 overlap, set 1 will have 2 in its part input, and 2 will have 1), there will be 2*(number of sets that are part of another). However, sets that are exactly equal only produce one shape, so any crossings between this shape and another must be reduced according to the number of sets that are equivalent. Thus, the sum of the number of elements that fall into the "parts" category across all sets equals the number intersections.

Mathematically,

For \$k\$ sets

\$ n_{crossings} = \displaystyle \sum_{i=1}^k(q_i - m_i/2) \$

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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