9
\$\begingroup\$

Consider the Tetris pieces, but made out of some number of (hyper)cubes instead of four squares, where two blocks are considered the same if one is a rotation, reflection, or translation of another. The goal of this challenge is to take two positive integer input values, n and k, and count the number of \$n\$-celled polyominoes consisting of \$k\$-dimensional hypercubes.

This is a challenge, so the shortest code wins.


Example

For example, when \$n = 4\$ and \$k = 3\$ there are seven different shapes:

Notice that the first piece could be made using \$1\$-cubes (line segments) instead of cubes, the next four could be made using \$2\$-cubes (squares), and only the last two require \$3\$-cubes (ordinary cubes). Thus \$p(4,1) = 1\$, \$p(4,2) = 5\$, and \$p(4,3) = 7\$.


Test Data

 n | k | p(n,k)
---+---+--------
 1 | 0 | 1
 2 | 0 | 0
 2 | 1 | 1
 3 | 2 | 2
 4 | 1 | 1
 4 | 2 | 5
 4 | 3 | 7
 4 | 4 | 7
 4 | 5 | 7
 5 | 4 | 26
 6 | 3 | 112
 7 | 3 | 607
 8 | 2 | 369
\$\endgroup\$
  • \$\begingroup\$ How did you create the graphics? \$\endgroup\$ – Jonah Apr 30 at 20:49
  • 2
    \$\begingroup\$ @Jonah, I used Mathematica. For example, the last image was made with the command Graphics3D[{Green, Cuboid[{0, 0, 0}], Cuboid[{0, 0, 1}], Cuboid[{0, 1, 0}], Cuboid[{1, 1, 0}]}]. \$\endgroup\$ – Peter Kagey Apr 30 at 21:22
  • \$\begingroup\$ What would 0-dimensions be like? \$\endgroup\$ – Wezl Apr 30 at 22:15
  • 1
    \$\begingroup\$ You made me look this up (and now my profile pic is a tesseract ;). Cool! \$\endgroup\$ – Wezl Apr 30 at 22:18
  • 1
    \$\begingroup\$ 0-dimensions is just a single point, so \$p(1,0) = 1\$ and \$p(n,0) = 0\$ for \$n > 0\$. \$\endgroup\$ – Peter Kagey Apr 30 at 22:41
5
\$\begingroup\$

Python 2, 338 335 330

Try it online!

from itertools import*
n,k=input()
O=[([0]*k,)]
R=range(k)
exec"O={min(tuple(sorted(zip(*[[x-min(p)for x in p]for p in f])))for q in permutations(zip(*(o+(r,))))for f in product(*[[p,[-x for x in p]]for p in q]))for o in O for s in o for r in[tuple(s[i]+x*(i==j)for i in R)for j in R for x in-1,1]if not r in o};"*~-n
print len(O)

Reads n,k as a list from stdin (e.g. [4,2]) and prints the number of polyominoes.

Starts with a single polyomino with a single cell at the origin.

n-1 times, replaces the polyominoes with all possible polyominoes created by adding an adjacent cell to an existing polyomino, and canonizing that polyomino by finding the minimum of all possible rotations of it.

-6 bytes thanks to math junkie, -2 bytes thanks to Surculose Sputum.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice work. I'd love to see the ungolfed version with explanation. \$\endgroup\$ – Jonah May 4 at 0:05

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.