Weight of the Least Weighted RoD Path
Clash 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
code-golf path-finding
add a comment |
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
code-golf path-finding
add a comment |
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
code-golf path-finding
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
code-golf path-finding
edited Nov 27 at 0:29
asked Nov 26 at 3:33
Chas Brown
4,7491522
4,7491522
add a comment |
add a comment |
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
add a comment .<.:)&.>/@.[:</.(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 _ _
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
add a comment |
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
add a comment |
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
add a comment |
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
add a comment |
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
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
edited Nov 27 at 12:40
answered Nov 26 at 10:19
Arnauld
70.3k686296
70.3k686296
add a comment |
add a comment |
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
add a comment |
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
add a comment |
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
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
edited Nov 26 at 18:55
answered Nov 26 at 14:41
nimi
30.9k31985
30.9k31985
add a comment |
add a comment |
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
add a comment |
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
add a comment |
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
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
edited Nov 27 at 10:05
answered Nov 26 at 14:31
Luis Mendo
73.8k885290
73.8k885290
add a comment |
add a comment |
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.
Possibly computing all paths and selecting the minimum is golfier.
– Giuseppe
Nov 28 at 3:53
add a comment |
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.
Possibly computing all paths and selecting the minimum is golfier.
– Giuseppe
Nov 28 at 3:53
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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
53 bytes through using$!
instead of&f
– Jo King
Nov 26 at 23:24
add a comment |
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
53 bytes through using$!
instead of&f
– Jo King
Nov 26 at 23:24
add a comment |
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
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
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
add a comment |
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
add a comment |
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
Hi! If you iterate from the ending point, you can get 91 bytes.
– Cows quack
Nov 26 at 16:09
add a comment |
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
Hi! If you iterate from the ending point, you can get 91 bytes.
– Cows quack
Nov 26 at 16:09
add a comment |
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
Röda, 100 89 bytes
f Ag=ming#A-1,#A[0]-1
Try it online!
-9 bytes thanks to Cows quack
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
add a comment |
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
add a comment |
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)
add a comment |
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)
add a comment |
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)
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)
edited Nov 26 at 17:54
answered Nov 26 at 17:47
David Foerster
26015
26015
add a comment |
add a comment |
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
2
Can you provide an explanation of your solution?
– Galen Ivanov
Nov 27 at 8:02
add a comment |
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
2
Can you provide an explanation of your solution?
– Galen Ivanov
Nov 27 at 8:02
add a comment |
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
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
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
add a comment |
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
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
answered Nov 26 at 22:58
Neil
78.5k744175
78.5k744175
add a comment |
add a comment |
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
add a comment |
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
add a comment |
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
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
edited Nov 26 at 23:31
answered Nov 26 at 23:18
Jonathan Allan
50.3k534165
50.3k534165
add a comment |
add a comment |
up vote
0
down vote
Jelly, 17 bytes
XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ
Try it online!
add a comment |
up vote
0
down vote
Jelly, 17 bytes
XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ
Try it online!
add a comment |
up vote
0
down vote
up vote
0
down vote
Jelly, 17 bytes
XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ
Try it online!
Jelly, 17 bytes
XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ
Try it online!
answered Nov 27 at 16:34
Erik the Outgolfer
30.9k429102
30.9k429102
add a comment |
add a comment |
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
add a comment |
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
add a comment |
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
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
answered Nov 27 at 17:24
Luke Stevens
714214
714214
add a comment |
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
edited Nov 28 at 1:16
answered Nov 27 at 20:16
Chas Brown
4,7491522
4,7491522
add a comment |
add a comment |
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
add a comment |
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
add a comment |
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
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
answered Nov 28 at 10:10
Kevin Cruijssen
34.6k554182
34.6k554182
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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