Liczenie polystrips

18

Polystrips to podzbiór poliominoesów zgodny z następującymi zasadami:

  • każdy kawałek składa się z 1 lub więcej komórek
  • żadna komórka nie może mieć więcej niż dwóch sąsiadów
  • komórki nie powinny otaczać dziury

Wolne poliomino są wyraźne, gdy żadna nie jest sztywną transformacją (translacja, obrót, odbicie lub odbicie poślizgowe) drugiej (części, które można podnieść i przewrócić). Tłumaczenie, obracanie, odbicie lub przesuwanie odzwierciedlające wolny poliomino nie zmienia jego kształtu ( Wikipedia )

Na przykład istnieje 30 darmowych pasków typu heptastrips (polystrips o długości 7). Oto wszystkie z nich, zapakowane w siatkę 14 x 15.

Heptastrips

Źródło zdjęcia: Miroslav Vicher

Cel

Napisz program / funkcję, która przyjmuje na nwejściu dodatnią liczbę całkowitą i wylicza różne wolne n-polystripy.

  • n = 1 -> 1 (pojedynczy kwadrat)

  • n = 2 -> 1 (Istnieje tylko jedna możliwa 2-polistripowa złożona z 2 kwadratów)

  • n = 3 -> 2 (jeden składa się z 3 kwadratów połączonych w linię, a drugi ma kształt litery L)

  • n = 4 -> 3 (jeden prosty, jeden w kształcie litery L i jeden w kształcie litery Z)

  • . . .

Przypadki testowe:

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

Punktacja

To jest , więc krótszy kod jest lepszy. Byłbym bardzo wdzięczny za szczegółowe wyjaśnienia algorytmu i kodu.

Częściowe wdrożenie odniesienia w J.

Postanowiłem opisać każdy kawałek w formacie „wektorowym” i potrzebuję tylko n-2 bloków, aby opisać kawałek n-polystrip (jest tylko 1 2-polystrip i jest on zwracany jawnie). Bloki opisują kierunek względny: 0 - bez zmian; 1 - skręć w lewo; 2 - skręć w prawo. Nie ma znaczenia, w którym kierunku zaczniesz, ale tylko wskazanie, gdzie ma zostać umieszczona następna komórka. Może istnieć dowolna liczba kolejnych zer, ale cyfry 1 i 2 są zawsze pojedyncze. Ta implementacja jest częściowa, ponieważ nie uwzględnia otworów - rozwiązania dla n> 6 również liczą kawałki z dziurami.

Wypróbuj online!

Galen Iwanow
źródło
1
Odpowiedni OEIS. (Ale nie wyklucza dziur.)
Martin Ender
@ Martin Ender Dziękuję, nie wiedziałem o tym.
Galen Iwanow
2
Dla pewności zakładam, że jeśli wypełnisz siatkę 3x3 oprócz środkowego i jednego rogu, który również liczy się jako dziura ( 101010w przykładowej notacji)?
Ton Hospel
@ Ton Hospel Tak, dokładnie - to jedyny kawałek heptastripu z otworem.
Galen Iwanow
1
Być może dobre pytanie do matematyki. SE
Jonasz

Odpowiedzi:

12

Python 3 , 480 433 406 364 309 299 295 bajtów

Wyglądało na to, że warto rozpocząć karierę PPCG (czy nie?).

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)

Wypróbuj online!

Edycje:

  • Wklęsły D i X, i trochę poprawione w niektórych miejscach do gry w golfa.
  • Zastosowałem więcej sztuczek, głównie związanych z zestawem.
  • Zmieniono na formę programu i zmieniono na używanie liczb zespolonych zamiast liczb dowolnych m. (Liczby zespolone są naprawdę silną, ale często ignorowaną cechą golfa; zaadaptowaną z rozwiązania xnor na kolejne wyzwanie )
  • Zmieniono LFRreprezentację ciągu na -1,0,1krotki i poświęcono czas wykonania dla szalonej ilości redukcji bajtów (!). Teraz rozwiązanie jest teoretycznie poprawne, ale upłynął limit czasu przed wyświetleniem wyniku dla 15.
  • Jedna linijka pętli dzięki Jonathanowi Frechowi, a następnie znalazłem znacznie lepszą alternatywę dla obliczeń r. WRESZCIE PONIŻEJ 300 BYTES !!!
  • Zaskakująco 1jpotrafi trzymać się czegokolwiek innego bez pomieszania parsera (-2B) i notma niesamowicie niski priorytet (-2B).

Przestarzała wersja (480 bajtów):

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

Wypróbuj online!

Niegolfowane rozwiązanie z komentarzami:

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

Wypróbuj online!

m = 999jest wybrana, ponieważ zliczenie wszystkiego zajmuje wykładniczy czas, a jej obliczenie zajmuje już około 8 sekund n = 1..15. Może warto zapisać 1 bajt, używając 99 zamiast tego. Już tego nie potrzebujemy, a teraz jest gwarantowana, że ​​jest poprawna dla dowolnego rozmiaru wejściowego, dzięki wbudowanej liczbie złożonej.

Bubbler
źródło
5
Witamy w PPCG! Zdecydowanie imponujący sposób na rozpoczęcie kariery PPCG. :)
Martin Ender
3
Witamy w PPCG i dziękuję za to rozwiązanie! Już się poddałem, oczekując rozwiązania :)
Galen Iwanow
3
Wyglądało na to, że warto rozpocząć karierę PPCG (czy nie?) . Cóż, jest to zaskakująco krótkie rozwiązanie, na które większość z nas nawet nie pomyślałaby, że mogłoby być, nawet wersja bez golfa wygląda zaskakująco prosto, ale może to jest średni sposób na rozpoczęcie kariery PPCG, prawda? :)
Erik the Outgolfer
1
@Erik Ta linia była pół żartem :) Ale tak, rozwiązanie jest dla mnie nawet zaskakujące - nigdy nie spodziewałem się, że wycofam się o ~ 36% od pierwotnego zgłoszenia.
Bubbler,
1
Możliwe 303 bajty .
Jonathan Frech
4

APL (Dyalog Unicode) , 70 65 bajtów

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

Wypróbuj online!

Pełna wersja programu kodu poniżej, dzięki Adám.


APL (Dyalog Unicode) , 70 bajtów

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

Wypróbuj online!

Jak to działa

Powyższy kod jest równoważny z następującą definicją:

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

Działa to podobnie do rozwiązania Python, ale w innej kolejności. To generates LFR-strips długości n-2, canonicalizes na pas, odbywa Nique pasków, tests każdy pasek jeśli porusza się (1 jeżeli nie dotykając, inaczej 0) i sumuje +/się logiczną wynik.

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
źródło
-5
Adám