Jam don't add like that

Question

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

Answer 1

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.

Answer 2

Jelly, 24 22 bytes

ß"+ŒḊ?çⱮç€</ɼ?,ŒḊ€©Eɗ?

Try it online! or see all test cases

This technically violates

To prevent boring and unbeatable solutions, if a language has this exact operation as a built-in, you may not use that language.

However, this is by no means a boring or unbeatable solution. The only time + is used here is to add two flat integers. The rest of it is recursion to get to that point.

This is a full program which takes the two lists are arguments, and outputs the result.

How it works

ß"+ŒḊ?çⱮç€</ɼ?,ŒḊ€©Eɗ? - Main link f(A, B). Takes A on the left and B on the right
                     ? - If:
                    ɗ  -   Condition:
              ,        -     [A, B]
               ŒḊ€     -     Depth of each
                  ©    -     (Save in register, R)
                   E   -     Both depths are equal?
                           Then:
     ?                 -     If:
   ŒḊ                  -       Condition: depth of A is non-zero
ß"                     -       Then: Run f(A, B) on each subarray in A, B
  +                    -       Else: Return A+B
                           Else:
             ?         -     If:
          </ɼ          -       Condition: depth of A is less than that of B
      çⱮ               -       Then: Over each element b of B, yield f(A, b)
        ç€             -       Else: Over each element a of A, yield f(a, B)

We (ab)use ç in order to get Ɱ to work, as ßⱮ will error due to a bug in setting the arity of ß during execution. ç technically calls the link above explicitly as a dyad, but in a full program with only one link, this wraps around to call the same link.

Answer 3

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.

Answer 4

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]]]]".

Answer 5

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.

Answer 6

C (GCC), 377 354 bytes

-23 bytes thanks to @ceilingcat

d(w,r,i,x)S w;{for(r=i=0;w.v&&i<w.n;r=x>r?x:r)x=d(w.v[i++]);return!!w.v+r;}s(S*z,S x,S y){int e=d(x),f=d(y);if(e-f){S X=e<f?x:y,Y=e<f?y:x;for(z->v=calloc(e=z->n=Y.n,16);e--;)s(z->v+e,X,Y.v[e]);}else if(e+f){z->v=malloc(x.n+y.n<<4);for(e=0;e<x.n|e<y.n;++e)e>=x.n|e>=y.n?z->v[e]=(e<x.n?x:y).v[e],0:s(z->v+e,x.v[e],y.v[e]);z->n=e;}else z->n=x.n+y.n,z->v=0;}

Attempt This Online! (footer contains main, non-golfed functions, and other useful functions)

Assumes that ragged arrays are represented with the following struct:

typedef struct S{
    int n;
    struct S *v;
} S;

where

• if x is an integer, x.n is its value, and x.v is set to NULL;
• if x is a ragged array, x.n is its length, and x.v is the array containing the sub-elements.

Possible improvement: write a function that computes the sum in-place instead of allocating a new ragged array.

---

Thanks to @zoomlogo for pointing to this old interesting challenge in this bounty

Answer 7

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.

Answer 8

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]

Answer 9

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.

Answer 10

Scala 3, 496 bytes

Port of @Value Ink's Ruby anwer in Scala.

---

Golfed version. Attmept this online!

496 bytes, it can be golfed much more.

val d:Any=>Int={case l:Seq[_]=>1+l.map(d).maxOption.getOrElse(0)case _=>0}
def f(x:Any,y:Any):Any=(d(x),d(y))match{
case(a,b)if a<b=>y.asInstanceOf[Seq[_]].map(f(x,_))
case(a,b)if a>b=>x.asInstanceOf[Seq[_]].map(f(_,y))
case _=>(x,y)match{
case(x:Int,y:Int)=>x+y
case(x:Seq[_],y:Seq[_])=>
val(a,b)=(math.min(x.size,y.size),math.max(x.size,y.size))
val z=x.take(a).zip(y.take(a)).map((f _).tupled)
z++(if(x.size==b)x.takeRight(b-a)else Seq())++(if(y.size==b)y.takeRight(b-a)else Seq())
case _=>x}}

Ungolfed version. Attmpt this online!

object Main {
  val depth: Any => Int = {
    case x: List[_] => 1 + x.map(depth).maxOption.getOrElse(0)
    case _ => 0
  }

  def function(x: Any, y: Any): Any = (depth(x), depth(y)) match {
    case (dx, dy) if dx < dy => y.asInstanceOf[List[_]].map(element => function(x, element))
    case (dx, dy) if dx > dy => x.asInstanceOf[List[_]].map(element => function(element, y))
    case _ => (x, y) match {
      case (x: Int, y: Int) => x + y
      case (x: List[_], y: List[_]) =>
        val minLen = math.min(x.size, y.size)
        val maxLen = math.max(x.size, y.size)
        val zipPart = x.take(minLen).zip(y.take(minLen)).map((function _).tupled)
        val remainingPartX = if(x.size == maxLen) x.takeRight(maxLen - minLen) else List()
        val remainingPartY = if(y.size == maxLen) y.takeRight(maxLen - minLen) else List()
        zipPart ++ remainingPartX ++ remainingPartY
      case _ => x
    }
  }

  def main(args: Array[String]): Unit = {
    println(function(List(1, List(2, List(3, List(4)))), List(10, List(20))))
    println(function(List(-1, 0, 1), List(1)))
  }
}

Answer 11

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>

Answer 12

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.

Answer 13

Ruby, 143 145 148 149 147 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.

The function has to be explicitly declared as a proc because -> declares a lambda, which has strict argument checking that won't splat arguments passed in through Array#map.

d=->a{-~(a.map(&d).max||0)rescue 0}
f=proc{|x,y|d[x]<d[y]?y.map{f[x,_1]}:d[x]>d[y]?x.map{f[_1,y]}:d[x]<1?x+(y||0):[*x.zip(y).map(&f),*y[x.size..]]}

Attempt This Online!