Modular broadcasting

Question

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:

• Input and output can be taken by any reasonable means. Their format is flexible as usual.

• Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

• Shortest code in bytes wins.

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]

Answer 1

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.

Answer 2

Charcoal, 25 23 bytes

ＡθＩＥ⌈ＥθＬιＥ⌈ＥθＬ§λ⁰ΣＥ觧νιλ

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

Ａθ

Input everything.

    θ                   Input
   Ｅ                    Map over arrays
      ι                 Current array
     Ｌ                  Length
  ⌈                     Maximum
 Ｅ                      Map over implicit range
          θ             Input
         Ｅ              Map over arrays
             λ          Current array
            § ⁰         First element
           Ｌ            Length
        ⌈               Maximum
       Ｅ                Map over implicit range
                 θ      Input
                Ｅ       Map over arrays
                    ν   Current array
                   § ι  Cyclically index using outer loop index
                  §   λ Cyclically index using inner loop index
               Σ        Sum
Ｉ                       Cast to string
                        Implicitly print on separate lines and paragraphs

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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!

Answer 7

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!

Answer 8

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]

Answer 9

K (ngn/k), 23 bytes

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

Try it online!

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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