11
\$\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
Improve this question
\$\endgroup\$
2
  • \$\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\$ Commented Mar 16, 2020 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\$ Commented Mar 16, 2020 at 4:48

1 Answer 1

Reset to default
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\$
1
  • \$\begingroup\$ I’m impressed! This is shorter than what I thought anyone would come up with! \$\endgroup\$ Commented Mar 16, 2020 at 16:12

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.