# Counting polyominoes on (hyper-)cubes

This challenge like some of my previous challenges will have you counting free polyforms, which are generalizations of Tetris pieces.

This challenge will have you count polyomino-like polyforms on hypercubes. In particular, this challenge is to write a program that takes in three parameters:

• n, which represents an $$\n\$$-dimensional hypercube,
• m, which represents $$\m\$$-dimensional faces of the hypercube, and
• k, which represents the number of cells in the polyform,

and outputs the number of ways to choose $$\k\$$ ($$\m\$$-dimensional) faces on the $$\n\$$-cube such that the $$\m\$$-faces are connected at $$\(m-1)\$$-faces. These polyforms are "free" which means they should be counted up to the rotations/reflections of the $$\n\$$-cube.

Again, this is a challenge, so shortest code wins.

# Example 1

Okay, this is all very abstract, so this warrants an example.

When n=3, we're talking about the $$\3\$$-dimensional (ordinary) cube. When m=2 this means we're talking about the $$\2\$$-dimensional (square) faces. And we're talking about k of these, joined along $$\1\$$-dimensional faces (edges).

When k=3, there are two such polyforms (on the left) up to rotations/reflections of the cube. When k=4 there are also two polyforms (on the right).

# Example 2

In this second example, n=3 still, so we're again talking about the $$\3\$$-dimensional (ordinary) cube. When m=1 this means we're talking about the $$\1\$$-dimensional faces (edges). And we're talking about k of these, joined along $$\0\$$-dimensional faces (corners).

When k=4 there are four such polyforms.

# Data

n | m | k | f(n,m,k)
--+---+---+---------
3 | 2 | 3 | 2       (Example 1, left)
3 | 2 | 4 | 2       (Example 1, right)
3 | 1 | 4 | 4       (Example 2)
2 | 1 | 2 | 1
3 | 0 | 0 | 1
3 | 0 | 1 | 1
3 | 0 | 2 | 0
3 | 1 | 3 | 3
3 | 1 | 5 | 9
3 | 1 | 6 | 14
3 | 1 | 7 | 19
3 | 1 | 8 | 16
3 | 1 | 9 | 9
3 | 3 | 0 | 1
3 | 3 | 1 | 1
3 | 3 | 2 | 0
4 | 1 | 4 | 7
4 | 1 | 5 | 21
4 | 1 | 6 | 72
4 | 1 | 7 | 269
4 | 1 | 8 | 994
4 | 1 | 9 | 3615
4 | 2 | 3 | 5
4 | 2 | 4 | 12
4 | 2 | 5 | 47
5 | 1 | 4 | 7
5 | 1 | 5 | 27
5 | 2 | 0 | 1
5 | 2 | 1 | 1
5 | 2 | 2 | 1
5 | 2 | 3 | 5
5 | 2 | 4 | 20
5 | 3 | 4 | 16
5 | 3 | 5 | 73
5 | 4 | 4 | 3
6 | 1 | 6 | 121

• I'm counting f(4,1,6) = 72, f(4, 1, 7) = 269, f(4,1,8) = 994 with all the other test cases being correct. Is this an error in the test cases? I also get f(4, 1, 9) = 3615 so I think those test cases might be off-by-one on k. – cardboard_box Mar 16 '20 at 4:28
• You're absolutely correct—I had an off-by-one in the data table. Sorry about that. It's corrected now. – Peter Kagey Mar 16 '20 at 4:48

# Python 3, 389

import itertools as I
S=sorted
P=I.product
def C(n,m,k):
Q=[((-1,)*(n-m)+(0,)*m,)]
for i in' '*(k-1):Q=set(tuple(S(q+(v,)))for q in Q for v in P(*[(-1,0,1)]*n)if sum(map(abs,v))==n-m if not v in q and any(sum((a!=b)*(1+2*a*b)for a,b in zip(v,u))==2for u in q))
return sum(all(S(q)<=S(zip(*r))for X in I.permutations(zip(*q))for r in P(*((p,tuple(-x for x in p)) for p in X)))for q in Q)


Try it online!

Basically just finds all connected polyominos, and discards ones which can be rotated into a lexicographically smaller polyomino, with rotations being brute-forced.

Can definitely be improved but it's my bedtime.

• I’m impressed! This is shorter than what I thought anyone would come up with! – Peter Kagey Mar 16 '20 at 16:12