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.
Źródło zdjęcia: Miroslav Vicher
Cel
Napisz program / funkcję, która przyjmuje na n
wejś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 golf golfowy , 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.
źródło
101010
w przykładowej notacji)?Odpowiedzi:
Python 3 ,
480433406364309299295 bajtówWyglądało na to, że warto rozpocząć karierę PPCG (czy nie?).
Wypróbuj online!
Edycje:
D
iX
, i trochę poprawione w niektórych miejscach do gry w golfa.m
. (Liczby zespolone są naprawdę silną, ale często ignorowaną cechą golfa; zaadaptowaną z rozwiązania xnor na kolejne wyzwanie )LFR
reprezentację ciągu na-1,0,1
krotki 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.r
. WRESZCIE PONIŻEJ 300 BYTES !!!1j
potrafi trzymać się czegokolwiek innego bez pomieszania parsera (-2B) inot
ma niesamowicie niski priorytet (-2B).Przestarzała wersja (480 bajtów):
Wypróbuj online!
Niegolfowane rozwiązanie z komentarzami:
Wypróbuj online!
Już tego nie potrzebujemy, a teraz jest gwarantowana, że jest poprawna dla dowolnego rozmiaru wejściowego, dzięki wbudowanej liczbie złożonej.m = 999
jest wybrana, ponieważ zliczenie wszystkiego zajmuje wykładniczy czas, a jej obliczenie zajmuje już około 8 sekundn = 1..15
. Może warto zapisać 1 bajt, używając 99 zamiast tego.źródło
APL (Dyalog Unicode) ,
7065 bajtówWypróbuj online!
Pełna wersja programu kodu poniżej, dzięki Adám.
APL (Dyalog Unicode) , 70 bajtów
Wypróbuj online!
Jak to działa
Powyższy kod jest równoważny z następującą definicją:
Działa to podobnie do rozwiązania Python, ale w innej kolejności. To
gen
eratesLFR
-strips długościn-2
,canonicalize
s na pas, odbywa∪
Nique pasków,test
s każdy pasek jeśli porusza się (1 jeżeli nie dotykając, inaczej 0) i sumuje+/
się logiczną wynik.gen
canonicalize
test
źródło