Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 lcm(length(A), length(B)). Here 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]]
share|improve this question

16 Answers 16

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}]`

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]));

share|improve this answer

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]]
share|improve this answer
    
Oh, that's a nice way to prepend the sum to the first element of the list. Far shorter than my cumbersome !. – nimi 4 hours ago

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.

share|improve this answer
    
Shouldn´t that be $b[$i%$y]? You can save 3 bytes by moving $x=count($a) to the first usage of $x; same for $y=count($b) and one byte with bitwise or in the while condition – Titus 7 hours ago
    
But I think anonymous functions are considered snippets and hence are no valid answers. – Titus 6 hours ago
    
@Titus Anonymous functions are allowed by default as per consensus on Meta. – Zgarb 4 hours ago
    
Thanks for the suggestions @Titus, I just kinda threw this together cause I wanted to beat the other PHP answers :P – Xanderhall 4 hours ago

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.

share|improve this answer
    
Are you sure? Is there a way to get the exact times? – Christian Sievers 2 hours ago
    
@ChristianSievers: I don't know if you can see the times directly. When the times of our edits were shown in minutes, I remember that yours was counted up a few seconds (about 20) earlier than mine. – nimi 1 hour ago
    
You're right: I found timestamps in the html source code of this page – Christian Sievers 6 mins ago

Python 3.5 - (146137134+13) = 147 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!
share|improve this answer
    
This gives an error for me. The gcd function is in fractions, not math. – Zgarb 12 hours ago
    
@Zgarb the gcd in fractions module is deprecated, you can check the change here . I guess rexter is using the old version 3.4.3. – Gurupad Mamadapur 12 hours ago
    
Neat, I didn't know about this change. You should mark the language as "Python 3.5" though, since it doesn't work in 3.4 or earlier. Also, you can drop the parentheses around l*k and have print(r);r=[] on the last line. – Zgarb 12 hours ago
    
Are you sure your byte count is correct? I think there're only 145 bytes. – vaultah 11 hours ago
    
In any case, you can save some more bytes: 1) l,k,*r=map(len,[a,b]) 2) r+=a[i%l]+b[i%k], 3) if i%k==k-1or i%l==l-1:... – vaultah 11 hours ago

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])

share|improve this answer
1  
Now TIO-Nexus supports Octave. Here's a link to test the code – Luis Mendo 5 hours ago
    
@LuisMendo Thanks, interesting service – rahnema1 5 hours ago

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.
share|improve this answer

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).
share|improve this answer

J, 34 bytes

(0=[:*/,|/i.@*.)&#<;.1[:+/*.&#$&>;

Probably could be made less than 30 bytes.

Try it online!

share|improve this answer

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]
share|improve this answer
    
You can replace ind by k or something, and there are some unnecessary parentheses around drop i l and map(+(-i))ind. Consider also having two cases for %, with pattern matching on l. – Zgarb 12 hours ago

Python 2, 133 bytes

def f(*a):
    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]
        if i==l(v[q^1]):break

Each line in the function body is indented with tab characters. Takes input as two tuples, outputs resulting lists to stdout.

Examples:

>>> f((1, 2, -3, -4), (15,))
[16]
[17]
[12]
[11]
>>> f((0, 3, 2, 2, 8, 4), (7, 8, 7, 2))
[7, 11, 9, 4]
[15, 12]
[7, 5]
[9, 10, 15, 6]

All test cases.

share|improve this answer
    
You can exit the program by throwing an error. Then you might be able to get the loop into a single line. – Zgarb 9 hours ago

PHP, 150 121 bytes

function f($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;}

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;
share|improve this answer

[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
share|improve this answer
    
Draw even with me using these tweaks: $i=$j=$k=0; is unnecessary if you use +$i etc. for the array indexes in the appending assignment (-8 bytes). $i++;if(!isset($A[$i])){$i=0;$k++;} --> isset($A[++$i])?:$i=!++$k; (-9, twice). $i==0&&$j==0&&!isset() --> !$i&!$j&!isset() (-6). return$O; needs no space (-1). – Titus 8 hours ago
    
@Titus can't remove $i=$j=0; part since first values from arrays won't be correct. I've modified logic a little so not sure how to implement ternary operators in this case. Thanks for ++$i advices. – Dexa 7 hours ago
    
Try unset($i);$A[+$i]. The + will cast null to integer 0. – Titus 7 hours ago
    
if(!isset($A[++$i])){$i=0;++$k;++$f;} --> isset($A[++$i])?:$i=!++$k|!++$f; still saves 5 bytes each. Save one more with $f<2 instead of $f!=2. and another two with while($f=$f<3){...} instead of while($f<2){$f=0;...} (initializes and resets $f to 1 unless it´s incremented twice) – Titus 7 hours ago
    
@Titus Thanks a lot, it is shorter now. – Dexa 6 hours ago

Python 3.5, 210 176 173 Bytes

def f(a,b):
 x=[];e=f=0              
 while(1):
  if(e==len(a)):         
   print(x)         
   if(f==len(b)):break
   x=[];e=0;
  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 tips and guidelines from Dennis and TimmyD
  • Reduced 3 bytes: was using c and d for len(a) and len(b), but turns out macros are not always useful :D
share|improve this answer
1  
Hi, and welcome to Programming Puzzles & Code Golf! Non-competing means something else here; you should remove that. You can save quite a few bytes by eliminating whitespace. For example, lines 2 to 5 can become x=[];c=len(a);d=len(b);e=f=0. Also, true can become 1, and x.append(a[e]+b[f]) can become x+=a[e]+b[f],. – Dennis 7 hours ago
1  
Welcome to PPCG! In addition to Dennis' specific tweaks, check out Tips for Golfing in Python to get some more general hints and tricks. – TimmyD 6 hours ago
    
Thank you so much. – officialaimm 6 hours ago
    
if and while statements do not need parenthesis. – orlp 37 mins ago

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

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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