Les polystrips sont un sous-ensemble de polyominos se conformant aux règles suivantes:

• chaque pièce se compose de 1 ou plusieurs cellules
• aucune cellule ne peut avoir plus de deux voisins
• les cellules ne doivent pas fermer un trou

Les polyominos libres sont distincts quand aucun n'est une transformation rigide (translation, rotation, réflexion ou réflexion de glissement) d'un autre (morceaux qui peuvent être ramassés et retournés). La traduction, la rotation, la réflexion ou le glissement reflétant un polyomino libre ne change pas sa forme ( Wikipedia )

Par exemple, il existe 30 heptastrips libres (polystrips de longueur 7). Voici tous, emballés dans une grille 14x15.

Crédit d'image: Miroslav Vicher

Objectif

Écrivez un programme / une fonction qui prend un entier positif nen entrée et énumère les nbandes de couleurs libres distinctes .

• n = 1 -> 1 (un seul carré)

• n = 2 -> 1 (Il n'y a qu'une seule bande 2 possible composée de 2 carrés)

• n = 3 -> 2 (l'un est composé de 3 carrés réunis en ligne et l'autre est en forme de L)

• n = 4 -> 3 (une droite, une en L et une en Z)

• . . .

Cas de test:

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

Notation

C'est du code-golf , donc le code le plus court est meilleur. J'apprécierais fortement les explications détaillées de l'algorithme et du code.

Implémentation de référence partielle dans J

J'ai décidé de décrire chaque pièce au format "vecteur" et je n'ai besoin que de n-2 blocs pour décrire une pièce n-polystrip (il n'y a que 1 2-polystrip et elle est retournée explicitement). Les blocs décrivent la direction relative: 0 - pas de changement; 1 - tournez à gauche; 2 - tournez à droite. Peu importe dans quelle direction on commencera, mais seulement pour indiquer où la cellule suivante doit être placée. Il peut y avoir n'importe quel nombre de 0 consécutifs, mais les 1 et les 2 sont toujours simples. Cette implémentation est partielle, car elle ne tient pas compte des trous - les solutions pour n> 6 comptent également les pièces avec des trous.

Essayez-le en ligne!

Python 3 , 480 433 406 364 309 299 295 octets

Cela semblait être un bon point pour commencer ma carrière PPCG (ou pas?).

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)

Essayez-le en ligne!

Modifications:

• Inline DetX , et peaufiné un peu sur certains spots golfables.
• Appliqué plus d'astuces, principalement celles liées aux ensembles.
• Modifié sous forme de programme et remplacé par l'utilisation de nombres complexes au lieu d'un nombre arbitraire m. (Les nombres complexes sont vraiment une caractéristique golfique forte mais souvent ignorée; adapté de la solution de xnor pour un autre défi )
• Changement de la LFRreprésentation des chaînes en -1,0,1tuples et sacrifié le temps d'exécution pour une quantité folle de réduction d'octets (!). Maintenant, la solution est théoriquement correcte, mais les délais d'attente avant de produire le résultat pour 15.
• Une boucle dans la boucle grâce à Jonathan Frech, puis j'ai trouvé la bien meilleure alternative pour le calcul r. ENFIN SOUS 300 OCTOS !!!
• Étonnamment, il 1jpeut s'en tenir à autre chose sans confondre l'analyseur (-2B) et nota une priorité incroyablement faible (-2B).

Version obsolète (480 octets):

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

Essayez-le en ligne!

Solution non golfée avec commentaires:

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

Essayez-le en ligne!

m = 999est choisi car il faut du temps exponentiel pour tout compter, et cela prend déjà ~ 8s pour calculer n = 1..15. Peut-être que c'est bien d'économiser 1 octet en utilisant 99 à la place. Nous n'en avons plus besoin, et maintenant il est garanti d'être correct pour une taille d'entrée arbitraire, grâce à un nombre complexe intégré.

APL (Dyalog Unicode) , ⁷⁰ 65 octets

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

Essayez-le en ligne!

Version complète du programme du code ci-dessous, grâce à Adám.

APL (Dyalog Unicode) , 70 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Le code ci-dessus est équivalent à la définition suivante:

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

Cela fonctionne comme la solution Python, mais dans un ordre différent. Il gennère LFR-strips de longueur n-2, canonicalizeest chaque bande, prend ∪bandes nique, testest chaque bande elle-même si elle touche (1 si ne se touchent pas, sinon 0), et additionne +/le résultat booléen.

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)