Jest to kontynuacja tablic Count, które tworzą unikalne zestawy . Istotną różnicą jest definicja wyjątkowości.

Rozważ tablicę Adł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 Asą (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 Bo takiej samej długości f(A) = f(B), z wyjątkiem Aodwró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, 3która generowałaby ten sam zestaw sum.

Zadanie

Zadaniem dla danego ni sjest policzenie liczby unikalnych tablic o tej długości. Możesz założyć, że sjest pomiędzy 1i 9. Trzeba tylko liczyć tablice, w których elementy są albo liczbą całkowitą, salbo s+1. Np. Jeśli s=1liczone tablice zawierają tylko 1i 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 = 2to:

(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 nkodu kod powinien wyświetlać odpowiedź dla wszystkich wartości sod 1do 9. Twój wynik jest najwyższą wartością, nktó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)

Haskell

import Control.Monad (replicateM)
import Data.List (tails)
import qualified Data.IntSet as S
import qualified Data.Map.Strict as M
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed.Mutable (write)
import System.Environment (getArgs)
import Control.Parallel.Strategies

orig:: Int -> Int -> M.Map S.IntSet (Maybe Int)
orig n s = M.fromListWith (\ _ _ -> Nothing) 
               [(sums l, Just $! head l) | 
                   l <- replicateM n [s, s+1],
                   l <= reverse l ]

sums :: [Int] -> S.IntSet
sums l = S.fromList [ hi-lo | (lo:r) <- tails $ scanl (+) 0 l, hi <- r ]

construct :: Int -> Int -> S.IntSet -> [Int]
construct n start set =
   setmax `seq` setmin `seq` setv `seq`
   [ weight r | r <- map (start:) $ constr (del start setlist)
                                           (V.singleton start)
                                           (n-1)
                                           (setmax - start),
                r <= reverse r ]
  where
    setlist = S.toList set
    setmin = S.findMin set
    setmax = S.findMax set
    setv = V.modify (\v -> mapM_ (\p -> write v p True) setlist)
                    (V.replicate (1+setmax) False)

    constr :: [Int] -> V.Vector Int -> Int -> Int -> [[Int]]
    constr m _ 0 _ | null m    = [[]]
                   | otherwise = []
    constr m a i x =
         [ v:r | v <- takeWhile (x-(i-1)*setmin >=) setlist,
                 V.all (V.unsafeIndex setv . (v+)) a,
                 let new = V.cons v $ V.map (v+) a,
                 r <- (constr (m \\\ new) $! new) (i-1) $! (x-v) ]

del x [] = []
del x yl@(y:ys) = if x==y then ys else if y<x then y : del x ys else yl

(\\\) = V.foldl (flip del)

weight l = if l==reverse l then 1 else 2

count n s = sum ( map value [ x | x@(_, Just _) <- M.toList $ orig n s]
                      `using` parBuffer 128 rseq )
  where 
    value (sms, Just st) = uniqueval $ construct n st sms
    uniqueval [w] = w
    uniqueval _   = 0


main = do
  [ n ] <- getArgs
  mapM_ print ( map (count (read n)) [1..9]
                    `using` parBuffer 2 r0 )

origFunkcja tworzy wszystkie wykazy długości nz wpisami slub s+1, utrzymuje je, jeśli pochodzą one przed ich odwrotności, oblicza ich podmenu sumsi 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ąpiony Nothing, więc wiemy, że nie musimy szukać innych sposobów na uzyskanie tych sum.

Do constructwyszukiwania funkcyjne dla list danej długości i podana wartość początkowa, które mają dany zestaw podmenu sum. Jego część rekurencyjna constrjest 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 przez Vector(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 constructznajdzie 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 jego weightlistę wyników.

Funkcja countłączy te części razem. Dla każdego zestawu sum podlisty (pochodzących z orig), który był unikalny wśród list zawierających tylko si s+1, wywołuje value, które wywołuje constructi poprzez uniquevalsprawdza, 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 lenistwa constructzatrzyma się, gdy znajdzie dwa wyniki.

Te mainuchwyty funkcyjne IO pętla sod 1 do 9.

Kompilowanie i uruchamianie

Na Debianie to musi pakiety ghc, libghc-vector-devi libghc-parallel-dev. Zapisz program w pliku prog.hsi skompiluj go ghc -threaded -feager-blackholing -O2 -o prog prog.hs. Uruchom ./prog <n> +RTS -Ngdzie gdzie <n>jest długość tablicy, dla której chcemy policzyć unikalne tablice.