Contando tiras de polietileno

18

Polystrips são um subconjunto de poliominoes em conformidade com as seguintes regras:

  • cada peça consiste em 1 ou mais células
  • nenhuma célula pode ter mais de dois vizinhos
  • as células não devem colocar um buraco

Os poliominos livres são distintos quando não há uma transformação rígida (translação, rotação, reflexão ou reflexão de deslizamento) de outra (peças que podem ser apanhadas e viradas). Traduzir, girar, refletir ou deslizar refletindo um poliomino livre não muda sua forma ( Wikipedia )

Por exemplo, existem 30 heptastrips livres (polystrips com comprimento 7). Aqui estão todos eles, agrupados em uma grade de 14x15.

Heptastrips

Crédito da imagem: Miroslav Vicher

Objetivo

Escreva um programa / função que receba um número inteiro positivo ncomo entrada e enumere as ntiras livres-distintas .

  • n = 1 -> 1 (um único quadrado)

  • n = 2 -> 1 (Existe apenas uma 2 faixas possíveis de 2 quadrados)

  • n = 3 -> 2 (um é composto por 3 quadrados unidos em uma linha e o outro é em forma de L)

  • n = 4 -> 3 (um reto, um em L e um em Z)

  • . . .

Casos de teste:

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

Pontuação

Isso é , então o código mais curto é melhor. Eu apreciaria muito as explicações detalhadas do algoritmo e do código.

Implementação de referência parcial em J

Decidi descrever cada peça no formato "vetor" e só preciso de n-2 blocos para descrever uma peça de n-poli-faixa (existe apenas 1 2-poli-faixa e é retornada explicitamente). Os blocos descrevem a direção relativa: 0 - sem alteração; 1 - vire à esquerda; 2 - vire à direita. Não importa em que direção uma começará, mas apenas para indicar onde a próxima célula será colocada. Pode haver qualquer número de 0s consecutivos, mas 1s e 2s são sempre únicos. Essa implementação é parcial, porque não leva em conta os furos - as soluções para n> 6 contam as peças com furos também.

Experimente online!

Galen Ivanov
fonte
1
OEIS relevante. (Mas não exclui buracos.)
9788 Martin Ender
@ Martin Ender Obrigado, eu não sabia disso.
Galen Ivanov
2
Só para ter certeza, presumo que, se você preencher uma grade 3x3, exceto o centro e um canto que também conta como um buraco ( 101010na notação de amostra)?
Ton Hospel
@ Ton Hospel Sim, exatamente - esta é a única peça de heptastrip com um orifício.
Galen Ivanov
1
Talvez seja uma boa pergunta para math.SE
Jonah

Respostas:

12

Python 3 , 480 433 406 364 309 299 295 bytes

Parecia um bom ponto para começar minha carreira no PPCG (ou não?).

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)

Experimente online!

Editar% s:

  • Inline De X, e tweaked um pouco em alguns pontos de golfe.
  • Aplicou mais truques, principalmente relacionados a conjuntos.
  • Alterado para o formato do programa e alterado para o uso de números complexos em vez de números arbitrários m . (Números complexos são realmente um recurso de golfe forte, mas muitas vezes ignorado; adaptados da solução da xnor para outro desafio )
  • Mudou o LFR representação string para -1,0,1tuplas e sacrificou o tempo de execução por uma quantidade louca de redução de bytes (!). Agora, a solução está teoricamente correta, mas expirou o tempo limite antes de gerar o resultado para 15.
  • Uma linha do loop, graças a Jonathan Frech, então eu encontrei a alternativa muito melhor para o cálculo r. FINALMENTE SOB 300 BYTES !!!
  • Surpreendentemente, ele 1jpode se ater a qualquer outra coisa sem confundir o analisador (-2B) enot tem precedência incrivelmente baixa (-2B).

Versão 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))

Experimente online!

Solução ungolfed com comentários:

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))

Experimente online!

m = 999é escolhido porque leva um tempo exponencial para contar tudo e já está demorando ~ 8s para calcular n = 1..15. Talvez seja bom economizar 1 byte usando 99. Não precisamos mais disso, e agora é garantido que o tamanho da entrada é arbitrário, graças ao número complexo incorporado.

Bubbler
fonte
5
Bem-vindo ao PPCG! Definitivamente, é uma maneira impressionante de começar sua carreira no PPCG. :)
Martin Enders
3
Bem-vindo ao PPCG e obrigado por esta solução! Eu já tinha desistido de esperar para ver uma solução :)
Galen Ivanov
3
Parecia um bom ponto para começar minha carreira no PPCG (ou não?) . Bem, esta é uma solução surpreendentemente curta para isso que muitos de nós nem pensamos que poderia ser, até mesmo a versão não-gasta parece surpreendentemente simples, mas, eh, talvez essa seja uma maneira comum de iniciar sua carreira no PPCG, certo? :)
Erik the Outgolfer
1
@ Erik Essa frase foi meio que uma piada :) Mas sim, a solução é até surpreendente para mim - eu nunca esperava que eu retirasse uma redução de ~ 36% da submissão original.
borbulhador
1
Possíveis 303 bytes .
Jonathan Frech 26/02
4

APL (Dyalog Unicode) , 70 65 bytes

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

Experimente online!

Versão completa do programa do código abaixo, graças a Adám.


APL (Dyalog Unicode) , 70 bytes

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

Experimente online!

Como funciona

O código acima é equivalente à seguinte definição:

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

Isso funciona como a solução Python, mas em uma ordem diferente. É generados LFR-strips de comprimento n-2, canonicalizes cada tira, leva tiras nique, tests cada tira se toca em si (1, se não se tocam, 0 de outro modo), e soma +/o resultado booleano.

gen

{2-,⍳3⍴⍨0⌈⍵-2}
{            }   ⍵←input number n
        0⌈⍵-2    xmax(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)
Bubbler
fonte
-5
Adám 20/12/19