가장 큰 줄 찾기

정수로 구성된 2 차원 배열 A와 길이 N이 주어집니다. 당신의 임무는 배열 내에서 가장 높은 총합을 산출하는 N 요소의 직선 (수평, 수직 또는 대각선)을 찾아 그 합을 반환하는 것입니다 .

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

이 배열에는 다음을 포함하여 34 개의 유효한 행이 있습니다.

 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

최대 라인은

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

참고 : 선이 배열의 가장자리를 감싸지 않을 수 있습니다.

입력

  • X, Y> 0 인 Y에 의한 AX 2 차원 배열 A. 배열의 각 요소는 양수, 0 또는 음수 일 수있는 정수 값을 포함합니다. 원하는 경우이 배열을 다른 형식 (예 : 1D 배열 목록)으로 사용할 수 있습니다.
  • max (X, Y)보다 크지 않은 단일 양의 정수 N

산출

  • 배열에서 찾을 수있는 최대 선 합을 나타내는 단일 값입니다. 해당 라인의 개별 요소 나 위치를 제공 할 필요 는 없습니다 .

테스트 사례

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


답변

젤리 , 15 바이트

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

온라인으로 사용해보십시오!

작동 원리

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

답변

Wolfram Language (Mathematica) , 73 바이트

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

온라인으로 사용해보십시오!

작동 원리

먼저 N행렬 A을 입력으로받습니다.

Join@@Partition[#2,{#,#},1,1,-∞]모든 발견 N에 의해 N행렬의 행렬 A, 패딩 -∞실행 밖으로 될 것이다 선이 그리드 밖으로 실행 보장하기 필요한 경우.

각 블록 Tr/@Join[#,#,{#,Reverse@#}]에 대해 각 행의 트레이스 (즉, 합계), 각 열의 트레이스 (즉, 합계), 블록 의 트레이스 ( 실제로 트레이스, Mathematica 코드 골프 기록에서 처음으로 트레이스)를 계산합니다. 블록의 흔적이 반전되었습니다. #입니다 Transpose@#.

그런 다음 Max이 모든 것을 찾습니다 .


답변

매스 매 티카, 135 123 바이트

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

온라인으로 사용해보십시오!


답변

젤리 , 16 바이트

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

온라인으로 사용해보십시오!


답변

자바 스크립트, 151 129 바이트

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

카레 함수는 두 개의 인수를 취합니다. 첫 번째는 숫자의 배열이고 두 번째는 숫자입니다.

Arnauld 덕분에 20 바이트 이상을 절약하십시오.

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>

답변

Jq 1.5 , 211 바이트

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

N및에 입력을 예상합니다 A. 예 :

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 ]
];

넓히는

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

이 과제는 기본적으로 Project Euler 문제 11 과 동일합니다.

온라인으로 사용해보십시오!


답변

파이썬 (2) , 208 (184) 183 176 바이트

  • -float("inf")모든 행렬 요소의 음수 합계를 계산하는 대신 확인 된 행이 행렬 외부에 도달했음을 나타 내기 위해 24 바이트를 절약 했습니다.
  • R,L=range,len내장 함수를 단축하고 y in R(L(A))...R(L(A[y]))대신을 사용하여 바이트를 저장했습니다 y,Y in e(A)...x,_ in e(Y).
  • 에 골프 float("inf")를 치고 7 바이트를 절약 했습니다 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

온라인으로 사용해보십시오!

설명

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