Find the greatest line

Question 1

You will be given a 2-D array A of integers, and a length N. Your task is to find within the array the straight line (horizontal, vertical or diagonal) of N elements that yields the highest total sum, and return that sum.

Example

This array has 34 valid lines, including

 Vertical
 [3] 3 7 9 3
 [2] 2 10 4 1
 [7] 7 2 5 0
 2 1 4 1 3 [3,2,7] = 12
 Horizontal
 3 3 7 9 3
 2 2 10 4 1
 7 7 [2] [5] [0]
 2 1 4 1 3 [2,5,0] = 7
 Diagonal
 3 3 [7] 9 3
 2 2 10 [4] 1
 7 7 2 5 [0]
 2 1 4 1 3 [7,4,0] = 11

The maximum line is

 3 3 7 [9] 3
 2 2 [10] 4 1
 7 [7] 2 5 0
 2 1 4 1 3 [7,10,9] = 26

Note: lines may not wrap around the edges of the array.

Inputs

A X by Y 2-D array A, with X,Y> 0. Each element of the array contains an integer value which may be positive, zero or negative. You may accept this array in an alternative format (e.g. list of 1-D arrays) if you wish.
A single, positive integer N, no greater than max(X,Y).

Output

A single value representing the maximal line sum that can be found in the array. Note that you do not need to provide the individual elements of that line or where it is located.

Test cases

N = 4, A = 
-88 4 -26 14 -90
-48 17 -45 -70 85
 22 -52 87 -23 22
-20 -68 -51 -61 41
Output = 58
N = 4, A =
 9 4 14 7
 6 15 1 12
 3 10 8 13
16 5 11 2
Output = 34
N = 1, A = 
 -2
Output = -2
N = 3, A =
1 2 3 4 5
Output = 12
N = 3, A = 
-10 -5 4
 -3 0 -7
-11 -3 -2
Output = -5

Question 2

Could you add a test case where the resulting output is negative? Like [[-10, -5, 4],[-3, 0, -7],[-11,-3,-2]] -> -5 (4 + -7 + -2)

Question 3

@KevinCruijssen Sure, added

Question 4

By the way: all answers with an explanation will gain an upvote from me, but otherwise I have no way of judging languages that I'm not familiar with (and that's most of them).

Question 5

Jelly, 15 bytes

,ZṚ\;ŒD$+9\€€FṀ

Try it online!

How it works

,ZṚ\;ŒD$+9\€€FṀ Main link. Left argument: M (matrix). Right argument: n (integer)
 ZṚ\ Zip/transpose and reverse M. This is equivalent to rotating M 90°
 counterclockwise.
, Pair M and the result to the right.
 ;ŒD$ Append the diagonals of both matrices to the pair.
 +9\€€ Take the sums of length n of each flat array.
 FṀ Flatten and take the maximum.

Question 6

Nice abuse of ¥ there...

Question 7

For future (new) users: $ creates a monad from ZṚ, while ¥ creates a dyad from ZṚ which returns the result of the same function (rotate 90 CCW) applied on its left operand. Which matches the pattern + × and evaluate v+(λ×ρ) (it is v = v , (M ZṚ¥ n) in this case). However just use $ doesn't work because there is no + F pattern in dyadic chain.

Question 8

Wolfram Language (Mathematica), 73 bytes

Max[Tr/@Join[#,#,{#,Reverse@#}]&/@Join@@Partition[#2,{#,#},1,1,-∞]]&

Try it online!

How it works

Takes first N and then the matrix A as input.

Join@@Partition[#2,{#,#},1,1,-∞] finds every N by N submatrix of the matrix A, padded with -∞ where necessary to ensure that lines running out of the grid will be out of the running.

For each of those blocks we compute Tr/@Join[#,#,{#,Reverse@#}]: the trace (i.e. sum) of each row, the trace (i.e. sum) of each column, the trace (actually the trace, for the first time in the history of Mathematica code golfing) of the block, and the trace of the block reversed. # is Transpose@#.

Then we find the Max of all of these.

Question 9

For most inputs, the 57-byte Max@BlockMap[Tr/@Join[#,#,{#,Reverse@#}]&,#2,{#,#},1]& also works. But we need to pad with -∞ to handle cases where A has fewer than N rows or columns, and BlockMap doesn't support padding.

Question 10

For TIO-friendly version (Mathematica script mode): The character U+F3C7 (\[Transpose]) can be typed in as \:f3c7.

Question 11

Also I believe it is not the first time Tr is used as trace.

Question 12

Thanks! And when I'm not exaggerating, I'm sure using Tr as the trace of a matrix has come up before, but it's still rare and surprising.

Question 13

I know I've said that before, but non-ASCII code should work just fine now. Try it online!

Question 14

Mathematica, (削除) 135 (削除ここまで) 123 bytes

Max[(s=#;r=#2;Max[Tr/@Partition[#,r,1]&/@Join[s,s~Diagonal~#&/@Range[-(t=Tr[1^#&@@s])+2,t-1]]])&@@@{#|#2,Reverse@#|#2}]&

Try it online!

Question 15

Some optimizations: Diagonal[s,#] to s~Diagonal~#, and {{Transpose@#,#2},{Reverse@#,#2}} to {#|#2,Reverse@#|#2}. (The unprintable is U+F3C7 = \[Transpose]; TIO doesn't seem to like this, though. Alternative: {Transpose@#|#2,Reverse@#|#2})

Question 16

@JungHwanMin It's not TIO's fault, Mathematica on TIO is run in script mode, which only support ASCII. You need to type \[Transpose] or \:f3c7 (at least the latter is shorter than Thread@) However if the answer is Mathematica REPL (not Mathematica script) you can assume the 3-byte solution.

Question 17

@user202729 Thanks, didn't know!

Question 18

Jelly, 16 bytes

μ;Z;Uμ;ŒDðṡ€ẎS€Ṁ

Try it online!

Question 19

Wow our solutions are nearly identical... Mine was µ;Z;UŒD$;ŒDṡ4ドルẎS€Ṁ

Question 20

@Mr.Xcoder Oh wow cool :P

Question 21

JavaScript, (削除) 151 (削除ここまで) 129 bytes

a=>n=>a.map((l,x)=>l.map((v,y)=>[...'01235678'].map(d=>m=(g=i=>i--&&g(i)+(a[x+d%3*i-i]||[])[y+i*~-(d/3)])(n)>m?g(n):m)),m=-1/0)|m

Curry function takes two arguments, first one is an array of array of numbers, second one is a number.

Thanks to Arnauld, save 20+ bytes.

f=
a=>n=>a.map((l,x)=>l.map((v,y)=>[...'01235678'].map(d=>m=(g=i=>i--&&g(i)+(a[x+d%3*i-i]||[])[y+i*~-(d/3)])(n)>m?g(n):m)),m=-1/0)|m

<p><label>N = <input id="N" type="number" min="1" value="3" /></label></p>
<p><label>A = <textarea id="A" style="width: 400px; height: 200px;"> 3 3 7 9 3
 2 2 10 4 1
 7 7 2 5 0
 2 1 4 1 3
</textarea></label></p>
<input value="Run" type="button" onclick="O.value=f(A.value.split('\n').filter(x=>x.trim()).map(x=>x.trim().split(/\s+/).map(Number)))(+N.value)" />
<p>Result = <output id="O"></output></p>

Question 22

1/s instead of s==s should work as expected.

Question 23

Getting rid of both eval's: 130 bytes

Question 24

@Arnauld Thanks. And change (s=(g=...)(n))>m?s:m to (g=...)(n)>m?g(n):m save 1 byte.

Question 25

Jq 1.5, 211 bytes

def R:reverse;def U:[range(length)as$j|.[$j][$j:]]|transpose|map(map(select(.))|select(length>=N));def D:U+([R[]|R]|U|map(R)[1:]);[A|.,transpose,D,(map(R)|D)|.[]|range(length-N+1)as$i|.[$i:$i+N]]|max_by(add)|add

Expects input in N and A, e.g:

def N: 3;
def A: [
 [ 3, 3, 7, 9, 3 ],
 [ 2, 2, 10, 4, 1 ],
 [ 7, 7, 2, 5, 0 ],
 [ 2, 1, 4, 1, 3 ]
];

Expanded

def chunks: .[] | range(length-N+1) as $i | .[$i:$i+N] ;
def flip: [ reverse[] | reverse ] ;
def upperdiag: [ range(length) as $j | .[$j][$j:] ] | transpose | map(map(select(.))|select(length>=N)) ;
def lowerdiag: flip | upperdiag | map(reverse)[1:] ;
def diag: upperdiag + lowerdiag ;
def allchunks: A | ., transpose, diag, (map(reverse)|diag) | chunks ;
[allchunks]|max_by(add)|add

Note this challenge is basically the same as Project Euler problem 11

Try it online!

Question 26

Python 2, (削除) 208 (削除ここまで) (削除) 184 (削除ここまで) (削除) 183 (削除ここまで) 176 bytes

Saved 24 bytes by using -float("inf") to represent that the checked line reached outside the matrix instead of computing the negative sum of all matrix elements.
Saved a byte by defining R,L=range,len to shorten built-in functions and using y in R(L(A))...R(L(A[y])) instead of y,Y in e(A)...x,_ in e(Y).
Saved seven bytes by golfing float("inf") to 9e999.

lambda N,A:max(sum(A[y+q*j][x+p*j]if-1<x+p*j<L(A[y])>-1<y+q*j<L(A)else-9e999for j in R(N))for y in R(L(A))for x in R(L(A[y]))for p,q in[(1,0),(0,1),(1,1),(1,-1)]);R,L=range,len

Try it online!

Explanation

lambda N,A: ;R,L=range,len # lambda function, golfed built-ins
 max( ) # return the maximum line sum
 for y in R(L(A)) # loop through matrix rows
 for x in R(L(A[y])) # loop through matrix columns
 for p,q in[(1,0),(0,1),(1,1),(1,-1)] # loop through four directions; east, south, south-east, north-east
 sum( ) # matrix line sum
 for j in R(N) # loop through line indices
 if-1<x+p*j<L(A[y])>-1<y+q*j<L(A) # coordinates inside the matrix?
 A[y+q*j][x+p*j] # true; look at the matrix element
 else-9e999 # false; this line cannot be counted, max(...) will not return this line

Question 27

R, 199 bytes

function(m,n,i=1,j=1){y=1:n-1
x=j-y;x[x<1]=NA
y=i-y;y[y<1]=NA
'if'(i>nrow(m)|j>ncol(m),NA,max(c(v(m[i,x]),v(m[y,j]),v(m[b(y,x)]),v(m[b(y,rev(x))]),f(m,n,i+1,j),f(m,n,i,j+1)), na.rm=T))}
v=sum
b=cbind

Try it online!

A recursive solution. For each element (i,j) of the matrix it returns the max between the sum along the row, the sum along the column, the sum along either diagonal, and the result of the function applied to (i+1,j) and (i,j+1). Results for the test cases are shown in the TIO.

Question 28

I hope I missed it, but R seems to be lacking a base function to compute the trace of a square matrix.

Question 29

Haven't worked out if it would save you bytes, but you can use sum(diag(m)) for the trace

Question 30

Husk, 14 bytes

▲さんかくmΣṁX0ṁëIT∂(∂↔

Try it online!

Thanks to the new anti∂iagonals builtin this is a quite short answer :)

Question 31

JavaScript 170 bytes

still wip on the golf part added 4 more chars because i didnt managed a case where the max is negative and N is bigger than 1

M=-1e9
G=(A,N)=>eval(`for(y in m=M,A)
for(x in R=A[y])
{for(a=b=c=d=j=0;j<N;d+=Y[x-j++])
{a+=R[X=+x+j]
b+=(Y=A[+y+j]||[])[x]
c+=Y[X]}
m=Math.max(m,a||M,b||M,c||M,d||M)}`)
console.log(G([ [3,3,7,9,3],
 [2,2,10,4,1],
 [7,7,2,5,0],
 [2,1,4,1,3]],3)==26)
 
 console.log(G([[-88,4,-26,14,-90],
[-48,17,-45,-70,85],
[22,-52,87,-23,22],
[-20,-68,-51,-61,41]],4)==58)
console.log(G([[9,4,14,7],[6,15,1,12],[3,10,8,13],[16,5,11,2]],4)==34)
console.log(G([[-2]],1)==-2)
console.log(G([[1,2,3,4,5]],3) ==12)

Question 32

@HermanLauenstein i remove the spaces but added more coverage which added in total more chars, but thx :)

Question 33

164 bytes by removing unnecessary newlines (G= is not counted)

Question 34

Why did you use a||M,b||M,c||M,d||M instead of a,b,c,d?

Question 35

@HermanLauenstein Math.max(NaN/undefined, 6) = NaN

Question 36

Python 2, (削除) 222 (削除ここまで) 218 bytes

n,a=input()
W=len(a[0]);Q=['']*W;R=range;a+=[Q]*n
for l in a:l+=Q
print max(sum(x)for y in[zip(*[(a[j][i+k],a[j+k][i],a[j+k][i+k],a[j+k][i+n+~k])for k in R(n)])for j in R(len(a)-n)for i in R(W)]for x in y if''not in x)

Try it online!

Question 37

Possible 219 bytes.

Question 38

Possible 218 bytes.

Dennis 212k41 gold badges380 silver badges830 bronze badges · Accepted Answer · 2017-10-16 17:37:20Z

10

\$\begingroup\$

Jelly, 15 bytes

,ZṚ\;ŒD$+9\€€FṀ

Try it online!

How it works

,ZṚ\;ŒD$+9\€€FṀ Main link. Left argument: M (matrix). Right argument: n (integer)
 ZṚ\ Zip/transpose and reverse M. This is equivalent to rotating M 90°
 counterclockwise.
, Pair M and the result to the right.
 ;ŒD$ Append the diagonals of both matrices to the pair.
 +9\€€ Take the sums of length n of each flat array.
 FṀ Flatten and take the maximum.

Share

Improve this answer

edited Oct 16, 2017 at 17:58

answered Oct 16, 2017 at 17:37

Dennis's user avatar

Dennis

212k41 gold badges380 silver badges830 bronze badges

\$\endgroup\$

2

\$\begingroup\$ Nice abuse of ¥ there... \$\endgroup\$

Erik the Outgolfer
– Erik the Outgolfer

2017年10月16日 18:17:10 +00:00
Commented Oct 16, 2017 at 18:17
\$\begingroup\$ For future (new) users: $ creates a monad from ZṚ, while ¥ creates a dyad from ZṚ which returns the result of the same function (rotate 90 CCW) applied on its left operand. Which matches the pattern + × and evaluate v+(λ×ρ) (it is v = v , (M ZṚ¥ n) in this case). However just use $ doesn't work because there is no + F pattern in dyadic chain. \$\endgroup\$

user202729
– user202729

2017年10月17日 00:56:09 +00:00
Commented Oct 17, 2017 at 0:56

Add a comment |

Stack Exchange Network

Find the greatest line

Example

Inputs

Output

Test cases

11 Answers 11

Jelly, 15 bytes

How it works

Wolfram Language (Mathematica), 73 bytes

How it works

Mathematica, (削除) 135 (削除ここまで) 123 bytes

Jelly, 16 bytes

JavaScript, (削除) 151 (削除ここまで) 129 bytes

Jq 1.5, 211 bytes

Python 2, (削除) 208 (削除ここまで) (削除) 184 (削除ここまで) (削除) 183 (削除ここまで) 176 bytes

Explanation

R, 199 bytes

Husk, 14 bytes

JavaScript 170 bytes

Python 2, (削除) 222 (削除ここまで) 218 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Hot Network Questions

Find the greatest line

Example

Inputs

Output

Test cases

11 Answers 11

Jelly, 15 bytes

How it works

Wolfram Language (Mathematica), 73 bytes

How it works

Mathematica, (削除) 135 (削除ここまで) 123 bytes

Jelly, 16 bytes

JavaScript, (削除) 151 (削除ここまで) 129 bytes

Jq 1.5, 211 bytes

Python 2, (削除) 208 (削除ここまで) (削除) 184 (削除ここまで) (削除) 183 (削除ここまで) 176 bytes

Explanation

R, 199 bytes

Husk, 14 bytes

JavaScript 170 bytes

Python 2, (削除) 222 (削除ここまで) 218 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Related

Hot Network Questions