Array alignment addition

Question

Introduction

Consider two non-empty integer arrays, say A = [0 3 2 2 8 4] and B = [7 8 7 2]. To perform alignment addition on them, we do the following:

1. Repeat each array enough times to have total length \$\text{lcm(length(A), length(B))}\$. Here \$\text{lcm}\$ stands for lowest common multiple.

    A -> [0 3 2 2  8 4][0 3  2 2 8 4]
    B -> [7 8 7 2][7 8  7 2][7 8 7 2]
   

2. Perform element-wise addition on the repeated arrays, and cut the result at every position where there's a cut in either of them.

    A -> [0  3 2 2   8  4][0 3  2  2  8 4]
    B -> [7  8 7 2][ 7  8  7 2][7  8  7 2]
      -> [7 11 9 4][15 12][7 5][9 10 15 6]
   

3. This array of arrays is your result.

The task

Your inputs are two non-empty arrays of integers, and your output shall be the result of their alignment addition, as defined above. The inputs and output can be in any reasonable format. You don't have to worry about integer overflow when performing the addition.

Rules and scoring

You can write a full program or a function. The lowest byte count wins.

Test cases

[1] [4] -> [[5]]
[1,2,-3,-4] [15] -> [[16],[17],[12],[11]]
[0,-4] [2,1,0,-3] -> [[2,-3],[0,-7]]
[0,3,2,2,8,4] [7,8,7,2] -> [[7,11,9,4],[15,12],[7,5],[9,10,15,6]]
[18,17,16] [-1,-2,-3,-4] -> [[17,15,13],[14],[16,14],[15,13],[15],[16,14,12]]
[18,17,16,15] [-1,-2,-3,-4] -> [[17,15,13,11]]
[1,1,1,1,1] [6,5,6,5,6,5,6,2,1] -> [[7,6,7,6,7],[6,7,3,2],[7],[6,7,6,7,6],[7,3,2],[7,6],[7,6,7,6,7],[3,2],[7,6,7],[6,7,6,7,3],[2],[7,6,7,6],[7,6,7,3,2]]
[1,1,1,1,1,1] [6,5,6,5,6,5,6,2,1] -> [[7,6,7,6,7,6],[7,3,2],[7,6,7],[6,7,6,7,3,2]]
[1,1,1,1,1,1,1] [6,5,6,5,6,5,6,2,1] -> [[7,6,7,6,7,6,7],[3,2],[7,6,7,6,7],[6,7,3,2],[7,6,7],[6,7,6,7,3,2],[7],[6,7,6,7,6,7,3],[2],[7,6,7,6,7,6],[7,3,2],[7,6,7,6],[7,6,7,3,2],[7,6],[7,6,7,6,7,3,2]]

Answer 1

JavaScript (ES6), 101 99 bytes

Takes input as 2 arrays. Returns a string.

f=(a,b,j=0,s='')=>a.map((v,i)=>(s+=i*j?' ':s&&'][',s+=b[j]+v,j=++j%b.length))|j?f(a,b,j,s):`[${s}]`

How it works

We iterate on the first array a with a pointer i while updating another pointer j into the second array b. The sums a[i] + b[j] are appended to the output string s. A separator is inserted each time i == 0 or j == 0. We repeat this process until j is back exactly at the beginning of b at the end of an iteration.

Note: When the | operator is applied, a.map(...) is coerced to either NaN (if a contains more than one element) or the current value of j (if a contains exactly one element). Therefore, a.map(...)|j == j in all cases and is safe to use here.

Test cases

f=(a,b,j=0,s='')=>a.map((v,i)=>(s+=i*j?' ':s&&'][',s+=b[j]+v,j=++j%b.length))|j?f(a,b,j,s):`[${s}]`

console.log(f([1], [4]));
console.log(f([1,2,-3,-4], [15]));
console.log(f([0,-4], [2,1,0,-3]));
console.log(f([0,3,2,2,8,4], [7,8,7,2]));
console.log(f([18,17,16], [-1,-2,-3,-4]));
console.log(f([18,17,16,15], [-1,-2,-3,-4]));
console.log(f([1,1,1,1,1], [6,5,6,5,6,5,6,2,1]));
console.log(f([1,1,1,1,1,1], [6,5,6,5,6,5,6,2,1]));
console.log(f([1,1,1,1,1,1,1], [6,5,6,5,6,5,6,2,1]));

Answer 2

Haskell, 84 79 bytes

a#b=a%b where(c:d)%(e:f)|(x:y)<-d%f=(c+e:x):y;[]%[]=[[]];c%[]=[]:c%b;_%d=[]:a%d

My first version was the same in more readable layout:

a#b=a%b where
 (c:d)%(e:f)|(x:y)<-d%f=(c+e:x):y
 []%[]=[[]]
 c%[]=[]:c%b
 _%d=[]:a%d

Using a local definition to avoid having to give (%) extra arguments for a and b. Amazingly, this is almost the same solution given at almost the same time as @nimi's, from whom I took the idea of using only one line for the local definition.

Usage:

*Main> [0,3,2,2,8,4] # [7,8,7,2]
[[7,11,9,4],[15,12],[7,5],[9,10,15,6]]

Answer 3

PHP, 126 120 bytes

function($a,$b){do{$c[$j][]=$a[$i%$x=count($a)]+$b[$i%$y=count($b)];++$i%$x&&$i%$y?:$j++;}while($i%$x|$i%$y);return$c;};

Try it here!

Anonymous function that returns the resulting array of arrays.

Essentially, we loop through the contents of both of our arrays, modding our iterator by the length of the array to simulate 'copying' them. Taking each of the values from the arrays, we sum them and add them to an array in $c. If we reach the end of one of our input arrays (a split, in terms of the challenge), we start assigning into a new array in $c.

The reason for the do while loop is because our condition is based on $i, which starts at 0. If we use a loop where the condition is checked at the beginning, the loop wouldn't run

We only end the summation once we reach the end of both of the arrays at the same time, which would imply the LCM.

Answer 4

Haskell, 87 84 bytes

a#b=a%b where[]%[]=[[]];(e:f)%(g:h)=f%h!(e+g);e%[]=[]:e%b;_%g=[]:a%g
(m:n)!l=(l:m):n

Usage example: [0,3,2,2,8,4] # [7,8,7,2] -> [[7,11,9,4],[15,12],[7,5],[9,10,15,6]].

Simple recursion. Base case: both lists are empty. If only one of them is empty, restart with a full version and start a new cluster in the output. If none is empty, prepend the sum to the from element.

Have also a look at @Christian Sievers' answer, which is almost identical and was posted a few seconds earlier.

Answer 5

Octave , 113 bytes

@(a,b)mat2cell(sum([repmat(a,1,(L=lcm(A=numel(a),B=numel(b)))/A);repmat(b,1,L/B)]),1,diff(unique([0:A:L,0:B:L])))

this function is directly callable to call it place it in parenthesis and call as (@(a,b)...)([1 2 3 4],[6 4 5])

Answer 6

CJam, 30 bytes

{Sf*Laf+_s,f*:.+La/0=S2*a-Sa/}

Try it online!

Takes input as a pair of lists.

Explanation

The idea is to insert some markers into the input arrays (in the form of short strings) which indicate where the aligned array ends, and where we need to insert the breaks in the arrays. This way we can avoid having to compute the LCM.

Sf*    e# Riffle each list with spaces. These are just place holders, so that having
       e# an array-end marker between two elements doesn't misalign subsequent elements.
Laf+   e# Append an empty string to each list. This is the array-end marker.
_s,    e# Convert the pair of lists to a string and get its length. This is always
       e# greater than the number of elements in either input.
f*     e# Repeat either array that many times. This is definitely more than necessary
       e# to reach the LCM (since multiplying by the length of the other list always
       e# gives a common multiple).
:.+    e# Pairwise addition of the list elements. There are four cases:
       e# - Both elements are numbers, add them. This is the actual addition
       e#   we need for the problem.
       e# - Both elements are spaces. This is just a regular position between
       e#   list elements.
       e# - One is a space, one is empty: the result is a single space, and
       e#   this marks a position where one of the arrays ended, which means
       e#   we need to split here.
       e# - Both elements are empty. This happens at the LCM of both list lengths
       e#   and indicates where we need to stop the output.
La/0=  e# Split the input around empty strings and discard everything except
       e# the first chunk.
S2*a-  e# Remove the double-space strings, we no longer need them.
Sa/    e# Split the list around single spaces.

Answer 7

Jelly, 21 20 18 bytes

ṁ€L€æl/$S
J€ỊÇœṗÇḊ

Try it online!

How it works

ṁ€L€æl/$S  Helper link. Argument [X, Y] (arrays of integers).

       $   Combine the two links to the left into a monadic chain.
  L€       Length each; yield the lengths of X and Y.
    æl/    Reduce by least common multiple.
ṁ€         Mold each; cyclically repeat the elements of X and Y to extend them
           to length lcm(length(X), length(Y)).
        S  Compute the sum of the extended X and Y arrays.

J€ỊÇœṗÇḊ   Main link. Argument [A, B] (arrays of integers).

J€         Indices each; replace A and B by the arrays of there 1-based indices.
  Ị        Insignificant; map 1 to itself, all other indices to 0.
   Ç       Apply the helper link to the result.
           This yield a Boolean array with a 1 (or 2) at all indices where a new
           repetition of A or B (or both) begins.
      Ç    Apply the helper link to [A, B].
    œṗ     Partition; break the result to the right at truthy elements (1 or 2) in
           the result to the right.
       Ḋ   Dequeue; remove the first element of the partition (empty array).

Answer 8

Python 3.5 - (146137134130+12) = 142 Bytes

import math
def s(a,b):
 l,k,*r=map(len,[a,b])
 for i in range(l*k//math.gcd(l,k)):
  r+=a[i%l]+b[i%k],
  if i%k==k-1or i%l==l-1:print(r);r=[]

I cannot figure out how to put the whole for loop in one line.

Edits:

• Thanks zgarb for saving 9 bytes!
• Thanks vaultah for saving 3 bytes!
• Thanks mathmandan saving 5 bytes!

Answer 9

Python 2, 119 bytes

a=input()
i,v,l=0,list(a),len
while 1:q=l(v[0])>l(v[1]);print map(sum,zip(*v)[i:]);i=l(v[q]);v[q]+=a[q];1/(i-l(v[q^1]))

Takes input from stdin as two tuples separated by comma, outputs resulting lists to stdout. Terminates by raising the ZeroDivisionError exception, since that seems to be allowed.

For example, if the input is (0, 3, 2, 2, 8, 4), (7, 8, 7, 2), the program will print

[7, 11, 9, 4]
[15, 12]
[7, 5]
[9, 10, 15, 6]

to stdout and the exception traceback to stderr.

Answer 10

J, 34 32 bytes

[:(<;.1~*)/[:+/*.&#$&>,:&(;2>#\)

Try it online!

Explanation

[:(<;.1~*)/[:+/*.&#$&>,:&(;2>#\)  Input: array A (LHS), array B (RHS)
                             #\   Length of each prefix of A and B
                           2>     Less than 2
                          ;       Link each with A and B
                      ,:&         Pair them
                  #               Length of A and B
               *.&                LCM of the lengths
                    &>            For each box
                   $              Reshape it to the LCM of the lengths
           [:+/                   Reduce by addition
[:        /                       Reduce by
        *                           Sign of RHS
   <;.1~                            Box each partition of LHS

Answer 11

Haskell, 166 bytes

This is probably not the most elegant approach: Basically the function ? creates one list of the needed length with thesums, and % is cutting this sum up again. ! is the final function that merges those two.

l=length
a?b=take(lcm(l a)$l b)$zipWith(+)(cycle a)$cycle b
l%(i:ind)|l==[]=[]|1>0=take i l:(drop i l)%(map(+(-i))ind)
a!b=(a?b)%[k|k<-[1..],k`mod`l a<1||k`mod`l b<1]

Answer 12

[PHP], 183 152 135 bytes

function O($A,$B){while($f<2){$O[$k][]=$A[+$i]+$B[+$j];$f=0;isset($A[++$i])?:$i=!++$k|!++$f;isset($B[++$j])?:$j=!++$k|!++$f;}return$O;}

Nice version:

function O($A,$B)
{
    while($f<2) {
        $O[$k][]=$A[+$i]+$B[+$j];
        $f=0;
        isset($A[++$i])?:$i=!++$k|!++$f;
        isset($B[++$j])?:$j=!++$k|!++$f;
    }

    return$O;
}

Output:

array (size=4)
  0 => 
    array (size=4)
      0 => int 7
      1 => int 11
      2 => int 9
      3 => int 4
  1 => 
    array (size=2)
      0 => int 15
      1 => int 12
  2 => 
    array (size=2)
      0 => int 7
      1 => int 5
  3 => 
    array (size=4)
      0 => int 9
      1 => int 10
      2 => int 15
      3 => int 6

Answer 13

PowerShell, 147 145 bytes

param($a,$b)$o=@{};do{$o[+$j]+=,($a[+$i%($x=$a.count)]+$b[$i++%($y=$b.count)]);if(!($i%$x-and$i%$y)){$j++}}until(($x,$y|?{!($i%$_)}).count-eq2)$o

Try it online!

(Golfing suggestions welcome. I feel there's probably another 10 to 15 bytes that can be squeezed out of this.)

Takes input as two explicit arrays (with the @(...) syntax) as command-line arguments. Returns a hashtable of the resulting arrays, because multidimensional arrays in PowerShell can get weird, and this is more consistent. Sets some initial variables, then enters a do/until loop again, with the conditional being until $i is the lcm of the array counts.

Each loop iteration, we add the corresponding $a and $b values together, treat it as an array ,(...) before adding it into the hashtable $o at the appropriate spot $j. The array encapsulation is necessary to prevent arithmetical addition -- this forces the += to overload to array concatenation instead. Then, a conditional on $x and $y (the counts) to determine if we're at an array edge - if so, we increment $j.

Finally, we leave $o on the pipeline and output is implicit.
(NB: Due to how PowerShell enumerates hashtables with the default Write-Output, this tends to be output "backward"; as in, the "0th" resultant array is on the "bottom" of the output. The hash itself is fine, and would be used just fine if you e.g., encapsulated this code in a return variable ... it just looks odd when it's printed.)

Saved 2 bytes by moving $x and $y into the array indexing rather than separate (saved two semicolons).

Answer 14

Python 2, 113 bytes

a,b=input()
i=m=n=0;r=[]
while(not i)+m+n:r+=[[]]*(not m*n);r[-1]+=[a[m]+b[n]];i+=1;m=i%len(a);n=i%len(b)
print r

Answer 15

Python 3.5, 210 176 173 169 158 Bytes

def f(a,b):
 x=[];e=f=0              
 while 1:
  if e==len(a):         
   print(x);x=[];e=0;
   if f==len(b):break
  if f==len(b):print(x);x=[];f=0
 x+=a[e]+b[f],;e+=1;f+=1

Takes two lists as input and prints all the lists.

Its my first answer and I don't know how to golf yet. The basic idea I've used is to have two counters for each list which indicate a split and a current list where the added values are appended onto; as soon as a split is encountered, we print the current list and make a new empty one.

• Saved 34 bytes: Thanks to Dennis and TimmyD
• Saved 3 bytes: was using c and d for len(a) and len(b), but turns out they weren't useful
• Saved 4 bytes: Thanks to orlp, removed unwanted paranthesis
• Saved 11 bytes: rearranged some blocks and crunched them down

Answer 16

Racket 373 bytes

(let*((lg length)(fl flatten)(ml make-list)(t rest)(r reverse)(m modulo)(o cons)(ln(lg l))(jn(lg j))(c(lcm ln jn))(l2(fl(ml(/ c ln)l)))
(j2(fl(ml(/ c jn)j)))(ll(for/list((a l2)(b j2))(+ a b))))(let p((ll ll)(ol '())(tl '())(n 0))(cond[(empty? ll)(t(r(o(r tl)ol)))]
[(or(= 0(m n ln))(= 0(m n jn)))(p(t ll)(o(r tl)ol)(take ll 1)(+ 1 n))][(p(t ll)ol(o(first ll)tl)(+ 1 n))])))

Ungolfed:

(define(f l j)
  (let* ((ln (length l))
         (jn (length j))
         (c (lcm ln jn))
         (l2 (flatten (make-list (/ c ln) l)))
         (j2 (flatten (make-list (/ c jn) j)))
         (ll (for/list ((a l2)(b j2))
               (+ a b))))

    ; TO CUT LIST INTO PARTS: 
    (let loop ((ll ll)
               (ol '())
               (templ '())
               (n 0))
      (cond
        [(empty? ll) 
         (rest (reverse (cons (reverse templ) ol)))]
        [(or (= 0 (modulo n ln))
             (= 0 (modulo n jn)))
         (loop (rest ll)
               (cons (reverse templ) ol)
               (list (first ll))
               (add1 n))]
        [(loop (rest ll)
               ol
               (cons (first ll) templ)
               (add1 n))]))))

Testing:

(f '[1]  '[4])
(f '[1 2 -3 -4] '[15])
(f '[0 3 2 2 8 4]  '[7 8 7 2])

Output:

'((5))
'((16) (17) (12) (11))
'((7 11 9 4) (15 12) (7 5) (9 10 15 6))

Answer 17

Clojure, 280 206 bytes

(fn[a b](let[A(count a)B(count b)Q quot](map #(map last %)(partition-by first(take-while #((% 0)2)(map-indexed(fn[i s][[(Q i A)(Q i B)(or(= i 0)(>(mod i A)0)(>(mod i B)0))]s])(map +(cycle a)(cycle b))))))))

Well this makes a lot more sense. Generating the element-wise sum, adding positional metadata, taking while we haven't repeated yet and putting the sum value to each partition.

(def f (fn[a b]
         (let[A(count a)B(count b)Q quot]
           (->> (map +(cycle a)(cycle b))
                (map-indexed (fn [i s][[(Q i A)(Q i B)(or(= i 0)(>(mod i A)0)(>(mod i B)0))]s]))
                (take-while #((% 0)2))
                (partition-by first)
                (map #(map last %))))))

Original: I'm hoping to improve this but this is the sortest one I have for now.

(fn[a b](let [C cycle o count c(take-while #(or(=(% 0)0)(>(% 1)0)(>(% 2)0))(map-indexed(fn[i[A B]][i(mod i(o a))(mod i(o b))(+ A B)])(map(fn[& v]v)(C a)(C b))))](map #(map last %)(partition-by first(map(fn[p c][p(last c)])(reductions + (map #(if(or(=(% 1)0)(=(% 2)0))1 0)c))c)))))

Ungolfed and verbose:

(def f (fn[a b]
         (let [c(->> (map (fn[& v]v) (cycle a) (cycle b))
                     (map-indexed (fn[i[A B]][i (mod i(count a)) (mod i(count b)) (+ A B)]))
                     (take-while #(or(=(% 0)0)(>(% 1)0)(>(% 2)0))))]
           (->> (map (fn[p c][p(last c)]) (reductions +(map #(if(or(=(% 1)0)(=(% 2)0))1 0)c)) c)
                (partition-by first)
                (map #(map last %))))))

Starts by "merging" an infinite cycle of collections a and b, adds metadata on each element's index within the collection, takes until both sequences start from index 0 again.

This collection c is then merged with partition data (a cumulative sum of ones and zeroes), partitioned and the last element (being sum of items) is selected.

I think for significant improvements a totally different approach is required.

Answer 18

PHP, 150 121 119 bytes

function($a,$b){while($i<2|$x|$y)$r[$k+=!($x=$i%count($a))|!$y=$i++%count($b)][]=$a[$x]+$b[$y];array_pop($r);return$r;}

anonymous function takes input as arrays.

breakdown

while($i<2|$x|$y)   // loop while either $a or $b has NO cut
    $r[
                // if either $a or $b has a cut, increment $k; post-increment $i
        $k+=!($x=$i%count($a))|!$y=$i++%count($b)
                // append current $a + current $b to $r[$k]
    ][]=$a[$x]+$b[$y];
array_pop($r);  // $r has one element too much; remove it
return$r;

Answer 19

C++14, 206 bytes

As unnamed generic lambda, requiring input containers P,Q and output container R to be like vector<vector<int>>.

[](auto P,auto Q,auto&R){R.clear();auto a=P.begin(),b=Q.begin(),x=P.end(),y=Q.end();auto A=a,B=b;do{R.emplace_back();while(a!=x&&b!=y)R.back().push_back(*a+++*b++);a=a==x?A:a;b=b==y?B:b;}while(a!=A||b!=B);}

Ungolfed and usage:

#include<vector>
#include<iostream>

using namespace std;

auto f=
[](auto P,auto Q,auto&R){
 R.clear();               //just clear the output to be sure
 //a and b are the iterators, x and y is the end
 auto a=P.begin(),b=Q.begin(),x=P.end(),y=Q.end();
 //just some abbreviations for .begin()
 auto A=a,B=b;
 do{
  R.emplace_back();      //add new vector
  while(a!=x&&b!=y)      //while not at the end of one vector
   R.back().push_back(*a+++*b++);  //add the pointed elements and advance
  a=a==x?A:a;            //reset if at the end   
  b=b==y?B:b;
 }while(a!=A||b!=B);     //if both were resetted, then finish
}
;


int main(){
 vector<int> A = {0, 3, 2, 2, 8, 4};
 vector<int> B = {7, 8, 7, 2};
 vector<vector<int>> R;
 f(A,B,R);
 for (auto c:R){
  for (int x:c)
   cout << x << ", ";
  cout << endl;
 }
 cout << endl;
}

Answer 20

Mathematica 112 Bytes

This could probably be improved upon. The idea is to create a 2D array with the second element used to track the lessor of the counter i mod the length of each input array.

Split[Table[{#[[1,(m=Mod[i,d=Length/@#,1])[[1]]]]+#[[2,m[[2]]]],Min@m},{i,LCM@@d}],#2[[2]]>#1[[2]]&][[;;,;;,1]]&

Usage

%@{{0,3,2,2,8,4},{7,8,7,2}}

Answer 21

JavaScript (ES6), 131 bytes

(a,b,g=(r,[n,...d]=a,[m,...e]=b,s=[])=>1/n?1/m?g(r,d,e,[...s,n+m]):g([...r,s],[n,...d]):1/m?g([...r,s],a,[m,...e]):[...r,s])=>g([])

Slightly ungolfed:

(a,b,r=[],[n,...d]=a,[m,...e]=b,s=[])
=>1/n?1/m?f(a,b,r,d,e,[...s,n+m])
         :f(a,b,[...r,s],[n,...d],b,[])
     :1/m?f(a,b,[...r,s],a,[m,...e],[])
         :[...r,s]

• If both arrays d and e contain numbers, the sum of the first number is appended to s and the remaining elements are processed recursively
• If one of the arrays contains numbers, the array of sums s is appended to the result r and the other array is reset to its initial array
• If both arrays are empty then simply return the result with the last sums appended.

Sadly this solution doesn't have the ruthless efficiency of @Arnauld's, but at least I think it's a beautiful solution.

Answer 22

Jelly, 17 bytes

Ẉæl/
ẈḍⱮǧkṁ€ÇSƊṖ

Try it online!

How it works

Ẉæl/ - Helper link. Takes an array [A, B] on the left
Ẉ    - Lengths; [len(A), len(B)]
   / - Reduce by:
 æl  -   LCM
       This yields R := lcm(length(A), length(B))

ẈḍⱮǧkṁ€ÇSƊṖ - Main link. Takes [A, B] on the left
Ẉ            - [len(A), len(B)]
   Ç         - Call the helper link on [A, B]
  Ɱ          - Over each integer i = 1, 2, ..., R:
 ḍ           -   Yield [x, y] where:
                   x = 1 if len(A) % i == 0 else 0
                   y = 1 if len(B) % i == 0 else 0
    §        - For each pair, yield 0 if x = y = 0 else a non-zero element
          Ɗ  - To [A, B]:
        Ç    -   Yield R
       €     -   Over each element A, B:
      ṁ      -     Mold to length R
         S   -   Columnwise sums
     k       - Partition this array on the right at the non-zero indexes on the left
           Ṗ - Remove the trailing empty array