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\$
  • \$\begingroup\$ Please, someone make something visual. That's what hypercubes are for \$\endgroup\$ – Martijn Jan 19 '16 at 12:25
  • \$\begingroup\$ you said but you may use. Did you mean you may use or you may not use? \$\endgroup\$ – Blue Jan 19 '16 at 12:26
  • \$\begingroup\$ functions like permute/cartesian product are allowed. \$\endgroup\$ – helloworld922 Jan 19 '16 at 21:39
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\$

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.