title: Golf the smallest sphere!

text:
# Question
Title: Golf the smallest sphere!
*Inspired by this challenge, as well as a problem I've been working on*

## **Problem:**

Given a non-empty set of points in `3D` space, find the diameter of the smallest sphere that encloses them all. The problem is trivial if the number of points is three or fewer so, for the sake of this challenge, the number of points shall be greater than three.

**Input:** A list of 4 or more points, such that no three points are colinear and no four points are coplanar. Coordinates must be floats, and it is possible that two or more points may share a coordinate, although no two points will be the same.

**Output:** The diameter of the set (the diameter of the smallest sphere that encloses all points in the set), as a float. As has been pointed out, this is *not* necessarily the same as the largest distance between any two points in the set.

## Rules:

1. You may assume that the points are not colinear.
2. The smallest program (in bytes) wins. Please include the language used, and the length in bytes as a header in the first line of your answer.

## Example I/O:

**Input:**

```
 [[4, 3, 6], [0, 2, 4], [3, 0, 4], [0, 9, 1]]

```

**Output:** `9.9498743710662`

---

**Input:**

```
 [[8, 6, 9], [2, 4, 5], [5, 5, 4], [5, 1, 6]]

```

**Output:** `7.524876236605994`

# Answer
> 20 votes
# Wolfram Language (Mathematica), 26 bytes

```
2#2&@@CircumscribedBall@#&

```

Version 13.3 introduced `CircumscribedBall`.

---

For versions 13.2 and below,

## Wolfram Language (Mathematica), 33 bytes

```
2#2&@@#~BoundingRegion~"MinBall"&

```

Try it online!

Nearly exactly the same as the Mathematica answer to the 2D version. Works for input points of any dimension.

# Answer
> 3 votes
# Python 3, 80 bytes

```
lambda l:2*m.get_bounding_ball(numpy.array(l))[1]**.5
import numpy,miniball as m

```

Try it online! (can't get it to work on TIO - no PyPI `miniball` module and won't let me install it through code - but works fine on my laptop)

Uses PyPI's miniball module and works in any dimension.

Inputs a list of floating-point points (at least one coordinate of one point must be a float - i.e. have a decimal point - or `numpy` gets upset) and returns the diameter of the smallest enclosing circumsphere.

## How?

PyPI's module `miniball`'s function `get_bounding_ball` takes a `numpy` `ndarray` as the input points (with optional parameter `epsilon` which defaults to `1e-07`) and returns the centre and the squared radius of the circumsphere as a tuple. We return double the square-root of the second element which is the diameter of the circumsphere.

# Answer
> 0 votes
# MATLAB/Octave, ~~3931~~ 1898 bytes

The MathWorks File Exchange often has user-submitted functions for tasks like this. One function that could work is `minboundsphere`. You can access the function here.

\\$ 3391 \text{bytes} \rightarrow 1898 \text{bytes} \\$ thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

```
function[c,r]=f(x)
if(n=size(x,1))<5
[c,r]=E(x);
else
l=10*eps*max(max(y=abs(x),[],1)-min(y,[],1));
c=inf(1,3);
r=inf;
if n>15
for i=1:250
a=randperm(n);
I=a(5:n);
for y=0:11
[C,R]=E(x(a(1:4),:));
[Q,k]=max(sqrt(sum((x(I,:)-repmat(C,n-4,1)).^2,2)));
if Q-R>l
[b,q]=E(x([a(2:4),I(k)],:));
if norm(b-x(a(1),:))>q
[b,q]=E(x([a([1 3 4]),I(k)],:));
if norm(b-x(a(2),:))>q
[b,q]=E(x([a([1 2 4]),I(k)],:));
if norm(b-x(a(3),:))>q
[b,q]=E(x([a(1:3),I(k)],:));
if norm(b-x(a(4),:))>q
l+=l;
else
C=b;
R=q;
w=a(4);
a=[I(k),a(1:3)];
I(k)=w;
end
else
C=b;
R=q;
w=a(3);
a=[I(k),a([1 2 4])];
I(k)=w;
end
else
C=b;
R=q;
w=a(2);
a=[I(k),a([1 3 4])];
I(k)=w;
end
else
C=b;
R=q;
w=a(1);
a=[I(k),a(2:4)];
I(k)=w;
end
else
break
end
end
if R<r
c=C;
r=R;
end
end
else
for i=1:size(A=nchoosek(1:n,4),1)
[C,R]=E(x(a=A(i,:),:));
[Q,k]=max(sqrt(sum((x(I=setdiff(1:n,a),:)-repmat(C,n-4,1)).^2,2)));
if Q-R<=l&R<r
c=C;
r=R;
end
end
end
end
end
function[c,r]=E(x)
u=inline('(A(:,z=[1 1 1 1])-A(:,z)'').^2','A');
D=sqrt(u(x(:,1))+u(x(:,2))+u(x(:,3)));
[d,i]=max(D(:));
[i,j]=ind2sub([4 4],i);
o=setdiff(1:4,[i,j]);
r=d/2;
c=(x(i,:)+x(j,:))/2;
if norm(c-x(o(1),:))>r|norm(c-x(o(2),:))>r
[c,r,n]=N(x(d=1:3,:),x(4,:),D(d,d));
if~n
[c,r,n]=N(x(d=[1 2 4],:),x(3,:),D(d,d));
if~n
[c,r,n]=N(x(d=[1 3 4],:),x(2,:),D(d,d));
if~n
[c,r,n]=N(x(d=2:4,:),x(1,:),D(d,d));
if~n
c=(2*(x(2:4,:)-repmat(x(1,:),3,1))\sum(x(2:4,:).^2-repmat(x(1,:).^2,3,1),2))';
r=norm(c-x(1,:));
end
end
end
end
end
end
function[c,r,n]=N(x,T,D)
if D(1,2)>=max(D(1,3),D(2,3))
c=mean(x(1:2,:),1);
r=D(1,2)/2;
n=norm(x(3,:)-c)<=r&norm(T-c)<=r;
elseif D(1,3)>=max(D(1,2),D(2,3))
c=mean(x([1 3],:),1);
r=D(1,3)/2;
n=norm(x(2,:)-c)<=r&norm(T-c)<=r;
elseif D(2,3)>=max(D(1,2),D(1,3))
c=mean(x(2:3,:),1);
r=D(2,3)/2;
n=norm(x(1,:)-c)<=r&norm(T-c)<=r;
end
if~n
t=x(2:3,:)-[z=x(1,:);z];
t*=o=orth(t');
c=(2*t\sum(t.^2,2))';
r=norm(c-t(1,:));
c=c*o'+z;
n=norm(T-c)<=r;
end
end

```

Ungolfed version. Try it online!

```
function [center,radius,isin] = enc3_4(xyz,xyztest,Di)
% minimum radius enclosing sphere for exactly 3 points in R^3
%
% xyz - a 3x3 array, with each row as a point in R^3
%
% xyztest - 1x3 vector, a point to be tested if it is
%       inside the generated enclosing sphere.
%
% Di - 3x3 array of interpoint distances

% test the farthest pair of points. do they form a diameter
% of the sphere?
if Di(1,2)>=max(Di(1,3),Di(2,3))
  center = mean(xyz([1 2],:),1);
  radius = Di(1,2)/2;
  isin = (norm(xyz(3,:) - center)<=radius) && (norm(xyztest - center)<=radius);
elseif Di(1,3)>=max(Di(1,2),Di(2,3))
  center = mean(xyz([1 3],:),1);
  radius = Di(1,3)/2;
  isin = (norm(xyz(2,:) - center)<=radius) && (norm(xyztest - center)<=radius);
elseif Di(2,3)>=max(Di(1,2),Di(1,3))
  center = mean(xyz([2 3],:),1);
  radius = Di(2,3)/2;
  isin = (norm(xyz(1,:) - center)<=radius) && (norm(xyztest - center)<=radius);
end
if isin
  % we found the minimal enclosing sphere already
  return
end

% If we drop down to here, no singularities should
% happen (I've already caught any degeneracies.)

% We transform the three points into a plane, then
% compute the enclosing sphere in that plane.

% translate to the origin
xyz0 = xyz(1,:);
xyzt = xyz(2:3,:) - [xyz0;xyz0];

rot = orth(xyzt');

% uv is composed of 2 points, in 2-d, plus we
% have the origin (after the translation)
uv = xyzt*rot;

A = 2*uv;
rhs = sum(uv.^2,2);
center = (A\rhs)';
radius = norm(center - uv(1,:));

% rotate and translate back
center = center*rot' + xyz0;

% test if the 4th point is enclosed also
isin = (norm(xyztest - center)<=radius);
end

function [center,radius] = enc4(xyz)
% minimum radius enclosing sphere for exactly 4 points in R^3
%
% xyz is a 4x3 array
%
% Note that enc4 will attempt to pass a sphere through all
% 4 of the supplied points. When the set of points proves to
% be degenerate, perhaps because of collinearity of 3 or
% more of the points, or because the 4 points are coplanar,
% then the sphere would nominally have infinite radius. Since
% there must be a finite radius sphere to enclose any set of
% finite valued points, enc4 will provide that sphere instead.
%
% In addition, there are some non-degenerate sets of points
% for which the circum-sphere is not minimal. enc4 will always
% try to find the minimum radius enclosing sphere.

% interpoint distance matrix D
% dfun = @(A) (A(:,[1 1 1 1]) - A(:,[1 1 1 1])').^2;
dfun = inline('(A(:,[1 1 1 1]) - A(:,[1 1 1 1])'').^2','A');
D = sqrt(dfun(xyz(:,1)) + dfun(xyz(:,2)) + dfun(xyz(:,3)));

% Find the most distant pair. Test if their circum-sphere
% also encloses the other points. If it does, then we are
% done.
[dij,ij] = max(D(:));
[i,j] = ind2sub([4 4],ij);
others = setdiff(1:4,[i,j]);
radius = dij/2;
center = (xyz(i,:) + xyz(j,:))/2;
if (norm(center - xyz(others(1),:))<=radius) && ...
   (norm(center - xyz(others(2),:))<=radius)
  % we can stop here.
  return
end

% next, we need to test each triplet of points, finding their
% enclosing sphere. If the 4th point is also inside, then we
% are done.
ind = 1:3;
[center,radius,isin] = enc3_4(xyz(ind,:),xyz(4,:),D(ind,ind));
if isin
  % the 4th point was inside this enclosing sphere.
  return
end

ind = [1 2 4];
[center,radius,isin] = enc3_4(xyz(ind,:),xyz(3,:),D(ind,ind));
if isin
  % the 3rd point was inside this enclosing sphere.
  return
end

ind = [1 3 4];
[center,radius,isin] = enc3_4(xyz(ind,:),xyz(2,:),D(ind,ind));
if isin
  % the second point was inside this enclosing sphere.
  return
end

ind = [2 3 4];
[center,radius,isin] = enc3_4(xyz(ind,:),xyz(1,:),D(ind,ind));
if isin
  % the first point was inside this enclosing sphere.
  return
end

% find the circum-sphere that passes through all 4 points
% since we have passed all the other tests, we need not
% worry here about singularities in the system of
% equations.
A = 2*(xyz(2:4,:)-repmat(xyz(1,:),3,1));
rhs = sum(xyz(2:4,:).^2 - repmat(xyz(1,:).^2,3,1),2);
center = (A\rhs)';
radius = norm(center - xyz(1,:));
end

function [center,radius] = minboundsphere(xyz)
% minboundsphere: Compute the minimum radius enclosing sphere of a set of (x,y,z) triplets
% usage: [center,radius] = minboundsphere(xyz)
%
% arguments: (input)
%  xyz - nx3 array of (x,y,z) triples, describing points in R^3
%        as rows of this array.
%
%
% arguments: (output)
%  center - 1x3 vector, contains the (x,y,z) coordinates of
%        the center of the minimum radius enclosing sphere
%
%  radius - scalar - denotes the radius of the minimum
%        enclosing sphere
%
%
% Example usage:
% Sample uniformly from the interior of a unit sphere.
% As the sample size increases, the enclosing sphere
% should asymptotically approach center = [0 0 0], and
% radius = 1.
%
%   xyz = rand(10000,3)*2-1;
%   r = sqrt(sum(xyz.^2,2));
%   xyz(r>1,:) = [];          % 5156 points retained
%   tic,[center,radius] = minboundsphere(xyz);toc
%
%   Elapsed time is 0.199467 seconds.
%
%   center = [0.00017275   8.5006e-05   0.00012015]
%
%   radius = 0.9999
%
% Example usage:
% Sample from the surface of a unit sphere. Within eps
% or so, the result should be center = [0 0 0], and radius = 1.
%
%   xyz = randn(10000,3);
%   xyz = xyz./repmat(sqrt(sum(xyz.^2,2)),1,3);
%   tic,[center,radius] = minboundsphere(xyz);toc
%
%   Elapsed time is 0.614762 seconds.
%
%   center =
%      4.6127e-17  -2.5584e-17   7.2711e-17
%
%   radius =
%       1
%
%
% See also: minboundrect, minboundcircle
%
%
% Author: John D'Errico
% E-mail: woodchips@rochester.rr.com
% Release: 1.0
% Release date: 1/23/07

% not many error checks to worry about
sxyz = size(xyz);
if (length(sxyz)~=2) || (sxyz(2)~=3)
  error 'xyz must be an nx3 array of points'
end
n = sxyz(1);

% start out with the convex hull of the points to
% reduce the problem dramatically. Note that any
% points in the interior of the convex hull are
% never needed.
if n>4
  tri = convhulln(xyz);

  % list of the unique points on the convex hull itself
  hlist = unique(tri(:));

  % exclude those points inside the hull as not relevant
  xyz = xyz(hlist,:);

end

% now we must find the enclosing sphere of those that
% remain.
n = size(xyz,1);

% special case small numbers of points. If we trip any
% of these cases, then we are done, so return.
switch n
  case 0
    % empty begets empty
    center = [];
    radius = [];
    return
  case 1
    % with one point, the center has radius zero
    center = xyz;
    radius = 0;
    return
  case 2
    % only two points. center is at the midpoint
    center = mean(xyz,1);
    radius = norm(xyz(1,:) - center);
    return
  case 3
    % exactly 3 points. For this odd case, just use enc4,
    % appending a new point at the centroid. This is simpler
    % than other solutions that would have reduced the
    % problem to 2-d. enc4 will do that anyway.
    [center,radius] = enc4([xyz;mean(xyz,1)]);
    return
  case 4
    % exactly 4 points
    [center,radius] = enc4(xyz);
    return
end

% pick a tolerance
tol = 10*eps*max(max(abs(xyz),[],1) - min(abs(xyz),[],1));

% more than 4 points. for no more than 15 points in the hull,
% just do an exhaustive search.
if n <= 15
  % for 15 points, there are only nchoosek(15,4) = 1365
  % sets to look through. this is only about a second.
  asets = nchoosek(1:n,4);

  center = inf(1,3);
  radius = inf;
  for i = 1:size(asets,1)
    aset = asets(i,:);
    iset = setdiff(1:n,aset);

    % get the enclosing sphere for the current set
    [centeri,radiusi] = enc4(xyz(aset,:));

    % are all the inactive set points inside the circle?
    ri = sqrt(sum((xyz(iset,:) - repmat(centeri,n-4,1)).^2,2));

    [rmax,k] = max(ri);
    if ((rmax - radiusi) <= tol) && (radiusi < radius)
      center = centeri;
      radius = radiusi;
    end
  end

else
  % Use an active set strategy, on many different
  % random starting sets.
  center = inf(1,3);
  radius = inf;

  for i = 1:250
    aset = randperm(n); % a random start, but quite adequate
    iset = aset(5:n);
    aset = aset(1:4);

    flag = true;
    iter = 0;
    centeri = inf(1,3);
    radiusi = inf;
    while flag && (iter < 12)
      iter = iter + 1;

      % get the enclosing sphere for the current set
      [centeri,radiusi] = enc4(xyz(aset,:));

      % are all the inactive set points inside the circle?
      ri = sqrt(sum((xyz(iset,:) - repmat(centeri,n-4,1)).^2,2));

      [rmax,k] = max(ri);
      if (rmax - radiusi) <= tol
        % the active set enclosing sphere also enclosed
        % all of the inactive points. We are done.
        flag = false;
      else
        % it must be true that we can replace one member of aset
        % with iset(k). That k'th element was farthest out, so
        % it seems best (a greedy algorithm) to swap it in. The
        % problem with the greedy algorithm, is it gets trapped
        % in a cycle at times. but since we are restarting the
        % algorithm multiple times, this will work.
        s1 = [aset([2 3 4]),iset(k)];
        [c1,r1] = enc4(xyz(s1,:));
        if (norm(c1 - xyz(aset(1),:)) <= r1)
          centeri = c1;
          radiusi = r1;

          % update the active/inactive sets
          swap = aset(1);
          aset = [iset(k),aset([2 3 4])];
          iset(k) = swap;

          % bounce out to the while loop
          continue
        end
        s1 = [aset([1 3 4]),iset(k)];
        [c1,r1] = enc4(xyz(s1,:));
        if (norm(c1 - xyz(aset(2),:)) <= r1)
          centeri = c1;
          radiusi = r1;

          % update the active/inactive sets
          swap = aset(2);
          aset = [iset(k),aset([1 3 4])];
          iset(k) = swap;

          % bounce out to the while loop
          continue
        end
        s1 = [aset([1 2 4]),iset(k)];
        [c1,r1] = enc4(xyz(s1,:));
        if (norm(c1 - xyz(aset(3),:)) <= r1)
          centeri = c1;
          radiusi = r1;

          % update the active/inactive sets
          swap = aset(3);
          aset = [iset(k),aset([1 2 4])];
          iset(k) = swap;

          % bounce out to the while loop
          continue
        end
        s1 = [aset([1 2 3]),iset(k)];
        [c1,r1] = enc4(xyz(s1,:));
        if (norm(c1 - xyz(aset(4),:)) <= r1)
          centeri = c1;
          radiusi = r1;

          % update the active/inactive sets
          swap = aset(4);
          aset = [iset(k),aset([1 2 3])];
          iset(k) = swap;

          % bounce out to the while loop
          continue
        end

        % if we get through to this point, then something went wrong.
        % Active set problem. Increase tol, then try again.
        tol = 2*tol;

      end
    end

    % have we improved over the best set so far?
    if radiusi < radius
      center = centeri;
      radius = radiusi;
    end
  end
end

end

```

---
Tags: code-golf, math, geometry
---


# Question
Title: Triangular battleships (A computational geometry problem)
You are the captain of a battleship. The engineering department's been cutting corners with designs this year, so the ship you're on takes the shape of a simple triangle.

You walk out onto the deck and enjoy the sea breeze... though not for long. An enemy has fired at you! — but will the shot hit?

## Input

You may write either a function or a full program for this challenge.

Your program will take in 11 integers, ten of which are paired:

* The first three pairs of integers (x1, y1), (x2, y2), (x3, y3) will specify the vertices of your ship. The triangle formed will have nonzero area.
* The next pair of integers (ex, ey) specifies the location of the enemy's cannon. The enemy cannon will never lie on, or within the boundary of your ship.\*
* The pair (ax, ay) after that specifies where the enemy aimed at. This will be distinct from (ex, ey).
* The final positive integer R specifies the range of the enemy's shot

\*You'd be a terrible captain if you didn't even notice that happening!

## Output

You must print/return a truthy value (e.g. true, 1) if the battleship will be hit, otherwise a falsy value (e.g. false, 0).

## What is a hit?

The enemy shot is a straight line segment of length R from (ex, ey) in the direction of (ax, ay). If this line segment overlaps any part of the *interior* of your triangular battleship, then this counts as a hit. Otherwise it is not a hit.

Shots which graze along or only reach up to the boundary of the triangle do not count as a hit.

## Examples

```
0 0 0 1 1 0
1 1
0 0
2

```

**Hit:** The enemy has shot right through the centre of your ship!

---

```
2 0 0 2 4 4
0 0
1 1
1

```

**No hit:** The enemy's range is too short, so you are safe.

---

```
0 0 1 2 3 0
-4 0
0 0
8

```

**No hit:** The enemy has grazed the side of your ship, so this does not count as a hit. Lucky!

---

```
0 0 -1 3 4 -1
-3 -4
3 4
5

```

**No hit:** The enemy shot just stops short of the ship, so you are safe. If the enemy's cannon had even slightly better range, then you would have been hit! Phew!

---

```
-2 -3 -3 6 7 -2
-6 2
1 -4
7

```

**Hit:** Even though the shot didn't penetrate to the other side, this is still a hit.

---

```
-3 2 2 -4 7 -3
-3 -4
-3 0
10

```

**No hit:** For the record, this is another close miss.

---

## Additional test cases

```
0 0 6 0 6 8
-6 -8
6 8
20

```

**No hit:** This is another graze, but at an angle.

---

```
0 0 -2 -5 5 3
-3 4
0 0
6

```

**Hit:** The shot entered via a vertex of the ship.

## Scoring

This is , so the shortest code in bytes wins. Standard loopholes apply.

# Answer
# Python 3, 252 bytes

This is certainly the most variables I've ever used in code golf. :^P

```
from math import*;A=atan2
def h(a,b,c,d,e,f,g,h,i,j,R):
 r=R;_=0
 while r>0:Q=A(j-h,i-g);k,l=g+r*cos(Q),h+r*sin(Q);D=A(d-b,c-a);E=A(f-b,e-a);F=A(l-b,k-a);G=A(b-d,a-c);H=A(f-d,e-c);I=A(l-d,k-c);_=_ or(D<F<E or E<F<D)and(G<I<H or H<I<G);r-=.001
 return _

```

Slightly ungolfed, with comments:

```
from math import*
# Parameters:
#  (a,b) (c,d) (e,f) - vertices of the triangle
#  (g,h) - location of cannon
#  (i,j) - aim of cannon
#  R - range of cannon
# Variables within function:
#  _ - was this shot a hit?
#  r - distance 0 < r <= R that we're testing
#  Q - angle between cannon source and destination
#  (k,l) - point that we're testing
#  D,E,F - angles between point 1 and 2,3,test
#  G,H,I - angles between point 2 and 1,3,test
def h(a,b,c,d,e,f,g,h,i,j,R):
    r=R;_=0
    while r>0:
        Q=atan2(j-h,i-g)
        k,l=g+r*cos(Q),h+r*sin(Q)
        D=atan2(d-b,c-a)
        E=atan2(f-b,e-a)
        F=atan2(l-b,k-a)
        G=atan2(b-d,a-c)
        H=atan2(f-d,e-c)
        I=atan2(l-d,k-c)
        _=_ or(D<F<E or E<F<D)and(G<I<H or H<I<G)
        r-=.001
    return _

```

**How it works:**

* Calculate the endpoint of the shot.
* Test lots of points along the line from the endpoint to the cannon's location:
    + Calculate angles from vertex 1 to other two vertices and to test point;
    + Calculate angles from vertex 2 to other two vertices and to test point;
    + If the test point angle is between the other two angles, in both cases, then the test point is within the triangle and the ship has been hit.

**Sample runs:**

```
>>> h(0,0,0,1,1,0,1,1,0,0,2)
True
>>> h(0,0,1,2,3,0,-4,0,0,0,8)
False
>>> h(0,0,-1,3,4,-1,-3,-4,3,4,5)
False
>>> h(-2,-3,-3,6,7,-2,-6,2,1,-4,7)
True

```
> 3 votes

# Answer
# Python 2.7, 235 bytes

```
from numpy import*
X=cross
h=lambda q,w,a,s,y,x,c,v,d,f,r:max([(X([a-q,s-w],[c+k*(d-c)-q,v+k*(f-v)-w])>0)==(X([y-a,x-s],[c+k*(d-c)-a,v+k*(f-v)-s])>0)==(X([q-y,w-x],[c+k*(d-c)-y,v+k*(f-v)-x])>0)for k in arange(0,r/hypot(d-c,f-v),1e-4)])

```

Computes the cross product `AB x AP` between the corners A,B and the point P. If all three have the same sign, then the point is inside the triangle.

Ungolfed:

```
from numpy import *
def i(q,w,a,s,y,x,e,r): # helper-function, checks whether ER is inside the triangle QW-AS-YX
  t=cross([a-q,s-w],[e-q,r-w])>0
  g=cross([y-a,x-s],[e-a,r-s])>0
  b=cross([q-y,w-x],[e-y,r-x])>0
  return t==g==b

def h(q,w,a,s,y,x,c,v,d,f,r):
  R=arange(0,r/hypot(d-c,f-v),1e-3)
  return max([i(q,w,a,s,y,x,c+k*(d-c),v+k*(f-v)) for k in R])

```

Tests:

```
In : h(0,0,0,1,1,0,1,1,0,0,2)
Out: True

In : h(-3,2,2,-4,7,-3,-3,-4,-3,0,10)
Out: False

In : h(0,0,1,2,3,0,-4,0,0,0,8)
Out: True
     Grazes may count as hits...
In : h(1,2,0,0,3,0,-4,0,0,0,8)
Out: False
     ...or not, depending on the order of edges

```
> 2 votes

# Answer
# C, 247 bytes

Definitely not quite golfed yet.

```
#include<math.h>
int z(float*k){float s=1e-3,t=s,p=k[8]-k[6],q=k[9]-k[7],r=k[10]/hypot(p,q);int w=0;for(;t<1;t+=s){float x=k[6]-k[0]+p*r*t,y=k[7]-k[1]+q*r*t,b=k[2]*k[5]-k[3]*k[4],d=(x*k[5]-y*k[4])/b,e=(x*k[3]-y*k[2])/b;w|=d>0&e<0&d-e<1;}return w;}

```

Currently this uses an approach similar to DLosc's solution, i.e. iterates through all possible coordinates on the line segment to determine if it intersects with the triangle. (So it will fail if the range is over 1000) However, it uses the formula from http://mathworld.wolfram.com/TriangleInterior.html to determine if a point is inside the triangle. This avoids a bunch of trigonometric functions.

---

Example check, should print `1 0 0 0 1 0`.

```
#include <stdio.h>
int main() {
    {
        float arr[] = {0,0,0,1,1,0,1,1,0,0,2};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {2,0,0,2,4,4,0,0,1,1,1};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {0,0,1,2,3,0,-4,0,0,0,8};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {0,0,-1,3,4,-1,-3,-4,3,4,5};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {-2,-3,-3,6,7,-2,-6,2,1,-4,7};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {-3,2,2,-4,7,-3,-3,-4,-3,0,10};
        printf("%d\n", z(arr));
    }
}

```
> 1 votes

# Answer
# JavaScript (ES6) 320 ~~448 522 627~~

(Could still be golfed more?)

Steps:

1. Find the actual hit target (point at distance r on the line from enemy to aim)
2. Hit: if the segment from enemy to target intersect any of the sides of the ship, but not at the endpoints
3. Hit too: if the target is inside the ship - even if the shot entered at a vertex - test case 8

Ref:
Segment intersection
Point inside triangle
Point in a segment given a distance

*Test in Firefox*

```
C=(i,j,k,l,m,n,g,h,a,b,r,
  d=a-g,e=b-h,f=r/Math.sqrt(d*d+e*e),
  p=g+f*d,q=h+f*e,
  z=j*(m-k)+i*(l-n)+k*n-l*m,
  s=(j*m-i*n+(n-j)*p+(i-m)*q)/z,
  t=(i*l-j*k+(j-l)*p+(k-i)*q)/z,
  S=(i,j,k,l,
     a=k-i,b=l-j,c=p-g,d=q-h,e=i-g,f=j-h,
     s=a*f-b*e,t=c*f-d*e,m=a*d-c*b)=>
     m&&((s/=m)>0&s<1&(t/=m)>0&t<1)
)=>s>0&t>0&s+t<1|S(i,j,k,l)|S(i,j,m,n)|S(m,n,k,l)

// Test
MyOutput.innerHTML = ['Test1', C(0,0, 0,1, 1,0, 1,1, 0,0, 2),
'<br>Test2', C(2,0, 0,2, 4,4, 0,0, 1,1, 1),
'<br>Test3', C(0,0, 1,2, 3,0, -4,0, 0,0, 8),
'<br>Test4', C(0,0, -1,3, 4,-1, -3,-4, 3,4, 5),
'<br>Test5', C(-2,-3, -3,6, 7,-2, -6,2, 1,-4, 7),
'<br>Test6', C(-3,2, 2,-4, 7,-3, -3,-4, -3,0 ,10),
'<br>Test7', C(0,0, 6,0, 6,8, -6,-8, 6,8, 20),
'<br>Test8', C(0,0,-2,-5, 5,3, -3,4, 0,0, 6)];
```

```
<div id="MyOutput"></div>
```

**Ungolfed**

```
function check(p0x, p0y, p1x, p1y, p2x, p2y, ex, ey, ax, xy, r)
{
  var sec = function(p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y)
  {
      var s10x = p1x - p0x, s10y = p1y - p0y,
          s32x = p3x - p2x, s32y = p3y - p2y,
          s02x = p0x - p2x, s02y = p0y - p2y,
          s = s10x * s02y - s10y * s02x, t = s32x * s02y - s32y * s02x,
          d = s10x * s32y - s32x * s10y;
      return d && (s/=d) > 0 && s<1 && (t/=d) > 0 && t < 1 && [p0x + (t * s10x), p0y + (t * s10y)];
  }
  var pr = function(p0x, p0y, p1x, p1y, r)
  {
      var dx = (p1x-p0x), dy = (p1y-p0y), f = r/Math.sqrt(dx*dx+dy*dy);
      return [p0x + f*dx, p0y+f*dy];
  }
  var inside = function(p0x, p0y, p1x, p1y, p2x, p2y, px, py)
  {
      var area2 = (-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y),
          s = (p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py)/area2,
          t = (p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py)/area2;
      return s > 0 && t > 0 && s+t < 1;
  }
  var tx, xy;
  [tx, ty] = pr(ex, ey, ax, ay, r);

  return inside(p0x, p0y, p1x, p1y, p2x, p2y, tx,ty)
  || sec(p0x, p0y, p1x, p1y, ex, ey, tx, ty)
  || sec(p0x, p0y, p2x, p2y, ex, ey, tx, ty)
  || sec(p2x, p2y, p1x, p1y, ex, ey, tx, ty);
}

```
> 1 votes

# Answer
# Scala, ~~349~~ 328 bytes

Saved 21 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

```
import scala.math.{atan2=>A,_};type Q=Double;def h(a:Q,b:Q,c:Q,d:Q,e:Q,f:Q,g:Q,h:Q,i:Q,j:Q,R:Q)={var r=R;var Z=1>1;while(r>0){val Q=A(j-h,i-g);val k=g+r*cos(Q);val l=h+r*sin(Q);val D=A(d-b,c-a);val E=A(f-b,e-a);val F=A(l-b,k-a);val G=A(b-d,a-c);val H=A(f-d,e-c);val I=A(l-d,k-c);Z=Z||D<F&F<E|E<F&F<D&&G<I&I<H|H<I&I<G;r-=1e-3};Z}

```

Ungolfed version. Try it online!

```
import scala.math.{atan2 => A, _}
object Main {
  type Q = Double
  def h(a: Q, b: Q, c: Q, d: Q, e: Q, f: Q, g: Q, h: Q, i: Q, j: Q, R: Q) = {
    var r = R
    var Z = false
    while (r > 0) {
      val Q = A(j - h, i - g)
      val k = g + r * cos(Q)
      val l = h + r * sin(Q)
      val D = A(d - b, c - a)
      val E = A(f - b, e - a)
      val F = A(l - b, k - a)
      val G = A(b - d, a - c)
      val H = A(f - d, e - c)
      val I = A(l - d, k - c)
      Z =
        Z || ((D < F && F < E) || (E < F && F < D)) && ((G < I && I < H) || (H < I && I < G))
      r -= 0.001
    }
    Z
  }

  def main(args: Array[String]): Unit = {
    println(h(0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 2)) // Output: true
    println(h(0, 0, 1, 2, 3, 0, -4, 0, 0, 0, 8)) // Output: false
    println(h(0, 0, -1, 3, 4, -1, -3, -4, 3, 4, 5)) // Output: false
    println(h(-2, -3, -3, 6, 7, -2, -6, 2, 1, -4, 7)) // Output: true
  }
}

```
> 0 votes

---
Tags: code-golf, geometry
---


title: Vertices of a regular dodecahedron

text:
# Question
Title: Vertices of a regular dodecahedron
A regular dodecahedron is one of the five Platonic solids. It has 12 pentagonal faces, 20 vertices, and 30 edges.

Your task is to output the vertex coordinates of a regular dodecahedron. The size, orientation, and position of the dodecahedron are up to you, as long as it is regular.

You may output the coordinates in any order, and in any reasonable format.

If the edge length of your dodecahedron is \\$a\\$, then the coordinates should be accurate to at least \\$a/1000\\$.

This is , so the shortest code in bytes wins.

## Example output

This is one possible output. Your output does not have to match this.

```
{-1.37638,0.,0.262866}
{1.37638,0.,-0.262866}
{-0.425325,-1.30902,0.262866}
{-0.425325,1.30902,0.262866}
{1.11352,-0.809017,0.262866}
{1.11352,0.809017,0.262866}
{-0.262866,-0.809017,1.11352}
{-0.262866,0.809017,1.11352}
{-0.688191,-0.5,-1.11352}
{-0.688191,0.5,-1.11352}
{0.688191,-0.5,1.11352}
{0.688191,0.5,1.11352}
{0.850651,0.,-1.11352}
{-1.11352,-0.809017,-0.262866}
{-1.11352,0.809017,-0.262866}
{-0.850651,0.,1.11352}
{0.262866,-0.809017,-1.11352}
{0.262866,0.809017,-1.11352}
{0.425325,-1.30902,-0.262866}
{0.425325,1.30902,-0.262866}

```

# Answer
# Wolfram Language (Mathematica), 15 bytes

```
SpherePoints@20

```

Try it online!

20 evenly spaced points on the surface of a unit sphere.

The more obvious `PolyhedronCoordinates@Dodecahedron[]` is a little bit longer.
> 23 votes

# Answer
# 05AB1E, ~~31~~ 25 bytes

```
®X‚D3ãsãvy5t<;D>‚*¾š2Ý._«

```

Uses \\$\sqrt{3}\\$ as the distance of each vector from the origin \\$\\{0,0\\}\\$. Will output the following 20 vertex-coordinates:

$$\[\\{-1,-1,-1\\},\\{-1,-1,1\\},\\{-1,1,-1\\},\\{-1,1,1\\},\\{1,-1,-1\\},\\{1,-1,1\\},\\{1,1,-1\\},\\{1,1,1\\},\\{0,-\phi,-\phi-1\\},\\{-\phi,-\phi-1,0\\},\\{-\phi-1,0,-\phi\\},\\{0,-\phi,\phi+1\\},\\{-\phi,\phi+1,0\\},\\{\phi+1,0,-\phi\\},\\{0,\phi,-\phi-1\\},\\{\phi,-\phi-1,0\\},\\{-\phi-1,0,\phi\\},\\{0,\phi,\phi+1\\},\\{\phi,\phi+1,0\\},\\{\phi+1,0,\phi\\}\]$$

Try it online.

**Explanation:**

```
®X‚             # Push pair [-1,1]
   D            # Duplicate it
    3ã          # Get all possible triplets using the cartesian power of 3
   s            # Swap so the [-1,1] pair is at the top again
    ã           # Also get all possible pairs using the cartesian power of 2
     vy         # Loop over each pair of [±1,±1]:
       5t<;     #  Push the golden ratio: (sqrt(5)-1)/2
           D    #  Duplicate it
            >   #  Increase the copy by 1
             ‚  #  Pair it together with the (sqrt(5)-1)/2
      y       * #  Multiply the values in the pair to pair [±1,±1] at the same positions
        ¾š      #  Prepend a 0 to this pair
          2Ý    #  Push list [0,1,2]
            ._  #  Rotate the triplet that many times to the left
              « #  Merge it to the original list of [-1,1]-triplets
                # (after which the list of 20 triplets is output implicitly as result)

```

---

I started with a port of this SO C# answer, but noticed (for \\$r=\sqrt{3}\\$ at least):

* \\$±\frac{1}{\sqrt{3}}\times\phi\times\sqrt{3}\\$ is simply \\$±\phi\\$
* \\$±\frac{\frac{1}{\sqrt{3}}}{\phi}\times\sqrt{3}\\$ is simply \\$±(\phi+1)\\$

Try it online.
> 12 votes

# Answer
# Python, 73 bytes

```
x={3*(55,),(89,34,0)}
for s in(-1,1)*3:x|={(s*y,*z)for*z,y in x}
print(x)

```

Attempt This Online!

Same approach as @xnor (I think), i.e. flip signs and rotate coordinates random-ish-ly. Only, I'm being more simple-minded about it ;-)

#### Retired Python, 103 bytes

```
*x,x[7],x[2]=6*[-55,55]
*y,y[11],_,_,y[2]=3*[-34,0,-89,34,0,89]
for a in x,y:*map(print,a,a[1:],a[2:]),

```

Attempt This Online!

Integer coordinates from @alephalpha / @xnor via @Arnauld.
> 11 votes

# Answer
# JavaScript (ES6), 88 bytes

Returns a set of strings, where each string is a triplet `x,y,z`.

This version takes inspiration from xnor's approach.

```
_=>(g=(s,x,y=x,z=x,k=y)=>k--?g(s.add(x+[,y,z]),k%4?z:-z,x,y,k):s)(g(new Set,55),0,34,89)

```

Try it online!

### Commented

```
_ => (               // main function ignoring its argument
  g = (              // g is a helper function taking:
    s,               //   s = output set
    x,               //   x = 1st coordinate
    y = x,           //   y = 2nd coordinate, or x by default
    z = x,           //   z = 3rd coordinate, or x by default
    k = y            //   k = counter, initialized to y
  ) =>               //
  k-- ?              // if k is not 0 (decrement afterwards):
    g(               //   do a recursive call:
      s.add(         //     add to the set:
        x + [, y, z] //       a stringified version of the triplet
      ),             //
      k % 4 ? z      //     rotate by putting z at the beginning
            : - z,   //     or -z if k is a multiple of 4
      x, y,          //     followed by x and y
      k              //     pass the updated counter
    )                //   end of recursive call
  :                  // else:
    s                //   stop and return the set
)(                   //
  g(new Set, 55),    // first call with x = y = z = 55
  0, 34, 89          // second call with (x, y, z) = (0, 34, 89)
)                    //

```

---

# JavaScript (V8), 108 bytes

*-5 bytes by using \\$\phi\approx 89/55\\$, as suggested by alephalpha*
*-3 bytes by scaling everything up (x55), as suggested by xnor*

A full program printing 20 triplets `x,y,z`.

```
[344,900,564,228].map(g=n=>n--&15&&g(n,j=0,print([4,6,8].map(i=>[0,55,89,34][v=n>>i&3]*(v&&n>>j++&1||-1)))))

```

Try it online!

## Encoding

We use the Cartesian coordinates based on the golden ration as described on Wikipedia, but with a different scale.

Each triplet pattern is encoded with the following bit mask:

```
ZZ YY XX NNNN
 |  |  | \__/
 |  |  |   |
 |  |  |   +--> number of triplets
 |  |  +------> x
 |  +---------> y
 +------------> z

```

where \\$x\\$, \\$y\\$ and \\$z\\$ are indices in the lookup array \\$\[0,1,\phi,\frac{1}{\phi}\]\\$.

This gives:

| Triplet pattern | x | y | z | N | Bit mask | As decimal |
| --- | --- | --- | --- | --- | --- | --- |
| \\$(\pm 1,\pm 1,\pm 1)\\$ | 1 | 1 | 1 | 8 | 01 01 01 1000 | 344 |
| \\$(0,\pm\phi,\pm\frac{1}{\phi})\\$ | 0 | 2 | 3 | 4 | 11 10 00 0100 | 900 |
| \\$(\pm\frac{1}{\phi},0,\pm\phi)\\$ | 3 | 0 | 2 | 4 | 10 00 11 0100 | 564 |
| \\$(\pm\phi,\pm\frac{1}{\phi},0)\\$ | 2 | 3 | 0 | 4 | 00 11 10 0100 | 228 |
> 7 votes

# Answer
# Haskell, 33 bytes

```
k=[0..19]

```

```
[[0^(x-y)^2|x<-k]|y<-k]

```

Try it online!

## Explanation

So this answer uses a trick, which some may consider a loophole. Actually uses *two tricks*. So I'm going to explain how it works.

If the OP wants to patch this approach out of the challenge, I will delete my answer.

### Skew polyhedra

The exact definition of a polyhedron varies from person to person. Some circumstances require that a polyhedron be finite and not self intersect, this gives 5 regular polyhedra, some allow self intersection but still require finiteness, this gives 9 regular polyhedra, some times Euclidean tilings are considered as well giving 12.

However in the beginning of the 20th century Petrie and Coxeter discovered 3 regular polyhedra that hadn't been considered before. These were infinite polyhedra with flat non-intersecting faces, however they didn't have insides, so they hadn't been considered before. Pictured below is a section of the mucube, one of the three:

This discovery lead to a new definition of polytope (and by extension a new definition of polyhedron). This definition was first given by Branko Grünbaum in the paper *Regular polyhedra - old and new*, but has been used pretty extensively. Under this definition vertices (and edges) have exact locations, but the higher dimensional elements no longer needed to have exact interiors. A polygon is just a sequence of vertices pairwise connected by edges, such that you can reach any vertex from any other by following edges. A polyhedron is shape made out of polygons with exactly two meeting at every edge.

For example, classically a polygon needs to be "flat" meaning all of its vertices lie in a plane. However skew polygons can have vertices which lie in higher dimensional space. For example here's a 4-dimensional regular polygon:

*Image by Plasmath see this page for liscensing*

(We will come back to this particular polygon later)

The same can also be done with polyhedra. Instead of requiring that the vertices of a polyhedron lie strictly in 3D space with each face lying on a plane, you can have polyhedra whose vertices span 4 or greater dimensions, and whose faces are non-planar.

Lots of great work would be done with this definition. I'd especially like to point out the work of McMullen and Schulte. The have a paper classifying all the regular polyhedra in 3-space, which has been summarized in this excellent youtube video:

jan Misali, there are 48 regular polyhedra

This definition is the one I am using in this answer.

Now the challenge says:

> Your task is to output the vertex coordinates of a regular dodecahedron. The size, orientation, and position of the dodecahedron are up to you, as long as it is regular.

So I just need to choose *a* regular dodecahedron. It turns out there are 28 distinct ways to realize the regular dodecahedron {5,3} in Euclidean space. The dodecahedron I chose is the its "Simplex realization". In general you can take any regular polyhedron with \\$n\\$ vertices and create an fully symmetric realization of it on a \\$(n-1)\\$-simplex. This is because all the symmetries of a polyhedron are permutations of its vertices. The symmetries of a simplex are *all* the permutations of its vertices. So when we place the vertices of a polyhedron on the vertices of a simplex every symmetry is possible. So this realization is always fully regular with maximum symmetry.

The dodecahedron has 20 vertices so that means the vertices of its simplex realization are the vertices of the 19-simplex. At first glance I've just made my problem much harder. The vertices of the 19-simplex centered at the origin are *nasty*, way worse than the vertices of the convex regular dodecahedron.

So here's where the second trick comes in. The vertices of a regular \\$n\\$-simplex are actually really simple if you express them in \\$n+1\\$ dimensions. If you place each vertex on an axis, all at the same distance from the origin, then permuting the axes is exactly the same as permuting the vertices. So this is fully regular, in fact its the same simplex its just lying on a weird hyperplane.

For example you can give the vertices of the triangle as:

$$ (1,0,0) \\ (0,1,0) \\ (0,0,1) \\ $$

This is a regular 2D triangle. This same trick comes up if you want to represent triangular (or hexagonal) coordinates. Instead of using 2D space and complicated square roots, you can represent them in 3D space as triplets of integers.

So returning to the problem at hand, the 19 simplex can be given in 20 dimensions as all permutations of \\$(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)\\$. Its symmetries being all permutations of of the coordinate axes.

So in summary, I am giving the vertices for a 19-dimensional dodecahedron in 20 dimensional space.

I can't exactly render this in any way that is helpful. But its faces I can say its faces are the regular 4D pentagon shown earlier. If you want to try to imagine 12 of those in 20 dimensional space.
> 7 votes

# Answer
# Python 3, 86 bytes

```
r=[]
for l in[[55]*3,[0,89,34]]*99:l+=(len(r)%11%-2|1)*l.pop(0),;r+=(*l,),
print({*r})

```

Try it online!

Outputs the golden-ratio vertices everyone is using, scaled up by 55, from the approximation of \\$ \phi \approx 89/55\\$ suggested by alephalpha.

The idea is to take the two vertices \\$(1,1,1)\\$ and \\$(0,\phi,1/\phi)\\$ and "randomly" negate entries and take cyclic permutations to reach all 20 vertices, then de-duplicate using sets. Each loop alternates between the two vertices, mutating it by moving the first entry to the back, and possibly negating that entry. Whether to negate is given by `i%11%2` on the `i`'th loop, which happens to hit all 20 vertices in not too many loops. The index `i` is actually tracked by the length of the list `l` of vertices we've generated so far.

---

# Python 3, 82 bytes

```
*l,k=0,34,89,718230
while k:k-175or(l:=[55]*3);l+=l.pop(0)*(-1)**k,;k>>=1;print(l)

```

Try it online!

To be golfed...
> 6 votes

# Answer
# Prolog (SWI), 130 bytes

```
A+B:-A=B;A is-B.
A*B*C*G*I*P:-A+P,B+P,C+P;A=0,B+G,C+I;B=0,A+I,C+G;C=0,A+G,B+I.
:-bagof([A,B,C],A*B*C*89*34*55,R),maplist(write,R).

```

Try it online!

Uses the approximation \\$\phi \approx 89/55\\$ then scaling the vertices by 55.
> 4 votes

# Answer
# Nekomata, 16 bytes

```
7Ƃ89\55:ŗÐçxŘ~?ŋ

```

Attempt This Online!

```
7Ƃ89\55:ŗÐçxŘ~?ŋ
7Ƃ                  Push the list [1,1,1]
  89\55             Push the number 89/55
       :ŗÐ          Pair with its reciprocal ([89/55,55/89])
          ç         Prepend zero ([0,89/55,55/89])
           xŘ~      Non-deterministic rotation ([0,89/55,55/89],[89/55,55/89,0],[55/89,0,89/55])
              ?     Non-deterministic choice ([1,1,1],[0,89/55,55/89],[89/55,55/89,0],[55/89,0,89/55])
               ŋ    Optionally negate each element

```
> 4 votes

# Answer
# Charcoal, ~~53~~ 44 bytes

```
≔Ｅ²Ｅ³∨ι∧⊖λ⊘⁺⊖λ₂⁵υＦυＦＥ²⊞ＯΦιν×⊖⊗κ§ι⁰Ｆ¬№υκ⊞υκＩυ

```

Try it online! Link is to verbose version of code. Explanation: Uses the formula from this Math.SE answer.

```
≔Ｅ²Ｅ³∨ι∧⊖λ⊘⁺⊖λ₂⁵υ

```

Get the points `[1/ϕ, 0, ϕ]` and `[1, 1, 1]`.

```
ＦυＦＥ²⊞ＯΦιν×⊖⊗κ§ι⁰Ｆ¬№υκ⊞υκＩυ

```

For each point, rotate it around the axis `x=y=z`, and also reflect the rotated point in the `xy` plane, and save and process any new points thus found.

```
Ｉυ

```

Output the final dodecahedron.
> 3 votes

# Answer
# Perl, 167 bytes

```
sub f{print"@_
"}sub g{$a=shift;map{$_[$_]*(!($a&1<<$_)*2-1)}0..~~@_-1}$p=.5+sqrt 5/4;f g $_,1,1,1 for 0..7;do{@v=((g $_,$p,1/$p,0)x2);f @v[$_..$_+2] for 0..2}for 0..3

```

Try it online!
> 3 votes

# Answer
# Jelly,  ~~18~~  17 bytes

<sup>...or 15 with repeats - remove `µQ`.</sup>

```
Ø+ṗ3µØpİƬŻṙJ×€jµQ

```

A niladic Link that yields a list of triples.

**Try it online!**

### How?

Produces the twenty triples as shown on Wikipedia:

$$(\pm 1, \pm 1, \pm 1)$$ $$(0, \pm \phi, \pm \phi^{-1})$$ $$(\pm \phi^{-1}, 0, \pm \phi)$$ $$(\pm \phi, \pm \phi^{-1}, 0)$$

```
Ø+ṗ3µØpİƬŻṙJ×€jµQ - Link: no arguments
Ø+                - [1, -1]
   3              - three
  ṗ               - Cartesian power -> (+/-1, +/-1, +/-1) "CubePoints"
    µ          µ  - monadic chain - f(CubePoints):
     Øp           -   phi
        Ƭ         -   collect up while distinct under:
       İ          -     inverse
         Ż        -   prefix with zero -> [0, phi, 1/phi]
           J      -   range of length {CubePoints} -> [1, 2, 3, 4, 5, 6, 7, 8]
          ṙ       -   rotate {[0, phi, 1/phi]} left by (vectorises) {that}
                      -> [[phi, 1/phi, 0], [1/phi, 0, phi], [0, phi, 1/phi], ...(8)]
             €    -   for each (rotation):
            ×     -     multiply by {CubePoints} (vectorises)
              j   -   join {that list of lists of triples} with {CubePoints}
                Q - deduplicate

```
> 3 votes

# Answer
# Ruby, 55 bytes

```
20.times{|j|p ~0**j*(1.309-k=j/10),1.618**k*1i**j*=0.4}

```

Try it online!

Golfed version using decimal approximations instead of exact formulas (I can't use fractions as Ruby would interpret using integer arithmetic.) Dimensions are now half the ones given in the wolfram page, instead of double, to avoid `j/10*4`. The polar vertices are now listed before the equatorial vertices, to enable the distance from the `z` axis to be calculated as `1.618**k` (1 or 1.618)

I also deleted the `[]` to save 2 bytes, although this impacts readability of the output.

# Ruby, ~~85~~ 63 bytes

```
20.times{|j|p [~0**j*z=5**0.5-1+j/10*4,[8/z,4].max*1i**j*=0.4]}

```

Try it online!

The coordinates given in the question are `x,y,z` with the dodecahedron's 5-fold rotational symmetry axis aligned with the `z` axis (It's actually a 10-fold axis for the rotate-and-flip operation.). This program outputs the same coordinates as the ones in the question, but in the format `[z,x+yi]` and scaled. First all the equatorial vertices are output, and then the polar vertices.

`~0**j` alternates the sign of the `z` coordinate as the `x` and `y` coordinates cycle through the 1/10th of a circle rotations. (`-1**j` would not work because unary minus has lower priority than raising to a power in Ruby.)

Exact coordinates in terms of the golden ratio are given at the wolfram page in formulas 1 and 2. The alternate coordinate system used in other answers is given a little below them on the same page, as well as in wikipedia. This code uses double the scale used in the Wolfram page, to avoid the division by 2 required to calculate the golden ratio. The footer in TIO link scales the coordinates given in the question and moves the `z` coordinate to the beginning for comparison. You still have to squint a bit because I've sorted the coordinates given in the question by `z` value, whereas the above code generates the vertices in an intercalated order with alternating sign of the `z` value.
> 3 votes

# Answer
# Pyth, 24 bytes

```
{+K^_BT3*VM*K.<L+tB.n3Z3

```

Try it online!

Uses the same \\$\varphi\\$ based coordinates that everybody else is using, just multiplied by 10, that is, \\$\[\pm 10,\pm 10,\pm 10\], \[\pm 10\varphi, \pm \frac{10}{\varphi}, 0\], \[0, \pm 10\varphi, \pm \frac{10}{\varphi}\], \[\pm \frac{10}{\varphi}, 0, \pm 10\varphi\]\\$.

But there's a really neat simplification here, which is that after I had the integer coordinates, I could use them as the signs for the other coordinates, just adding the need to deduplicate at the end since \\$0=-0\\$.

### Explanation

```
    _BT                     # bifurcate 10 on negation (gives us [1,-1])
   ^   3                    # get all possible triplets
  K                         # assign this list to K
                   .n3      # phi
                 tB         # bifurcated on subtracting 1
                +     Z     # append 0 to the pair
             .<L       3    # map [0,1,2] to cyclic rotation on this list
           *K               # get the cartesian product of these rotations with K
        *VM                 # map over vectorized multiplication
 +K                         # add K to this list
{                           # deduplicate to eliminate repeat coordinates

```
> 2 votes

# Answer
# Scala, 226 bytes

Golfed version. Try it online!

```
val p=Seq(-1,1)
val g=(sqrt(5)-1)/2
((for{a<-p;b<-p;c<-p}yield Seq(a,b,c))++(for{p<-((for{a<-p;b<-p}yield Seq(a,b)).map{case Seq(a,b)=>Seq(a*g,b*(g+1))}.map(0.0+:_));i<-0 to 2}yield p.drop(i)++p.take(i))).foreach(println)

```

Ungolfed version. Try it online!

```
import scala.math._

object Main {
  def main(args: Array[String]): Unit = {
    val pair = List(-1, 1)
    val triplets = for {
      a <- pair
      b <- pair
      c <- pair
    } yield List(a, b, c)
    val pairs = for {
      a <- pair
      b <- pair
    } yield List(a, b)
    val goldenRatio = (sqrt(5) - 1) / 2
    val goldenRatioMultipliedPairs = pairs.map {
      case List(a, b) => List(a * goldenRatio, b * (goldenRatio + 1))
    }
    val prependedPairs = goldenRatioMultipliedPairs.map(0.0 :: _)
    val rotatedPairs = for {
      pair <- prependedPairs
      i <- 0 to 2
    } yield pair.drop(i) ++ pair.take(i)
    val finalTriplets = triplets ++ rotatedPairs
    finalTriplets.foreach(println)
  }
}

```
> 2 votes

# Answer
# Perl, ~~139~~ ~~137~~ 135 bytes

```
sub p{print"@_
"}sub g{($x)=@_;map{$_[$_]*(1-(4*$x>>$_&2))}1..3}p g$_,(55)x3 for 0..7;map{@v=(g$_,89,34,0)x2;p@v[$_..$_+2]for 0..2}0..3

```

try it online
> 2 votes

---
Tags: code-golf, kolmogorov-complexity, geometry
---


title: Detect Maxima Using Persistent Homology

text:
# Question
Title: Detect Maxima Using Persistent Homology
Inspired by this SO answer about peak detection.

## Background

Persistent homology is a fancy term for a fancy math concept, but in this case all we care about is how it can be used for peak detection. In the case of a 1-dimensional array we can describe the algorithm as follows:

We are given an array as input. We begin by sorting it, while maintaining references to the original indices for each value. We also create some kind of data structure to group points together into peaks. We then loop over each point in the sorted array. For each point we have three cases:

* If it is not adjacent to any points in existing groups, a new group is created with a "position" of the point's original index and given a "birth time" equal to that point's value.
* If it is adjacent to one point that is in a group, it is added to said group.
* If it is adjacent to two points in different groups, the younger group is given a "death time" equal to that point's value, and all its points are given to the older group.

At the end, the single group which remains is given a death time of the final value. Now we have a list of groups, each of which have a position that corresponds to a local maximum, and a persistence which is equal to their "birth time" minus their "death time".

## The challenge

Given a 1-dimensional sequence of inputs which support comparison and subtraction, and an integer \\$n \geq 1\\$, your task is to output the indices of the \\$n\\$ most persisent peaks, sorted by their persistence.

Your program does not need to follow the algorithm exactly as I've described it, nor does it need to be as efficient. You only need to support one class of inputs for the sequence (ie. integers, floats, etc.) and any reasonable format for I/O is allowed so long as it is consistent. You may assume that \\$n\\$ is less than or equal to the number of local maxima.

In the case that two local maxima to be merged have the same "birth time", the behavior for which one persists is undefined, and either is considered valid for this challenge. In the case that two or more maxima have the same persistence, they may appear in any order in the output.

This is , so the shortest answer in bytes wins.

## Worked example

Let's look at `[1, 2, 1, 2, 3, 2, 1]`. First we'll enumerate and sort `[0:1, 1:2, 2:1, 3:2, 4:3, 5:2, 6:1]` to `[4:3, 1:2, 3:2, 5:2, 0:1, 2:1, 6:1]` then we iterate over this. I'll show for each iteration what the aforementioned "group" data structure might look like, in this case simply a list of point indices, birth time and death time

```
[[[4], 3, None]]
[[[4], 3, None], [[1], 2, None]]
[[[4, 3], 3, None], [[1], 2, None]]
[[[4, 3, 5], 3, None], [[1], 2, None]]
[[[4, 3, 5], 3, None], [[1, 0], 2, None]]
[[[4, 3, 5, 1, 0, 2], 3, None], [[1, 0], 2, 1]]
[[[4, 3, 5, 1, 0, 2, 6], 3, 1], [[1, 0], 2, 1]]

```

this gives us the a peak at 4 with persistence 3-1=2 and a peak at 1 with persistence 2-1=1 thus our sorted list of peaks is \[4,1\]

## Test cases

Outputs here are 0-indexed.

```
[1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1]
2
->
[9, 4]

[1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 1]
3
->
[7, 19, 12]

[93, 92, 89, 88, 89, 88, 87, 87, 88, 88, 90, 89, 88, 87, 86, 90, 89, 89, 88, 88, 86, 82, 76, 69, 61, 52, 44, 38, 33, 30, 27, 24, 22, 21, 18, 15, 10, 6, 2, 0, 0, 2, 2, 1, 2, 5, 8, 10, 13, 16]
4
->
[0, 49, 15, 10]

```

More information about persistent homology in general can be found on wikipedia and this more detailed write-up by the author of the SO answer.

# Answer
> 6 votes
# Python3, 350 bytes:

```
S=sorted
def f(s,n):
 r,R={},0
 for i,v in S(enumerate(s),key=lambda x:-x[1]):
  R+=1
  if(K:=[r.pop(I)for I in[*r]if i+1in r[I][2]or i-1in r[I][2]]):
   *a,b=S(K,key=lambda x:x[0])
   if a:r[R]=[a[0][0]-v,a[0][1],[]];b[2]+=a[0][2]+[i];R+=1;r[R]=b
   else:b[2]+=[i];r[R]=b
  else:r[R]=[v,i,[i]]
 return[r[i][1]for i in S(r,key=lambda x:-r[x][0])][:n]

```

Try it online!

# Answer
> 4 votes
# JavaScript (ES10*), 215 bytes

** ES10 guarantees a stable sort, but the OP has since clarified that this is not a strict requirement.*

(or 214 bytes in ES12, but ATO doesn't seem to be working right now)

Expects `(array)(n)`.

```
a=>n=>(o=[]).map(a=>a[2],a.map((v,i)=>[v,i]).sort(g=([a],[b])=>b-a).map(([v,i])=>([p,q]=o.sort(g).filter(a=>a[1].some(j=>(j-=i)*j<2)),q=q||[,[]],p)?q[p[1].push(...q[1],i),q[0]-=v,1]=[]:o.push([v,[i],i]))).slice(0,n)

```

Try it online!

### Commented

```
a =>                        // outer function taking a[]
n =>                        // inner function taking n
(o = [])                    // o[] = array of [ value, group, index ] tuples
.map(a =>                   // once o[] is finalized ...
  a[2],                     //   ... keep only the original indices
  a.map((v, i) => [ v, i ]) //   we first turn a[] into an array of
                            //   [ value, index ] pairs
  .sort(g = ([a], [b]) =>   //   and sort them ...
    b - a                   //     ... from highest to lowest value
  )                         //
  .map(([v, i]) =>          //   for each pair [ value, index ]:
    ( [p, q] = o.sort(g)    //     sort o[] by decreasing 'birth time'
      .filter(a =>          //     and keep only the tuples ...
        a[1].some(j =>      //       ... whose groups contain a value
          (j -= i) * j < 2  //       adjacent to the current value
        )                   //
      ),                    //     save at most 2 tuples in [ p, q ]
      q = q || [, []],      //     force a default dummy value for q
      p                     //     test p
    ) ?                     //     if p is defined:
      q[                    //
        p[1].push(          //       append to the group of p:
          ...q[1],          //         the values from the group of q
          i                 //         followed by i
        ),                  //
        q[0] -= v,          //       subtract the 'dead time' from the
        1                   //       'birth time' of q
      ] = []                //       and clear the group of q
    :                       //     else:
      o.push([v, [i], i])   //       create a new tuple
  )                         //   end of inner map()
)                           // end of outer map()
.slice(0, n)                // return only the n first elements

```

# Answer
> 4 votes
# Python, 322 307 298 279 272 bytes

```
def P(l,n,*o):
 L=len(l);*u,S=1,*[0]*L,1,sorted
 for i in S(range(L),key=lambda x:-l[x]):*r,d=0,0,1;exec('k,c=i,sum(u[i-(d<0)::d])<2\nwhile~-u[k+1]:r[c]=max(r[c],l[i]-l[k]);k+=d\nd=-1;'*2);o+=((-r[0]or-r[1],i),)*(1>i%~-L*sum(u[i:i+3]));u[i+1]=1
 return[*zip(*S(o))][1][:n]

```

Using different algorithm than the one in the question:

1. Sort descending
2. For each value, if it's a peak (immediate left and right have not been visited) iterate left and iterate right, record max diff until encountering a previously visited value or end of array. Give priority to encountering previously visited value. Store them.
3. Sort and return

Try it online!

-9 bytes thanks to UnrelatedString
-19 bytes thanks to AnttiP and Kevin
-7 bytes thanks to AnttiP

# Answer
> 4 votes
# Python, 153 bytes

```
lambda a,n:sorted(r:=range(N:=len(a)),key=lambda j:max((g:=lambda s,k:g(s,k+s)if k in r and a[k]<=a[j]else min(a[j:k%-N:s]or[0]))(1,j),g(-1,j))-a[j])[:n]

```

Attempt This Online!

Expects a sequence of positive integers (other positive numbers should work, too).

How?

I'm using the following algorithm which I think is equivalent to OP's:

For each position p find the nearest position with larger value and take the smallest value in between. Do this on the left and the right and keep the larger of the two minima minus the value at p. Sort positions by this quantity.

# Answer
> 2 votes
# Charcoal, 46 bytes

```
ＵＭθ⟦⁻⌈Ｅ⟦⮌…θ⊕κ✂θκ⟧∨⌊…λ⌕Ｅλ›νι¹¦⁰ικ⟧Ｆη⊞υ⌊⁻θυＩＥυ⊟ι

```

Try it online! Link is to verbose version of code. Explanation: Port of @Albert.Lang's Python answer, because it's the only post here I could understand.

```
ＵＭθ⟦⁻⌈Ｅ⟦⮌…θ⊕κ✂θκ⟧∨⌊…λ⌕Ｅλ›νι¹¦⁰ικ⟧

```

For each element of the input array, get the reversed prefix and suffix, truncate each at the first element greater than the current element, then take the minimum, or zero if the list is empty, subtract the current element from the larger of the two, and pair it with the current index.

```
Ｆη⊞υ⌊⁻θυ

```

Get the persistence and index of the `n` most persistent peaks.

```
ＩＥυ⊟ι

```

Output the indices.

# Answer
> 0 votes
# Scala, ~~516~~ 511 bytes

Port of @Ajax1234's Python answer in Scala.

Saved many bytes thanks to the comment of @Aiden Chow

---

Golfed version. Try it online!

```
def f(s:Seq[Int],n:Int)={val r=mutable.Map[Int,(Int,Int,Seq[Int])]();var R=0;for((v,i)<-s.zipWithIndex.sortBy(vi=> -vi._1)){val K=r.keys.filter(I=>r(I)._3.contains(i+1)||r(I)._3.contains(i-1)).map(I=>r.remove(I).get).toSeq.sortBy(_._1);if(K.nonEmpty){val(a,b)=(K.init,K.last);R+=1;if(a.nonEmpty){r+=(R->(a.head._1-v,a.head._2,Nil));R+=1;r+=(R->(b._1,b._2,b._3++a.head._3++Seq(i)))}else{r+=(R->(b._1,b._2,b._3++Seq(i)))}}else{R+=1;r+=(R->(v,i,Seq(i)))}};r.keys.toSeq.sortBy(k=> -r(k)._1).map(i=>r(i)._2).take(n)}

```

Ungolfed version. Try it online!

```
def f(s:Seq[Int],n:Int)={
  val r = mutable.Map[Int, (Int, Int, Seq[Int])]()
  var R = 0
  for ((v, i) <- (s.zipWithIndex.sortBy { case (v, i) => -v})) {
    val K = r.keys
      .filter(I => r(I)._3.contains(i + 1) || r(I)._3.contains(i - 1))
      .map(I => r.remove(I).get)
      .toSeq
      .sortBy(_._1)
    if (K.nonEmpty) {
      val (a, b) = (K.init, K.last)
      R += 1
      if (a.nonEmpty) {
        r += (R -> (a.head._1 - v, a.head._2, Nil))
        R += 1
        r += (R -> (b._1, b._2, b._3 ++ a.head._3 ++ Seq(i)))
      } else {
        r += (R ->  (b._1, b._2, b._3 ++ Seq(i)))
      }
    } else {
      R += 1
      r += (R -> (v, i, Seq(i)))
    }
  }
  r.keys.toSeq.sortBy(key => -r(key)._1).map(i => r(i)._2).take(n)
}

```

---
Tags: code-golf, number
---


title: Smallest groups in an array

text:
# Question
Title: Smallest groups in an array
### Introduction

Let's observe the following array:

```
[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]

```

A **group** consists of the same digits next to each other. In the above array, there are 5 different groups:

```
[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]

 1, 1, 1
          2, 2
                1, 1, 1, 1
                            2, 2, 2
                                     1, 1, 1

```

The smallest group of these is `[2, 2]`, so we output `[2, 2]`.

Let's take another example:

```
[3, 3, 3, 4, 4, 4, 4, 5, 5, 4, 4, 3, 3, 4, 4]

 3, 3, 3
          4, 4, 4, 4
                      5, 5
                            4, 4
                                  3, 3
                                        4, 4

```

You can see that there are multiple groups with the same length. The smallest groups are:

```
[3, 3], [4, 4], [4, 4] and [5, 5].

```

So we just output `[3, 3], [4, 4], [4, 4], [5, 5]` in any reasonable format. You may output these in any order.

### The Task

Given an array consisting of only positive integers, output the smallest group(s) from the array. You can assume that the array will contain at least 1 integer.

### Test cases

```
Input: [1, 1, 2, 2, 3, 3, 4]
Output: [4]

Input: [1]
Output: [1]

Input: [1, 1, 10, 10, 10, 100, 100]
Output: [1, 1], [100, 100]

```

This is , so the submission with the least amount of bytes wins!

# Answer
# Pyth, ~~14~~ ~~12~~ 11

```
mM_MmhbrQ8

```

Test Suite

2 bytes thanks to Jakube! And 1 byte thanks to isaacg!

Unfortunately, run length decoding doesn't quite do what we want it to do, but it will work with a minor workaround, but that makes it slightly longer than the manual implementation:

```
mr]d9.mhbrQ8

```

Credit to Jakube for finding this out.
> 5 votes

# Answer
# Mathematica, 24 bytes

```
MinimalBy[Length]@*Split

```

This is a composition of two functions that can be applied to a list. `Split` takes all groups of consecutive numbers, and `MinimalBy[Length]` selects those with minimal length.
> 9 votes

# Answer
## Haskell, 38 bytes

```
import Data.Lists
argmins length.group

```

Usage example: `argmins length.group $ [3,3,3,4,4,4,4,5,5,4,4,3,3,4,4]` -\> `[[4,4],[3,3],[4,4],[5,5]]`.

Build groups of equal elements and find those with minimal length.
> 5 votes

# Answer
## Python 2, 120 bytes

```
import re
r=[x.group().split()for x in re.finditer(r'(\d+ )\1*',input())]
print[x for x in r if len(x)==min(map(len,r))]

```

Takes input as a string of space-separated integers with a trailing space, and outputs a list of lists of strings. The strategy is to find groups using the regex `(\d+ )\1*` (which matches one or more space-separated integers, with a trailing space), then split them on spaces into lists of integers, and print those groups whose length is equal to the minimum group length.

Try it online
> 4 votes

# Answer
## C#, 204 bytes

```
void f(string o){var r=Regex.Matches(o,@"([0-9])\1{0,}").Cast<Match>().OrderBy(x=>x.Groups[0].Value.Length);foreach(var s in r){foreach(var z in r)if(s.Length>z.Length)return;Console.WriteLine(s.Value);}}

```

I don't know if using a string is fair considering all the golfing esolangs get their input in the same way but he requested array input.

ungolfed:

```
    public static void f(string inp)
    {

        var r = Regex.Matches(inp, @"([0-9])\1{0,}").Cast<Match>().OrderBy(x => x.Groups[0].Value.Length);

        foreach (Match s in r)
        {
            foreach (Match z in r)
                if (s.Length > z.Length)
                    return;

        Console.WriteLine(s.Value);
        }

    }

```

I need a way to get the smallest matches for the match array, most of my bytes are wasted there, help appreciated. I'm trying to get into LINQ and lambda stuff.
> 2 votes

# Answer
# Python 2.x, 303 bytes

```
x=input()
r=[q[2]for q in filter(lambda l:(len(l[2])>0)&((l[0]<1)or(x[l[0]-1]!=x[l[0]]))&((l[1]>len(x)-1)or(x[l[1]]!=x[l[1]-1]))&(len(filter(lambda k:k==l[2][0],l[2]))==len(l[2])),[(a,b,x[a:b])for a in range(0,len(x))for b in range(0,len(x)+1)])]
print filter(lambda k:len(k)==min([len(s)for s in r]),r)

```

Ugliest. Code. Ever.

Input: An array in the format `r'\[(\d,)*(\d,?)?\]'`
In other words, a python array of numbers

Output: An array of arrays (the smallest groups), in the order that they appear in the input array

Additional Coincidental Features (Features that I did not intend to make):

* The input can be an empty array; the output will be an empty array.
* By changing `min` to `max`, it will return an array of the largest groups.
* If you just do `print r`, it will print all of the groups in order.
> 2 votes

# Answer
# Retina, ~~91~~ ~~85~~ ~~80~~ ~~79~~ ~~77~~ ~~76~~ ~~75~~ 74 bytes

```
M!`\b(\d+)(,\1\b)*
(,()|.)+
$#2:$&
O#`.+
s`^(.*\b(.+:).*)¶(?!\2).+
$1
.+:
<empty-line>

```

Try it online!

## Explanation

The input is `1,1,10,10,10,100,100`.

The first line matches groups with same terms:

```
M!`\b(\d+)(,\1\b)*

```

The input becomes:

```
1,1
10,10,10
100,100

```

The following two lines prepend the number of commas to the line:

```
(,()|.)+
$#2:$&

```

The input becomes:

```
1:1,1
2:10,10,10
1:100,100

```

Then they are sorted by this line, which looks for the first number as index:

```
O#`.+

```

The input becomes:

```
1:1,1
1:100,100
2:10,10,10

```

Then these two lines find the place where the length is different, and remove everything onwards:

```
s`^(.*\b(.+:).*)¶(?!\2).+
$1

```

The input becomes:

```
1:1,1
1:100,100

```

Then the numbers are removed by these two lines:

```
.+:
<empty-line>

```

Where the input becomes:

```
1,1
100,100

```
> 2 votes

# Answer
# , ~~70~~ 65 bytes

*Edit: -5 bytes thanks to Giuseppe*

```
function(x)(y=split(x,diffinv(!!diff(x))))[min(l<-lengths(y))==l]

```

Try it online!

This feels rather clunky, so I won't be surprised if there's a much slicker  way to do this... *Edit: there is...*

```
function(x)             # x is vector of values;
(y=                     # define y as
  split(x,              # groups of values of x that share the same
          cumsum(       # cumulative sum of
          x!=c(0,x))))  # 1 if different to the next element;
[                       # now, get element(s) of y
 (l=lengths(y))         # whose length(s)
        ==min(l[l>0])]  # equal the smallest non-zero lengths of y

```
> 2 votes

# Answer
# Jelly, ~~22~~ ~~17~~ 16 bytes

```
I0;œṗ¹L=¥ÐfL€Ṃ$$

```

Try it online!

```
I0;œṗ¹L=¥ÐfL€Ṃ$$     Main link. List: z = [a,b,c,...]

I                    Compute [b-a, c-b, d-c, ...]
 0;                  Concatenate 0 in front: [0, b-a, c-b, d-c, ...]
   œṗ                Split z where the corresponding item in the above array is not zero.
      L=¥Ðf          Filter sublists whose length equal:
           L€Ṃ$      the minimum length throughout the list.

     ¹         $     (grammar stuffs)

```
> 1 votes

# Answer
# MATL, 15 bytes

```
Y'tX<tb=bw)wTX"

```

Try it online

Input is a vector, like `[1 2 3 4]`, and output is a matrix where each column is one of the smallest groups, e.g.:

```
1 100
1 100

```

for the third test case.

Explanation:

```
Y'    %// Run length encoding, gives 2 vectors of group-lengths and values
t     %// Duplicate group lengths
X<    %// Minimum group length
tb    %// Duplicate and get vector of group lengths to the top
=     %// Find which group lengths are equal to the minimum
bw)   %// And get the values of those groups
wTX"  %// Repeats the matrix of minimum-length-group values by the minimum group length

```
> 1 votes

# Answer
# JavaScript (ES6), 106

```
a=>(a.map((v,i)=>v==a[i-1]?g.push(v):h.push(g=[v]),h=[]),h.filter(x=>!x[Math.min(...h.map(x=>x.length))]))

```

**Test**

```
f=a=>(a.map((v,i)=>v==a[i-1]?g.push(v):h.push(g=[v]),h=[]),h.filter(x=>!x[Math.min(...h.map(x=>x.length))]))

console.log=x=>O.textContent+=x+'\n'

;[[1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1]
, [3, 3, 3, 4, 4, 4, 4, 5, 5, 4, 4, 3, 3, 4, 4]
, [1, 1, 2, 2, 3, 3, 4]
, [1]
, [1, 1, 10, 10, 10, 100, 100]]
.forEach(t=>console.log(t+' -> '+f(t).join` `))
```

```
<pre id=O></pre>
```
> 1 votes

# Answer
## JavaScript (ES6), 113 bytes

```
a=>a.map(n=>n==c[0]?c.push(n):b.push(c=[n]),c=b=[])&&b.sort((a,b)=>a[l]-b[l],l='length').filter(e=>e[l]==b[0][l])

```
> 1 votes

# Answer
## APL, 25 chars

```
{z/⍨(⊢=⌊/)≢¨z←(1,2≠/⍵)⊂⍵}

```

In English:

* put in z the argument split where a number is different than the one preceding;
* compute the length of each subarray
* compare the minimum with each of the lengths producing a boolean...
* ... that is used to reduce z
> 1 votes

# Answer
# , 31 bytes

```
[:(#~[:(=<./)#@>)]<;.1~1,2~:/\]

```

Input is an array of values. Output is an array of boxed arrays.

## Usage

```
   f =: [:(#~[:(=<./)#@>)]<;.1~1,2~:/\]
   f 1 1 2 2 3 3 4
┌─┐
│4│
└─┘
   f 3 3 3 4 4 4 4 5 5 4 4 3 3 4 4
┌───┬───┬───┬───┐
│5 5│4 4│3 3│4 4│
└───┴───┴───┴───┘

```

## Explanation

```
[:(#~[:(=<./)#@>)]<;.1~1,2~:/\]  Input: s
                              ]  Identity function, get s
                         2       The constant 2
                             \   Operate on each overlapping sublist of size 2
                          ~:/      Check if each pair is unequal, 1 if true else 0
                       1,        Prepend a 1 to that list
                 ]               Identity function, get s
                  <;.1~          Using the list above, chop s at each true index
[:(             )                Operate on the sublists
             #@>                 Get the length of each sublist
     [:(    )                    Operate on the length of each sublist
         <./                     Get the minimum length
        =                        Mark each index as 1 if equal to the min length else 0
   #~                            Copy only the sublists with min length and return

```
> 1 votes

# Answer
## Clojure, 65 bytes

```
#(let[G(group-by count(partition-by + %))](G(apply min(keys G))))

```

Uses `+` as `identity` function as `(+ 5)` is 5 :) The rest should be obvious, `G` is a hash-map used as a function and given a key it returns the corresponding value.
> 1 votes

# Answer
# Brachylog, 6 bytes

```
ḅlᵒlᵍh

```

Try it online!

Input through the input variable and output through the output variable.

```
ḅ         The list of runs of consecutive equal elements of
          the input
 lᵒ       sorted by length
   lᵍ     and grouped by length
          has the output variable
     h    as its first element.

```

Although, unlike ,  groups non-consecutive equal elements, the `lᵒ` is still necessary to find the group with the shortest lengths, and it works because the order of groups in the output from  is determined by the position of the first element of each group, so that `ᵍhᵐ` could function as sort of a *deduplicate by* pseudo-metapredicate.
> 1 votes

# Answer
# Perl 5 `-MList::Util=pairkeys,min -a`, 69 bytes

```
map$r{y/ //}.="[ $_]",pairkeys"@F "=~/((\d+ )\2*)/g;say$r{min keys%r}

```

Try it online!
> 1 votes

# Answer
# Husk, 4 bytes

```
←kLg

```

Try it online!
> 1 votes

# Answer
# Jelly, 5 bytes

```
ŒgLÐṂ

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 5 bytes

```
γé¬gù

```

Try it online!

**Commented**:

```
γ      # split into chunks of equal adjacent elements
 é     # sort the chunks by length
  ¬    # get the shortest (first) chunk without popping the list
   g   # take the length of that chunk
    ù  # keep all chunks with this length

```

Try it with step-by-step output!
> 1 votes

# Answer
# Japt `-g`, 4 bytes

Outputs a 2D-array.

```
òÎüÊ

```

Try it

```
òÎüÊ     :Implicit input of array
ò        :Partition between elements where
 Î       :  The sign of their difference is truthy (not 0)
  ü      :Group and sort by
   Ê     :  Length
         :Implicit output of first element

```
> 1 votes

# Answer
# , 56 bytes

```
function(x,r=rle(x),l=min(r$l))lapply(r$v[r$l==l],rep,l)

```

Try it online!

-2 bytes thanks to Dominic van Essen. Uses `rle` and `rep` to collapse and reconstruct the array.
> 1 votes

# Answer
# K (ngn/k), 24 bytes

```
{{x=&/x:#'x}#(&~=':x)_x}

```

Try it online!

* `(&~=':x)_x` split the input on indices where the values change
* `{x=&/x:#'x}#` filter down to items of the minimum length
> 1 votes

# Answer
# Factor \+ `grouping.extras`, 36 bytes

```
[ [ ] group-by values all-shortest ]

```

Try it online!

* `[ ] group-by values` Split a sequence into groups of contiguous equal elements.
* `all-shortest` Take all the shortest groups.

`[ stable-slices all-shortest ]` would work except it doesn't have the right behavior for 1-element inputs.
> 1 votes

# Answer
# Nekomata, 2 bytes

```
ĉş

```

Attempt This Online!

```
ĉ       Split the input into chunks of equal elements
 ş      Find the shortest chunk

```
> 1 votes

# Answer
# JavaScript (Node.js), 97 bytes

```
x=>eval(`[[${x}]]`.replace(/\b(\d+),(?!\1\b)/g,'$1],[')).filter((t,_,x)=>!x.some(y=>t[y.length]))

```

Try it online!
> 1 votes

# Answer
# PowerShell for Windows, 88 bytes

```
$h=@{}
$args|%{$i+=$p-ne$_;$h.+$i+=,$p=$_}
($g=@($h|% v*|sort c*))|? c*t -eq $g[0].count

```

Try it online!

The script uses the Powershell alias `sort` that should be `sort-object` with Linux.

Less golfed:

```
$hashTable=@{}
$args|foreach-object{
    $i += ($prev -ne $_)
    $prev = $_
    $hashTable.+$i += ,$prev
}
$groups=@($hashTable|foreach-object Values|sort-object Count)
$groups|where-object count -eq $groups[0].count

```
> 0 votes

# Answer
# Arturo, 46 bytes

```
$=>[c:chunk&=>[&]select c=>[=size&size min c]]

```

Try it
> 0 votes

---
Tags: code-golf, number, array
---


title: The Jaccard Index

text:
# Question
Title: The Jaccard Index
The Jaccard index / similarity coefficient, also known as the Tanimoto index / coefficient, is a statistic used for gauging the similarity and diversity of finite sample sets. It was developed by Grove Karl Gilbert in 1884 for the field of weather forecasting \[1\] and later independently developed by Paul Jaccard \[2\] who was studying species of alpine plants. Finally, it was also formulated again by T. Tanimoto \[3\]. Overall, it is widely used in various fields where binary or binarized data are used. These include computer science, ecology, genomics, etc.

Mathematically speaking, it is defined as the size of the intersection divided by the size of the union of finite sample sets. Specifically, for two sets \\$A\\$ and \\$B\\$ it is defined as:

\\$J(A, B) = \frac{|A \bigcap B|}{|A\bigcup B|}\\$

It ranges from \\$0\<= J(A, B) \<=1\\$, where `0` is the case of the intersection between \\$A\\$ and \\$B\\$ being equal to the empty set.

# Challenge

Given two finite sets, containing positive or negative integers, calculate their Jaccard index. You may assume that at least one of the sets will be non-empty. This index is applied on mathematical sets, meaning that if your language of choice does not support sets, use any other data collection containing *unique* elements.

## Test cases

```
{1, 2}, {}                -> 0.0
{-7, 3, -9}, {9, 2, 3, 4} -> ~0.167
{1, 2, 3}, {2, 4, 6}      -> 0.2
{0, 64}, {0, 64, 89, 93}  -> 0.5
{6, 42, 7, 1}, {42, 7, 6} -> 0.75
{3, 6, 9}, {3, 6, 9}      -> 1.0

```

## Rules

# Answer
# APL(Dyalog Unicode), 5 bytes SBCS

```
∩÷⍥≢∪

```

Try it on APLgolf!

Input `A f B`
> 10 votes

# Answer
# MATL, 7 bytes

```
h8#uqYm

```

Try it at MATL online! Or verify all test cases.

### How it works

```
h     % Implicit inputs. Concatenate
8#u   % Number of occurrences of each unique value (will be 1 or 2)
q     % Subtract 1, element-wise
Ym    % Mean. Implicit display

```
> 7 votes

# Answer
# Vyxal, ~~8 7~~ 6 bytes

```
₍↔∪@÷/

```

Try it Online!

-1 thanks to TheThonnu, -1 thanks to Lyxal

```
₍↔∪@÷/  # implicit input of two lists
₍       # apply each to the stack, and wrap:
 ↔      #   intersection
  ∪     #   union
   @    # map each set to its size
    ÷   # dump list onto stack
     /  # divide

```
> 6 votes

# Answer
# Python 3, 28 bytes

```
lambda a,b:len(a&b)/len(a|b)

```

Try it online!

Simply uses the built-in python set operations
> 5 votes

# Answer
# , ~~15~~ 12 bytes

```
+/@e.%#@~.@,

```

Uses formal definition. -3 thanks to att.

Attempt This Online!

```
+/@e.%#@~.@,
           ,  NB. concat
        ~.@   NB. then uniquify
      #@      NB. then get size
   e.         NB. vectorized "is x in y"
+/@           NB. then sum the resulting boolean list to get size
     %        NB. division

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), ~~50~~ 30 bytes

```
Tr[1^(#⋂#2)]/Tr[1^(#⋃#2)]&

```

Try it online!

-20 thanks to *@att*
> 4 votes

# Answer
# K (ngn/k), ~~16~~ 13 bytes

-3 from @ovs's improvement

```
+/%/#:\2=#'=,

```

Try it online!

* `=,` group the concatenated inputs
* `2=` determine which elements in each input are present in both (1 if so, 0 otherwise)
* `+/%/#:\` calculate the average
> 4 votes

# Answer
# Arturo, ~~40~~ 35 bytes

```
$[a b]->//size a--a--b size b++a--b

```

Try it

Port of Neil's Charcoal answer.

`--` is set difference, `++` is concatenation, `size` is length, and `//` is float division.
> 4 votes

# Answer
# , 27 bytes

```
\(x,y)mean(table(c(x,y))-1)

```

Attempt This Online!
> 4 votes

# Answer
# Julia, 26 characters, 30 bytes

Correction from Ashlin Harris much appreciated.

```
n=length
A\B=n(A∩B)/n(A∪B)

```

Doesn't actually require A and B to be `Set` objects, as if they aren't it converts them anyway.
> 4 votes

# Answer
# JavaScript (ES6), 74 bytes

Expects two sets as `(a)(b)`.

There's unfortunately not any union nor intersection built-in in the current ECMAScript specification. :-/

```
a=>b=>new Set([...a,...b]).forEach(v=>k+=a.has(v)&b.has(v,n++),n=k=0)||k/n

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 8 bytes

```
Ãg¹²«Ùg/

```

Try it online!

#### Explanation

```
Ãg¹²«Ùg/  # Implicit input
 g        # Length of...
Ã         # ...intersection of inputs...
       /  # ...divided by...
      g   # ...length of...
  ¹²      # ...both inputs...
    «     # ...merged...
     Ù    # ...without duplicates
          # Implicit output

```
> 3 votes

# Answer
# Charcoal, 14 bytes

```
Ｉ∕Ｌ⁻θ⁻θηＬ⁺η⁻θη

```

Try it online! Link is to verbose version of code. Takes input as lists which the program assumes are unique. Explanation: Charcoal doesn't have set union or intersection but it can do set difference of two set-type lists, so I have to simulate intersection with double set difference and union by concatenation of set difference.

```
    θ           First input
   ⁻            Set difference with
      θ         First input
     ⁻          Set difference with
       η        Second input
  Ｌ             Take the length
 ∕              Divided by
            θ   First input
           ⁻    Set difference with
             η  Second input
         ⁺      Concatenated with
          η     Second input
        Ｌ       Take the length
Ｉ               Cast to string
                Implicitly print

```
> 3 votes

# Answer
# Nibbles, 6.5 bytes (13 nibbles)

```
,`&$_"/",`|$_

```

Outputs as a non-reduced fraction (one of the standard I/O methods, following the consensus that reducing fractions is optional unless specified).

```
,               # length of
 `&             # set intersection of
   $            # arg1 and
    _           # arg2;
     "/"        # the character "/";
        ,       # length of
         `|     # set union of
           $    # arg1 and
            _   # arg2;
                # concatenated into output

```

---

# Nibbles, 8 bytes (16 nibbles)

```
/*,`&$_100,`|$_

```

Outputs the Jaccard index truncated at two decimal places; the decimal point is omitted (so, equivalently, an integer representing 100x the Jaccard index).

```
/               # divide:
  ,             #   length of
   `&           #   set intersection of
     $          #   arg1 and
      _         #   arg2
 *     100      #   multiplied by 100
                # by:
          ,     #   length of
           `|   #   set union of
             $  #   arg1 and
              _ #   arg2

```

The choice of two decimal places (costing +2.5 bytes) here is arbitrary: if zero decimal places is acceptable (meaning that output can only be `1` or `0`), then the same approach could be only 5.5 bytes: `/,`&$_,`|$_`.
> 3 votes

# Answer
# Scala, 33 bytes

```
(a,b)=>((a&b).size+.0)/(a|b).size

```

Try it online!
> 3 votes

# Answer
# Lua, 106 bytes

```
load"i=0u=0g,h=...for k in next,g do i=h[k]and i+1or i h[k]=1 end for k in next,h do u=u+1 end return i/u"

```

Try it online!

Takes in tables that represent sets- This page should describe how they are formatted. Ungolfed version below.

```
function f(g,h)
    i=0 u=0                       -- Represents size of intersection and union
    for k in next,g do            -- For each element in set g
        i=h[k]and i+1or i         -- Increment i if k is in h
        h[k]=1                    -- Add k to set h
    end
    for k in next,h do            -- Counts elements in h (now union set)
        u=u+1
    end
    return i/u
end

```
> 3 votes

# Answer
# Raku, 19 characters/23 bytes

```
{($^a∩$^b)/($a∪$b)}

```

Straight out of the definition. Try it online!
> 3 votes

# Answer
# JavaScript, 65 bytes

```
a=>b=>a.filter(i=>b.includes(i)).length/new Set(a.concat(b)).size

```

Try it online!
> 3 votes

# Answer
# Pyt, 15 bytes

```
Á←ÁáĐỤ⇹ɔĐŁ⅟⇹⁻Ʃ*

```

Try it online!

```
Á                      implicit input; push contents of Árray to stack
 ←Á                    get input; push contents of Árray to stack
   á                   push contents of stack to árray
    Đ                  Đuplicate
     Ụ                 get Ụnique elements
      ⇹                swap
       ɔ               get ɔount how many times each unique element occurs in the combined list
        Đ              Đuplicate
         Ł             get Łength (size of union)
          ⅟            multiplicative inverse
           ⇹           swap
            ⁻          decrement each element
             Ʃ         sum (size of intersection)
              *        multiply

```
> 2 votes

# Answer
# Jelly, 7 bytes

```
f,œ|Ẉ÷/

```

Try it online!

## How it works

```
f,œ|Ẉ÷/ - Main link. Takes A on the left, B on the right
f       - Intersection of A and B
  œ|    - Set union of A and Q
 ,      - Pair
    Ẉ   - Lengths of each
      / - Reduce the length pair by:
     ÷  -   Division

```
> 2 votes

# Answer
# Factor \+ `math.unicode`, 37 bytes

```
[ 2dup ∩ length -rot ∪ length / ]

```

Try it online!

```
           ! { 1 2 3 } { 2 4 6 }
2dup       ! { 1 2 3 } { 2 4 6 } { 1 2 3 } { 2 4 6 }
∩          ! { 1 2 3 } { 2 4 6 } { 2 }
length     ! { 1 2 3 } { 2 4 6 } 1
-rot       ! 1 { 1 2 3 } { 2 4 6 }
∪          ! 1 { 1 2 3 4 6 }
length     ! 1 5
/          ! 1/5

```
> 2 votes

# Answer
# Pyth, 7 bytes

```
cl@FQls

```

Try it online!

### Explanation

```
cl@FQlsQ    # implicitly add Q
            # implicitly assign Q = eval(input())
c           # float division of
 l          # length of
  @FQ       # intersection of the two elements of Q
     l      # and the length of
      sQ    # union of the two elements of Q

```
> 2 votes

# Answer
# BQN, 10 bytes

```
(+´⊒÷·≠⍷)∾

```

Try it at BQN REPL

```
         ∾  # join L & R args together
(       )   # and apply this:
 +´         #   sum of
   ⊒        #   occurrence counts of each element
            #   (zero if one instance, one if two instances)
    ÷·      #   divided by
      ≠     #   length of
       ⍷    #   deduplicated elements

```
> 2 votes

# Answer
# Haskell, 43 bytes

```
a%b=1/(sum(1<$a++b)/sum[1|x<-a,elem x b]-1)

```

Try it online!

Haskell makes an interesting language for this challenge because it lacks sets or set operations like union barring a costly import. Also, it won't take the ratio of two lengths to make a real number without a costly type conversion.

The answer uses the formula \\$1/\left(\frac{\left| A \right| + \left| B \right|}{\left| A\cap B \right|} - 1 \right)\\$. The inputs are lists. Lengths are computed as `sum(1<$l)` which converts each element to 1 then takes the sum -- unlike `length`, this can produce a float because Haskell typechecks the literal `1` as a float here. The `sum(1<$a++b)` takes the length of the concatenation of the two inputs lists, which is the sum of their lengths.

The intersection uses a list comprehension to extract all elements of `a` that are also in `b`. Two more symmetric version of this are 1 byte longer:

```
a%b=1/(sum(1<$a++b)/sum[1|x<-a,y<-b,x==y]-1)
a%b=1/(sum(1<$a++b)/sum[1|0<-(-)<$>a<*>b]-1)

```

Importing `Data.List` comes out longer:

**53 bytes**

```
import Data.List
a%b=sum(1<$a++b)/sum(1<$nub(a++b))-1

```

Try it online!
> 2 votes

# Answer
# PowerShell Core, 49 bytes

```
param($a,$b)($c=$a+$b).Count/($c|sort|gu).Count-1

```

Try it online!

Takes two lists as parameters, returns a `double` or an `int32`.
Knowing that A and B are sets, I'm calculating the Jaccard index this way:

```
U = Size of the union of A and B with duplicates
D = Size of the union of A and B without duplicates
Jaccard Index = (U - D) / D
              = U / D - 1

```

## Explanation

```
param($a,$b)($c=$a+$b).Count/($c|sort|gu).Count-1  # Function body
param($a,$b)                                       # Declares the two parameters $a and $b
            ($c=$a+$b)                             # Concatenates the two input lists and keep the result in $c
                      .Count                       # Gets the size of the two set's union
                              $c|sort|gu           # Finds only the unique elements in the union
                             (          ).Count    # Calculates the size of the intersection
                            /                  -1  # Divides the size of the union by the size of the unique items and subtracts one

```
> 2 votes

# Answer
# Thunno 2, 6 bytes

```
çȯċḷẸ/

```

Attempt This Online!

#### Explanation

```
çȯċḷẸ/  # Implicit input
ç       # Apply two functions in parallel:
 ȯ      #  Set intersection
  ċ     #  Set union
   ḷ    # Length of each list
    Ẹ   # Dump onto stack
     /  # Divide
        # Implicit output

```
> 2 votes

# Answer
# Nekomata, 4 bytes

```
,Ţ←µ

```

Attempt This Online!

A port of @Luis Mendo's MATL answer.

```
,     Join
 Ţ    Tally (count occurrences of each unique element)
  ←   Decrement
   µ  Mean

```
> 2 votes

# Answer
# Japt, 10 bytes

```
fV Ê/UâV Ê

```

Try it

```
fV Ê/UâV Ê  # implicit input of two lists U, V
fV          # intersection of U and V
   Ê        # length
    /       # divided by
     UâV    # union of U and V
         Ê  # length

```

Just for fun:

# Japt v2.0a0, 12 bytes

```
£rYgâif¹ÊÃr÷

```

-3 thanks to Shaggy

Try it

```
£rYgâif¹ÊÃr÷ # implicit input of two lists in a list
£            # for each input:
 r           #   reduce the two lists by:
  Ygâif      #     index into [intersect, union] with the index
       ¹Ê    #   length
         Ãr÷ # reduce by division

```
> 1 votes

# Answer
# Go (using `golang.org/x/exp/slices`), ~~170~~ 168 bytes

```
import."golang.org/x/exp/slices"
func f(a[]int,b[]int)float64{i,j:=0.,0.
for _,x:=range a{if Contains(b,x){i++}
j++}
for _,y:=range b{if!Contains(a,y){j++}}
return i/j}

```

Attempt This Online!

Go has *literally* no built-ins (including `Contains`) so we have to implement set union and intersection ourselves.

*-2 thanks to @code*

#### Commented

```
import ."golang.org/x/exp/slices"   // Import the module we need to get Contains
func f(a []int, b []int) float64 {  // Define a function, f, taking two lists of ints,
                                    // a and b, and returning a float
  i, j := 0., 0.                    // Initialise i (Intersection length) and j (Union length) to 0.0
  for _, x := range a {             // Loop through each x in a:
    if Contains(b, x) {             //  If x is in b:
      i++ }                         //   Increment i
    j++ }                           //  Increment j
  for _, y := range b {             // Loop through each y in b:
    if ! Contains (a, y) {          //  If y is not in b:
      j++ } }                       //   Increment j
  return i / j }                    // Return the Jacard index

```
> 1 votes

# Answer
# Excel, 72 bytes

```
=LET(x,VSTACK(A1#,B1#),(COUNT(x)-COUNT(UNIQUE(x,,1)))/ROWS(UNIQUE(x))/2)

```

where `A1#` and `B1#` are vertical spilled ranges containing the elements of each set.
> 1 votes

# Answer
# MathGolf, 11 bytes

```
+h\▀£_@-²√╠

```

Try it online.

**Explanation:**

```
+           # Merge the two (implicit) input-lists together
 h          # Push the total length (without popping the list)
  \         # Swap so the list is at the top of the stack again
   ▀        # Uniquify it
    £       # Pop and push the length
     _      # Duplicate this union-length
      @     # Triple-swap the stack
       -    # Subtract the union-length from the total length to get the amount of
            # items that are in both input-lists
        ²√  # Convert it to a float, by taking the square-root of its square
            # (otherwise division builtins would be integer-division)
          ╠ # Divide this top float by the duplicated union-length
            # (after which the entire stack is output implicitly as result)

```
> 1 votes

# Answer
# PHP, 80 bytes

```
fn($a,$b)=>count(array_intersect($a,$b))/count(array_unique(array_merge($a,$b)))

```

Try it online!

First attempt, naive implementation, wasted by all these `array_` prefixes (sigh)
> 1 votes

# Answer
# Desmos, 75 bytes

```
f(A,B)=[0^{(i-join(e,B))^2}.maxfori=A.unique].total/join(A,B).unique.length

```

Thank god Desmos has a `unique` function... It is very unfortunate that Desmos doesn't have any set functions like union or intersection though.

Keep in mind that this would only work if the lists contain integers. Specifically, if the first inputted list has the value `e` in it, then the output would most likely be wrong.

Try It On Desmos!

Try It On Desmos! - Prettified

I also had an attempt where I tried to factor out a `x.unique.length` call from both the numerator and denominator, but that came out a few bytes longer at 81 bytes:

```
f(A,B)=U(A[[(i-join(e,B))^2.minfori=A.sort]=0])/U(join(A,B))
U(x)=x.unique.length

```
> 1 votes

# Answer
# J-uby, 18 bytes

```
:+@**:fdiv%[:&,:|]

```

Attempt This Online!

(This uses an older version of J-uby due to the missing `**` operator in the current version, hence the long prelude on ATO.)
> 1 votes

# Answer
# JavaScript (Node.js), 61 bytes

```
a=>b=>[...a,...b].sort().map(x=>a===(a=x)?++A:++B,A=B=0)&&A/B

```

Try it online!

# JavaScript (Node.js), 67 bytes

```
a=>b=>[...a,...b].sort().map((x,i,b)=>x==b[i+1]?++A:++B,A=B=0)&&A/B

```

Try it online!

No set operation
> 1 votes

---
Tags: code-golf, math, array, set-theory
---