# Is this a cube?

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.

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

# 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

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

• 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.
– xnor
May 12, 2020 at 20:57
• 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. May 13, 2020 at 2:06
• @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)]
– l4m2
May 13, 2020 at 3:42
• @l4m2, thanks! I added a new test case to reflect this. May 13, 2020 at 5:04
• @PeterKagey Thanks - have added a correction. May 13, 2020 at 8:40

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

# 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

– l4m2
May 13, 2020 at 3:43
• I added a new test case to reflect this. May 13, 2020 at 5:04

# 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

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!