Wyzwanie to będzie musiał liczyć pseudo polyforms na kafli zadartym kwadratowy .
Myślę, że ta sekwencja jeszcze nie istnieje w OEIS , więc istnieje wyzwanie, aby obliczyć jak najwięcej terminów dla tej sekwencji.
Aktualizacja: teraz jest to w OEIS jako A309159 : liczba uogólnionych poliform na kwadratowym kafelku z n komórkami.
Definicje
Dachówka kwadratowa jest półprawidłowym kafelkiem płaszczyzny składającej się z równobocznych trójkątów i kwadratów.
Pseudopoliforma na kwadratowych kafelkach to płaska figura zbudowana przez połączenie tych trójkątów i kwadratów wzdłuż ich wspólnych boków, analogicznie do poliomino. Oto przykład pseudopolifenu sześciokomórkowego i ośmiokomórkowego:
Przykłady
Ponieważ n = 1
istnieją dwa 1-komórkowe pseudopolimorfy, mianowicie kwadrat i trójkąt:
W przypadku n = 2
istnieją dwie 2-komórkowe polyforms pseudo-kwadrat, a mianowicie z trójkąta i dwóch trójkątów.
Ponieważ n = 3
istnieją cztery 3-komórkowe pseudopolimorfy.
Wyzwanie
Celem tego wyzwania jest obliczenie jak największej liczby terminów w tej sekwencji, która zaczyna się 2, 2, 4, ...
i gdzie n-ty składnik jest liczbą pseudopolifaktów komórek n aż do obrotu i odbicia.
Uruchom kod tak długo, jak chcesz. Zwycięzcą tego wyzwania będzie użytkownik, który opublikuje najwięcej terminów sekwencji wraz ze swoim kodem. Jeśli dwóch użytkowników opublikuje tę samą liczbę warunków, wygrywa ten, kto opublikuje swój ostatni termin najwcześniej.
(Gdy będzie wystarczająco dużo znanych terminów, aby udowodnić, że ta sekwencja jeszcze nie istnieje w OEIS, utworzę wpis w OEIS i wymienię autora jako współautora, jeśli tego chce).
źródło
Odpowiedzi:
Haskell
Teraz, gdy nie tylko komentarze mówią, że Peter Taylor jako pierwszy podał wystarczająco dużo terminów do wyszukiwania w OEIS, mogę podać moje wyniki.
Wcześniej liczyłem sześciokątne poliominoes . Poza pewnymi optymalizacjami to, co tu robię, jest bardzo podobne.
Elementy kafelków są reprezentowane w następujący sposób: Możesz przejść w prawie prostej linii od lewej do prawej (na pierwszym zdjęciu), na przemian między kwadratami i prostokątami. Są prawie równoległe dalsze linie, poruszające się w przeciwnych kierunkach. Wspólnie tęsknią za trójkątami. Istnieją podobne prawie proste równoległe linie od dołu do góry, zawierające brakujące trójkąty. Teraz zignoruj poruszenie i użyj kartezjańskiego układu współrzędnych, ale używaj tylko liczb nieparzystych dla współrzędnych kwadratów. Następnie trójkąty naturalnie otrzymują pary współrzędnych z jedną parzystą i jedną nieparzystą współrzędną. Pary o obu współrzędnych nawet nie reprezentują elementów sąsiadujących.
(Równie dobrze możesz użyć liczb parzystych jako współrzędnych kwadratów. Myślę, że zdecydowałem w ten sposób, ponieważ myślałem o odbiciu przed rotacją.)
Zapisz program w pliku o nazwie podobnej do
cgp.hs
i skompiluj zghc -O2 -o cgp cgp.hs
. Pobiera jeden argument liczbowy z wiersza poleceń i oblicza liczbę poliominoów o tym rozmiarze lub nie ma żadnego, w którym to przypadku oblicza wartości aż do zatrzymania.Wypróbuj online!
źródło
2, 2, 4, 10, 28, 79, 235, 720, 2254, 7146, 22927, 74137, 241461, 790838, 2603210, 8604861, 28549166, 95027832
Zamierzam postawić kołek w ziemi, zanim Christian Sievers wyśle odpowiedź za n = 18. To jest tak daleko, jak mogę przejść z obecnym kodem i 16 GB pamięci RAM. Już musiałem poświęcić trochę prędkości, aby zmniejszyć zużycie pamięci, i będę musiał to zrobić jeszcze bardziej. Mam kilka pomysłów ...
Ten fragment to plik SVG z pierwszego komentarza.
Kod to C #. Uruchomiłem go z .Net Core 2.2.6 pod Linuksem.
źródło