11
\$\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.

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

6 Answers 6

Reset to default
5
\$\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\$
7
  • \$\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\$ Commented May 12, 2020 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\$ Commented May 13, 2020 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\$ Commented May 13, 2020 at 3:42
  • \$\begingroup\$ @l4m2, thanks! I added a new test case to reflect this. \$\endgroup\$ Commented May 13, 2020 at 5:04
  • \$\begingroup\$ @PeterKagey Thanks - have added a correction. \$\endgroup\$ Commented May 13, 2020 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\$
2
  • \$\begingroup\$ Error like Noodle9's answer \$\endgroup\$ Commented May 13, 2020 at 3:43
  • \$\begingroup\$ I added a new test case to reflect this. \$\endgroup\$ Commented May 13, 2020 at 5:04
1
\$\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\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.