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

15 Answers 15

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 _ _
  • 3
    This is a really nice solution! – Galen Ivanov Nov 26 at 6:55

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

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

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. – Giuseppe Nov 28 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

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

  • Hi! If you iterate from the ending point, you can get 91 bytes. – Cows quack Nov 26 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)

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

  • 2
    Can you provide an explanation of your solution? – Galen Ivanov Nov 27 at 8:02

Charcoal, 46 bytes

≔E§θ⁰∧κΣ§θ⁰ηFθ«≔§η⁰ζFLι«≔⁺⌊⟦§ηκζ⟧§ικζ§≔ηκζ»»Iζ

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.

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

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

Fθ«

Loop over the rows of the input.

≔§η⁰ζ

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

FLι«

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.

»»Iζ

Print the total once the input has been completely processed.

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

Jelly, 17 bytes

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

Try it online!

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

Java 8, 197 bytes

m->{int r=m.length-1,c=m[0].length-1,i=r,j=c,a,b;for(;i-->0;m[i][c]+=m[i+1][c]);for(;j-->0;m[r][j]+=m[r][j+1]);for(i=r;i-->0;)for(j=c;j-->0;b=m[i][j+1],m[i][j]+=a<b?a:b)a=m[i+1][j];return m[0][0];}

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,j=c,          //  Index integers
      a,b;              //  Temp integers
  for(;i-->0;m[i][c]+=m[i+1][c]);
                        //  Calculate the suffix-sums for the rightmost column
  for(;j-->0;m[r][j]+=m[r][j+1]);
                        //  Calculate the suffix-sums for the bottom row
  for(i=r;i-->0;)       //  Loop over the rows backwards
    for(j=c;j-->0       //   Inner loop over the columns backwards
        ;               //     After every iteration:
         b=m[i][j+1],   //      Set `b` to the value left of the current cell
         m[i][j]+=a<b?  //      If `a` is smaller than `b`:
                   a    //       Add `a` to the current cell
                  :     //      Else:
                   b)   //       Add `b` to the current cell
      a=m[i+1][j];      //    Set `a` to the value below the current cell
  return m[0][0];}      //  Return the value in the cell at index {0,0} as result

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.