16
\$\begingroup\$

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.

  1. If x and y have depth 0, return their sum.

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

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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – miles Jun 3 '16 at 0:51
  • \$\begingroup\$ What do you mean by restructuring the input? \$\endgroup\$ – Dennis Jun 3 '16 at 0:55
  • \$\begingroup\$ 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. \$\endgroup\$ – miles Jun 3 '16 at 1:00
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Jun 3 '16 at 1:13
  • 3
    \$\begingroup\$ Hey, nice title!.. now that Google helped me get it :-) \$\endgroup\$ – Luis Mendo Jun 3 '16 at 18:45

10 Answers 10

3
+100
\$\begingroup\$

Pyth, 42 bytes

L?sIb0heSyM+b0M?qFyMJ,GH?yGgM.tJ0+GHgLFyDJ

Test suite

The last 4 bytes simply run the function on the input.

L?sIb0heSyM+b0M?qFyMJ,GH?yGgM.tJ0+GHgLFyDJ

L?sIb0heSyM+b0
                  Define y(b), a helper function to calculate the depth.
 ?                Ternary:
  sIb             If b is invariant under the s function, which is only the case
                  if s is an int.
     0            The depth is 0.
           +b0    Add a 0 on to b. This handles the edge case where b is [].
         yM       Map each to their depth
       eS         Take the max.
      h           Add one.

M?qFyMJ,GH?yGgM.tJ0+GHgLFyDJ
M                               Define g(G, H), which calculates the Jelly +.
 ?                              Ternary:
       ,GH                      Form [G, H].
      J                         Save it to J.
    yM                          Map each to its depth.
  qF                            Check if they are equal.
          ?yG                   If so, check if the depth is nonzero.
               .tJ0             If so, transpose J, pairing each element of each
                                argument with the corresponding element of the
                                other. Pad with zeroes.
             gM                 Map each to its Jelly +.
                   +GH          If the depths are zero, return the normal sum.
                         yDJ    If the depths are different, order J by depth.
                      gLF       Apply the function which left-maps the Jelly +
                                function to the two values. The first is
                                treated as a constant, while the second varies
                                over elements over the second values.
\$\endgroup\$
7
\$\begingroup\$

APL, 44 bytes

{1=≡⍺⍵:⍺+⍵⋄=/∆←|≡¨⍺⍵:⊃∇¨/↓↑⍺⍵⋄</∆:⍺∘∇¨⍵⋄⍵∇⍺}

APL's + distributes over arrays as well, but in a different enough manner that this can't really be used. However, there is a built-in depth function ().

Explanation:

  • 1=≡⍺⍵:⍺+⍵: if the depths of are both zero (and therefore the depth of ⍺ ⍵ is 1), add them.
  • ∆←|≡¨⍺⍵: take the absolute of the depth of both and and store them in . ( gives a negative value if not all elements have the same depth.)
  • =/∆: if they have the same depth:
    • ↓↑⍺⍵: pad the shortest array with zeroes to match the longer array
    • ⊃∇¨/: distribute the function over both arrays
  • </∆: if the depth of is less than that of :
    • ⍺∘∇¨⍵: bind and then map over
  • ⍵∇⍺: if nothing else (so is deeper than ), swap the arguments and try again.
\$\endgroup\$
  • 3
    \$\begingroup\$ Sometimes I think I know APL okay. Then I see a masterpiece like this and I realize that I barely know it at all. \$\endgroup\$ – Alex A. Jun 4 '16 at 6:08
  • \$\begingroup\$ Do APL characters count as bytes really? \$\endgroup\$ – metalim Jun 6 '16 at 11:44
  • \$\begingroup\$ @metalim APL has legacy code pages that predate Unicode by a few decades. In those, each character is a single byte. \$\endgroup\$ – Dennis Jun 6 '16 at 14:40
  • \$\begingroup\$ Then encoding type should be provided with solution. Just IMO. \$\endgroup\$ – metalim Jun 14 '16 at 10:03
  • \$\begingroup\$ @metalim I added a link. \$\endgroup\$ – Adám Jan 17 '17 at 15:27
5
\$\begingroup\$

Mathematica, 122 bytes

d=Depth
x_~f~y_/;d@x>d@y:=y~f~x
x_~f~y_/;d@x<d@y:=x~f~#&/@y
x_List~f~y_:=MapThread[f,{x,y}~PadRight~Automatic]
x_~f~y_=x+y

Defines a recursive function f which computes the sum. Making use of Mathematica's pattern matching, this function is made up of four separate definitions:

x_~f~y_/;d@x>d@y:=y~f~x

If the depth of x is greater than that of y, swap the arguments so that we only have to handle distribution in one direction (which we can do, since addition is commutative).

x_~f~y_/;d@x<d@y:=x~f~#&/@y

If the depth of x is less thann that of y, replace each value # in y with f[x,#], which takes care of the distribution for arguments of unequal depth.

x_List~f~y_:=MapThread[f,{x,y}~PadRight~Automatic]

Otherwise, if one argument is a list (which implies that the other also is a list, since we know they have the same depth), we put both arguments in a list, pad them to the same length with PadRight[..., Automatic] (which simply fills up a ragged array with zeros to make it rectangular), and then use MapThread to apply f to corresponding pairs from the two lists.

And finally, the base case:

x_~f~y_=x+y

If none of the other patterns match, we must be trying to add two numbers, so we just do that.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 150 bytes

data L=S Int|V{v::[L]}
d(V z)=1+maximum(d<$>S 0:z);d _=0
S x!S y=S$x+y
x!y|d x<d y=V$(x!)<$>v y|d x>d y=y!x|1<2=V$v x#v y
(x:a)#(y:b)=x!y:a#b;a#b=a++b

Explanation

The first line defines an algebraic data type L, which is either a Scalar (containing an Int) or a Vector (containing a list of Ls, accessed using a record getter v, which is a partial function L → [L].)

The second line defines the depth function: the depth of a Vector is one plus its maximum depth. I prepend S 0 to the values in the vector, so that depth [] == 1 + maximum [depth (S 0)] == 1. The depth of “anything else” (a scalar) is 0.

The third line defines the base case for ! (the addition function): the sum of scalars is simply a scalar.

The fifth line defines a variant of zipWith (!) that just picks elements from the longest list when one of them is empty.

The fourth line is split in three cases:

x!y | d x<d y = V$(x!)<$>v y
    | d x>d y = y!x
    | True    = V$v x#v y
  • If the depth of x is strictly less than the depth of y, map (x!) over the elements of y. (The use of v is guaranteed to be valid, as d(y) ≥ 1.)

  • If the depth of x is strictly greater, flip the arguments and restart.

  • If their depths are equal, zip the arguments together with (!). (The use of v is guaranteed to be valid, as the case d(x) = d(y) = 0 was handled as a base case.)

Test cases

instance Show L where
  show (S x) = show x
  show (V x) = show x

lArg = V [S 1, V [S 2, V [S 3, V [S 4]]]]
rArg = V [S 10, V [S 20]]

Then show (lArg ! rArg) == "[[11,[21]],[[12,[22]],[13,[24]]]]".

\$\endgroup\$
  • \$\begingroup\$ I just fixed that, too ^^ (I had swapped the lines for readability, but I did it the wrong way…) The import is because Ideone has an old Haskell compiler. Modern versions of GHC put <$> in Prelude, so you don’t need to import Control.Applicative to use it these days. \$\endgroup\$ – Lynn Jun 3 '16 at 17:25
  • \$\begingroup\$ Agh too many edits at the same time as my other actions :P And sure, it seems ok now, but I find it pretty weird that that causes a compilation error. Do all the pattern matching bits of a function have to be consecutive? \$\endgroup\$ – FryAmTheEggman Jun 3 '16 at 17:27
  • \$\begingroup\$ That’s exactly right. \$\endgroup\$ – Lynn Jun 3 '16 at 17:28
  • \$\begingroup\$ Alright, thanks for all your help :) "I'll get the hang of this language some day" - FryAmTheEggman 7 years ago. \$\endgroup\$ – FryAmTheEggman Jun 3 '16 at 17:34
4
\$\begingroup\$

Java, 802 794 754 746 bytes

I decided to take up @Dennis♦ for the challenge to operate on strings "as a last resort" because it was probably "too complicated". Also, in the worst language to golf on.

Arrays in the input are comma-separated, surrounded with square brackets, and without whitespace.

Full program with functions wrapped into a class and with test cases

import java.util.*;
List<String>p(String s){List r=new ArrayList<String>();String p="";int l=0;for(char c:s.substring(1,s.length()-1).toCharArray()){l+=c=='['?1:c==']'?-1:0;if(c==','&&l<1){r.add(p);p="";}else p+=c;}if(p!="")r.add(p);return r;}
int d(String s){int l=0;if(s.contains("[")){for(String c:p(s))l=d(c)>l?d(c):l;l++;}return l;}
String f(String x,String y){int i=0;String r="";if(d(x)<1&&d(y)<1)r+=Integer.valueOf(x)+Integer.valueOf(y);else{r="[";if(d(x)<d(y))for(String k:p(y))r+=(i++<1?"":",")+f(x,k);else if(d(x)>d(y))for(String k:p(x))r+=(i++<1?"":",")+f(k,y);else for(;i<p(x).size()||i<p(y).size();i++)r+=(i<1?"":",")+(i<p(x).size()&&i<p(y).size()?f(p(x).get(i),p(y).get(i)):i<p(x).size()?p(x).get(i):p(y).get(i));r+="]";}return r;}

I might port this to C++ later since it's the other language I know that doesn't support ragged arrays, since I'm pretty sure almost certain it'll be shorter than this answer. This was mostly a proof of concept but any golfing tips would still be appreciated!

-31 bytes from @user902383 suggesting using a foreach over a converted character array, and then I saved a little more from rearranging the if blocks in the final part.

\$\endgroup\$
  • \$\begingroup\$ That's impressive. \$\endgroup\$ – Dennis Jun 6 '16 at 3:30
  • \$\begingroup\$ I think if you replace your loops with foreach loop trough char array obtained from string, you could save quite lot of bytes. \$\endgroup\$ – user902383 Jun 6 '16 at 13:10
  • 1
    \$\begingroup\$ Errr... Java supports ragged arrays; I'm not sure what you mean by that. Use Object[], which contains either nested Object[] or Integer. Or just non-generic List. \$\endgroup\$ – Robert Fraser Sep 24 '16 at 18:45
4
\$\begingroup\$

Python 2.7, 261 209 202 198 191 185 197 181 bytes

FGITW trivial solution

EDIT: Of course @Dennis beats it

Thanks to @LeakyNun for saving 57 bytes with tips on lambda expressions, and 2 bytes from unneeded brackets.

Thanks to @Adnan for 4 bytes due to suggestion to use type instead of isinstance

Thanks to @Lynn for 7 bytes with -~ and map

Thanks to @FryAmTheEggman for z>=[] instead of type

+12 bytes to convert lambda to if else and fix a major bug

-16 bytes thanks to @Kevin Lau - not Kenny

Try it online

d=lambda z:z==[]or z>[]and-~max(map(d,z))
p=lambda x,y:p(y,x)if d(x)>d(y)else(x+y if d(x)<1 else[p(a,b)for a,b in zip(x,y)]+x[len(y):]+y[len(x):])if d(x)==d(y)else[p(a,x)for a in y]
\$\endgroup\$
  • \$\begingroup\$ It’s even shorter to switch to Python 2.7 and write z==[]or`z`>']'and ... \$\endgroup\$ – Lynn Jun 3 '16 at 15:33
  • \$\begingroup\$ Also, I think replacing max(d(a)+1for a in z) with -~max(d(a)for a in z) saves a byte (because you can remove the space before max). Which is then just -~max(map(d,z)). \$\endgroup\$ – Lynn Jun 3 '16 at 15:34
  • \$\begingroup\$ Switching to python 2 saves even more in that you can change [p(a,b)for a,b in zip(x,y)] into map(p,x,y). You can still do this in 3 but you need to add a call to list. I think you could also improve Lynn's suggestion to be z>=[]. Unrelated, you should also be able to swap the type comparison order to save a space. \$\endgroup\$ – FryAmTheEggman Jun 3 '16 at 17:47
  • \$\begingroup\$ Err, I meant or`z`>'[', of course, but I can’t change my comment anymore. But indeed, z>[] is even shorter (the == case is already handled)! \$\endgroup\$ – Lynn Jun 3 '16 at 17:53
  • \$\begingroup\$ @FryAmTheEggman map doesn't work when the lists are of different sizes; zip truncated correctly. I will update with the list check tho \$\endgroup\$ – Blue Jun 3 '16 at 18:58
3
\$\begingroup\$

Python 2, 145 136 bytes

d=lambda t:t>{}and-~max(map(d,t+[0]))
s=lambda x,y:s(y,x)if d(y)<d(x)else map(s,(x,[x]*len(y))[d(x)<d(y)],y)if d(y)else(x or 0)+(y or 0)

Test it on Ideone.

How it works

In Python 2, all integers are less than all dictionaries, but all lists are greater. d recursively computes the depth of t by returning 0 for integers or the incremented maximum of the depths of its elements and 0. t+[0] avoids special-casing the empty list.

s recursively computes the Jelly sum of x and y.

If y's depth exceeds x's, s(y,x) calls s with swapped arguments, making sure that d(x) ≤ d(y).

If y has positive depth, map(s,(x,[x]*len(y))[d(x)<d(y)],y) does the following.

  • If the x's and y's depths match, it executes map(s,x,y), mapping s over all elements of x and the corresponding elements of y.

    In the case of lists of different lengths, map will pass None as left or right argument for missing elements in the shorter list.

  • If x's depth is lower than y's, it executes map(s,[x]*len(y),y), mapping s(x, · ) over y.

If y (and, therefore, x) has depth 0, (x or 0)+(y or 0) replaces falsy arguments (None or 0) with zeroes and returns the sum of the resulting integers.

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

JavaScript (ES6), 152 bytes

f=(a,b,g=a=>a.map?1+Math.max(0,...a.map(g)):0)=>g(a)<g(b)?f(b,a):g(b)<g(a)?a.map(e=>f(e,b)):g(a)?a.length<b.length?f(b,a):a.map((e,i)=>f(e,b[i]||0)):a+b
;t=(x,y,z)=>o.textContent+=`
${JSON.stringify(x)}
${JSON.stringify(y)}
${JSON.stringify(z)}
${JSON.stringify(f(x,y))}
`;`
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]]]]`.slice(1).split`
`.map(l=>t(...l.split(/ [+=] /).map(a=>JSON.parse(a))));
<pre id=o></pre>

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

Ruby 2.3, 143 145 148 149 bytes

Ruby has all these little quirks in how zip works with different-length arrays and map with multi-argument functions, making this pretty fun to golf down.

f=->x,y{d=->a{-~(a.map(&d).max||0)rescue 0}
d[x]<d[y]?y.map{|e|f[x,e]}:d[x]>d[y]?x.map{|e|f[e,y]}:d[x]<1?x+(y||0):[*x.zip(y).map(&f),*y[x.size..-1]]}
\$\endgroup\$
  • \$\begingroup\$ That's very interesting-- I've never seen that error before for this function. I still patched some things up because of other bugs now, but other than that it works for me (but still fails on ideone). I think it's because ideone runs 2.1 and I have 2.3, so perhaps 2.1 can't just map on a two-arg function the way I set it up at the end. Here's a version edited for 2.1 that works that tweaks the map call at the end to work. ideone.com/q1jqTA \$\endgroup\$ – Value Ink Jun 5 '16 at 5:39
1
\$\begingroup\$

Julia, 113 bytes

~=endof;!t=0t!=0&&1+maximum(!,[t;0])
x::Array+y::Array=(!x,~x)>(!y,~y)?y+x:!x<!y?map(t->x+t,y):~x<~y?[x;0]+y:x.+y

Try it online!

How it works

~=endof

creates a 1-byte alias for endof, which returns the length of an array.

!t=0t!=0&&1+maximum(!,[t;0])

defines a depth function. The depth of t is zero if and only if 0t == 0. If not, t is an array, and its depth is calculated as the incremented maximum of the depths of its elements and 0. [t;0] appends a 0 to the array t, thus avoiding the need to special-case the empty array.

Julia's built-in sum + already behaves like Jelly's sum if either (or both) of its arguments is an integer. However, the sum of two arrays (+) requires arrays of the same shape, and even the vectorized sum (.+) required arrays that can be broadcast to a common shape.

We redefine + for a pair of arrays via

x::Array+y::Array=(!x,~x)>(!y,~y)?y+x:!x<!y?map(t->x+t,y):~x<~y?[x;0]+y:x.+y

This does not affect the definition of + for integer/integer, array/integer or integer/array arguments.

(!x,~x)>(!y,~y) lexicographically compares the pairs of depths and lengths of both x and y. If x's depth exceeds y's, or if their depth match and x's length exceeds y's, y+x recursively calls + with swapped arguments.

Otherwise, !x<!y tests if x's depth is lower than y's. If it is, map(t->x+t,y) maps x + · over y.

If the depths match, ~x<~y tests if x is shorter than y. If it is, [x;0]+y recursively calls + after appending a 0 to the left argument.

Finally, if both depths and lengths are identical, x.+y maps + over all elements of x and the corresponding elements of y.

\$\endgroup\$

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.