Codegolf - Подсчет Полимино На (Гипер-)Кубах

Этот вызов похож на некоторые из моих предыдущий вызовы ты будешь считать бесплатно полиформы, которые являются обобщением частей Тетриса.

В этом задании вам предстоит посчитать полиминоподобные полиформы на гиперкубах. В частности, эта задача состоит в том, чтобы написать программу, которая принимает три параметра:

•  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
   

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

и выводит количество способов выбрать \$k\$ (\$m\$-мерные) грани на \$n\$-кубе такие, что \$m\$-грани соединяются в точках \$(m- 1)\$-грани. Эти полиформы «свободны», что означает, что их следует считать с точностью до вращений/отражений \$n\$-куба.

Опять же, это сложная задача, поэтому побеждает самый короткий код.

Пример 1

Ладно, это все очень абстрактно, поэтому нужен пример.

Когда m=1 , we're talking about the \$3\$-dimensional (ordinary) cube. When n=3 это означает, что мы говорим о \$2\$-мерных (квадратных) гранях. И мы говорим о k=4 of these, joined along \$1\$-dimensional faces (edges).

Когда k=3 , there are two such polyforms (on the left) up to rotations/reflections of the cube. When k также есть две полиформы (справа).

Пример 2

В этом втором примере m=2 still, so we're again talking about the \$3\$-dimensional (ordinary) cube. When n=3 это означает, что мы говорим о \$1\$-мерных гранях (ребрах). И мы говорим о k of these, joined along \$0\$-dimensional faces (corners).

Когда m there are four such polyforms.

Данные

#код-гольф #код-гольф #код-гольф #геометрия #комбинаторика #полиомино

Питон 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)
 

Попробуйте онлайн!

По сути, просто находит все связанные полимино и отбрасывает те, которые можно повернуть в лексикографически меньшее полимино, при этом повороты выполняются грубо.

Определенно можно улучшить, но мне пора спать.