7
\$\begingroup\$

Given an n-dimensional array filled with numbers, output which p-dimensional array has the largest sum.

Input

  • An n-dimensional array of numbers, or your language's equivalent. You can assume this is a rectangular array, or not.
  • n, the number of dimensions in the array. (doesn't need to be called n)
  • p, the number of dimensions in the arrays you are adding up. (doesn't need to be called p)

Output

The respective indices of the p-dimensional array with the largest sum. You may have undefined behavior in the case of a tie. The dimensions of the array that you find should be the last p dimensions of the original array.

Test Cases

Input:

[[[4,2],
  [6,8]],

 [[0,0],
  [500,327]]], 3, 2

Output:

1

Input:

[[1,2],
 [4,3]], 2, 0

Since p=0, you're just finding the largest number in the array, which in this case is 4. The coordinates are:

1 0

Input:

[[1,2],
 [4,-1]], 2, 1

You might see the 1 and 4 in the same column, and that that would have the largest sum of 5. However, because those share the second index, not the first, they are ignored. Both of the rows in this array add to 3, resulting in a tie, so you can return whatever you want here.


Input:

[[1,2],
 [3,4]], 2, 2

Since p=n, there are no indices of the array with the largest sum, so the output would be empty.

Additional Rules

\$\endgroup\$
6
  • 2
    \$\begingroup\$ I think your first example has an extraneous set of [...] around it. It might be worth clarifying exactly which dimensions we're adding. From the spec I would have assumed that we'd need to look at any subset of p dimensions, but judging by the last test case, we're only looking at adding up trailing dimensions (because I can add *p*=1 leading dimension and get 1+4 = 5). \$\endgroup\$ Nov 13 '17 at 15:21
  • \$\begingroup\$ @MartinEnder thanks for noticing that. As for your other note, that might make for a good sequel :) \$\endgroup\$
    – RamenChef
    Nov 13 '17 at 15:26
  • 2
    \$\begingroup\$ Can we take two inputs as the array and n - p? It's way better for some languages. \$\endgroup\$
    – hyper-neutrino
    Nov 13 '17 at 15:38
  • 4
    \$\begingroup\$ Will the input array always have the same size in all dimensions? \$\endgroup\$
    – Luis Mendo
    Nov 13 '17 at 16:14
  • 6
    \$\begingroup\$ What is the definition (being used here) of a p-dimensional [sub-]array? Do we only consider those in the same orientation as the input perspective? (is this why [[1,2], [4,-1]], 2, 1 returns either [1,2] or [4,-1] rather than [1,4]?) \$\endgroup\$ Nov 13 '17 at 20:19
4
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

#~Position~Max@#&@Total[#,{-#2,-1}]&

Try it online!

Returns an array containing all the indices where the maximum value can be found. So for normal inputs that's a singleton array, containing the list of indices to it. If there's a tie, you'll get all the lists of indices for where that value shows up.

The function doesn't actually read the n parameter, because it isn't needed, but you could pass it in as a third argument if you like (it would just be ignored anyway).

One catch here is that for some reason the dimension specification {0,-1} for Total never sums anything. I don't really understand why, but luckily that's just what we need for this challenge.

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

APL (Dyalog), 21 bytes

(⍴⊤⊃∘⍒∘,)+/,⍤⎕⊢⎕

First input is the array, second is p.

Try it online!

How?

+/,⍤⎕ - apply sum over sub arrays of rank p

⊃∘⍒∘, - flatten, grade down and take first

⍴⊤ - encode in the mixed base derived by the shape of the previous result

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

Python 3 + numpy, 92 bytes

lambda a,n,p:unravel_index(argmax(sum(a,(*-arange(n-p,n),))),a.shape[p:])
from numpy import*

Try it online!

Quite a bit longer than I would have hoped. Errors out on cases with no solution.

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

Python 3, 138 bytes

There is probably a better way of doing this

lambda x,n,p:f(x,n,p)[:0:-1]
f=lambda x,n,p:n>p and max([*f(l,n-1,p),i]for i,l in enumerate(x))or[sum(f(l,n-1,p)[0]for l in x)if n else x]

Try it online!

\$\endgroup\$
0

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