7
\$\begingroup\$

Your goal is to output all the "sides" (corners, edges, faces, etc.) of an N-dimensional unit hypercube, where N is non-negative. A "side" is defined as any (N-M)-dimension surface embedded in N-dimensional space, where 1 <= M <= N.

The hypercube spans the space [0, 1] in each dimension. For example, for N=2 the square is bounded by the corner points (0, 0) and (1, 1).

Input

Your function/program should take a single non-negative integer N. You may assume N <= 10.

Outputs

The output may be to any convenient format desired: return a list, print to stdio/file, output parameters, etc.

The output must contain the min/max bounds of all unique sides. Order does not matter.

Example sides formats

A 0D side (a.k.a. a point) in 3D space could be bounded by:

# in [(min0, max0),...] format, this is the point 0,1,0 [(0, 0), (1, 1), (0, 0)] 

A 1D side (a.k.a. an edge) in 2D space could be bounded by:

# in [(min0, min1,...), (max0, max1,...)] format, this is the line from point (0,0) to (1,0) [(0, 0), (1, 0)] 

Note that it is ok to flatten the output any way you want ([min0, max0, min1, max1, ...] or [min0, min1, min2, ..., max0, max1, max2, ...], etc.)

Wikipedia has a list of the number of sides to expect for various hypercubes. In total, there should be 3N-1 results.

Full sample outputs

This uses the convention [min0, max0, min1, max1, ...]

N = 0

empty list (or no output) 

N = 1

[0, 0] [1, 1] 

N = 2

[0, 1, 0, 0] [0, 0, 0, 1] [0, 1, 1, 1] [1, 1, 0, 1] [0, 0, 0, 0] [0, 0, 1, 1] [1, 1, 0, 0] [1, 1, 1, 1] 

N = 3

[0, 1, 0, 1, 0, 0] [0, 1, 0, 0, 0, 1] [0, 0, 0, 1, 0, 1] [0, 1, 0, 1, 1, 1] [0, 1, 1, 1, 0, 1] [1, 1, 0, 1, 0, 1] [0, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0] [0, 0, 0, 0, 0, 1] [0, 1, 0, 0, 1, 1] [0, 1, 1, 1, 0, 0] [0, 0, 0, 1, 1, 1] [0, 0, 1, 1, 0, 1] [1, 1, 0, 1, 0, 0] [1, 1, 0, 0, 0, 1] [0, 1, 1, 1, 1, 1] [1, 1, 0, 1, 1, 1] [1, 1, 1, 1, 0, 1] [0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1] [0, 0, 1, 1, 0, 0] [1, 1, 0, 0, 0, 0] [0, 0, 1, 1, 1, 1] [1, 1, 0, 0, 1, 1] [1, 1, 1, 1, 0, 0] [1, 1, 1, 1, 1, 1] 

Scoring

This is code golf; shortest code wins. Standard loop-holes apply. You may use built-in functions like "permute a sequence" so long as it wasn't designed specifically for this problem.

Your code should run in a reasonable amount of time for N <= 6 (say, 10 minutes or less)

\$\endgroup\$
3
  • \$\begingroup\$ Please, someone make something visual. That's what hypercubes are for \$\endgroup\$ Commented Jan 19, 2016 at 12:25
  • \$\begingroup\$ you said but you may use. Did you mean you may use or you may not use? \$\endgroup\$ Commented Jan 19, 2016 at 12:26
  • \$\begingroup\$ functions like permute/cartesian product are allowed. \$\endgroup\$ Commented Jan 19, 2016 at 21:39

5 Answers 5

5
\$\begingroup\$

Pyth, 10 chars

P^cj49J2JQ 

Try it here. Output is a list of sides each in the format. [[min0, max0],[min1, max1],...].

P All but the last element of ^ Q the nth cartesian power of j49J2 the number 49 as a binary list [1,1,0,0,0,1] c J split into chunks of 2 [[1,1],[0,0],[0,1]] 

In our output, we want all lists of n elements from [[1,1],[0,0],[0,1]], except the one with only [0,1]'s. This is just the nth cartesian power of [[1,1],[0,0],[0,1]] with the last element removed.

The list [[1,1],[0,0],[0,1]] is created by converting 49 into binary and breaking into chunks of 2. One can do .CU2 2 to get [[0,0],[0,1],[1,1] as all sorted sublists of 2 elements from [0,1], but we need [0,1] at the start or end to remove the list with only it from the product.

\$\endgroup\$
4
\$\begingroup\$

CJam (13 bytes)

49Yb2/rim*);` 

Online demo

Output format is as a list of list of ranges: e.g. for input 1 (where the two sides are the points (0, 0) and (1, 1)) the output is [[[1 1]] [[0 0]]].

Dissection

49Yb2/ e# Generate the list of ranges: [[1 1] [0 0] [0 1]] rim* e# Take the nth Cartesian power ); e# Remove the last one, which is the full hypercube ` e# Format for output 
\$\endgroup\$
3
\$\begingroup\$

Ruby, 66 63

Returns an array of strings, each one containing 2n 0s and 1s without separators.

->n{(0..3**n-2).map{|i|s="" n.times{s+="0011"[-i%3,2];i/=3} s}} 

In a similar way to at at least one other answer it generates all possibilities of ["00","11","01"] repeated n times, except "0101....0101", by iterating through all the n-digit base 3 numbers 00..00 to 22..21 (deliberately missing 22..22) and then substituting. Initially I had the string "011101" ("01" had to be at the end) but then I realised if I fed -i instead of i to the %3 operation, I could swap the 2 and 1. I was then able to reduce the string to "0011", overlapping the three possible 2-character strings I required.

Ungolfed in test program

f=->n{ (0..3**n-2).map{|i| #iterate through all n-digit base 3 numbers 00..00 to 22..21 s="" n.times{ #for each base 3 digit in i append the following to s s+="0011"[-i%3,2] #0 --> 0 -->"00"; -1 --> 2 --> "11"; -2 --> 1 --> "01" i/=3 #divide by 3 to remove the last base 3 digit from i } s #add s to the array being built by map. } } puts f[gets.to_i] 

Output n=2

0000 1100 0100 0011 1111 0111 0001 1101 
\$\endgroup\$
2
\$\begingroup\$

CJam, 24 bytes

2ri2*m*{2/__:$=\2,a-*},p 

Uses the same interleaved [min0 max0 min1 max1 ...] format as the test cases in the challenge. It solves N = 10 in a couple of minutes.

Test it here.

Explanation

2 e# Push a 2. ri e# Read input and convert to integer N. 2* e# Multiply by 2. m* e# Get all 2N-tuples consisting of 0 and 1 as potential sides. A tuple is a valid e# side if a) all of its min/max pairs are sorted and b) not all of them are [0 1], e# because that corresponds to the entire N-dimensional hypercube. { e# Filter the tuples... 2/ e# Split the tuple into min/max pairs. __ e# Make two copies. :$ e# Sort each pair in the second copy. = e# Check for equality with the first copy. \ e# Swap with the original list of pairs. 2,a- e# Remove all [0 1]. * e# Repeat this array 0 or 1 times depending on the first result. This effectively e# computes the logical AND of two truthy/falsy values. }, p e# Pretty-print the list of sides. 
\$\endgroup\$
0
\$\begingroup\$

ES7, 88 bytes

n=>[...Array(3**n-1)].map((_,i)=>[...(3**n+i).toString(3).slice(1)].map(x=>[x%2,+!!x])) 

Turns out I ended up porting the Ruby solution, except I return a list of an array of a pair of bounds for each dimension, since that makes for the shortest code.

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