Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Write a function or program that outputs the number of each type of element (vertex, edge, face, etc.) of an N-dimensional hypercube.

As an example, the 3 dimensional cube has 1 cell (i.e. 1 3-dimensional cube), 6 faces (i.e. 6 2-dimensional cubes), 12 edges (i.e. 12 2-dimensional cubes) and 8 vertices (i.e. 8 0-dimensional cubes).

More details about Hypercube elements can be found here

You can as well take a look at the following OEIS sequence.

Input

Your code will take as input (via STDIN or a function parameter or similar things) an integer greater or equal to 0, which is the dimension of the hypercube.

Your code has to theoretically work for any input >= 0, disregarding memory and time issues (that is, speed and potential stack overflows are not a problem for your answer if the input is big). Inputs given as test cases will not be above 12.

Output

You will ouput a list of all elements of the hypercube, starting with the "highest dimension" element. For example, for a cube (input = 3), you will output the list [1,6,12,8] (1 cell, 6 faces, 12 edges, 8 vertices).

The format of the list in the output is relatively free, as long as it looks like a list.

You can output the result to STDOUT or return it from a function.

Test cases

Input = 0
Output = [1]

Input = 1
Output = [1,2]

Input = 3
Output = [1,6,12,8]

Input = 10
Output = [1, 20, 180, 960, 3360, 8064, 13440, 15360, 11520, 5120, 1024]

Input = 12
Output = [1, 24, 264, 1760, 7920, 25344, 59136, 101376, 126720, 112640, 67584, 24576, 4096]

Scoring

This is , so the shortest answer in bytes wins.

share|improve this question

15 Answers 15

up vote 10 down vote accepted

Samau, 8 5 bytes

Saved 3 bytes thanks to Dennis.

▌2/$ⁿ

Hex dump (Samau uses CP737 encoding):

dd 32 2f 24 fc

Explanation:

▌        read a number
 2/      push the array [1 2]
   $     swap
    ⁿ    take the convolution power

Convolving two vectors is equivalent to multiplying two polynomials. Similarly, taking the n-th convolution power is equivalent to taking the n-th power of a polynomial.

share|improve this answer

J, 13 bytes

[:p.2&^;$&_.5

Inspired by @alephalpha's PARI/GP answer. Try it online with J.js.

Background

By the binomial theorem,

formula

Thus, the output for input n consist precisely of the coefficients of the above polynomial.

Code

[:p.2&^;$&_.5  Monadic verb. Argument: n

        $&_.5  Yield an array of n instances of -0.5.
    2&^        Compute 2^n.
       ;       Link the results to the left and right.
               This specifies a polynomial of n roots (all -0.5)
               with leading term 2^n.  
[:p.           Convert from roots to coefficients.
share|improve this answer

MATL, 8 bytes

1i:"2:X+

Inspired by @alephalpha's PARI/GP answer.

Try it online! (uses Y+ for modern day MATL)

How it works

1        % Push 1.
 i:      % Push [1 ... input].
   "     % Begin for-each loop:
    2:   %   Push [1 2].
      X+ %   Take the convolution product of the bottom-most stack item and [1 2].
share|improve this answer
5  
My first MATL answer. – Dennis Jan 31 at 14:23
    
And an excellent one! It's such an honour that you used this language :-) – Luis Mendo Jan 31 at 16:43
1  
Beautiful. Everyone's starting to jump on the MATL bandwagon now! – rayryeng Jan 31 at 16:51
    
@rayryeng We miss you :-) – Luis Mendo Jan 31 at 17:55

MATL, 12 bytes

Q:q"H@^G@Xn*

Try it online

Explanation

         % implicit: input number "n"
Q:q      % generate array[0,1,...,n]
"        % for each element "m" from that array
  H@^    % compute 2^m
  G      % push n
  @      % push m
  Xn     % compute n choose m
  *      % multiply
         % implicit: close loop and display stack contents
share|improve this answer

Mathematica, 29 bytes

CoefficientList[(1+2x)^#,x]&

My first Mathematica answer! This is a pure function that uses the same approach as Alephalpha's PARI/GP answer. We construct the polynomial (1+2x)^n and get the list of coefficients, listed in order of ascending power (i.e. constant first).

Example usage:

> F := CoefficientList[(1+2x)^#,x]&`
> F[10]
{1,20,180,960,3360,8064,13440,15360,11520,5120,1024}
share|improve this answer

PARI/GP, 20 15 bytes

n->Vec((x+2)^n)
share|improve this answer

APL, 15 11 bytes

1,(2*⍳)×⍳!⊢

This is a monadic function train that accepts an integer on the right and returns an integer array.

Explanation, calling the input n:

        ⍳!⊢  ⍝ Get n choose m for each m from 1 to n
       ×     ⍝ Multiply elementwise by
  (2*⍳)      ⍝ 2^m for m from 1 to n
1,           ⍝ Tack 1 onto the front to cover the m=0 case

Try it online

Saved 4 bytes thanks to Dennis!

share|improve this answer

Jelly, 8 bytes

0rð2*×c@

I should really stop writing Jelly on my phone.

0r            Helper link. Input is n, inclusive range from 0 to n. Call the result r.
  ð           Start a new, dyadic link. Input is r, n.
   2*         Vectorized 2 to the power of r
     ×c@      Vectorized multiply by n nCr r. @ switches argument order.

Try it here.

share|improve this answer

TI-BASIC, 10 bytes

3^Ansbinompdf(Ans,2/3
share|improve this answer
    
I think this is one of the more interesting solutions. I don't know if I would have ever thought of binompdf. – PhiNotPi Feb 1 at 13:51

CJam (17 14 bytes)

ri_3@#_2+@#\b`

Online demo

This approach uses the ordinary generating function (x + 2)^n. The OEIS mentions (2x + 1)^n, but this question indexes the coefficients in the opposite order. I'm kicking myself for not thinking to reverse the g.f. until I saw Alephalpha's update to the PARI/GP answer which did the same.

The interesting trick in this answer is to use integer powers for the polynomial power operation by operating in a base higher than any possible coefficient. In general, given a polynomial p(x) whose coefficients are all non-negative integers less than b, p(b) is a base-b representation of the coefficients (because the individual monomials don't "overlap"). Clearly (x + 2)^n will have coefficients which are positive integers and which sum to 3^n, so each of them will individually be less than 3^n.

ri     e# Read an integer n from stdin
_3@#   e# Push 3^n to the stack
_2+    e# Duplicate and add 2, giving a base-3^n representation of x+2
@#     e# Raise to the power of n
\b`    e# Convert into a vector of base-3^n digits and format for output

Alternative approaches: at 17 bytes

1a{0X$2f*+.+}ri*`

Online demo

or

1a{0X$+_]:.+}ri*`

Online demo

both work by summing the previous row with an offset-and-doubled row (in a similar style to the standard manual construction of Pascal's triangle).

A "direct" approach using Cartesian powers (as opposed to integer powers) for the polynomial power operation, comes in at 24 bytes:

2,rim*{1b_0a*2@#+}%z1fb`

where the map is, unusually, complicated enough that it's shorter to use % than f:

2,rim*1fb_0af*2@f#.+z1fb`
share|improve this answer

ES6, 71 bytes

n=>[...Array(n+1)].fill(n).map(b=(n,i)=>!i?1:i>n?0:b(--n,i-1)*2+b(n,i))

Simple recursive formula. Each hypercube is created by moving the previous hypercube 1 unit through the Nth dimension. This means that the M-dimensional objects are duplicated at the start and end of the unit, but also the (M-1)-dimensional objects gain an extra dimension, turning into M-dimensional objects. In other words, c(n, m) = c(n - 1, m) * 2 + c(n - 1, m - 1). (The actual submission reverses the parameters so that the formula outputs in the desired order.)

Ingeniously, fill allows map to provide the correct arguments to the recursive function, saving me 6 bytes.

share|improve this answer

Pyth, 10 9 bytes

.<L.cQdhQ

Uses the nCr algorithm everyone seems to be using.

share|improve this answer
    
L-map saves a byte: .<L.cQdhQ – isaacg Jan 31 at 0:54

05AB1E, 9 bytes

Code:

WƒNoZNc*,

Explanation:

W          # Push input and store in Z
 ƒ         # For N in range(0, input + 1)
  No       # Compute 2**N
    ZNc    # Compute Z nCr N
       *   # Multiply
        ,  # Pop and print

Uses CP-1252 encoding.

share|improve this answer

Julia, 31 bytes

n->[2^m*binomial(n,m)for m=0:n]

This is a lambda function that accepts an integer and returns an integer array. To call it, assign it to a variable.

For each m from 0 to the input n, we count the number of (n-m)-dimensional hypercubes on the boundary of the parent n-dimensional hypercube. Using the formula on Wikipedia, it's simply 2m * choose(n, m). The case of m = 0 refers to the n-cube itself, so the output begins with 1 regardless of the input. Edges are given by m = n, vertices by m = n - 1, etc.

share|improve this answer

Ruby, Rev B 57 bytes

->n{a=[1]+[0]*n
(n*n).downto(n){|i|a[1+j=i%n]+=2*a[j]}
a}

The previous rev only scanned through the used part of the array each time. This rev scans through the entire array on every iteration. This is slower, but it saves bytes. A further byte is saved by using 1 loop to do the job of 2.

Ruby, Rev A 61 bytes

->n{a=[1]+[0]*n
n.times{|i|i.downto(0){|j|a[j+1]+=2*a[j]}}
a}

Starts with a point and iteratively creates the next dimension

In each iteration, each existing element increases in dimensionality and generates 2 new elements of its original dimensionality. For example, for a square in the horizontal plane that is extended vertically to become a cube:

The 1 face becomes a cube and generates 1 pair of faces (1 above, 1 below)

The 4 edges become faces and generate 4 pairs of edges (4 above, 4 below)

The 4 vertices become edges and generate 4 pairs of vertices (4 above, 4 below)

Ungolfed in test program

f=->n{a=[1]+[0]*n                  #make an array with the inital point and space for other dimensions
  n.times{|i|                      #iteratively expand dimension by dimension 
    i.downto(0){|j|a[j+1]+=2*a[j]} #iterating downwards (to avoid interferences) add the 2 new elements generated by each existing element.
  }
a}                                 #return the array

p f[gets.to_i]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.