Weight of the Least Weighted RoD Path

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
15
down vote

favorite












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









share|improve this question



























    up vote
    15
    down vote

    favorite












    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









    share|improve this question

























      up vote
      15
      down vote

      favorite









      up vote
      15
      down vote

      favorite











      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









      share|improve this 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






      code-golf path-finding






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Nov 27 at 0:29

























      asked Nov 26 at 3:33









      Chas Brown

      4,7491522




      4,7491522




















          15 Answers
          15






          active

          oldest

          votes

















          up vote
          14
          down vote














          J, 42 bytes



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


          Try it online!



          How it works



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


          Try it online!



          How it works



          v(+.<.:)&.>/@.[:</.(2#v=._1+1#.$)improve this answer
















          • 3




            This is a really nice solution!
            – Galen Ivanov
            Nov 26 at 6:55









          share.<.:)&.>/@.[:</.(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 _ _





          share.<.:)&.>/@.[:</.(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 _ _






          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered Nov 26 at 4:06









          Bubbler

          6,164759




          6,164759







          • 3




            This is a really nice solution!
            – Galen Ivanov
            Nov 26 at 6:55












          • 3




            This is a really nice solution!
            – Galen Ivanov
            Nov 26 at 6:55







          3




          3




          This is a really nice solution!
          – Galen Ivanov
          Nov 26 at 6:55




          This is a really nice solution!
          – Galen Ivanov
          Nov 26 at 6:55










          up vote
          7
          down vote













          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





          share|improve this answer


























            up vote
            7
            down vote













            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





            share|improve this answer
























              up vote
              7
              down vote










              up vote
              7
              down vote









              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





              share|improve this answer














              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






              share|improve this answer














              share|improve this answer



              share|improve this answer








              edited Nov 27 at 12:40

























              answered Nov 26 at 10:19









              Arnauld

              70.3k686296




              70.3k686296




















                  up vote
                  5
                  down vote













                  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





                  share|improve this answer


























                    up vote
                    5
                    down vote













                    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





                    share|improve this answer
























                      up vote
                      5
                      down vote










                      up vote
                      5
                      down vote









                      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





                      share|improve this answer














                      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






                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      edited Nov 26 at 18:55

























                      answered Nov 26 at 14:41









                      nimi

                      30.9k31985




                      30.9k31985




















                          up vote
                          4
                          down vote














                          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





                          share|improve this answer


























                            up vote
                            4
                            down vote














                            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





                            share|improve this answer
























                              up vote
                              4
                              down vote










                              up vote
                              4
                              down vote










                              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





                              share|improve this answer















                              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






                              share|improve this answer














                              share|improve this answer



                              share|improve this answer








                              edited Nov 27 at 10:05

























                              answered Nov 26 at 14:31









                              Luis Mendo

                              73.8k885290




                              73.8k885290




















                                  up vote
                                  3
                                  down vote














                                  R, 90 bytes





                                  function(m)l=sum(m


                                  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.






                                  share|improve this answer




















                                  • Possibly computing all paths and selecting the minimum is golfier.
                                    – Giuseppe
                                    Nov 28 at 3:53














                                  up vote
                                  3
                                  down vote














                                  R, 90 bytes





                                  function(m)l=sum(m


                                  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.






                                  share|improve this answer




















                                  • Possibly computing all paths and selecting the minimum is golfier.
                                    – Giuseppe
                                    Nov 28 at 3:53












                                  up vote
                                  3
                                  down vote










                                  up vote
                                  3
                                  down vote










                                  R, 90 bytes





                                  function(m)l=sum(m


                                  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.






                                  share|improve this answer













                                  R, 90 bytes





                                  function(m)l=sum(m


                                  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.







                                  share|improve this answer












                                  share|improve this answer



                                  share|improve this answer










                                  answered Nov 26 at 14:09









                                  Giuseppe

                                  16.1k31052




                                  16.1k31052











                                  • Possibly computing all paths and selecting the minimum is golfier.
                                    – Giuseppe
                                    Nov 28 at 3:53
















                                  • Possibly computing all paths and selecting the minimum is golfier.
                                    – Giuseppe
                                    Nov 28 at 3:53















                                  Possibly computing all paths and selecting the minimum is golfier.
                                  – Giuseppe
                                  Nov 28 at 3:53




                                  Possibly computing all paths and selecting the minimum is golfier.
                                  – Giuseppe
                                  Nov 28 at 3:53










                                  up vote
                                  3
                                  down vote














                                  Perl 6, 57 54 bytes





                                  my&f=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





                                  share|improve this answer






















                                  • 53 bytes through using $! instead of &f
                                    – Jo King
                                    Nov 26 at 23:24














                                  up vote
                                  3
                                  down vote














                                  Perl 6, 57 54 bytes





                                  my&f=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





                                  share|improve this answer






















                                  • 53 bytes through using $! instead of &f
                                    – Jo King
                                    Nov 26 at 23:24












                                  up vote
                                  3
                                  down vote










                                  up vote
                                  3
                                  down vote










                                  Perl 6, 57 54 bytes





                                  my&f=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





                                  share|improve this answer















                                  Perl 6, 57 54 bytes





                                  my&f=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






                                  share|improve this answer














                                  share|improve this answer



                                  share|improve this answer








                                  edited Nov 26 at 19:16

























                                  answered Nov 26 at 18:40









                                  nwellnhof

                                  6,3231125




                                  6,3231125











                                  • 53 bytes through using $! instead of &f
                                    – Jo King
                                    Nov 26 at 23:24
















                                  • 53 bytes through using $! instead of &f
                                    – Jo King
                                    Nov 26 at 23:24















                                  53 bytes through using $! instead of &f
                                  – Jo King
                                  Nov 26 at 23:24




                                  53 bytes through using $! instead of &f
                                  – Jo King
                                  Nov 26 at 23:24










                                  up vote
                                  3
                                  down vote














                                  Röda, 100 89 bytes



                                  f Ag=ming#A-1,#A[0]-1


                                  Try it online!



                                  -9 bytes thanks to Cows quack






                                  share|improve this answer






















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














                                  up vote
                                  3
                                  down vote














                                  Röda, 100 89 bytes



                                  f Ag=ming#A-1,#A[0]-1


                                  Try it online!



                                  -9 bytes thanks to Cows quack






                                  share|improve this answer






















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












                                  up vote
                                  3
                                  down vote










                                  up vote
                                  3
                                  down vote










                                  Röda, 100 89 bytes



                                  f Ag=ming#A-1,#A[0]-1


                                  Try it online!



                                  -9 bytes thanks to Cows quack






                                  share|improve this answer















                                  Röda, 100 89 bytes



                                  f Ag=ming#A-1,#A[0]-1


                                  Try it online!



                                  -9 bytes thanks to Cows quack







                                  share|improve this answer














                                  share|improve this answer



                                  share|improve this answer








                                  edited Nov 26 at 21:48

























                                  answered Nov 26 at 11:54









                                  fergusq

                                  4,65211036




                                  4,65211036











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
















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















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




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










                                  up vote
                                  2
                                  down vote














                                  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)





                                  share|improve this answer


























                                    up vote
                                    2
                                    down vote














                                    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)





                                    share|improve this answer
























                                      up vote
                                      2
                                      down vote










                                      up vote
                                      2
                                      down vote










                                      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)





                                      share|improve this answer















                                      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)






                                      share|improve this answer














                                      share|improve this answer



                                      share|improve this answer








                                      edited Nov 26 at 17:54

























                                      answered Nov 26 at 17:47









                                      David Foerster

                                      26015




                                      26015




















                                          up vote
                                          2
                                          down vote














                                          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






                                          share|improve this answer


















                                          • 2




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














                                          up vote
                                          2
                                          down vote














                                          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






                                          share|improve this answer


















                                          • 2




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












                                          up vote
                                          2
                                          down vote










                                          up vote
                                          2
                                          down vote










                                          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






                                          share|improve this answer















                                          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







                                          share|improve this answer














                                          share|improve this answer



                                          share|improve this answer








                                          edited Nov 27 at 9:10

























                                          answered Nov 27 at 7:22









                                          ngn

                                          6,53312459




                                          6,53312459







                                          • 2




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












                                          • 2




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







                                          2




                                          2




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




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










                                          up vote
                                          1
                                          down vote














                                          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.






                                          share|improve this answer
























                                            up vote
                                            1
                                            down vote














                                            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.






                                            share|improve this answer






















                                              up vote
                                              1
                                              down vote










                                              up vote
                                              1
                                              down vote










                                              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.






                                              share|improve this answer













                                              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.







                                              share|improve this answer












                                              share|improve this answer



                                              share|improve this answer










                                              answered Nov 26 at 22:58









                                              Neil

                                              78.5k744175




                                              78.5k744175




















                                                  up vote
                                                  1
                                                  down vote














                                                  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





                                                  share|improve this answer


























                                                    up vote
                                                    1
                                                    down vote














                                                    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





                                                    share|improve this answer
























                                                      up vote
                                                      1
                                                      down vote










                                                      up vote
                                                      1
                                                      down vote










                                                      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





                                                      share|improve this answer















                                                      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






                                                      share|improve this answer














                                                      share|improve this answer



                                                      share|improve this answer








                                                      edited Nov 26 at 23:31

























                                                      answered Nov 26 at 23:18









                                                      Jonathan Allan

                                                      50.3k534165




                                                      50.3k534165




















                                                          up vote
                                                          0
                                                          down vote














                                                          Jelly, 17 bytes



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


                                                          Try it online!






                                                          share|improve this answer
























                                                            up vote
                                                            0
                                                            down vote














                                                            Jelly, 17 bytes



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


                                                            Try it online!






                                                            share|improve this answer






















                                                              up vote
                                                              0
                                                              down vote










                                                              up vote
                                                              0
                                                              down vote










                                                              Jelly, 17 bytes



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


                                                              Try it online!






                                                              share|improve this answer













                                                              Jelly, 17 bytes



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


                                                              Try it online!







                                                              share|improve this answer












                                                              share|improve this answer



                                                              share|improve this answer










                                                              answered Nov 27 at 16:34









                                                              Erik the Outgolfer

                                                              30.9k429102




                                                              30.9k429102




















                                                                  up vote
                                                                  0
                                                                  down vote














                                                                  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






                                                                  share|improve this answer
























                                                                    up vote
                                                                    0
                                                                    down vote














                                                                    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






                                                                    share|improve this answer






















                                                                      up vote
                                                                      0
                                                                      down vote










                                                                      up vote
                                                                      0
                                                                      down vote










                                                                      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






                                                                      share|improve this answer













                                                                      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







                                                                      share|improve this answer












                                                                      share|improve this answer



                                                                      share|improve this answer










                                                                      answered Nov 27 at 17:24









                                                                      Luke Stevens

                                                                      714214




                                                                      714214




















                                                                          up vote
                                                                          0
                                                                          down vote














                                                                          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.






                                                                          share|improve this answer


























                                                                            up vote
                                                                            0
                                                                            down vote














                                                                            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.






                                                                            share|improve this answer
























                                                                              up vote
                                                                              0
                                                                              down vote










                                                                              up vote
                                                                              0
                                                                              down vote










                                                                              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.






                                                                              share|improve this answer















                                                                              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.







                                                                              share|improve this answer














                                                                              share|improve this answer



                                                                              share|improve this answer








                                                                              edited Nov 28 at 1:16

























                                                                              answered Nov 27 at 20:16









                                                                              Chas Brown

                                                                              4,7491522




                                                                              4,7491522




















                                                                                  up vote
                                                                                  0
                                                                                  down vote













                                                                                  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





                                                                                  share|improve this answer
























                                                                                    up vote
                                                                                    0
                                                                                    down vote













                                                                                    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





                                                                                    share|improve this answer






















                                                                                      up vote
                                                                                      0
                                                                                      down vote










                                                                                      up vote
                                                                                      0
                                                                                      down vote









                                                                                      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





                                                                                      share|improve this answer












                                                                                      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






                                                                                      share|improve this answer












                                                                                      share|improve this answer



                                                                                      share|improve this answer










                                                                                      answered Nov 28 at 10:10









                                                                                      Kevin Cruijssen

                                                                                      34.6k554182




                                                                                      34.6k554182



























                                                                                          draft saved

                                                                                          draft discarded
















































                                                                                          If this is an answer to a challenge…



                                                                                          • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.


                                                                                          • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
                                                                                            Explanations of your answer make it more interesting to read and are very much encouraged.


                                                                                          • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.


                                                                                          More generally…



                                                                                          • …Please make sure to answer the question and provide sufficient detail.


                                                                                          • …Avoid asking for help, clarification or responding to other answers (use comments instead).





                                                                                          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                                                                                          Please pay close attention to the following guidance:


                                                                                          • Please be sure to answer the question. Provide details and share your research!

                                                                                          But avoid


                                                                                          • Asking for help, clarification, or responding to other answers.

                                                                                          • Making statements based on opinion; back them up with references or personal experience.

                                                                                          To learn more, see our tips on writing great answers.




                                                                                          draft saved


                                                                                          draft discarded














                                                                                          StackExchange.ready(
                                                                                          function ()
                                                                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176563%2fweight-of-the-least-weighted-rod-path%23new-answer', 'question_page');

                                                                                          );

                                                                                          Post as a guest















                                                                                          Required, but never shown





















































                                                                                          Required, but never shown














                                                                                          Required, but never shown












                                                                                          Required, but never shown







                                                                                          Required, but never shown

































                                                                                          Required, but never shown














                                                                                          Required, but never shown












                                                                                          Required, but never shown







                                                                                          Required, but never shown






                                                                                          Popular posts from this blog

                                                                                          How to check contact read email or not when send email to Individual?

                                                                                          Bahrain

                                                                                          Postfix configuration issue with fips on centos 7; mailgun relay