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\$

closed as unclear what you're asking by Jonathan Allan, pajonk, caird coinheringaahing, 0 ', Sanchises Nov 15 '17 at 8:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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\$ – Martin Ender 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\$ – HyperNeutrino 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\$ – Jonathan Allan Nov 13 '17 at 20:19
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\$
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\$
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
\$\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\$

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