9
\$\begingroup\$

This challenge is a riff on Dion's challenge "Is this a rectangle?". The goal of this challenge is to write a program to decide whether or not some collection of tuples of integers represents a hypercube of some dimension.

Background

A hypercube is a generalization of a square.

  • A \$0\$-cube is a single point.
  • A \$1\$-cube is a line segment.
  • A \$2\$-cube is a square.
  • A \$3\$-cube is an ordinary cube.
  • An \$n\$-cube is a connected geometric object consisting of pairs of parallel line segments, perpendicular to each other and of the same length.

Example

For example, if you are given the input \$\{(0, 4, 0, 9), (2, 2, -4, 9), (-2, 0, -6, 9), (-4, 2, -2, 9)\}\$, then you should return a truthy value because these four points define a \$2\$-cube (a square).

You are allowed to input the data in any reasonable format—but the computation needs to work regardless of the input order of the points.

An \$n\$ cube has \$2^n\$ vertices, so if the list of numbers does not contain \$2^n\$ numbers, you must return a falsey value.

Challenge

This is a challenge, so shortest code wins.

Test data

Cubes:

[(1,9,7,7)]
[(1),(2)]
[(9,1,9),(1,2,9)]
[(0,0,5),(0,1,5),(1,0,5),(1,1,5)]
[(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)]
[(0,0,0),(0,3,4),(0,-4,3),(0,-1,7),(5,0,0),(5,3,4),(5,-4,3),(5,-1,7)]

Non-cubes:

[(1,0,0),(0,1,0),(0,0,1),(1,1,1)]
[(0,0,0),(0,0,1),(0,1,0),(1,0,0)]
[(1,0,0),(0,1,0),(0,0,1)]
[(1,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,1,1,1)]

If you'd like more test data, or if you'd like to suggest more test data, let me know.

\$\endgroup\$
  • \$\begingroup\$ In the first paragraph one can read "to decide whether or some" \$\endgroup\$ – RGS May 12 at 6:32
  • \$\begingroup\$ Are you sure [(0,4,0),(0,1,1),(1,0,1),(1,1,1)] is a cube? \$\endgroup\$ – Adám May 12 at 7:24
  • \$\begingroup\$ May we assume that all points have the same number of coordinates? \$\endgroup\$ – Adám May 12 at 7:33
  • \$\begingroup\$ @Adám, yes, all points have the same number of coordinates. \$\endgroup\$ – Peter Kagey May 12 at 7:59
  • 1
    \$\begingroup\$ Will the input points be distinct? \$\endgroup\$ – xnor May 12 at 8:35
4
\$\begingroup\$

APL (Dyalog Unicode), 44 bytes

{≡/((÷∘⊃⍨1↓⍋⌷¨⊂)⍤1∘.(+.×⍨-)⍨)¨⍵(,⍳2⍴⍨⌊2⍟≢⍵)}

Try it online!

the argument is a vector of coordinate vectors

,⍳2⍴⍨⌊2⍟≢⍵ build a hypercube as the cartesian product \$\{0,1\}^{\left\lfloor \log_2\left|\omega\right|\right\rfloor}\$

≡/(f)¨⍵(..) evaluate f for and the 01 hypercube, and test if they match

∘.(+.×⍨-)⍨ matrix of pairwise distances

(÷∘⊃⍨1↓⍋⌷¨⊂)⍤1 sort each row and divide by its second element

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

Python, 262 \$\cdots\$ 305 303 bytes

Saved a whopping 19 bytes thanks to dingledooper!!!

Added 118 bytes to fix a bug kindly pointed out by xnor, Peter Kagey and l4m2.

lambda l,R=range,L=len:(n:=L(l))<2or(d:=L(bin(n))-3)and(p:=sorted([sum((x-y)**2for x,y in zip(i,j))for i in l for j in l]))==[i*p[n]for i in R(d+2)for _ in R(2**d*math.comb(d,i))]and(K:=R(L(l[0])))and L({sum(([sum(l[i][j]for i in R(n))for j in K][j]-n*l[i][j])**2for j in K)for i in R(n)})<2
import math

Try it online!

Inputs a list of points and returns True/False.

How

Calculates the square of the distances between all possible pairs of points (including self-pairs and both \$(p_i,p_j)\$ and \$(p_j,p_i)\$ for all points \$p_j\$ and \$p_i\$ where \$i\neq j\$) and normalises them by the smallest non-zero square distance. For an \$n\$-cube we should then see a pattern of integers \$i = 0,1,\dots, n\$ each occurring \$2^{n}{n\choose i}\$ times. This corresponds with the \$0\$s for all the self-pairs, and the square of the lengths of all the sides being \$a^2\$, and the square of the lengths of all the diagonals being \$2a^2, 3a^2,\dots, na^2\$.

Correction

Also checks that the given vertices are all equidistant from the centre of mass.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I feel like this should work and not give false positives, but I don't see how to prove it. The multiset of distances doesn't always determine the set of points. In one dimension, I found that [0, 1, 3, 3, 7, 8] and [0, 1, 1, 4, 6, 8] have the same multiset of pairwise distances even though they are not translations or reflections of each other. But it feels like the distances of vertices in a cube constraints it in a more structured way. \$\endgroup\$ – xnor May 12 at 20:57
  • 2
    \$\begingroup\$ I think the points \$\{(0,0,0), (1,0,0), (\frac 12, \frac{\sqrt{3}}{2}, 0), (\frac 12, \frac{\sqrt{3}}{2}, 1)\}\$ meet this criteria but don't form a square. I'll see if I can rotate and scale this to make it fit on the integer lattice. \$\endgroup\$ – Peter Kagey May 13 at 2:06
  • 3
    \$\begingroup\$ @PeterKagey So after rotation it's [(1,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,1,1,1)] \$\endgroup\$ – l4m2 May 13 at 3:42
  • \$\begingroup\$ @l4m2, thanks! I added a new test case to reflect this. \$\endgroup\$ – Peter Kagey May 13 at 5:04
  • \$\begingroup\$ @PeterKagey Thanks - have added a correction. \$\endgroup\$ – Noodle9 May 13 at 8:40
2
\$\begingroup\$

Python 3, 339 338

lambda P:1==L(P)or P in map(g,permutations(P))
from itertools import*
L=len
Z=zip
D=lambda a,b:sum(x*y for x,y in Z(a,b))
def g(Q):B=[[x-y for x,y in Z(p,Q[0])]for p in Q[3-L(bin(L(Q))):]];return any(D(a,b)or D(a,a)-D(b,b)for a,b in combinations(B,2))or{tuple(x+sum(y)for x,y in Z(Q[0],Z(*C)))for C in product(*[(p,(0,)*L(p))for p in B])}

Try it online!

Takes a set of points as input.

Pseudocode explanation:

def f(points):
    let n = log_2(|points|)
    for each permutation Q of the points:
        let q be the first point in Q
        let B be the following n points, with q subtracted from each
        if all pairs of points in B are orthogonal and have equal magnitude:
            let S be the set of points which can be obtained by summing q and any subset of B
            if S == points: return True
    return False

Can definitely be golfed further but it's bedtime.

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

JavaScript (Node.js), 258 bytes

x=>(q=(x,z)=>g=x.flatMap(a=>x.map(b=>z*a.reduce((s,v,i)=>s+(v-b[i])**2,0))).sort((a,b)=>b-a))([...x,x[0].map((_,i)=>x.reduce((s,v)=>s+v[i],P=0)/(K=x.length))],K)+''==q([x.slice(D=~Math.log2(K)).map(_=>!P++||.5),...x.map(_=>[...(K++).toString(2)])],g[0]/~D|0)

Try it online!

Similar to Noodle9's answer, but generate another square to compare rather than use formula and add midpoint like normal ones

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Error like Noodle9's answer \$\endgroup\$ – l4m2 May 13 at 3:43
  • \$\begingroup\$ I added a new test case to reflect this. \$\endgroup\$ – Peter Kagey May 13 at 5:04
0
\$\begingroup\$

JavaScript (Node.js), 182 bytes

x=>(g=(q=(x,z)=>x.flatMap(a=>x.flatMap(c=>x.map(b=>z*a.reduce((s,v,i)=>s+(v-b[i])**2+(v-c[i])**2,0)))).sort((a,b)=>a-b))(x,K=x.length))+''==q(x.map(_=>[...(K++).toString(2)]),g[K]|0)

Try it online!

Check sums of length squares of A-B-C, where A,B,C can be same

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