10
\$\begingroup\$

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). enter image description here

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. enter image description here


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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – cardboard_box Mar 16 at 4:28
  • 1
    \$\begingroup\$ You're absolutely correct—I had an off-by-one in the data table. Sorry about that. It's corrected now. \$\endgroup\$ – Peter Kagey Mar 16 at 4:48
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I’m impressed! This is shorter than what I thought anyone would come up with! \$\endgroup\$ – Peter Kagey Mar 16 at 16:12

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.