Make the cheapest cut

Question

“Cut” a matrix of integers on the line where the sum of the absolute differences of “severed” neighbors is the least.

Example

Consider this matrix:

 1  2 -4
 5 -1  3
 2 -2  0

It can be cut in 4 places, here shown by lines lettered A–D:

     A    B
     ╷    ╷
   1 ╎  2 ╎ -4
C ---╎----╎----
   5 ╎ -1 ╎  3
D ---╎----╎----
   2 ╎ -2 ╎  0
     ╵    ╵  

The cost to cut on a line is the sum of the absolute differences of the numbers opposing each other on that line. For example, cutting on B would cost \$\lvert 2--4\rvert+\lvert-1-3\rvert+\lvert-2-0\rvert=12\$.

Your task, however, is to find the cheapest cut, which in this case is D: \$\lvert 5-2\rvert+\lvert-1- -2\rvert+\lvert 3-0\rvert=7\$.

Input

The input will be a 2-D matrix of integers in any reasonable format. It will always have at least two rows and at least two columns and might not be square.

Output

The output may be one of the following:

1. Two separate matrices representing the “pieces” of the original matrix after the cut, in any reasonable format. The two matrices may be in either order but must be the same shape as they were in the original matrix.
2. An expression representing where the cut is, e.g. D as above or the equivalent index 3 (0-based) or 4 (1-based), in any reasonable format. You may invent your own indexing scheme but it must be described in your answer and be consistent.

Rules

• If more two or more cuts are tied for lowest cost, you may either output any one of them, or all of them.

• Default I/O rules and standard rules apply. Standard loopholes are forbidden.

• This is code-golf; shortest solution in bytes wins.

Test cases

Input

 8  1  2 -3
 6 -2 -7 -4
-1 -6 -9  3

Output
      x
 8  1 ╎  2 -1
 6 -2 ╎ -7 -4
-1 -6 ╎ -9  3
      ╵

Input
                 
 2 -2  1
 8  7 -7
-9  5 -3
 0 -8  6

Output

  2 -2  1
x---------
  8  7 -7
 -9  5 -3
  0 -8  6

and/or

  2 -2  1
  8  7 -7
x---------
 -9  5 -3
  0 -8  6

Answer 1

Excel, 321 bytes

Golfed code:

Sub z()
With ActiveSheet.UsedRange
m=-1
x=.Rows.Count
y=.Columns.Count
For c=2To y
t=0
For r=1To x
t=t+Abs(Cells(r,c)-Cells(r,c-1))
Next
If m=-1Then m=t
If t <= mThen m=t:Set a=.Columns(c)
Next
For r=2To x
t=0
For c=1To y
t=t+Abs(Cells(r,c)-Cells(r-1,c))
Next
If t<mThen m=t:Set a=.Rows(r)
Next
a.Insert
End With
End Sub

Formatted and commented code:

Sub z()

    ' Using With for the entire procedure saves plenty of bytes.
    With ActiveSheet.UsedRange
        
        ' Set the initial minimum to -1 so we can tell when it hasn't been changed yet.
        ' We could possibly set this (2^1023*1.99) or something but then there'd be some weird edge case where this would fail to cut at the right place.
        m = -1
        
        ' Save the number of rows and columns now to save bytes later.
        x = .Rows.Count
        y = .Columns.Count
        
        ' Loop through each column, starting with the second column and looking to the left.
        For c = 2 To y
            
            ' Calculate the cut cost for this column.
            t = 0
            For r = 1 To x
                t = t + Abs(Cells(r, c) - Cells(r, c - 1))
            Next
            
            ' Check if the min is still the initial value and change it.
            If m = -1 Then m = t
            
            ' If the total is <= the current minimun, then save it as the new minimum.
            ' We have to use <= here because "a" is not set in the line above.
            If t <= m Then m = t: Set a = .Columns(c)
        Next
        
        ' Repeat everything we just did but go row by row instead and don't worry about the initial min value.
        For r = 2 To x
            t = 0
            For c = 1 To y
                t = t + Abs(Cells(r, c) - Cells(r - 1, c))
            Next
            If t < m Then m = t: Set a = .Rows(r)
        Next
        
        ' Insert a row or column as needed. This will default to shifting rows and and columns to the right.
        a.Insert
    
    End With
    
End Sub

Input format:

Input the matrix with one number per cell starting in cell A1 of the active sheet.

Output format:

The code will insert a row or column in the correct location, cutting the data. This is equivalent to output option #1 the way the question is written now.

Answer 2

MATLAB / Octave, 63 46 bytes

-17 bytes thanks to @Luis Mendo

g=@(B)sum(abs(diff(B))')
@(A)min([g(A') g(A)])

Returns an anonymous function, used like

f = ans
[v,i] = f([1 2 3; 4 5 6; 7 8 9])

Where i becomes the "index" of the cut, mapping to the letter assigned to the cut in the problem description (1 -> A, 2 -> B, etc.)

Answer 3

J, 23 bytes

(=<./)@,&(1#.2|@-/\])|:

Try it online!

output

Output is a boolean list of "all possible horizontal cuts" followed by "all possible vertical cuts". For example, if the input is a 3 x 4 matrix, the output will be length 5 and should be interpreted as follows:

      the first vertical cut is minimal
      v
0 0 | 1 0 0
^^^
 neither horizontal cut is minimal

If there are multiple ones in the output, all of them are minimal.

how

• ...|: For both the input and its transpose...
• &(1#.2|@-/\]) Take every pair of rows, take the absolute value of the elementwise differences, and sum
• , Cat those results together, putting the horizontal results first
• (=<./) Mark every place that equals the minimum with a 1

Answer 4

Jelly, 9 bytes

,ZạƝ€§NŒM

A monadic Link that accepts a list of lists and yields a list of all possible minimal cuts, each of which is a pair of numbers, the (1-indexed) index to cut before (an integer, two or greater) and a direction indicator which is \$1\$ if the index is counting rows or \$2\$ if counting columns - e.g. [5,2] means to cut after the fifth column.

Try it online!

How?

,ZạƝ€§NŒM - Link: list of lists, M
 Z        - transpose (M)
,         - (M) paired with (that)
    €     - for each:
   Ɲ      -   for neighbours:
  ạ       -     (left) absolute difference (right) (vectorises)
     §    - sums (vectorises at depth 1)
      N   - negate
       ŒM - maximal multi-dimensional indices

Answer 5

MATL, 13 bytes

!G,wd|!s]h&X<

The output indicates the cut as the letters in the challenge text, with 1, 2 corresponding to A, B, ...

Try it online! Or verify all test cases.

How it works

!      % Implicit input. Transpose
G      % Push input again
,      % Do twice
  w    %   Swap
  d    %   Consecutive differences, vertically
  |    %   Absolute value, element-wise
  !    %   Tranpose
  s    %   Sum, vertically. Gives a row vector
]      % End
h      % Concatenate the two row vectors
&X<    % (1-based) index of (first) minimum. Implicit display

Answer 6

APL (Dyalog APL), 18 bytes

⊃∘⍋,⍥(+⌿∘|2-/⊢)∘⍉⍨

Attempt This Online!

I/O

• Input is a numerical matrix
• Output is the index of the cut with the same (1-based) indexing scheme as the OP -- leftmost vertical cut is 1, enumerate vertical cuts left-to-right, then horizontal cuts top-to-bottom

Explanation

⊃∘⍋,⍥(+⌿∘|2-/⊢)∘⍉⍨

       (+⌿∘|2-/⊢)     ⍝ Cost function, calculates costs of vertical cuts
            2-/⊢      ⍝   Pairwise difference of horizontally adjacent entries
           |          ⍝   Absolute value
        +⌿           ⍝   Sum vertically

    ,⍥( ...... )     ⍝ Concatenate the result of calling the cost function on ...
                 ∘⍉⍨ ⍝   ...the input and its transpose
⊃∘⍋                  ⍝ Argsort ascending and return the first entry
                      ⍝  (index of smallest value)

Answer 7

05AB1E, 8 bytes

ø‚€üαOWQ

Outputs a pair of \$[horizontalCuts,verticalCuts]\$, where the truthy cut (1) is the minimum result (e.g. [[0,1],[0,0]] for the example of the challenge description, where the cuts are \$[[C,D],[A,B]]\$). (If more than one minimal cut is possible like the final test case, both cuts will be 1.)

Try it online or verify all test cases.

Explanation:

ø         # Zip/transpose the (implicit) input-matrix; swapping rows/columns
 ‚        # Pair the (implicit) input-matrix with its transposed matrix
  €       # Map over this pair of matrices:
   ü      #  Loop over each overlapping pair of rows:
    α     #   Take the (vectorized) absolute difference between values at the same
          #   positions in the two rows
     O    # Take the sum of each inner-most list
      W   # Push the flattened minimum (without popping the pair of lists)
       Q  # Check which inner-most value(s) are equal to this minimum
          # (after which the result is output implicitly)

Answer 8

PARI/GP 114 bytes

C(v,w)=vecsum(abs(v-w));c(M)=vecmin(concat(vector(#M-1,i,C(M[,i+1],M[,i])),vector(#M~-1,i,C(M[i+1,],M[i,]))),&L);L

Input: Matrix M, output: position of cut, encoded as integer, i.e., {1,2,3,4,...} corresponds to {A,B,C,D,...} in the task description.

Examples

c([1,2,-4;5,-1,3;2,-2,0])
4
c([2,-2,1;8,7,-7;-9,5,-3;0,-8,6])
3
c([8,1,2,-3;6,-2,-7,-4;-1,-6,-9,3])
2

Answer 9

Charcoal, 36 bytes

Ｆ⟦θＥ⌊θＥθ§λκ⟧Ｆ⊖Ｌ⌊ι⊞υΣＥι↔⁻§λκ§λ⊕κＩ⌕υ⌊υ

Try it online! Link is to verbose version of code. Outputs a 0-indexed integer corresponding to the letters from the challenge. Explanation:

Ｆ⟦θＥ⌊θＥθ§λκ⟧

Loop over the matrix and its transpose.

Ｆ⊖Ｌ⌊ι

Loop over the indices of pairs of adjacent columns (which for the transposed matrix map to rows of the original matrix).

⊞υΣＥι↔⁻§λκ§λ⊕κ

Calculate the cost of this cut.

Ｉ⌕υ⌊υ

Output the (first) index of the minimum cost.

Answer 10

sclin, 50 bytes

"tpose"Q ,"."mapf"\& fold~"Q =
2%`",_ - abs +/"map

Try it here!

For testing purposes:

[[8 1 2 3_ ][6 2_ 7_ 4_ ][1_ 6_ 9_ 3]] ; \>N map >A f>o
"tpose"Q ,"."mapf"\& fold~"Q =
2%`",_ - abs +/"map

Explanation

Prettified code:

\tpose Q , \; mapf ( \& fold~ ) Q =
2%` ( ,_ - abs +/ ) map

• \tpose Q , pair matrix with its transposed copy
• \; mapf flatmap...
  • 2%` (...) map pairwise map over each row/column...
    • ,_ - abs +/ absolute difference, sum
• ( \& fold~ ) Q get minimum sum
• = get all minimum sums