Split arrays and programs in half

Question

Introduction

You have been tasked to write a program that splits a rectangular integer array evenly in half (for whatever reason). This task is computationally intensive, but luckily you have a dual-core machine to perform the calculations. To maximize the benefits of parallelism, you decide to split the program evenly in half and let each core run one of the parts independently of the other.

Input and output

Your input is a rectangular 2D array of nonnegative integers of size at least 1×1, taken in any reasonable format. A splitting of such an array is obtained by splitting each horizontal row into a prefix and a suffix (either of which may be empty). For a splitting to be valid, two adjacent rows must be split at the same index or adjacent indices. For example, consider the array

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

This is a valid splitting:

 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

This is also a valid splitting:

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

This is not a valid splitting:

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

Your output shall be the minimum value of

abs(sum_of_prefixes - sum_of_suffixes)

over all valid splittings of the input.

Rules and scoring

You shall write two programs (either full programs or functions) in the same language, which must not have any shared code between them. Let's call them P1 and P2. Program P1 takes the input array, and outputs something. Program P2 takes this something as input, and outputs the answer of the above task for the input array.

Your score is the maximum of the byte counts of P1 and P2, lower score being better.

Some clarifications:

• You can write two full prorgams, one function and one full program, or two functions.
• In the case of two full programs, the entire output of P1 is fed to P2 as input, as in the Unix pipeline P1 | P2. The programs must function correctly if compiled/interpreted from two separate source files.
• If either program is a function, it is converted to a full program by adding the necessary boilerplate code, and the above rule is applied to it. In particular, two functions cannot use shared auxiliary functions, shared import statements, or shared global variables.

Test cases

[[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

Answer 1

Haskell, 102 bytes

Function 1 (102 bytes):

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]

Function 2 (90 bytes):

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

Missing boilerplate for F1 to make it a full program, including the hardcoded integer array to check:

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]]

and for F2:

main = print . g . read =<< getContents

Now you can call runhaskell f1.hs | runhaskell f2.hs which outputs 8.

How it works: f takes a list of list of integers.

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

Now we have a list of all possible splits, for example the first one and a random one from the middle

[([],[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])]

Function g takes such a list and

                    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

Note: the second function can be golfed a little bit more, but it doesn't change the score.