Compter les polystrips

18

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.

Heptastrips

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 , 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!

Galen Ivanov
la source
1
OEIS pertinent. (Mais n'exclut pas les trous.)
Martin Ender
@ Martin Ender Merci, je ne le savais pas.
Galen Ivanov
2
Juste pour être sûr, je suppose que si vous remplissez une grille 3x3 à l'exception du centre et d'un coin qui compte également comme un trou ( 101010dans votre exemple de notation)?
Ton Hospel
@Ton Hospel Oui, exactement - c'est la seule pièce heptastrip avec un trou.
Galen Ivanov
1
Peut-être une bonne question pour math.SE
Jonah

Réponses:

12

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é.

Bubbler
la source
5
Bienvenue chez PPCG! Certainement une façon impressionnante de commencer votre carrière PPCG. :)
Martin Ender
3
Bienvenue chez PPCG et merci pour cette solution! J'avais déjà renoncé à attendre une solution :)
Galen Ivanov
3
Cela semblait être un bon point pour commencer ma carrière PPCG (ou pas?) . Eh bien, c'est une solution étonnamment courte à ce que la plupart d'entre nous ne penseraient même pas pouvoir être, même la version non golfée semble étonnamment simple, mais, hein, c'est peut-être un moyen moyen de commencer votre carrière PPCG, non? :)
Erik the Outgolfer le
1
@Erik Cette ligne était une demi-blague :) Mais oui, la solution me surprend même - je ne m'attendais pas à retirer ~ 36% de réduction par rapport à la soumission d'origine.
Bubbler
1
303 octets possibles .
Jonathan Frech
4

APL (Dyalog Unicode) , 70 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    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
la source
-5
Adám