Najnowsza „ładna” sekwencja OEIS, A328020 , została właśnie opublikowana kilka minut temu.
Liczba wyraźnych nachyleń kwadratu n X n z wolnymi n-poliominoami.
Ta sekwencja zlicza przechylenia do symetrii kwadratu. Sekwencja ma sześć terminów, ale chciałbym sprawdzić, czy ludzie tutaj mogą ją jeszcze rozszerzyć.
Przykład
Ponieważ n=4
istnieją 22 takie siatki, jak pokazano na tym obrazie z OEIS.
Źródło: Jeff Bowermaster, ilustracja A328020 (4).
Wyzwanie
Podobnie jak w poprzednim wyzwaniu , celem tego wyzwania jest obliczenie jak największej liczby terminów w tej sekwencji, która zaczyna się 1, 1, 2, 22, 515, 56734
i gdzie n-ty składnik jest liczbą nachyleń siatki n X n za pomocą n-poliominoów.
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 do jej wygenerowania. Jeśli dwóch użytkowników opublikuje tę samą liczbę warunków, wygrywa ten, kto opublikuje swój ostatni termin najwcześniej.
źródło
Odpowiedzi:
Rozszerzenie kodu @ Grimy otrzymuje N = 8
To tylko podkreśla, że @Grimy zasługuje na nagrodę:
Mogę przycinać drzewo wyszukiwania, rozszerzając kod, aby sprawdzić, po każdym zakończonym poliomino, czy pozostała wolna przestrzeń nie jest podzielona na komponenty o rozmiarze niepodzielnym przez N.
Na komputerze, na którym oryginalny kod zajął 2m11s dla N = 7, zajmuje to 1m4s, a N = 8 obliczono w 33h46m. Wynik to 23437350133.
Oto mój dodatek jako diff:
Wypróbuj online!
źródło
C, 7 warunków
Siódma kadencja to 19846102 . (Pierwsze sześć to 1, 1, 2, 22, 515, 56734, jak stwierdzono w pytaniu).
Wypróbuj online! (dla N = 6, ponieważ N = 7 przekroczyłoby limit czasu).
Na mojej maszynie N = 6 zajęło 0,171 s, a N = 7 zajęło 2m23 s. N = 8 zajęłoby kilka tygodni.
źródło