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]

"Implement addition for two-dimensional arrays" - there are one dimensional test cases. — Jonathan Allan, May 3, 2018 at 12:16
May we assume that we get no ragged arrays input? (looks like it) — Jonathan Allan, May 3, 2018 at 12:21
@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]) — Luis Mendo, May 3, 2018 at 13:02
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)? — user2357112, May 4, 2018 at 4:34
@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 — Luis Mendo, May 4, 2018 at 8:30

Neil · Accepted Answer · 2018-05-05 10:31:41Z

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

\$\begingroup\$ :P (it's longer though >_>) \$\endgroup\$
– ASCII-only
May 11, 2018 at 7:43 — ASCII-only, May 11, 2018 at 7:43

Giuseppe · Accepted Answer · 2018-05-11 19:42:59Z

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

:-D My program for the test cases had 26 bytes, well done! Nice use of : with vector input — Luis Mendo, May 11, 2018 at 15:57

Dennis · Accepted Answer · 2018-05-03 13:49:47Z

4

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.

edited May 3, 2018 at 13:49

answered May 3, 2018 at 13:32

Dennis

210k41 gold badges368 silver badges819 bronze badges

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, 2018 at 14:05
1

\$\begingroup\$ @KevinCruijssen APL is not a golfing language. \$\endgroup\$
– Adám
May 4, 2018 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, 2018 at 6:34

Add a comment |

etene · Accepted Answer · 2018-05-04 08:30:15Z

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.

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)? — Jonathan Frech, May 3, 2018 at 15:37

Arnauld · Accepted Answer · 2018-05-03 13:52:56Z

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!

Mr. Xcoder · Accepted Answer · 2018-05-03 15:32:47Z

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.

JayCe · Accepted Answer · 2018-05-16 20:55:53Z

3

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!

edited May 16, 2018 at 20:55

answered May 3, 2018 at 15:19

JayCe

2,94311 silver badges17 bronze badges

\$\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, 2018 at 16:05
\$\begingroup\$ @Giuseppe Thanks! The 104 version does not give the expected output though. \$\endgroup\$
– JayCe
May 3, 2018 at 16:38
1

\$\begingroup\$ Ugh, I keep leading you astray! this one should work \$\endgroup\$
– Giuseppe
May 3, 2018 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, 2018 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, 2018 at 20:54

| Show 4 more comments

ngn · Accepted Answer · 2018-05-03 10:58:51Z

2

K (ngn/k), 23 bytes

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

Try it online!

answered May 3, 2018 at 10:58

ngn

15.2k2 gold badges42 silver badges87 bronze badges

Add a comment |

Emigna · Accepted Answer · 2018-05-03 13:14:24Z

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

user48543user48543 · Accepted Answer · 2018-05-03 13:26:37Z

2

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.

answered May 3, 2018 at 13:26

user48543

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

ngn · Accepted Answer · 2018-05-03 14:54:06Z

2

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]

edited May 3, 2018 at 14:54

answered May 3, 2018 at 10:29

ngn

15.2k2 gold badges42 silver badges87 bronze badges

Add a comment |

Dead Possum · Accepted Answer · 2018-05-03 17:05:55Z

2

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

edited May 3, 2018 at 17:05

answered May 3, 2018 at 16:11

Dead Possum

3,39612 silver badges25 bronze badges

\$\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, 2018 at 8:25
1

\$\begingroup\$ @etene You should post it, it's good solution! \$\endgroup\$
– Dead Possum
May 4, 2018 at 9:48
\$\begingroup\$ Damn, pretty stupid mistakes on my part, thank you (again) ! \$\endgroup\$
– etene
May 4, 2018 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, 2018 at 10:13
1

\$\begingroup\$ @etene Back to 105 bytes :C \$\endgroup\$
– Dead Possum
May 4, 2018 at 10:14

| Show 1 more comment

etene · Accepted Answer · 2018-05-04 10:28:50Z

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

Sundar R · Accepted Answer · 2018-07-04 13:53:31Z

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

Stack Exchange Network

Modular broadcasting

Introduction

Definition of modular broadcasting

The challenge

Test cases

15 Answers 15

Charcoal, 25 23 bytes

MATL, 25 24 bytes

Jelly, 10 bytes

How it works

Python 3, 127 126 125 bytes

JavaScript (ES6), 131 bytes

How?

Recursive version, 134 bytes

05AB1E, 15 bytes

Old version, 25 bytes

Explanation

R, 136 104 103 95 93 bytes

K (ngn/k), 23 bytes

05AB1E, 18 bytes

Pyth, 24 bytes

Explanation

Java 8, 172 bytes

APL (Dyalog Classic), 23 21 bytes

Python 2, 124 116 bytes

Python 2, 101 97 105 bytes

Julia 0.6, 85 83 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number
array
integer
or ask your own question.

Linked

Hot Network Questions

Modular broadcasting

Introduction

Definition of modular broadcasting

The challenge

Test cases

15 Answers 15

Charcoal, 25 23 bytes

MATL, 25 24 bytes

Jelly, 10 bytes

How it works

Python 3, 127 126 125 bytes

JavaScript (ES6), 131 bytes

How?

Recursive version, 134 bytes

05AB1E, 15 bytes

Old version, 25 bytes

Explanation

R, 136 104 103 95 93 bytes

K (ngn/k), 23 bytes

05AB1E, 18 bytes

Pyth, 24 bytes

Explanation

Java 8, 172 bytes

APL (Dyalog Classic), 23 21 bytes

Python 2, 124 116 bytes

Python 2, 101 97 105 bytes

Julia 0.6, 85 83 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfnumberarrayinteger or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number
array
integer
or ask your own question.