14
\$\begingroup\$

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

 N = 3, A = 
 3    3    7    9    3
 2    2   10    4    1
 7    7    2    5    0
 2    1    4    1    3

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 
\$\endgroup\$
3
  • \$\begingroup\$ 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) \$\endgroup\$ Oct 17, 2017 at 8:01
  • \$\begingroup\$ @KevinCruijssen Sure, added \$\endgroup\$ Oct 17, 2017 at 8:16
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Oct 17, 2017 at 10:24

11 Answers 11

10
\$\begingroup\$

Jelly, 15 bytes

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

Try it online!

How it works

,ZṚ¥;ŒD$+⁹\€€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.
        +⁹\€€    Take the sums of length n of each flat array.
             FṀ  Flatten and take the maximum.
\$\endgroup\$
2
  • \$\begingroup\$ Nice abuse of ¥ there... \$\endgroup\$ 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\$
    – DELETE_ME
    Oct 17, 2017 at 0:56
6
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 17, 2017 at 0:36
  • 1
    \$\begingroup\$ For TIO-friendly version (Mathematica script mode): The character U+F3C7 (\[Transpose]) can be typed in as \:f3c7. \$\endgroup\$
    – DELETE_ME
    Oct 17, 2017 at 1:07
  • 3
    \$\begingroup\$ Also I believe it is not the first time Tr is used as trace. \$\endgroup\$
    – DELETE_ME
    Oct 17, 2017 at 1:10
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 17, 2017 at 1:12
  • 3
    \$\begingroup\$ I know I've said that before, but non-ASCII code should work just fine now. Try it online! \$\endgroup\$
    – Dennis
    Oct 17, 2017 at 1:31
4
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ 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}) \$\endgroup\$ Oct 16, 2017 at 20:56
  • \$\begingroup\$ @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. \$\endgroup\$
    – DELETE_ME
    Oct 17, 2017 at 1:06
  • \$\begingroup\$ @user202729 Thanks, didn't know! \$\endgroup\$ Oct 17, 2017 at 1:19
3
\$\begingroup\$

Jelly, 16 bytes

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

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Wow our solutions are nearly identical... Mine was µ;Z;UŒD$;ŒDṡ€⁴ẎS€Ṁ \$\endgroup\$
    – Mr. Xcoder
    Oct 16, 2017 at 17:01
  • \$\begingroup\$ @Mr.Xcoder Oh wow cool :P \$\endgroup\$
    – hyper-neutrino
    Oct 16, 2017 at 17:35
3
\$\begingroup\$

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>

\$\endgroup\$
3
  • \$\begingroup\$ 1/s instead of s==s should work as expected. \$\endgroup\$
    – Arnauld
    Oct 17, 2017 at 14:56
  • \$\begingroup\$ Getting rid of both eval's: 130 bytes \$\endgroup\$
    – Arnauld
    Oct 17, 2017 at 15:31
  • \$\begingroup\$ @Arnauld Thanks. And change (s=(g=...)(n))>m?s:m to (g=...)(n)>m?g(n):m save 1 byte. \$\endgroup\$
    – tsh
    Oct 18, 2017 at 1:06
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I hope I missed it, but R seems to be lacking a base function to compute the trace of a square matrix. \$\endgroup\$
    – NofP
    Oct 28, 2017 at 23:57
  • \$\begingroup\$ Haven't worked out if it would save you bytes, but you can use sum(diag(m)) for the trace \$\endgroup\$ Oct 29, 2017 at 8:59
1
\$\begingroup\$

Husk, 14 bytes

▲mΣṁX⁰ṁëIT∂(∂↔

Try it online!

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

\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$
4
  • \$\begingroup\$ @HermanLauenstein i remove the spaces but added more coverage which added in total more chars, but thx :) \$\endgroup\$ Oct 16, 2017 at 18:00
  • \$\begingroup\$ 164 bytes by removing unnecessary newlines (G= is not counted) \$\endgroup\$
    – Herman L
    Oct 16, 2017 at 18:03
  • \$\begingroup\$ Why did you use a||M,b||M,c||M,d||M instead of a,b,c,d? \$\endgroup\$
    – Herman L
    Oct 16, 2017 at 18:11
  • \$\begingroup\$ @HermanLauenstein Math.max(NaN/undefined, 6) = NaN \$\endgroup\$ Oct 16, 2017 at 19:15
0
\$\begingroup\$

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!

\$\endgroup\$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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