Minimum vertical slice sum

Question

I want to input a matrix size N x N and cut a slice such that each element is directly below, left-below or right-below the one above it. And cost is the sum of all elements in the slice. How do I write a program to do this?

Eg. matrix is given as list of list

[[1,2,3],
 [4,5,6],
 [7,8,9]]

which has the following slices:

(1,4,7), (1,4,8), (1,5,7), (1,5,8), (1,5,9), 
(2,4,7), (2,4,8), (2,5,7), (2,5,8), (2,5,9), (2,6,8), (2,6,9), 
(3,5,7), (3,5,8), (3,5,9), (3,6,8), (3,6,9)

Then slice of lowest weight is (1,4,7) which has sum 12.

Answer 1

def findMinPath(mat): 
  
    # To find max val in first row 
    res = min([mat[0][i] for i in range(M)])
   
    for i in range(1, N):     
        for j in range(M):
            if j == 0: #if the left most, no col(j-1) in the row above
                mat[i][j] += min(mat[i - 1][j], mat[i - 1][j + 1]) 
            elif j == M-1: #if the right most, no col(j+1) in the row above
                mat[i][j] += min(mat[i - 1][j], mat[i - 1][j - 1]) 
            else:
                mat[i][j] += min(mat[i - 1][j], mat[i - 1][j - 1],mat[i - 1][j + 1]) 
   
    # To find max val in first row      
    res = min([mat[N-1][i] for i in range(M)])
    
    return res 

Answer 2

This is a question of recursion + dynamic programming(DP). You may or may not use DP depending on the size of the test cases. Such questions usually get asked in competitive programming contests and if you find your test cases timing out, I'd recommend that you augment my code with DP. I will talk about how to do it once I explain the algorithm and give you the code.

From every element in the topmost row of your matrix, you will have to traverse down. While traversing down, you will have three options:

1. Traverse down to the element directly below the element you are at
2. Traverse down to the element to the left of the element which is directly below the element you are at
3. Traverse down to the element to the right of the element which is directly below the element you are at

Keep on adding the elements as you keep on traversing using recursion. Thus for every element in the matrix, three kinds of summation are possible. I call them left sum, middle sum, and right sum. The names themselves are intuitive, but please feel free to ask in comments in case they are not.

I maintain a global list to keep the sum of every slice. Finally, I return the minimum sized element from this global list. Not to mention that the smallest element of this list only will be the minimum vertical slice of your matrix.

Please find the code below (in Python 2.7):

#!/bin/python

# Global list L to store sum of all the vertical slices.

L = []
def fun(M, i, j):
    """
    M: The matrix
    i: Row number
    j: Column number
    Return: Add M[i][j] to the left, middle and right sum and return the three values as a list
    """
    # Reutrn the element if you are at the last row
    if i==len(M)-1:
        return [M[i][j]]
    # Calculate the left sum only if you are not in the first column 
    if j>0:
        l_sum = [M[i][j] + elm for elm in fun(M, i+1, j-1)]
    m_sum = [M[i][j] + elm for elm in fun(M, i+1, j)]
    # Calculate the right sum only if you are not in the last column
    if j<len(M[0])-1:
        r_sum = [M[i][j] + elm for elm in fun(M, i+1, j+1)]
    # Return the sum of columns as a list
    if j>0 and j<len(M[0])-1:
        return l_sum+m_sum+r_sum
    if j==0:
        return m_sum+r_sum
    if j==len(M[0])-1:
        return l_sum+m_sum

def MinSliceWeight(Matrix):
    """
    Matrix: The matrix whose vertical slice sum is to be calculated
    Return: The minimum sum of the slices
    """
    global L
    # Iterate over all elements in the topmost row and find the sum of all slices for an element
    for k in range(len(Matrix[0])):
        slices = fun(Matrix, 0, k)
        for elm in slices:
            L.append(elm)
    return min(L)

Matrix_rows = int(raw_input().strip())
Matrix_columns = int(raw_input().strip())

Matrix = []

for _ in xrange(Matrix_rows):
    Matrix.append(map(int, raw_input().rstrip().split()))

res = MinSliceWeight(Matrix)
print res

Adding DP to the code: As you might have noticed, this code keeps track of every element's left, middle and right sum. You can easily find by dry running this code on a small sized matrix(preferably 2x3) that sums for elements get calculated again. To prevent this, you can make a matrix of the same size as the original matrix and store the three sums of every element in it as a tuple. If the tuple exists for a particular element, fetch the tuple from your matrix. This will prevent additional function calls and save memory.

Answer 3

We can treat the matrix elements as vertices in a graph and consider the possible connections (defined as by your "slices") as edges. Then the problem can be expressed as finding the shortest path from any of the top-row vertices to any of the bottom-row vertices where each edge has the a weight equals the value of the connected element (except for edges connecting the first row which have the first row element's weight in addition).

Then we can use for example the Bellman-Ford algorithm for finding the shortest path under these conditions. The following is an example implementation:

import numpy as np


m, n = 10, 10
M = np.arange(m*n).reshape(m, n) + 1
for i in range(1, m):
    M[i:] = np.roll(M[i:], 1 if i <= m // 2 else -1, axis=1)
print('Matrix:')
print(M, end='\n\n')


def edges():
    for i in range(m - 1):
        yield [(i, 0), (i + 1, 0)]
        yield [(i, 0), (i + 1, 1)]
        for j in range(1, n - 1):
            yield [(i, j), (i + 1, j - 1)]
            yield [(i, j), (i + 1, j)]
            yield [(i, j), (i + 1, j + 1)]
        yield [(i, n - 1), (i + 1, n - 1)]
        yield [(i, n - 1), (i + 1, n - 2)]


def compute_path(start):
    distance = {index: np.inf for index in np.ndindex(m, n)}
    predecessor = {index: None for index in np.ndindex(m, n)}

    distance[start] = M[start]
    for __ in range(M.size - 1):
        for u, v in edges():
            weight = M[v]
            if distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight
                predecessor[v] = u
    stop = min(filter(lambda x: x[0] == n - 1, distance), key=lambda y: distance[y])
    path = [stop]
    while predecessor[path[-1]] is not None:
        path.append(predecessor[path[-1]])
    return path[::-1], distance[stop]


paths = [compute_path((0, c)) for c in range(n)]
opt = min(paths, key=lambda x: x[1])
print('Optimal path: {}, with weight: {}'.format(*opt))
print('Vertices: ', M[list(zip(*opt[0]))])

Which gives as an output:

Matrix:
[[  1   2   3   4   5   6   7   8   9  10]
 [ 20  11  12  13  14  15  16  17  18  19]
 [ 29  30  21  22  23  24  25  26  27  28]
 [ 38  39  40  31  32  33  34  35  36  37]
 [ 47  48  49  50  41  42  43  44  45  46]
 [ 56  57  58  59  60  51  52  53  54  55]
 [ 67  68  69  70  61  62  63  64  65  66]
 [ 78  79  80  71  72  73  74  75  76  77]
 [ 89  90  81  82  83  84  85  86  87  88]
 [100  91  92  93  94  95  96  97  98  99]]

Optimal path: [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 4), (7, 3), (8, 2), (9, 1)], with weight: 460
Vertices:  [ 1 11 21 31 41 51 61 71 81 91]

Answer 4

This problem can be represented using graph theory and then solved by using linear programming techniques.

By treating all elements of the matrix as vertices the goal is to find a set of edges that minimizes the weighted path through the matrix under certain constraints (e.g. how slices can be built).

We can use scipy.optimize.linprog (which uses the Simplex algorithm) for solving the linear programming problem c.T @ x. Each element of the solution represents a possible connection between any of the N nodes (i.e. the solution vector has size N**2). The coefficients c determine the weight of a connection: that is the weight of the node connected to (the value of the matrix element), except for the first layer where we need add the starting weights as well.

We also need to apply several constraints in order to get a valid solution:

1. The result must have exactly N - 1 edges.
2. Each node must not be connected to itself.
3. Each row must connect to exactly one node except for the last row.
4. Each node can connect to at most one other node (except for the ones of the last layer which must have zero connections).
5. Each node must respect its possible successors (which are given by the "shape" of slices).
6. For each of the layers 1 through (N-1) any node connected to must connect to the next layer.

These are quite a lot of pieces we must fit together and so the resulting code is a bit lengthy and might appear overwhelming at first. However when taking a closer look it should be possible to identify the single pieces and their structure (I tried to comment as much as possible + added several prints). So here goes the example code:

import numpy as np
from scipy.optimize import linprog


M = np.arange(9).reshape(3, 3) + 1
print('Matrix:')
print(M)
print('\n\n')

N = len(M)

# Compute all possible connections between nodes (1: possible, 0: forbidden).
pc = np.zeros(shape=(N**2, N**2), dtype=int)

# Connect to nodes below (except the last layer).
i = np.arange(N**2 - N)
pc[i, i + N] = 1

# Connect to left nodes (except the last layer and leftmost column).
pc[i, i + N - 1] = 1
pc[i[::N], i[::N] + N - 1] = 0

# Connect to left nodes (except the last layer and rightmost column).
r = i + N + 1
mask = r < N**2
pc[i[mask], r[mask]] = 1
r = r[N-1::N]
mask = mask[N-1::N]
pc[i[N-1::N][mask], r[mask]] = 0

print('Possible connections:')
print(pc)
print('\n\n')

# Coefficients for linear programming problem represent the weight of connections.
c = np.zeros(shape=(N**2, N**2), dtype=int)
# Add weights for connections.
c = np.tile(M.ravel(), (N**2, 1))
# Add additional weights for first layer.
c[:N] += M[0, :][:, None]
print('Coefficient matrix:')
print(c)
print('\n\n')

# === Add constraints ===
A_eq_1 = np.concatenate((
    # Exactly N-1 connections.
    np.ones(N ** 4, dtype=int)[None, :],
    # No node can connect to itself.
    np.diag([1] * N**2).flatten()[None, :]
), axis=0)
b_eq_1 = np.asarray([N - 1, 0], dtype=int)
print('Exactly N-1 connections and no self-connecting nodes:')
print(A_eq_1)
print(b_eq_1)
print('\n\n')

# Each layer connects to exactly one other node (except the last layer).
A_eq_2 = np.zeros((N, N ** 4), dtype=int)
for j in range(N):
    A_eq_2[j, j * N**3:(j + 1)*N**3] = 1
b_eq_2 = np.ones(N, dtype=int)
b_eq_2[-1] = 0
print('Each layer connects to exactly one other node (except the last layer):')
print(A_eq_2)
print(b_eq_2)
print('\n\n')

# Each node connects to at most one other node (except the ones in the last layer).
N = N ** 2
A_ub_1 = np.zeros((N, N ** 2), dtype=int)
for j in range(N):
    A_ub_1[j, j * N:j * N + N] = 1
b_ub_1 = np.ones(N, dtype=int)
b_ub_1[-1] = 0
print('Each node connects to at most one other node (except the ones in the last layer):')
print(A_ub_1)
print(b_ub_1)
print('\n\n')

# Each node respects its possible succesors (i.e. forbid all other connections).
A_eq_3 = np.zeros((N, N ** 2), dtype=int)
for j in range(N):
    A_eq_3[j, j * N:j * N + N] = 1 - pc[j, :]
b_eq_3 = np.zeros(N, dtype=int)
print('Each node respects its possible succesors (i.e. forbid all other connections):')
print(A_eq_3)
print(b_eq_3)
print('\n\n')

# For the layers 1 through (N-1) each node connected to must connect to the next layer.
A_eq_4 = np.zeros((N, N ** 2), dtype=int)
for j in range(len(M), N-len(M)):
    A_eq_4[j, j::N] = 1
    A_eq_4[j, j*N:(j+1)*N] = -1
b_eq_4 = np.zeros(N, dtype=int)
print('For the layers 1 through (N-1) each node connected to must connect to the next layer:')
print(A_eq_4)
print(b_eq_4)
print('\n\n')

# Concatenate all constraints.
A_eq = np.concatenate([A_eq_1, A_eq_2, A_eq_3, A_eq_4])
b_eq = np.concatenate([b_eq_1, b_eq_2, b_eq_3, b_eq_4])

A_ub = np.concatenate([A_ub_1])
b_ub = np.concatenate([b_ub_1])

res = linprog(c.ravel(), A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0, 1))
print(res.success)
print(res.x.reshape(N, N))  # Edges.

The very last output is the result and it is of the form:

[[0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0.]]

Which tells us that in order to get the minimum path we should connect node 0 (row index) to node 3 (column index) as well as node 3 (row index) to node 6 (column index). This represents the path (or "slice") (1, 4, 7). We can deduce the path by starting at the first row and then walking through the graph as the edges point:

edges = res.x.reshape(N, N)
for i, r in enumerate(edges):
    # Numerical instabilities can cause some elements to have very small values > 0.
    if r.sum() > 0.5:
        print('Connect {} -> {}'.format(i, r.argmax()))

path = [edges[:len(M)].ravel().argmax() // N]
while edges[path[-1]].max() > 0.5:
    path.append(edges[path[-1]].argmax())
print('Path: ', path)
print('Elements: ', M.ravel()[path])
print('Path weight: ', M.ravel()[path].sum())

Final note

The above example code leaves lots of room for performance improvements. For example it considers all possible connections between nodes as solutions which scale as M.size**2. Though we constrain the possible connections the number of computations is still much larger than if we constrained it right from the beginning, by including it in the problem architecture. That means that instead of having M.size**2 coefficients we could go with just 2*(M.shape[0] - 1) + 3*(M.shape[1] - 2)*(M.shape[0] - 1) which scales only as M.size. Plus we can use a much smaller constraint matrix since we've built these constraints already in the architecture of the problem. Taking the above code example as a basis it should be possible to adapt it accordingly. Thus I'll conclude at this point and leave the implementation of possible performance improvements to the interested reader.

(The above implementation also only works on square matrices, generalization to non-square matrices should be straightforward though.)

Answer 5

As vivek mentioned, you can solve this with a dynamic program:

Create a cost table that has the same size as your input matrix. Every element of the cost matrix stores the cost of the minimal slice that ends at that element. If you also store the preceding slice element in this cost table, you can also extract the actual slice in the end (instead of just its cost).

You can initialize the cost table pretty easily. Just copy the first row of your input matrix into the table. Then, we are going to fill the rest of the table row by row. Let C be the cost matrix and M the input matrix. Then:

//Initialize cost table
for col = 0 to N - 1
    C(0, col) = M(0, col)
//Run dynamic program
for row = 1 to N - 1
    for col = 0 to N - 1
        //take the minimum of the three possible predecessors:
        //make sure that the entries exist (i.e., take care of the edges, not shown here)
        C(row, col) = M(row, col) 
                       + min(C(row - 1, col - 1)), C(row - 1, col), C(row - 1, col + 1))

After this, you just need to find the minimum in the last row of C, which will give you the cost of the minimal slice. To get the actual slice, walk along the predecessor pointers that you set up during the loop (not shown in the pseudo-code snippet).