14
\$\begingroup\$

Challenge

Given the Cartesian coordinates of two or more distinct points in Euclidean n-space (\$\mathbb{R}^n\$), output the minimum dimension of a flat (affine) subspace that contains those points, that is 1 for a line, 2 for a plane, and so on.

For example, in 3-space (the 3-dimensional world we live in), there are a few possibilities:

  1. The points are not coplanar, e.g. (0,0,0),(0,0,1),(0,1,0),(1,0,0). The full 3 dimensions would be needed to describe the points, so the output would be 3
  2. The points are coplanar but not all collinear, e.g. (0,0,0),(1,0,0),(0,1,0),(1,1,0). The points lie on a 2-dimensional surface (a plane), so the output would be 2.
  3. The points are collinear, and there is more than one, e.g. (0,0,0),(1,0,0). They all lie on a line (1-dimensional), so the output is 1.
  4. One or zero points are given. You do not have to handle these degenerate cases.

As @user202729 pointed out in sandbox, this is equivalent to the rank of the matrix whose column vectors are the given points if one of the points is the zero vector.

I encourage upvoting answers that don't have built-ins do most of the work, but they are valid answers.

Details

  1. The coordinates of each point will always be integers, so errors due to excessive floating-point roundoff are not acceptable
  2. Again, you do not have to handle fewer than 2 points
  3. The dimension n will be at least 2
  4. The set of points can be taken in any format that encodes equivalent information to a list of n-tuples. Your program/function may also take n as input if you desire.
  5. Note that the subspace may not necessarily pass through the origin*
  6. This is , so shortest bytes wins

*Mathematically, if we require the subspace to pass through the origin, then it would be more specifically called a "linear subspace", not just flat.

Testcases

n points -> output
2 (1,0),(0,0) -> 1
2 (0,1),(0,0) -> 1
2 (6,6),(0,-2),(15,18),(12,14) -> 1
2 (0,0),(250,500),(100001,200002) -> 1
2 (0,0),(250,500),(100001,200003) -> 2
2 (3,0),(1,1),(1,0) -> 2
3 (0,0,0),(0,0,1),(0,1,0),(1,0,0) -> 3
3 (0,0,0),(1,0,0),(0,1,0),(1,1,0) -> 2
3 (0,0,0),(1,0,0) -> 1
4 (1,2,3,4),(2,3,4,5),(4,5,6,7),(4,4,4,4),(3,3,3,3),(2,2,2,2) -> 2
5 (5,5,5,5,5),(5,5,6,5,5),(5,6,5,5,5),(6,5,5,5,5),(5,4,3,2,1) -> 4

Related Challenges:

\$\endgroup\$
  • \$\begingroup\$ Is it possible for the input to be something like (1,3),(1,3) so the output is 0? \$\endgroup\$ – Luis Mendo Jul 13 at 17:16
  • \$\begingroup\$ …set of at least two distinct points… \$\endgroup\$ – fireflame241 Jul 13 at 17:18
  • \$\begingroup\$ Ah, I see, thanks \$\endgroup\$ – Luis Mendo Jul 13 at 17:23
  • 2
    \$\begingroup\$ @Shaggy This task does not consist of implementing a single algorithm, and there's already broad examples. Do you need more? \$\endgroup\$ – fireflame241 Jul 13 at 20:38
  • 6
    \$\begingroup\$ I am curious as to why this has been flagged as unclear. It seems all clear to me. \$\endgroup\$ – Wheat Wizard Jul 13 at 21:34
4
\$\begingroup\$

Wolfram Language (Mathematica), 23 bytes

MatrixRank@*Differences

Try it online!

Alternative: (23 bytes, 21 characters)

MatrixRank[#&@@#-#]&

Try it online!

SingularValueDecomposition in Mathematica is already 26 bytes long.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

MATL, 12 bytes

t1Y)-X$&Yvoz

Input is a matrix, where each row defines a point.

Try it online! Or verify all test cases.

Explanation

The code uses the singular value decomposition of a matrix, which is done symbolically to prevent floating-point issues. The rank of a matrix equals the number of non-zero singular values.

t      % Implicit input: matrix of integer values. Duplicate
1Y)    % Get the first row
-      % Subtract, with broadcast. This subtracts this row from each row
X$     % Convert to symbolic matrix. Note that integers, are represented
       % exactly as floating-point values up to ±2^53.
&Yv    % Single-output singular value decomposition. Gives a vector with
       % the singular values
o      % Convert to floating point. Note that 0 is represented exactly
       % as a floating-point value
z      % Number of nonzeros. Implicit output
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What are the errors in the all-test-cases link? \$\endgroup\$ – fireflame241 Jul 13 at 17:35
  • \$\begingroup\$ The code for testing all cases uses an infinite loop that keeps taking an input and producing an output. When there are no more inputs an error is produced. (This is allowed, and anyway it only affects the modified code that checks all test cases) \$\endgroup\$ – Luis Mendo Jul 13 at 17:38
2
\$\begingroup\$

APL (Dyalog Unicode), 17 bytes

≢⍸1≠1+2⊃8415⌶2-⌿⎕

Try it online!

Happens to be a mix of existing MATL and Mathematica solutions. Performs Singular Value Decomposition on pairwise differences of the rows, and counts nonzero eigenvalues in the result of SVD. Since APL does not have symbolic computation, we use "significantly different from zero" test instead.

How it works

≢⍸1≠1+2⊃8415⌶2-⌿⎕
             2-⌿⎕  ⍝ Pairwise row differences of the input
      2⊃8415⌶      ⍝ The second matrix (diagonal matrix of eigenvalues) in SVD
  1≠1+             ⍝ Check if each number is significantly different from zero
≢⍸                 ⍝ Count ones
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Julia 0.7, 18 bytes

m->rank(m.-m[:,1])

Try it online!

Analogous approach in R is slightly longer (3 bytes saved by Giuseppe):

R, 27 24 bytes

function(m)qr(m-m[,1])$r

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ qr()$r is 3 bytes shorter. \$\endgroup\$ – Giuseppe Jul 14 at 13:04
  • \$\begingroup\$ Uh, I can't understand why I keep forgetting to try partial names instead of full ones... Thanks! \$\endgroup\$ – Kirill L. Jul 14 at 13:39
2
\$\begingroup\$

JavaScript (ES6), 187 bytes

There's probably a much shorter way. This is using the matrix rank method.

m=>m[m=m.map(r=>r.map((v,i)=>v-m[0][i])),n=0].map((_,i)=>(R=m.find((r,k)=>r[i]&&r[j=~k]^(r[j]=1)))&&m.map(r=>++j*r[i]&&R.map((v,k)=>r[k]-=k>i&&v*r[i]),n++,R=R.map((v,k)=>k>i?v/R[i]:v)))|n

Try it online!

| improve this answer | |
\$\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.