Is this a cube?

Question

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

Answer 1

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

Answer 2

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.

Answer 3

Python 3, ³³⁹ 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.

Answer 4

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

Answer 5

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

Answer 6

Haskell, 139 bytes

import Data.List
import Data.List.Ordered
c p=has[(2^n,n*2^n)|n<-[0..]](length p,length$group(sort[sum$(^2)<$>zipWith(-)x y|x<-p,y<-p])!!1)

Try it online!