Podziel tablice i programy na pół

Wprowadzenie

Masz za zadanie napisać program, który dzieli prostokątną tablicę liczb całkowitych równomiernie na pół (z dowolnego powodu). To zadanie wymaga intensywnych obliczeń, ale na szczęście masz maszynę dwurdzeniową do wykonywania obliczeń. Aby zmaksymalizować korzyści z równoległości, decydujesz się podzielić program równomiernie na pół i pozwolić, aby każdy rdzeń uruchamiał jedną z części niezależnie od drugiej.

Wejście i wyjście

Twoje dane wejściowe to prostokątna tablica 2D nieujemnych liczb całkowitych o wielkości co najmniej 1 × 1 , wykonana w dowolnym rozsądnym formacie. Rozszczepienie takiej tablicy otrzymuje się przez podział każdego poziomego rzędu do prefiksu i sufiksu (z których każdy może być pusta). Aby podział był ważny, dwa sąsiednie wiersze muszą być podzielone na ten sam indeks lub sąsiednie indeksy. Rozważmy na przykład tablicę

2 4 5 5 6 3
9 7 1 7 7 0
0 0 3 6 7 8
1 2 4 7 6 1
6 6 8 2 0 0

To jest prawidłowy podział:

 2;4 5 5 6 3
;9 7 1 7 7 0
;0 0 3 6 7 8
 1;2 4 7 6 1
 6 6;8 2 0 0

Jest to również prawidłowy podział:

2 4 5 5 6 3;
9 7 1 7 7;0
0 0 3 6 7;8
1 2 4 7;6 1
6 6 8;2 0 0

To nie jest prawidłowy podział:

2 4;5 5 6 3
9 7 1;7 7 0
0;0 3 6 7 8
1 2;4 7 6 1
6 6;8 2 0 0

Twój wynik powinien wynosić minimum

abs(sum_of_prefixes - sum_of_suffixes)

nad wszystkimi prawidłowymi podziałami danych wejściowych.

Zasady i punktacja

Powinieneś napisać dwa programy (pełne programy lub funkcje) w tym samym języku, w którym nie może istnieć żaden wspólny kod. Nazwijmy je P1 i P2 . Program P1 bierze tablicę wejściową i coś wyprowadza . Program P2 przyjmuje to jako dane wejściowe i wysyła odpowiedź z powyższego zadania dla tablicy wejściowej.

Twój wynik to maksymalna liczba bajtów P1 i P2 , przy czym niższy wynik jest lepszy.

Kilka wyjaśnień:

• Możesz napisać dwie pełne prorgamy, jedną funkcję i jeden pełny program lub dwie funkcje.
• W przypadku dwóch pełnych programów całe wyjście P1 jest podawane do P2 jako dane wejściowe, tak jak w potoku Unix P1 | P2. Programy muszą działać poprawnie, jeśli zostaną skompilowane / zinterpretowane z dwóch oddzielnych plików źródłowych.
• Jeśli którykolwiek z programów jest funkcją, jest on konwertowany na pełny program poprzez dodanie niezbędnego kodu płyty kotłowej i stosuje się do niego powyższą zasadę. W szczególności dwie funkcje nie mogą korzystać ze wspólnych funkcji pomocniczych, wspólnych instrukcji importu lub wspólnych zmiennych globalnych.

Przypadki testowe

[[1]] -> 1
[[4,5],[8,3]] -> 4
[[8],[11],[8],[10],[4]] -> 1
[[5,7,0,9,11,2,1]] -> 7
[[146,194,71,49],[233,163,172,21],[121,173,14,302],[259,169,26,5],[164,30,108,37],[88,55,15,2]] -> 3
[[138,2,37,2],[168,382,33,77],[31,199,7,15],[192,113,129,15],[172,88,78,169],[28,6,97,197]] -> 7
[[34,173,9,39,91],[169,23,56,74,5],[40,153,80,60,28],[8,34,102,60,32],[103,88,277,4,2]] -> 0
[[65,124,184,141],[71,235,82,51],[78,1,151,201],[12,24,32,278],[38,13,10,128],[9,174,237,113]] -> 2
[[164,187,17,0,277],[108,96,121,263,211],[166,6,57,49,73],[90,186,26,82,138],[173,60,171,265,96]] -> 8

Haskell, 102 bajty

Funkcja 1 (102 bajty):

l=length
[]#i=[[]]
(r:s)#i=id=<<[(splitAt j r:)<$>s#j|j<-[i-1..i+1],j>=0,j<l r]
f r=(r#)=<<[0..l$r!!0]

Funkcja 2 (90 bajtów):

g::[[([Int],[Int])]]->Int 
g a=minimum$map(\(x,y)->abs$sum(sum<$>x)-sum(sum<$>y))$unzip<$>a

Brakuje bojlera dla F1, aby uczynić go pełnym programem, łącznie z zakodowaną tablicą liczb całkowitych do sprawdzenia:

main = print $ f [[164,187,17,0,277],[108,96,121,263,211],[166,6,57,49,73],[90,186,26,82,138],[173,60,171,265,96]]

i dla F2:

main = print . g . read =<< getContents

Teraz możesz zadzwonić, runhaskell f1.hs | runhaskell f2.hsktóre wyjścia 8.

Jak to działa: fpobiera listę liczb całkowitych.

f r = (r#)=<<[0..l$r!!0]          -- for each index [0 .. length r] call # with
                                  -- the first parameter being r and
                                  -- collect the results in a single list

[]#i=[[]]                         -- base case. If the list of lists is empty, stop
(r:s)#i                           -- else let r be the first list, s all others
           j<-[i-1..i+1],         -- foreach possible index j for the next line
                 j>=0,j<l r       --    (skipping out of range indices)
     (splitAt j r:)<$>            -- split the current line at j into a pair of
                                  -- lists and prepend it to every element of
                      s#j         -- a recursive call with s and j
id=<<                             -- flatten into a single list

Teraz mamy listę wszystkich możliwych podziałów, na przykład pierwszy i losowy od środka

[([],[164,187,17,0,277]),                  [([164,187],[17,0,277]),
 ([],[108,96,121,263,211]),                 ([108,96],[121,263,211]),
 ([],[166,6,57,49,73]),                     ([166],[6,57,49,73]),
 ([],[90,186,26,82,138]),                   ([90,186],[26,82,138]),
 ([],[173,60,171,265,96])]                  ([173,60,171],[265,96])]

Funkcja gprzyjmuje taką listę i

                    unzip<$>a       -- turn every pair of lists into a list of pairs
  map(\(x,y)->                      -- foreach such pair     
      abs$sum(sum<$>x)-sum(sum<$>y) -- calculate the score
minimum                             -- and find the minimum

Uwaga: drugą funkcję można nieco zagrać w golfa, ale nie zmienia to wyniku.