Las tiras de polis son un subconjunto de poliominós que se ajustan a las siguientes reglas:

• cada pieza consta de 1 o más celdas
• ninguna celda puede tener más de dos vecinos
• las celdas no deben encerrar un agujero

Los poliominoes libres son distintos cuando ninguno es una transformación rígida (traslación, rotación, reflexión o reflexión de deslizamiento) de otra (piezas que pueden recogerse y voltearse). Traducir, rotar, reflejar o deslizar reflejando un poliomino libre no cambia su forma ( Wikipedia )

Por ejemplo, hay 30 heptastrips libres (polystrips con longitud 7). Aquí están todos, empaquetados en una cuadrícula de 14x15.

Crédito de imagen: Miroslav Vicher

Objetivo

Escriba un programa / función que tome un entero positivo ncomo entrada y enumere las distintas nfranjas de polystrips libres .

• n = 1 -> 1 (un solo cuadrado)

• n = 2 -> 1 (solo hay una posible 2-polystrip hecha de 2 cuadrados)

• n = 3 -> 2 (uno está compuesto por 3 cuadrados unidos en una línea y el otro tiene forma de L)

• n = 4 -> 3 (uno recto, uno en forma de L y uno en forma de Z)

• . . .

Casos de prueba:

n   polystrips

1   1
2   1
3   2
4   3
5   7
6   13
7   30
8   64
9   150
10  338
11  794
12  1836
13  4313
14  10067
15  23621

Puntuación

Este es el código de golf , por lo que el código más corto es mejor. Apreciaría mucho las explicaciones detalladas del algoritmo y el código.

Implementación de referencia parcial en J

Decidí describir cada pieza en formato "vector" y solo necesito bloques n-2 para describir una pieza de n-polystrip (solo hay 1 2-polystrip y se devuelve explícitamente). Los bloques describen la dirección relativa: 0: sin cambios; 1 - gire a la izquierda; 2 - gire a la derecha. No importa en qué dirección comenzará, sino solo para indicar dónde se colocará la siguiente celda. Puede haber cualquier número de ceros consecutivos, pero 1 y 2 siempre son únicos. Esta implementación es parcial porque no tiene en cuenta los agujeros: las soluciones para n> 6 también cuentan las piezas con agujeros.

Pruébalo en línea!

Python 3 , 480 433 406 364 309 299 295 bytes

Parecía un buen punto para comenzar mi carrera PPCG (¿o no?).

def C(s):
 S,*a={''},0,1;n=d=r=1
 for c in s:d=c*d*1jor d;n+=d;a+=n,;r*=not{n}&S;x,*a=a;S|={x+t+u*1jfor t in A for u in A}
 return r
from itertools import*;A=-1,0,1;n,y=int(input())-2,0;x={*filter(C,product(*[A]*n))}
while x:s=x.pop();S=*(-u for u in s),;x-={s[::-1],S,S[::-1]}-{s};y+=1
print(y)

Pruébalo en línea!

Ediciones:

• En línea Dy X, y ajusté un poco en algunos puntos de golf.
• Se aplicaron más trucos, principalmente los relacionados con conjuntos.
• Cambió a forma de programa y cambió a usar números complejos en lugar de números arbitrarios m. (Los números complejos son realmente una característica de golf fuerte pero a menudo ignorada; adaptada de la solución de xnor para otro desafío )
• Cambió la LFRrepresentación de cadena a -1,0,1tuplas y sacrificó el tiempo de ejecución por una cantidad loca de reducción de bytes (!). Ahora la solución es teóricamente correcta, pero se agota el tiempo de espera antes de generar el resultado para 15.
• Una línea del círculo gracias a Jonathan Frech, luego encontré la alternativa mucho mejor para calcular r. ¡FINALMENTE BAJO 300 BYTES!
• Sorprendentemente, 1jpuede adherirse a cualquier otra cosa sin confundir al analizador (-2B), y nottiene una precedencia increíblemente baja (-2B).

Versión obsoleta (480 bytes):

def C(s):
 m=999;a=[0,1];n=d=1
 D={'F':{},'L':{1:m,m:-1,-1:-m,-m:1},'R':{1:-m,-m:-1,-1:m,m:1}}
 X=lambda x:{x+~m,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x-~m}
 for c in s:
  d=D[c].get(d,d);n+=d;a+=n,
  if n in set().union(*map(X,a[:-3])):return 0
 return 1
def f(n):
 if n<3:return 1
 x={*'LF'}
 for _ in range(3,n):x={s+c for s in x for c in({*'LRF'}-{s[-1]})|{'F'}}
 y={*x}
 for s in x:
  if s in y:S=s.translate(str.maketrans('LR','RL'));y-={s[::-1],S,S[::-1]}-{s}
 return sum(map(C,y))

Pruébalo en línea!

Solución sin golf con comentarios:

t = str.maketrans('LR','RL')

# hole checking function
def check(s):
    m = 999   # (imaginary) board size enough to fit all generated polyominoes
    a = [0,1] # previous path
    n = 1     # current cell
    d = 1     # current direction
    # dict for direction change
    D = {'F':{}, 'L':{1:m, m:-1, -1:-m, -m:1}, 'R':{1:-m, -m:-1, -1:m, m:1}}
    # used to 'blur' all cells in path into 3x3
    X = lambda x: {x-m-1,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x+m+1}
    for c in s:
        d = D[c].get(d,d) # change direction
        n += d            # move current cell
        # the polyomino has a hole if the current cell touches previous cells (including diagonally; thus the blurring function)
        if n in set().union(*map(X,a[:-2])): return False
        a.append(n)       # add current cell to the path
    return True

# main function
def f(n):
    if n < 3: return 1
    x = {*'LF'}
    # generate all polystrips using the notation similar to the reference
    for _ in range(3, n): x = {s+c for s in x for c in ({*'LRF'}-{s[-1]})|{'F'}}
    y = {*x}
    # remove duplicates (mirror, head-to-tail, mirror of head-to-tail) but retain self
    for s in x:
        if s in y:
            S = s.translate(t)
            y -= {s[::-1], S, S[::-1]} - {s}
    # finally filter out holey ones
    return sum(map(check,y))

Pruébalo en línea!

m = 999se elige porque se necesita un tiempo exponencial para contarlo todo, y ya se tarda unos 8 segundos en calcularlo n = 1..15. Tal vez esté bien guardar 1 byte usando 99 en su lugar. Ya no necesitamos esto, y ahora está garantizado que es correcto para el tamaño de entrada arbitrario, gracias al complejo número incorporado.

APL (Dyalog Unicode) , ⁷⁰ 65 bytes

+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳2↓⎕⍴3

Pruébalo en línea!

Versión completa del programa del siguiente código, gracias a Adám.

APL (Dyalog Unicode) , 70 bytes

{+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳3⍴⍨0⌈⍵-2}

Pruébalo en línea!

Cómo funciona

El código anterior es equivalente a la siguiente definición:

gen←{2-,⍳3⍴⍨0⌈⍵-2}
canonicalize←{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
test←{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{+/test¨∪canonicalize¨gen⍵}

Esto funciona como la solución Python, pero en un orden diferente. Se generates LFR-strips de longitud n-2, canonicalizees cada tira, lleva ∪tiras nique, testes cada tira si toca en sí (1 si no se tocan, 0 en caso contrario), y resume +/el resultado booleano.

gen

{2-,⍳3⍴⍨0⌈⍵-2}
{            }  ⍝ ⍵←input number n
        0⌈⍵-2   ⍝ x←max(0, n-2)
     3⍴⍨        ⍝ x copies of 3
   ,⍳           ⍝ multi-dimensional indexes; x-th cartesian power of [1,2,3]
                ⍝ (`⍳` gives x-dimensional hypercube; `,` flattens it)
 2-             ⍝ compute 2-k for each k in the array

⍝ in each strip, ¯1, 0, 1 corresponds to R, F, L respectively

canonicalize

{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
{                  }  ⍝ ⍵←single strip
              ⍵(-⍵)   ⍝ nested array of ⍵ and its LR-flip
        (⊢,⌽¨)        ⍝ concatenate their head-to-tail flips to the above
 (⊃∘⍋  )              ⍝ find the index of the lexicographically smallest item
     ⊃⊢               ⍝ take that item

test

{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{                                  }  ⍝ ⍵←single strip
                              0j1*⍵   ⍝ power of i; direction changes
                            ×\        ⍝ cumulative product; directions
                        0 1,    ⍝ initial position(0) and direction(1)
                      +\        ⍝ cumulative sum; tile locations
 (  ⊢{           }¨,\)   ⍝ test with current tile(⍺) and all tiles up to ⍺(⍵):
             ¯3↓⍵        ⍝ x←⍵ with last 3 tiles removed
           ⍺-            ⍝ relative position of each tile of x from ⍺
        2≤|              ⍝ test if each tile of x is at least 2 units away
      ∧/                 ⍝ all(...for each tile in x)
  ∧/        ⍝ all(...for each position in the strip)