# Weight of the Least Weighted RoD Path

Let A be an m by n rectangular matrix of positive integers, where m and n are also positive integers.

We are interested in RoD ('Right-or-Down') paths from the upper-left cell of A to the lower right cell; in an RoD path, each successive cell of the path is either one cell to the Right of or one cell Down from the previous cell.

Given any such RoD path, we can take the sum of the cells in A in that path.

For example, consider the 4 by 3 matrix:

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


Then we can consider the RoD path:

1 > 2   3   4
v
5   1   6   7
v
8   2 > 1 > 1


which has a sum of 1+2+1+2+1+1=8. It's worth noting that this path has the smallest sum of all possible RoD paths from upper left to lower right in that matrix.

So, the proposed challenge is to provide the shortest function/program in your language of choice that outputs the minimum sum an RoD path from upper left to lower right can have in a given matrix A.

The usual forbidden loopholes are in effect. Your input can be in any reasonable format; your output must be an integer.

This is code-golf; answers are scored by number of bytes.

## Test Cases

[  ] -> 5

[ [5, 2] ] -> 7

[ ,
 ] -> 7

[ [ 9 , 1 , 12, 3 ],
[ 12, 11, 6 , 11],
[ 12, 9 , 2 , 11] ] -> 40

[ [ 6 , 8 , 11, 2 ],
[ 3 , 6 , 7 , 6 ],
[ 6 , 2 , 8 , 12] ] -> 37

[ [ 4 , 5 , 8 , 4 ],
[ 6 , 5 , 9 , 4 ],
[ 2 , 5 , 6 , 8 ] ] -> 31

[ [ 4 , 5 , 15, 18, 30],
[ 26, 26, 3 , 4 , 5 ],
[ 7 , 9 , 29, 25, 14],
[ 16, 1 , 27, 13, 27],
[ 23, 11, 25, 24, 12],
[ 17, 23, 7 , 14, 5 ] ] -> 94

[ [ 10, 15, 7 , 2 , 9 ],
[ 24, 5 , 2 , 1 , 25],
[ 2 , 12, 14, 30, 18],
[ 28, 4 , 12, 22, 14],
[ 15, 21, 21, 11, 4 ],
[ 21, 15, 21, 29, 9 ] ] -> 103


# J, 42 bytes

v=._1+1#.$Sum of two dimensions - 1; assign to v (v is a verb) (2# ){.!._] Extend the given array in both dimensions [:</. Extract the antidiagonals as boxed arrays v @{. Take the first v antidiagonals ( )&.>/ Reduce over unboxed items: }.<.}: Given the right item R, take the minimum of R[1:] and R[:-1] + Add to the left item  ### Illustration 1 2 3 4 Input array, dimensions = 3,4 5 1 6 7 8 2 1 1 1 2 3 4 _ _ Extended to 6,6 with filler _ (infinity) 5 1 6 7 _ _ 8 2 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 Diagonalize and take first 6 rows 5 2 8 1 3 _ 2 6 4 _ _ 1 7 _ _ _ _ 1 _ _ Reduction: left+min(right[1:], right[:-1]) 1 1 => 8 5 2 5 2 => 10 7 8 1 3 8 1 3 => 12 5 11 _ 2 6 4 _ 2 6 4 => _ 4 8 12 _ _ 1 7 _ => _ _ 2 8 _ _ _ _ 1 _ _  • This is a really nice solution! Nov 26, 2018 at 6:55 # JavaScript (ES6), 7877 76 bytes m=>(M=g=s=>(v=(m[y]||0)[x])?g(s+=v,y++)|g(s,x++,y--)*x--|M<s?M:M=s:0)(x=y=0)  Try it online! ### Commented m => ( // m[] = input matrix M = // initialize the minimum M to a non-numeric value g = s => // g = recursive function taking the current sum s (v = (m[y] || 0)[x]) ? // if the current cell v is defined: g(s += v, y++) | // do a recursive call at (x, y + 1) g(s, x++, y--) * x-- // do a recursive call at (x + 1, y) | // if at least one call did not return 0 (which means // that we haven't reached the bottom-right corner) M < s ? // or M is less than s (false if M is still non-numeric): M // return M unchanged : // else: M = s // update M to s, and return this new value : // else (we're outside the bounds of the matrix): 0 // return 0 )(x = y = 0) // initial call to g with s = x = y = 0  ## Haskell, 63 57 bytes f x@((a:_:_):c:d)=a+min(f$c:d)(f$tail<$>x)
f x=sum$id=<<x  Try it online! f x@((a:_:_):c:d)= -- if it's at least a 2x2 matrix a+min -- add the top left element to the minimum of the -- path costs of f$c:d                --   the matrix with the first row dropped and
f$tail<$>x           --   the matrix with the first column dropped
f x=                         -- else, i.e. a 1xm or nx1 matrix, i.e. a vector
sum$id=<<x -- return the sum of this vector  # MATL, 383630 29 bytes Thanks to @Giuseppe for pointing out a mistake, now corrected. lyZyqsG&nghZ^Yc!tsGz=Z)Ys)sX<  ### Explanation l % Push 1 y % Input, implicit. Duplicate from below. Pushes the input below % the current 1, and a copy of the input on top Zy % Size of input. Gives [m, n] qs % Subtract 1 element-wise, sum. Gives m+n-2 G % Push input again &n % Push size as two separate numbers. Gives m, n gh % Transform n into 1 and concatenate horizontally. Gives [m, 1] Z^ % Cartesian power of [m, 1] raised to m+n-2. This produces the % Cartesian tuples as row of a matrix. A typical tuple may be % [1, m, 1, m, m]. This will define a path along the matrix in % linear, column-wise indexing (down, then across). So 1 means % move 1 step down, and m means move m steps "down", which is % actually 1 step to the right Yc % Concatenate strcat-like. This prepends the 1 that is at the % bottom of the stack to each row ! % Transpose. Each tuple (extended with initial 1) is now a column !ts % Duplicate, sum of each column Gz % Number of nonzeros of input. Gives m*n-1 =Z) % Keep only columns that sum m*n. That means that, starting from Ys % Cumulative sum of each column. This defines the path ) % Index: pick entries specified by the path s % Sum of each column X< % Minimum % Display, implicit  # R, 90 bytes function(m){l=sum(m|1) if(l>1)for(i in 2:l)m[i]=m[i]+min(m[i-1],m[max(0,i-nrow(m))]) m[l]}  Try it online! The naive solution: iterate through the array (down the columns), replacing each entry by the sum of itself and the minimum of its above and to-the-left neighbors, if they exist, then return the last entry. • Possibly computing all paths and selecting the minimum is golfier. Nov 28, 2018 at 3:53 # Perl 6, 57 54 bytes my&f={|.flat&&.[0;0]+min (f(.[1..*]),f$_>>[1..*])||0}


Try it online!

### Explanation

my&f={                                               }  # Function f
|.flat&&  # Return empty slip if matrix is empty
.[0;0]+  # Value at (0,0) plus
min  # Minimum of
f(.[1..*])   # Rows 1..*
f $_>>[1..*] # Columns 1..* ( , )||0 # Or 0 if empty  • 53 bytes through using $! instead of &f
– Jo King
Nov 26, 2018 at 23:24

# Röda, 100 89 bytes

f A{g={|x,y|{g(x-1,y)if[x>0];g(x,y-1)if[y>0];if[x+y=0]}|min|[A[x][y]+_]}g#A-1,#A-1}


Try it online!

-9 bytes thanks to Cows quack

• Hi! If you iterate from the ending point, you can get 91 bytes. Nov 26, 2018 at 16:09

# Python 3, 108 bytes

def f(A,m,n,i=0,j=0):r=i+1<m and f(A,m,n,i+1,j);d=j+1<n and f(A,m,n,i,j+1);return A[i][j]+min(r or d,d or r)


Try it online!

## Ungolfed

def f(A, m, n, i=0, j=0):
right = i + 1 < m and f(A, m, n, i + 1, j)
down  = j + 1 < n and f(A, m, n, i, j + 1)
return A[i][j] + min(right or down, down or right)


# Jelly, 21 bytes

ZI_.ỊȦ
ŒJŒPÇƇLÐṀœị⁸§Ṃ


Try it online!

### How?

ZI_.ỊȦ - Link 1: isDownRight?: List of 2d indices (limited to having no repetitions)
Z      - transpose
I     - deltas (vectorises)
_.   - subtract 1/2 (vectorises)
Ị  - insignificant? (effectively _.Ị here is like "v in {0,1}? 1 : 0")
Ȧ - any & all (0 if a 0 is present when flattened, else 1)

ŒJŒPÇƇLÐṀœị⁸§Ṃ - Main Link: list of lists of integers, A
ŒJ             - multi-dimensional indices of A
ŒP           - power-set
Ƈ         - filter keep only those truthy by:
ÐṀ      - filter keep only those maximal by:
L        -   length
⁸   - chain's left argument, A
œị    - multi-dimensional index into (vectorises)
§  - sum each
Ṃ - minimum


# APL (Dyalog Classic), 37 32 bytes

{⊃⌽,9e9(⊢⌊⍵+(2⊣⌿⍪)⌊2⊣/,)⍣≡+⍀+\⍵}


Try it online!

+⍀+\ partial sums horizontally and vertically - this provides an initial overestimate for the paths to each square

9e9(...)⍣≡ apply "..." until convergence, at each step passing some very large number (9×109) as left argument

, add 9e9-s to the left of the current estimate

2⊣/ take the first from each pair of consecutive cells, effectively dropping the last column

2⊣⌿⍪ same thing vertically - put 9e9 on top and drop last row

(2⊣⌿⍪) ⌊ 2⊣/, minima

⍵+ add the original matrix

⊢⌊ try to improve the current estimates with that

⊃⌽, bottom-right cell

• Can you provide an explanation of your solution? Nov 27, 2018 at 8:02

# Charcoal, 46 bytes

≔Ｅ§θ⁰∧κΣ§θ⁰ηＦθ«≔§η⁰ζＦＬι«≔⁺⌊⟦§ηκζ⟧§ικζ§≔ηκζ»»Ｉζ


Try it online! Link is to verbose version of code. Explanation: This would probably be shorter if there was a three-argument reduce in Charcoal.

≔Ｅ§θ⁰∧κΣ§θ⁰η


Prefill the working array with large values except for the first which is zero.

Ｆθ«


Loop over the rows of the input.

≔§η⁰ζ


Initialise the current total with the first element of the working array.

ＦＬι«


Loop over the columns of the input.

≔⁺⌊⟦§ηκζ⟧§ικζ


Take the minimum of the current total and the current element of the working array and add the current element of the input to give the new current total.

§≔ηκζ


And store that back in the working array ready for the next row.

»»Ｉζ


Print the total once the input has been completely processed.

# Jelly, 17 bytes

XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ


Try it online!

# Brachylog, 26 25 bytes

∧≜.&{~g~g|hhX&{b|bᵐ}↰+↙X}


Try it online!

-1 byte because the cut isn't necessary--you can't take the head of an empty list

There's probably a lot of room to golf this but I need sleep.

The approach boils down to trying every value for the output, smallest first, (∧≜.) until a path can be found (b|bᵐ) to the bottom right corner (~g~g) which produces that sum (hhX&...↰+↙X).

# Java 8, 197193190 188 bytes

m->{int r=m.length-1,c=m.length-1,i=r;for(;i-->0;)m[i][c]+=m[i+1][c];for(i=c;i-->0;)m[r][i]+=m[r][i+1];for(i=r*c;i-->0;)m[i/c][r=i%c]+=Math.min(m[i/c+1][r],m[i/c][r+1]);return m;}


-9 bytes thanks to @ceilingcat.

Try it online.

General explanation:

I actually already did this challenge about a year ago with Project Euler #81, except that was limited to a square-matrix instead of an N by M matrix. So I slightly modified my code from back then to account for that.

I first sum the bottom row and rightmost column from the very last cell backwards. So let's use the example matrix of the challenge:

1, 2, 3, 4
5, 1, 6, 7
8, 2, 1, 1


The last cell remains the same. The second last cell of the bottom row becomes the sum: 1+1 = 2, and the same for the second last cell of the rightmost column: 1+7 = 8. We continue doing this, so now the matrix looks like this:

 1,  2,  3, 12
5,  1,  6,  8
12,  4,  2,  1


After doing that, we look at all the remaining rows one by one from bottom to top and right to left (except for the last column/row), and we look for each cell at both the cell below it and right of it to see which one is smaller.

So the cell containing the number 6 becomes 8, because the 2 below it is smaller than the 8 right of it. Then we look at the 1 next of it (to the left), and do the same. That 1 becomes 5, because the 4 below it is smaller than the 8 right of it.

So after we're done with the second to last row, the matrix looks like this:

 1,  2,  3, 12
10,  5,  8,  8
12,  4,  2,  1


And we continue doing this for the entire matrix:

 8,  7, 11, 12
10,  5,  8,  8
12,  4,  2,  1


Now the very first cell will contain our result, which is 8 in this case.

Code explanation:

m->{                    // Method with integer-matrix input and integer return-type
int r=m.length-1,     //  Amount of rows minus 1
c=m.length-1,  //  Amount of columns minus 1
i=r;              //  Index integer
for(;i-->0;)m[i][c]+=m[i+1][c];
//  Calculate the suffix-sums for the rightmost column
for(i=c;i-->0;)m[r][i]+=m[r][i+1];
//  Calculate the suffix-sums for the bottom row
for(i=r*c;i-->0;)     //  Loop over the cells in reversed order:
m[i/c][r=i%c]+=     //   Add to the value of the current cell:
Math.min(         //    The minimum of:
m[i/c+1][r],    //     The value in the cell below it
m[i/c][r+1]);   //     And the value in the cell left of it
return m;}      //  Return the value in the cell at index {0,0} as result


# Java (JDK), 223 bytes

Takes input as a 2D List of ints.

Additional 19 bytes for import java.util.*; included.

import java.util.*;m->{var l=m.get(0);int s=m.size(),c=l.size(),x=-1>>>1,a=l.get(0);return s*c<2?a:Math.min(s>1?n.n(new Vector(m.subList(1,s))):x,c>1?n.n(new Vector<>(m){{replaceAll(l->new Vector(l.subList(1,c)));}}):x)+a;}


Try it online!

How it works

import java.util.*;                                     // Import needed for Vector class
m->{                                                    // Lambda that takes a 2D list of integers
var r=m.get(0);                                     // Store first row in variable
int h=m.size(),                                     // Store number of rows
w=r.size(),                                     // Store number of columns
x=-1>>>1,                                       // Store int max
a=r.get(0);                                     // Store the current cell value
return h*w<2?a:                                     // If matrix is single cell return value
Math.min(                                       // Otherwise return the minimum of...

h>1?                                        // If height is more than 1
n.n(                                    // Recursively call this function with
new Vector(m.subList(1,h))):        // a new matrix, without the top row
x,                                      // Otherwise use int max as there is no row below this

w>1?                                        // If width is more than 1
n.n(new Vector<>(m){{                   // Recursively call this function with a new matrix
replaceAll(                         // where all columns have been replaced with
l->new Vector(l.subList(1,w))   // cloned lists without the leftmost column
);
}}):                                    // Otherwise use int max as there is
x                                       // no column to the right of this
)+a;                                            // Add the current cell value to the result before returning
}


# Python 2, 86 bytes

f=lambda A:len(A)>1<len(A)and A+min(f(zip(*A)[1:]),f(A[1:]))or sum(sum(A,()))


Try it online!

If B is the transpose of A, then the problem definition implies that f(A)==f(B).

A[1:] is the array A missing its top row. zip(*A[1:]) is the array A missing its leftmost column and transposed. sum(sum(A,())) is the sum of all elements in A.

If A has only a single column or single row, there is only one path, so f returns the sum of all elements in A; otherwise we recurse and return the sum of A + the smaller of f of A missing the top row and f of A missing the leftmost column.