24
\$\begingroup\$

This challenge is related to some of the MATL language's features, as part of the May 2018 Language of the Month event.


Introduction

In MATL, many two-input functions work element-wise with broadcast. This means the following:

  • Element-wise (or vectorized): the function takes as inputs two arrays with matching sizes. The operation defined by the function is applied to each pair of corresponding entries. For example, using post-fix notation:

    [2 4 6] [10 20 30] +
    

    gives the ouput

    [12 24 36]
    

    This also works with multi-dimensional arrays. The notation [1 2 3; 4 5 6] represents the 2×3 array (matrix)

    1 2 3
    4 5 6
    

    which has size 2 along the first dimension (vertical) and 3 along the second (horizontal). So for example

    [2 4 6; 3 5 7] [10 20 30; 40 60 80] *
    

    gives

    [20 80 180; 120 300 560]
    
  • Broadcasting or (singleton expansion): the two input arrays do not have matching sizes, but in each non-matching dimension one of the arrays has size 1. This array is implicitly replicated along the other dimensions to make sizes match; and then the operation is applied element-wise as above. For example, consider two input arrays with sizes 1×2 and 3×1:

    [10 20] [1; 2; 5] /
    

    Thanks to broadcasting, this is equivalent to

    [10 20; 10 20; 10 20] [1 1; 2 2; 5 5] /
    

    and so it gives

    [10 20; 5 10; 2 4]
    

    Similarly, with sizes 3×2 and 3×1 (broadcasting now acts along the second dimension only),

    [9 8; 7 6; 5 4] [10; 20; 30] +
    

    gives

    [19 18; 27 26; 35 34]
    

    The number of dimensions may even be different. For example, inputs with sizes 3×2 and 3×1×5 are compatible, and give a 3×2×5 result. In fact, size 3×2 is the same as 3×2×1 (there are arbitrarily many implicit trailing singleton dimensions).

    On the other hand, a pair of 2×2 and 3×1 arrays would give an error, because the sizes along the first dimension are 2 and 3: they are not equal and none of them is 1.

Definition of modular broadcasting

Modular broadcasting is a generalization of broadcasting that works even if none of the non-matching sizes are 1. Consider for example the following 2×2 and 3×1 arrays as inputs of the function +:

[2 4; 6 8] [10; 20; 30] +

The rule is as follows: for each dimension, the array that is smaller along that dimension is replicated modularly (cyclically) to match the size of the other array. This would make the above equivalent to

[2 4; 6 8; 2 4] [10 10; 20 20; 30 30] +

with the result

[12 14; 26 28; 32 34]

As a second example,

[5 10; 15 20] [0 0 0 0; 1 2 3 4; 0 0 0 0; 5 6 7 8; 0 0 0 0] +

would produce

[5 10 5 10; 16 22 18 24; 5 10 5 10; 20 26 22 28; 5 10 5 10]

In general, inputs with sizes a×b and c×d give a result of size max(a,b)×max(c,d).

The challenge

Implement addition for two-dimensional arrays with modular broadcasting as defined above.

The arrays will be rectangular (not ragged), will only contain non-negative integers, and will have size at least 1 in each dimension.

Aditional rules:

Test cases

The following uses ; as row separator (as in the examples above). Each test case shows the two inputs and then the output.

[2 4; 6 8]
[10; 20; 30]
[12 14; 26 28; 32 34]

[5 10; 15 20]
[0 0 0 0; 1 2 3 4; 0 0 0 0; 5 6 7 8; 0 0 0 0]
[5 10 5 10; 16 22 18 24; 5 10 5 10; 20 26 22 28; 5 10 5 10]

[1]
[2]
[3]

[1; 2]
[10]
[11; 12]

[1 2 3 4 5]
[10 20 30]
[11 22 33 14 25]

[9 12 5; 5 4 2]
[4 2; 7 3; 15 6; 4 0; 3 3]
[13 14 9;12 7 9;24 18 20;9 4 6;12 15 8]

[9 12 5; 5 4 2]
[4 2 6 7; 7 3 7 3; 15 6 0 1; 4 0 1 16; 3 3 3 8]
[13 14 11 16; 12 7 9 8; 24 18 5 10; 9 4 3 21; 12 15 8 17]

[6 7 9]
[4 2 5]
[10 9 14]
\$\endgroup\$
  • \$\begingroup\$ "Implement addition for two-dimensional arrays" - there are one dimensional test cases. \$\endgroup\$ – Jonathan Allan May 3 '18 at 12:16
  • \$\begingroup\$ May we assume that we get no ragged arrays input? (looks like it) \$\endgroup\$ – Jonathan Allan May 3 '18 at 12:21
  • 1
    \$\begingroup\$ @JonathanAllan Sorry for not being clear. Yes, you can assume no ragged arrays. They will be rectangular arrays. The "one dimensional" ones should be regarded as two-dimensional with size 1×n (such as [1 2 3]) or n×1 (such as [1; 2; 3]) \$\endgroup\$ – Luis Mendo May 3 '18 at 13:02
  • \$\begingroup\$ The broadcasting you describe seems more limited than MATLAB or NumPy broadcasting; in your description, the inputs have to have the same number of dimensions, a restriction not present in MATLAB or NumPy. Is this a MATL restriction, or a simplification for the purposes of the challenge (since the challenge is limited to 2D input)? \$\endgroup\$ – user2357112 May 4 '18 at 4:34
  • \$\begingroup\$ @user2357112 Yes, it was a simplification in the description. MATL's broadcasting is the same as in MATLAB: you can have 3×2 and 3×1×5 inputs and get a 3×2×5 result. Actually, 3×2 is equivalent to 3×2×1 (implicit trailing dimensions). I think it is similar in Numpy (but with leading dimensions). I've clarified that in the introduction \$\endgroup\$ – Luis Mendo May 4 '18 at 8:30

15 Answers 15

4
\$\begingroup\$

Jelly, 10 bytes

ṁ€ZL$Z€Ɗ⁺S

Takes a matrix pair (two arrays of rows) as input and returns a matrix.

Try it online!

How it works

ṁ€ZL$Z€Ɗ⁺S  Main link. Argument: [M, N] (matrix pair)

  Z $       Zip M with N (i.e., transpose the matrix of arrays [M, N], ...
   L            then take the length (number of rows) of the result.
ṁ€          Mold M and N like the indices, cyclically repeating their rows as many
            times as needed to reach the length to the right.
     Z€     Zip each; transpose both M and N.
       Ɗ⁺   Combine the three links to the left into a chain and duplicate it.
            The first run enlarges the columns, the second run the rows.
         S  Take the sum of the modified matrices.
\$\endgroup\$
  • 1
    \$\begingroup\$ Of course... I see all these golfing languages as somewhat compatible in terms of bytes necessary for a challenge (Jelly, 05AB1E, Pyth, APL, etc.) Most of the current answers are about 20 bytes, and here comes Wizard Dennis along with an answer halve of that.. ;) Pretty funny when memes and truth are one and the same: "Nobody outgolfs Dennis!.." \$\endgroup\$ – Kevin Cruijssen May 3 '18 at 14:05
  • 1
    \$\begingroup\$ @KevinCruijssen APL is not a golfing language. \$\endgroup\$ – Adám May 4 '18 at 5:37
  • 1
    \$\begingroup\$ @Adám I know, I know. But it's still very short (despite being first developed in the 1960s). Maybe I should have said short languages instead of golfing languages. Ah well.. \$\endgroup\$ – Kevin Cruijssen May 4 '18 at 6:34
5
\$\begingroup\$

Charcoal, 25 23 bytes

AθIE⌈EθLιE⌈EθL§λ⁰ΣE觧νιλ

Try it online! Link is to verbose version of code. Takes input as a 3-dimensional array. Explanation:

Aθ

Input everything.

    θ                   Input
   E                    Map over arrays
      ι                 Current array
     L                  Length
  ⌈                     Maximum
 E                      Map over implicit range
          θ             Input
         E              Map over arrays
             λ          Current array
            § ⁰         First element
           L            Length
        ⌈               Maximum
       E                Map over implicit range
                 θ      Input
                E       Map over arrays
                    ν   Current array
                   § ι  Cyclically index using outer loop index
                  §   λ Cyclically index using inner loop index
               Σ        Sum
I                       Cast to string
                        Implicitly print on separate lines and paragraphs
\$\endgroup\$
  • \$\begingroup\$ :P (it's longer though >_>) \$\endgroup\$ – ASCII-only May 11 '18 at 7:43
5
\$\begingroup\$

MATL, 25 24 bytes

,iZy]vX>XKx,@GK:KP:3$)]+

Try it online!

Finally! It only took a week for the Language of the Month-inspired challenge to be answered by the Language of the Month!

My guess is that it's not quite as short as possible, but I'm happy enough because my initial version was over 40 bytes. edit: I was right, Luis found another byte to squeeze out!

,iZy]	# do twice: read input and find the size of each dimension
vX>	# find the maximum along each dimension
XKx	# save this into clipboard K and delete from stack. Stack is now empty.
,	# do twice:
 @G	# push the input at index i where i=0,1.
	# MATL indexes modularly, so 0 corresponds to the second input
 K:	# push the range 1...K[1]
 KP:	# push the range 1...K[2]
 3$)	# use 3-input ) function, which uses modular indexing
	# to expand the rows and columns to the appropriate broadcasted size
]	# end of loop
+	# sum the now appropriately-sized matrices and implicitly display
\$\endgroup\$
  • \$\begingroup\$ waits for Luis Mendo to golf off 5 more bytes ;-) \$\endgroup\$ – Giuseppe May 11 '18 at 14:57
  • \$\begingroup\$ :-D My program for the test cases had 26 bytes, well done! Nice use of : with vector input \$\endgroup\$ – Luis Mendo May 11 '18 at 15:57
4
\$\begingroup\$

Python 3, 127 126 125 bytes

golfed a byte by changing sum(m) to m+n

One more byte thanks to @Jonathan Frech

lambda y:[[m+n for n,m,j in Z(l)]for*l,i in Z(y)]
from itertools import*
Z=lambda y:zip(*map(cycle,y),range(max(map(len,y))))

Takes input as a list of two 2-dimensional arrays.

  • The Z lambda takes two arrays as input and returns an iterator yielding an index and merged values from both arrays, until the index reaches the largest array's length. The index variable isn't useful to me and costs me bytes, but I don't know how to do without it... (related)
  • The main lambda just takes the input arrays and calls Z on the outer and inner arrays. The innermost values are added together.

Try it online!

Using itertools.cycle feels a bit like cheating but I think I've been punished enough by the sheer import statement length :)

I'm sure this could be golfed some more, especially the iteration method that leaves these useless i and j variables. I would be grateful on any tips on how to golf that, I'm probably missing something obvious.

\$\endgroup\$
  • \$\begingroup\$ Could you swap your zip's arguments, reverse f's comprehension assignment and thus remove one space (for i,*l -> for*l,i)? (125 bytes)? \$\endgroup\$ – Jonathan Frech May 3 '18 at 15:37
  • \$\begingroup\$ One more byte, thank you ! I'll update my post. \$\endgroup\$ – etene May 3 '18 at 17:54
3
\$\begingroup\$

JavaScript (ES6), 131 bytes

Not the right tool for the job, and probably not the right approach either. Oh well... ¯\_(ツ)_/¯

a=>b=>(g=(a,b,c)=>[...Array((a[b[L='length']]?a:b)[L])].map(c))(a,b,(_,y)=>g(a[0],b[0],(_,x)=>(h=a=>a[y%a[L]][x%a[0][L]])(a)+h(b)))

Try it online!

How?

The helper function g() creates an array which is as large as the largest input array (a or b) and invokes the callback function c over it:

g = (a, b, c) =>
  [...Array(
    (a[b[L = 'length']] ? a : b)[L]
  )].map(c)

The helper function h() reads the 2D-array a at (x, y) with modular broadcasting:

h = a => a[y % a[L]][x % a[0][L]]

The main code now simply reads as:

a => b =>
  g(a, b, (_, y) =>
    g(a[0], b[0], (_, x) =>
      h(a) + h(b)
    )
  )

Recursive version, 134 bytes

a=>b=>(R=[],g=x=>a[y]||b[y]?a[0][x]+1|b[0][x]+1?g(x+1,(R[y]=R[y]||[])[x]=(h=a=>a[y%a.length][x%a[0].length])(a)+h(b)):g(+!++y):R)(y=0)

Try it online!

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

05AB1E, 15 bytes

2FεIζg∍ø]øεø¨}O

Try it online!


Old version, 25 bytes

é`DŠg∍)Σнg}`DŠнgδ∍€˜)ø€øO

Try it online!

Explanation

15-byter:

2FεIζg∍ø]øεø¨}O – Full program. Takes input as a 3D [A, B] list from STDIN.
2F              – Apply twice:
  ε             – For each in [A, B]:
   Iζ             – Transpose the input (filling gaps with spaces).
     g            – Length (retrieve the number of rows).
      ∍           – Extend the current item (A or B) to the necessary length.
       ø          – Transpose.
        ]       – Close all loops.
         ø      – Transpose again.
          ε     – For each row in ^ (column of the loops result):
           ø    – Transpose the column.
            ¨}  – Remove the last element and close the map-loop.
              O – Sum.

25-byter:

é`DŠg∍)Σнg}`DŠнgδ∍€˜)ø€øO – Full program. Takes input as a 3D list from STDIN.
é                         – Sort the list by length.
 `D                       – Dump contents separately onto the stack, duplicate the ToS.
   Š                      – Perform a triple swap. a, b, c -> c, a, b.
    g                     – Get the length of the ToS.
     ∍                    – Extend the shorter list (in height) accordingly.
      )Σ  }               – Wrap the whole stack into a list and sort it by:
        нg                – The length of its first item.
           `DŠ            – Same as above.
              нg          – The length of the first element.
                δ∍€˜      – Extend the shorter list (in width) accordingly. 
                    )ø    – Wrap the stack into a list and transpose (zip) it.
                      €ø  - Then zip each list.
                        O – Apply vectorised summation.
\$\endgroup\$
3
\$\begingroup\$

R, 136 104 103 95 93 bytes

Golfed down a whopping 33 35 bytes following Giuseppe's advice. Managed to get under 100 bytes by using an operator as a function name. See history for more legible code.

function(x,y,d=pmax(dim(x),dim(y)))y/d[2]/d[1]+x/d[2]/d[1]
"/"=function(x,j)apply(x,1,rep,,j)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice! I've golfed this down to 104 bytes but using apply and rep.len is what I had considered, although I hadn't gotten around to coding it up myself. \$\endgroup\$ – Giuseppe May 3 '18 at 16:05
  • \$\begingroup\$ @Giuseppe Thanks! The 104 version does not give the expected output though. \$\endgroup\$ – JayCe May 3 '18 at 16:38
  • 1
    \$\begingroup\$ Ugh, I keep leading you astray! this one should work \$\endgroup\$ – Giuseppe May 3 '18 at 18:02
  • 1
    \$\begingroup\$ @Giuseppe Love the use of dim, much cleaner and opens the door to a multi-dimensional generalization with recursive calls to r \$\endgroup\$ – JayCe May 3 '18 at 18:09
  • \$\begingroup\$ I've been trying to use outer(x,y,"+") which contains all the right sums, and in a clear pattern. Can't figure out how to extract them efficiently. \$\endgroup\$ – ngm May 3 '18 at 20:54
2
\$\begingroup\$

K (ngn/k), 23 bytes

{+/2{+:'(|/#:'x)#'x}/x}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 18 bytes

éR`UvXNèy‚é`©g∍®+ˆ

Try it online!

Explanation

éR                  # sort by length, descending
  `U                # store the shorter list in X
    v               # for each list y, index N in the longer list
     XNè            # get the nth element of the shorter list
        y‚é         # pair with y and sort by length
           `©g∍     # repeat the shorter list to the same length as the longer
               ®+   # elementwise addition of the lists
                 ˆ  # add to global list
                    # implicitly print global list
\$\endgroup\$
2
\$\begingroup\$

Pyth, 24 bytes

KeSmlhdQmm+Fm@@bdkQKeSlM

Try it here

Explanation

KeSmlhdQmm+Fm@@bdkQKeSlM
                    eSlMQ  Get the maximum length of (implicit) input...
KeSmlhdQ           K       ... and the maximum row length.
        mm                 For each 2d index ...
          +Fm@@bdkQ        ... get the sum of the appropriate elements.
\$\endgroup\$
2
\$\begingroup\$

Java 8, 172 bytes

A->B->{int m=A.length,o=A[0].length,d=B.length,u=B[0].length,l=m>d?m:d,a=o>u?o:u,r[][]=new int[l][a],$;for(;l-->0;)for($=a;$-->0;)r[l][$]=A[l%m][$%o]+B[l%d][$%u];return r;}

Try it online.

Explanation:

A->B->{                   // Method with integer-matrix as both parameters and return-type
  int m=A.length,         //  Rows of `A`                        (we got an     M)
      o=A[0].length,      //  Columns of `A`                     (we got an     O)
      d=B.length,         //  Rows of `B`                        (we got a      D)
      u=B[0].length,      //  Columns of `B`                     (we got a      U)
      l=m>d?m:d,          //  Maximum of both rows               (we got an     L)
      a=o>u?o:u,          //  Maximum of both columns            (we got an     A)
      r[][]=new int[l][a],//  Result-matrix of size `l` by `a`   (and we got an R)
      $;                  //  Temp integer                       (which $pells? ;P)
  for(;l-->0;)            //  Loop over the rows
    for($=a;$-->0;)       //   Inner loop over the columns
      r[l][$]=            //    Set the current cell in the result-matrix to:
        A[l%m][$%o]       //     The value at {`l` modulo-`m`, `$` modulo-`o`} in `A`
        +B[l%d][$%u];     //     Plus the value at {`l` modulo-`d`, `$` modulo-`u`} in `B`
  return r;}              //  Return the result matrix
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Classic), 23 21 bytes

↑{+⌿⍺[⍵|[0]⍳⍴⍺]}2,¨⍴¨

Try it online!

this could be the only time ever I get a chance to use |[0]

\$\endgroup\$
2
\$\begingroup\$

Python 2, 124 116 bytes

l=len
A,B=sorted(input(),key=l)
A*=l(B)
for i in eval(`zip(A,B)`):a,b=sorted(i,key=l);a*=l(b);print map(sum,zip(*i))

Try it online!

Explanation:

Takes list of two 2-d lists as input.

l=len
A,B=sorted(input(),key=l)         # Sort inputed lists by length
A*=l(B)                           # Extend shorter list
for i in eval(`zip(A,B)`):        # Zip and remove copied references
  a,b=sorted(i,key=l)             # Sort lists in each pair (keep references)
  a*=l(b)                         # Extend shorter list
  print map(sum,zip(*i))          # Zip and sum
\$\endgroup\$
  • \$\begingroup\$ I took ideas from both our solutions and came down to 105 bytes. I had to use Python 2 though, and i got the multiplication trick from your code, so it wouldn't feel right to update my answer :) \$\endgroup\$ – etene May 4 '18 at 8:25
  • 1
    \$\begingroup\$ @etene You should post it, it's good solution! \$\endgroup\$ – Dead Possum May 4 '18 at 9:48
  • \$\begingroup\$ Damn, pretty stupid mistakes on my part, thank you (again) ! \$\endgroup\$ – etene May 4 '18 at 10:12
  • 1
    \$\begingroup\$ @etene Just noticed, this solution had issues with 2 and 6 test cases. Need to remove copied references \$\endgroup\$ – Dead Possum May 4 '18 at 10:13
  • 1
    \$\begingroup\$ @etene Back to 105 bytes :C \$\endgroup\$ – Dead Possum May 4 '18 at 10:14
2
\$\begingroup\$

Python 2, 101 97 105 bytes

Edit: Thanks (again !) to Dead Possum for saving 4 bytes

Edit 2: lost 8 bytes, some tests cases weren't passing

A mix between Dead Possum's earlier solution (thanks to him !), and my own Python 3 solution.

lambda y:[map(sum,P(i))for i in P(y)]
def P(y):y=sorted(y,key=len);y[0]*=len(y[1]);return eval(`zip(*y)`)

Try it online!

Same input as my Python 3 solution (a pair of 2 dimensional lists).

Commented code:

# Iterate over the nested lists, resized & joined by P(),
# and sum the inner joined items
lambda y:[map(sum,P(i))for i in P(y)]
def P(y):
 y=sorted(y,key=len)  # Sort the two input lists by length
 y[0]*=len(y[1])      # Multiply the smallest one by the biggest one's length
                      # (The smallest list is now the previously largest one)
 return eval(`zip(*y)`)  # Return paired list elements up to the smallest list's length
\$\endgroup\$
1
\$\begingroup\$

Julia 0.6, 85 83 bytes

M\N=(((r,c),(s,d))=size.((M,N));repmat(M,s,d)+repmat(N,r,c))[1:max(r,s),1:max(c,d)]

Try it online!

(Replace with \ thanks to Jo King)

Works by repeating each matrix horizontally and vertically so they both have the same size (product of row sizes x product of column sizes), adding those up and extracting out the correct region from that. (Row vector inputs or column vector inputs need a reshape call to be cast as 2-dimensional arrays, which I'm assuming is fine since the question specifies "Implement addition for two-dimensional arrays" and "Input and output can be taken by any reasonable means. Their format is flexible as usual.")

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