Weight of the Least Weighted RoD Path

Question

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

[ [5, 2] ] -> 7

[ [5], 
  [2] ] -> 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

Answer 1

J, 42 bytes

v(+}.<.}:)&.>/@{.[:</.(2#v=._1+1#.$){.!._]

Try it online!

How it works

v(+}.<.}:)&.>/@{.[:</.(2#v=._1+1#.$){.!._]
                         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 _ _

Answer 2

JavaScript (ES6), 78 77 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

Answer 3

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

Answer 4

MATL, 38 36 30 29 bytes

Thanks to @Giuseppe for pointing out a mistake, now corrected.

lyZyqsG&nghZ^Yc!tsGz=Z)Ys)sX<

Try it online! Or verify all test cases.

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

Answer 5

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.

Answer 6

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

Answer 7

Röda, 100 89 bytes

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

Try it online!

-9 bytes thanks to Cows quack

Answer 8

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)

Answer 9

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:
    Ç          -   last link as a monad
       ÐṀ      - filter keep only those maximal by:
      L        -   length
           ⁸   - chain's left argument, A
         œị    - multi-dimensional index into (vectorises)
            §  - sum each
             Ṃ - minimum

Answer 10

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×10⁹) 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

Answer 11

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.

Answer 12

Jelly, 17 bytes

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

Try it online!

Answer 13

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).

Answer 14

Java 8, 197 193 190 188 bytes

m->{int r=m.length-1,c=m[0].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[0][0];}

-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[0].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[0][0];}      //  Return the value in the cell at index {0,0} as result

Answer 15

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
}

Answer 16

Python 2, 86 bytes

f=lambda A:len(A)>1<len(A[0])and A[0][0]+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[0][0] + the smaller of f of A missing the top row and f of A missing the leftmost column.