Jest to kontynuacja tablic Count, które tworzą unikalne zestawy . Istotną różnicą jest definicja wyjątkowości.
Rozważ tablicę A
długości n
. Tablica zawiera tylko dodatnie liczby całkowite. Na przykład A = (1,1,2,2)
. Zdefiniujmy f(A)
jako zbiór sum wszystkich niepustych, sąsiadujących pod-macierzy A
. W tym przypadku f(A) = {1,2,3,4,5,6}
. Kroki do produkcji f(A)
są następujące:
Podziemne A
są (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)
. Ich odpowiednie kwoty to 1,1,2,2,2,3,4,4,5,6
. Zestaw, który otrzymujesz z tej listy, to dlatego {1,2,3,4,5,6}
.
Tablicę nazywamy A
unikalną, jeśli nie ma innej tablicy B
o takiej samej długości f(A) = f(B)
, z wyjątkiem A
odwróconej tablicy . Na przykład, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}
ale nie ma innej tablicy długości, 3
która generowałaby ten sam zestaw sum.
Zadanie
Zadaniem dla danego n
i s
jest policzenie liczby unikalnych tablic o tej długości. Możesz założyć, że s
jest pomiędzy 1
i 9
. Trzeba tylko liczyć tablice, w których elementy są albo liczbą całkowitą, s
albo s+1
. Np. Jeśli s=1
liczone tablice zawierają tylko 1
i 2
. Jednak definicja wyjątkowości odnosi się do każdej innej tablicy o tej samej długości. Konkretny przykład nie[1, 2, 2, 2]
jest wyjątkowy, ponieważ daje taki sam zestaw sum jak .[1, 1, 2, 3]
Należy liczyć odwrotność tablicy, a także samą tablicę (o ile tablica nie jest oczywiście palindromem).
Przykłady
s = 1
, odpowiedzi dla n = 2,3,4,5,6,7,8,9 to:
4, 3, 3, 4, 4, 5, 5, 6
Dla s = 1
, unikatowe tablice długości 4 są
(1, 1, 1, 1)
(2, 1, 1, 2)
(2, 2, 2, 2)
s = 2
, odpowiedzi dla n = 2,3,4,5,6,7,8,9 to:
4, 8, 16, 32, 46, 69, 121, 177
Przykład tablicy, która nie jest unikalna, s = 2
to:
(3, 2, 2, 3, 3, 3).
Ma to ten sam zestaw sum co oba: (3, 2, 2, 2, 4, 3)
i (3, 2, 2, 4, 2, 3)
.
s = 8
, odpowiedzi dla n = 2,3,4,5,6,7,8,9 to:
4, 8, 16, 32, 64, 120, 244, 472
Wynik
W przypadku danego n
kodu kod powinien wyświetlać odpowiedź dla wszystkich wartości s
od 1
do 9
. Twój wynik jest najwyższą wartością, n
której wypełnienie następuje w ciągu jednej minuty.
Testowanie
Będę musiał uruchomić Twój kod na moim komputerze z Ubuntu, więc podaj możliwie szczegółowe instrukcje dotyczące tego, jak skompilować i uruchomić kod.
Tabela liderów
- n = 13 autorstwa Christian Sievers w Haskell (42 sekundy)
źródło
s
? Co to reprezentuje?Odpowiedzi:
Haskell
orig
Funkcja tworzy wszystkie wykazy długościn
z wpisamis
lubs+1
, utrzymuje je, jeśli pochodzą one przed ich odwrotności, oblicza ich podmenusums
i umieszcza je na mapie, który pamięta także pierwszy element listy. Kiedy ten sam zestaw sum zostanie znaleziony więcej niż jeden raz, pierwszy element zostanie zastąpionyNothing
, więc wiemy, że nie musimy szukać innych sposobów na uzyskanie tych sum.Do
construct
wyszukiwania funkcyjne dla list danej długości i podana wartość początkowa, które mają dany zestaw podmenu sum. Jego część rekurencyjnaconstr
jest zasadniczo taka sama, jak ta , ale zawiera dodatkowy argument podający sumę, którą muszą mieć pozostałe wpisy listy. Pozwala to zatrzymać wcześniej, gdy nawet najmniejsze możliwe wartości są zbyt duże, aby uzyskać tę sumę, co dało znaczną poprawę wydajności. Dalsze duże udoskonalenia uzyskano poprzez przeniesienie tego testu do wcześniejszego miejsca (wersja 2) i poprzez zastąpienie listy bieżących sum przezVector
(wersja 3 (zepsuta) i 4 (z dodatkową surowością)). Najnowsza wersja wykonuje test członkostwa z tabelą odnośników i dodaje trochę więcej ścisłości i równoległości.Gdy
construct
znajdzie listę, która podaje sumy podlisty i jest mniejsza niż jej odwrotność, może ją zwrócić, ale tak naprawdę nie jesteśmy nią zainteresowani. Prawie wystarczyłoby po prostu wrócić,()
aby wskazać jego istnienie, ale musimy wiedzieć, czy musimy policzyć go dwukrotnie (ponieważ nie jest to palindrom i nigdy nie zajmiemy się jego odwrotnością). Dlatego umieszczamy 1 lub 2 jako jegoweight
listę wyników.Funkcja
count
łączy te części razem. Dla każdego zestawu sum podlisty (pochodzących zorig
), który był unikalny wśród list zawierających tylkos
is+1
, wywołujevalue
, które wywołujeconstruct
i poprzezuniqueval
sprawdza, czy jest tylko jeden wynik. Jeśli tak, to taką wagę musimy policzyć, w przeciwnym razie zestaw sum nie byłby unikalny i zwracane jest zero. Zauważ, że z powodu lenistwaconstruct
zatrzyma się, gdy znajdzie dwa wyniki.Te
main
uchwyty funkcyjne IO pętlas
od 1 do 9.Kompilowanie i uruchamianie
Na Debianie to musi pakiety
ghc
,libghc-vector-dev
ilibghc-parallel-dev
. Zapisz program w plikuprog.hs
i skompiluj goghc -threaded -feager-blackholing -O2 -o prog prog.hs
. Uruchom./prog <n> +RTS -N
gdzie gdzie<n>
jest długość tablicy, dla której chcemy policzyć unikalne tablice.źródło