16
3
Background
Jelly's arithmetic atoms vectorize automatically. In fact, x + y is well-defined whenever x and y are numbers or ragged arrays of numbers. Jelly's source code implements this behavior using a generic vectorizer, but for this challenge, we'll only consider addition of integers and nested integer arrays.
Definitions
Define the depth of x as 0 if x is an integer, as 1 if it is a (possibly empty) flat array of integers, and as n + 1 if it contains at least one element of depth n and no elements of depth k > n.
This way, 1 has depth 0, [] and [1] and [1, 1] have depth 1, [[], []] and [[1], [1]] and [[1]] and [1, []] have depth 2, [1, [1, [1]]] has depth 3, etc.
The operation x + y is defined as follows.
If x and y have depth 0, return their sum.
If x and y have equal but positive depths, recursively apply + to all items of x and the corresponding items of y.
If x and y have different lengths, append the tail of the longer array to the array of sums.
Return the result.
If x's depth is strictly smaller than y's depth, recursively apply + to x and all items of y, and return the result.
Do the opposite if y's depth is strictly smaller than x's.
For example, consider the operation [1, [2, 3], [4]] + [[[10, 20], [30], 40, 50], 60].
The depth of the left argument is 2, while the depth of the right argument is 3, so we compute [1, [2, 3], [4]] + [[10, 20], [30], 40, 50] and [1, [2, 3], [4]] + 60.
[1, [2, 3], [4]] and [[10, 20], [30], 40, 50] both have depth 2, so we compute 1 + [10, 20], [2, 3] + [30] and [4] + 40.
1 + [10, 20] = [1 + 10, 1 + 20] = [11, 21]
[2, 3] + [30] = [2 + 30, 3] = [32, 3]
Note that 3 remains untouched, since it doesn't have a matching element.
[4] + 40 = [4 + 40] = [44]
50 doesn't have a matching element, so the result is [[[11, 21], [32, 3], [44], 50]].[1, [2, 3], [4]] + 60 = [1 + 60, [2, 3] + 60, [4] + 60] = [61, [2 + 60, 3 + 60], [4 + 60]], resulting in [61, [62, 63], [64]].
The final result is [[[11, 21], [32, 3], [44], 50], [61, [62, 63], [64]]].
Task
Write a program or a function that takes two integers, two nested arrays of integers or a combination thereof as input and returns their sum, as defined above.
If your language has multiple array-like types (lists, tuples, vectors, etc.) you may choose any of them for your answer. The return type must match the argument type.
To prevent boring and unbeatable solutions, if a language has this exact operation as a built-in, you may not use that language.
All built-ins of all other languages are allowed. If your language of choice permits this, you may overload and/or redefine the built-in addition.
This is code-golf, so the shortest code in bytes wins.
Test cases
0 + 0 = 0
[-1, 0, -1] + [1] = [0, 0, -1]
[] + [0] = [0]
[] + 0 = []
[] + [] = []
[[], 0] + [] = [[], []]
[1, 2, 3] + 10 = [11, 12, 13]
[1, 2, 3] + [10] = [11, 2, 3]
[1, 2, 3] + [10, [20]] = [[11, 12, 13], [21, 2, 3]]
[1, 2, 3, []] + [10, [20]] = [11, [22], 3, []]
[1, [2, [3, [4]]]] + [10, [20]] = [[11, [21]], [[12, [22]], [13, [24]]]]
To generate more test cases, you can use this Jelly program.
What if our language doesn't support ragged arrays? Are we allowed to restructure the input or should we implement ragged arrays? Or perhaps just use a different language? – miles – 2016-06-03T00:51:28.490
What do you mean by restructuring the input? – Dennis – 2016-06-03T00:55:34.870
In further thinking, I realize it would not work to restructure the input but anyways I'll summarize what I meant before. I thought about using a fill value to pad, which would eliminate some work but also create a different problem (probably different from your intended question) but realize now that your test cases include negative numbers too. – miles – 2016-06-03T01:00:16.607
The arrays may also be heterogeneous, so fill values wouldn't suffice to make them rectangular. As a last resort, there's always the option to operate on strings, but that's probably too complicated. – Dennis – 2016-06-03T01:13:57.717
3Hey, nice title!.. now that Google helped me get it :-) – Luis Mendo – 2016-06-03T18:45:07.947