# Compute the convolution of two strings

While implementing polynomial multiplication in Itr I found the following interesting operation on strings

To compute the convolution of two strings (for instance Hello and World) first combine all pairs of letters with indices that add up to the same number (ordered by the index of the first element)

0 -> "HW"
1 -> "Ho" "eW"
2 -> "Hr" "eo" "lW"
3 -> "Hl" "er" "lo" "lW"
4 -> "Hd" "el" "lr" "lo" "oW"
5 -> "ed" "ll" "lr" "oo"
6 -> "ld" "ll" "or"
7 -> "ld" "ol"
8 -> "od"


and then concatenate all these letter pairs into a single string.
Which in this example gives HWHoeWHreolWHlerlolWHdellrlooWedlllrooldllorldolod.

Write a program of function that takes two strings as input and outputs their convolution.

## Examples:

"" "Empty" -> ""         // empty string
"Hello" "World" -> "HWHoeWHreolWHlerlolWHdellrlooWedlllrooldllorldolod"
"Code" "Golf" -> "CGCooGCloodGCfoldoeGofdleodfelef"
"123" "ABC" -> "1A1B2A1C2B3A2C3B3C"
"split" " " -> "s p l i t " // note the trailing whitespace
"+-" "12345" -> "+1+2-1+3-2+4-3+5-4-5"


This is the shortest solution (per language) wins.

# JavaScript (Node.js), 62 bytes

a=>b=>a.map((c,i)=>b.map(d=>L[i]=[L[i++]]+c+d),L=[])&&L.join


Try it online!

# APL (NARS2000), 7 glyphs

,/⍞,⍡,⍞

• ,/ Concatenate
• ,⍡, the convolution by concatenation and concatenation
• ⍞ of a string input
• ⍞ and another string input

# Jelly, 10 bytes

+þŒdṙL{UFṚ


Try It Online!

This can almost certainly be about half the length; I'll get back to this when I can.

## Explanation

+þŒdṙL{UFṚ    Main Link
+þ            Outer product table with sum
Œd          Matrix antidiagonals
ṙL{       Rotate left by the length of the left string
U      Reverse (vectorizing)
F     Flatten
Ṛ    Reverse the whole list


The reason I use +þ instead of just cartesian product is that cartesian product in Jelly returns a flat list of pairs.

## Step-by-step

Let's start with "+- and "12345". First, we take the outer product table with sum which gives us [['+1', '-1'], ['+2', '-2'], ['+3', '-3'], ['+4', '-4'], ['+5', '-5']]. Normally, in Jelly, strings are arrays of their characters, but using + breaks that. This usually causes problems but in this case actually helps as getting the matrix antidiagonals would not work correctly if this had depth 3.

Then, we take the matrix antidiagonals which start at the main anti-diagonal and go left, which gives [[['-', '1'], ['+', '2']], [['+', '1']], [['-', '5']], [['-', '4'], ['+', '5']], [['-', '3'], ['+', '4']], [['-', '2'], ['+', '3']]]. For some reason, this operation turns the strings back into normal Jelly strings.

We then rotate to the left by the length of the left string, which puts the pair containing the first character in each string at the end, giving us [[['-', '5']], [['-', '4'], ['+', '5']], [['-', '3'], ['+', '4']], [['-', '2'], ['+', '3']], [['-', '1'], ['+', '2']], [['+', '1']]].

Now, all of our pairs are in inverse order, so we want to reverse the whole thing. However, because the pairs are at depth 2, we would also need to reverse each sublist. There are thus two ways to do this:

1. We can reverse each pair and then flatten the whole thing and reverse it, removing the need to worry about depth. This is the solution Jonathan Allen came up with in his golf. We do this with UFṚ (UFU would do the same thing).
2. We can reverse each sublist and then reverse the whole list, and the depth does not matter because Jelly will smashprint all of the characters onto one line at the end. We do this with any of Ṛ€Ṛ, ṚṚ€, or Ṛ⁺€.

## Credits

• -1 byte thanks to Jonathan Allan using +þ instead of +€Ɱ
• -2 bytes thanks to Jonathan Allan by changing the way the ordering is done.
• +þŒdṙL{UFṚ for ten. Commented Aug 5, 2023 at 17:24
• @JonathanAllan huh, that's an interesting way to do it, thanks Commented Aug 5, 2023 at 19:06

# J, 17 14 12 10 bytes

[:;]/.@{@;


Try it online!

J's /. builtin is tailor made for this...

• {@; Create a table of all pairs
• ]/.@ Get each diagonal
• [:; Flatten and unbox

# APL (dzaima\APL), 7 glyphs

∊⊂⍁⍤∘.,

• ∊ flatten into a list
• ⊂⍁ every diagonal
• ∘., of the table of all pairs of the input

# Scala, 118 bytes

Golfed verson. Try it online!

(p,q)=>{(for{z<-0 until p.length+q.length;i<-0 to z;j=z-i;if i<p.length&&j<q.length}yield s"${p(i)}${q(j)}").mkString}


Ungolfed version. Try it online!

object Main {
def main(args: Array[String]): Unit = {
val tests = List(
("" -> "Empty"),
("Hello" -> "World"),
("Code" -> "Golf"),
("123" -> "ABC"),
("split" -> " "),
("+-" -> "12345")
)

tests.foreach {
case (s1, s2) =>
println(s""""$s1" "$s2" -> "${convolve(s1, s2)}"""") } } def convolve(s1: String, s2: String): String = { (for { sum <- 0 until s1.length + s2.length i <- 0 to sum j = sum - i if i < s1.length && j < s2.length } yield s"${s1(i)}${s2(j)}").mkString } }  # Haskell, 72 66 bytes -6 bytes thanks to @xnor import Data.List f=(map snd=<<).sortOn(sum.map fst).mapM(zip[0..])  Attempt This Online! Attempt This Online! • You can do (map snd=<<) for concatMap(map snd) – xnor Commented Aug 6, 2023 at 2:16 • I think you need the parens or it won't parse – xnor Commented Aug 6, 2023 at 19:35 # K (ngn/k), 30 bytes {,/+l@'d\<,/+\:/!'d:#'l:(x;y)}  Try it online! # Jelly, 8 bytes Ẉp/SÞị"€  A full program that accepts a pair of lists of characters and prints the result. Try it online! Or see the test-suite. ### How? Make a list of all of the pairs of indices of the strings in row-major order, sort these by their sums and then use each of these pairs to index back into the two strings respectively. The result is implicitly smashed together and printed. Ẉp/SÞị"€ - Main Link: pair of lists of characters = [A, B] Ẉ - length of each -> [len(A), len(B)] / - reduce by: p - Cartesian product -> [[1, 1], [1, 2], ..., [1, len(B)], [2, 1], ..., [len(A), len(B)]] Þ - sort by: S - sum € - for each: " - zip-wise: ị - index into {[A, B]} - implicit, smashing print  # Python, 78 bytes f=lambda a,b,i=0:a and''.join(sum(zip(a,b[i::-1]),()))+f(a[b==b[:i+1]:],b,i+1)  Attempt This Online! # Pip, 22 bytes a@_.b@BMU$+_SKFL#aCG#b


Attempt This Online!

### Explanation

a@_.b@BMU$+_SKFL#aCG#b #a ; Length of first input #b ; Length of second input CG ; Make a 2D grid that size of [row, col] coordinates FL ; Flatten into a 1D list of coordinate pairs SK ; Sort by this key function:$+_            ;   Sum of coordinate pair
; SK is stable, so coords on the same diagonal stay in the
; original order, which puts smaller row numbers first
MU               ; Map to each pair, unpacking into two separate args:
a@_                     ;   Index into first string with first arg
b@B                 ;   Index into second string with second arg
.                    ;   Concatenate
; Autoprint the list concatenated together (implicit)


# Charcoal, 17 bytes

⭆⁺θη⭆θ⭆Φη⁼κ⁺μξ⁺λν


Try it online! Link is to verbose version of code. Explanation:

  θ                 First input
⁺                  Concatenated with
η                Second input
⭆                   Map over characters and join
θ              First input
⭆               Map over characters and join
η           Second input
Φ            Filtered where
μ       Inner index
⁺        Plus
ξ      Innermost index
⁼          Equals
κ         Outer index
⭆             Map over characters and join
λ    Inner character
⁺     Plus
ν   Innermost character
Implicitly print


# Retina, 47 bytes

Lw$(.).*¶.*(.)$.*¶$.>*¶$1$2 O$(¶+).+
$1 ¶  Try it online! Takes input on separate lines but link is to test suite that splits on tabs for convenience. Explanation: Lw$(.).*¶.*(.)
$.*¶$.>*¶$1$2


List the Cartesian product of the two strings, but prefix each result with a number of newlines corresponding to the sum of the indices. (Results after the first gain an extra newline but this doesn't affect the overall sort order.) If I didn't have to handle empty strings then the L$ could be removed to save two bytes. O$(¶+).+
\$1


Sort each pair of characters by the sum of their original indices.

¶



Join everything together.

# Python3, 121 bytes:

E=enumerate
def f(x,y):
d={}
for i,a in E(x):
for j,k in E(y):d[i+j]=d.get(i+j,'')+a+k
return''.join(d[i]for i in d)


Try it online!

• Couldn't you use d.values() instead of d[i]for i in d? Commented Aug 5, 2023 at 19:23

# Ruby, 74 bytes

->a,b,*r{a.size.times{|i|b.size.times{r[k=i+_1]=[*r[k],a[i],b[_1]]}}
r*''}


Attempt This Online!

# C, 123 121 bytes

Very naive approach: 3 nested loops.

k,n;main(int c,char**v){char*a,*b;do for(c=n++,a=v[1];*a;a++)for(k=c--,b=v[2];*b;b++)k--||printf("%c%c",*a,*b);while(k);}


Compile, then run the executable with the two strings as parameters.

# 05AB1E, 14 bytes

€.āâΣ€θO}€€н˜


Input as a pair of strings; output as a list of characters.

Explanation:

€           # Map over both strings in the (implicit) input-pair:
.ā         #  Enumerate the string, pairing each character with its (0-based) index
# Pop and push both lists separated to the stack
â       # Cartesian product the two together, creating pairs
Σ      # Sort this list of pairs of pairs by:
€θ    #  Map over both pairs:
#   Keep the last item of the inner-most pair (the indices)
O   #  Sum them together
}€€    # After the sort-by: nested map over each inner-most pairs:
н   #  Keep the first item (the characters)
˜  # Flatten the list of pairs of characters
# (after which it is output implicitly as result)


# T-SQL, 323 bytes

DECLARE @n BIGINT=1;SELECT STRING_AGG(COALESCE(SUBSTRING(a,Y.value,1)+SUBSTRING(b,Z.value,1),''),'') WITHIN GROUP(ORDER BY Y.value+Z.value,Y.value)FROM(VALUES(@a,@b)) X(a,b)JOIN GENERATE_SERIES(@n,LEN(@a+'x')-1) Y ON LEN(@a+'x')>1JOIN GENERATE_SERIES(@n,LEN(@b+'x')-1) Z ON LEN(@b+'x')>1RIGHT JOIN (SELECT 1 AS c) W ON 1=1

Explanation:

DECLARE @a VARCHAR(MAX) = '123'; --Input string @a
DECLARE @b VARCHAR(MAX) = 'ABC'; --Input string @b
DECLARE @n BIGINT=1; --GENERATE_SERIES requires all arguments have the same integer data type. LEN of a VARCHAR(MAX) returns BIGINT, need the value 1 (INT by default) to also be BIGINT.

--This query shows the result set that STRING_AGG would act upon, in the correct order. (The final column would be aggregated)
SELECT
Y.value --The 1-indexed index of string @a. NULL if either string is empty
, Z.value --The 1-indexed index of string @b. NULL if either string is empty
, Y.value+Z.value --The sum of indicies
, SUBSTRING(a,Y.value,1) --Single character of @a at the Y.value index. NULL if either string is empty
, SUBSTRING(a,Y.value,1) --Single character of @b at the Z.value index. NULL if either string is empty
, COALESCE(SUBSTRING(a,Y.value,1)+SUBSTRING(b,Z.value,1),'') --The concatenation of a character from @a and @b, empty string if either is NULL.
FROM(VALUES(@a,@b)) X(a,b) --A single row table with each input string as its own column
JOIN GENERATE_SERIES(@n,LEN(@a+'x')-1) Y --GENERATE_SERIES generates values from start to stop (With default step of 1). LEN function ignores TRAILING whitespace, so we concat a charcater and substract 1 from length.
ON LEN(@a+'x')>1 --INNER JOIN ensures an empty result set if the length of the string is 0, otherwise a cartesian product.
JOIN GENERATE_SERIES(@n,LEN(@b+'x')-1) Z --GENERATE_SERIES generates values from start to stop (With default step of 1). LEN function ignores TRAILING whitespace, so we concat a charcater and substract 1 from length.
ON LEN(@b+'x')>1 --INNER JOIN ensures an empty result set if the length of the string is 0, otherwise a cartesian product.
RIGHT JOIN (SELECT 1 AS c) W ON 1=1 --RIGHT JOIN ensures we always have at least one row. As STRING_AGG on an empty result set will result in NULL not an empty string.
ORDER BY Y.value+Z.value,Y.value -- The order with which the final concatentation should take place: sum of indicies, then index of first string.


Returns:

This will only work on SQL Sever 2022 or later (probably on Azure Database etc...) due to the compatibility of the new function, GENERATE_SERIES.

• Ahhh, could of -1 byte by using FULL JOIN instead of RIGHT. Commented Aug 9, 2023 at 3:49