[Question]
  [
*While implementing polynomial multiplication in [Itr](https://github.com/bsoelch/OneChar.js/blob/main/ItrLang.md) 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`.
Your task is to implement this operation:   
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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") the shortest solution (per language) wins.
  
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 62 bytes
```
a=>b=>a.map((c,i)=>b.map(d=>L[i]=[L[i++]]+c+d),L=[])&&L.join``
```
[Try it online!](https://tio.run/##JcexCsMgEADQf8kQPEzvB8o5d3DvIAexaorBeiEp/X0j6fLgrf7nj7Dn7XurElNbqHkyLzIeP35TKkwZ@q9EMtZlJtfVmlkHHWGy5BjG0eIquc5zC1IPKQmLvNWiHCIOj1SKDAz/PWUvsQ/u7QQ "JavaScript (Node.js) – Try It Online")
[Answer]
# APL (NARS2000), 7 glyphs
```
,/⍞,⍡,⍞
```
* `,/` Concatenate
* `,⍡,` the convolution by concatenation and concatenation
* `⍞` of a string input
* `⍞` and another string input
[Answer]
# [Jelly](https://github.com/DennisMitchell/jellylanguage), 10 bytes
```
+þŒdṙL{UFṚ
```
[Try It Online!](https://jht.hyper-neutrino.xyz/tio#WyIiLCIrw77FkmThuZlMe1VG4bmaIiwiIiwiIixbIistIiwiXCIxMjM0NVwiIl1d)
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.
[Answer]
# [J](http://jsoftware.com/), 17 14 12 10 bytes
```
[:;]/.@{@;
```
[Try it online!](https://tio.run/##dY29CsIwEIB3n@JwiZIm/V@iQlGQDOLgkkGcTETl4KTt5sPHa6ujHPfDx3d3zzjX4gYbAwISyMBwKg2702Efz2Z1SXXzblZxOTtuNTA4m3WzSNJlqpN5ls7C9U4gbEAkATcQjlr04osFKDNU5j9knaXgbBsIncXQ4tA9r/NELnjkiQi5D4cIyU9H/nzo4AUID@hh0roXPvpR4/g6MpeFymWpClmpUtaqUvVkSzWqeVFWTOIH "J – Try It Online")
J's `/.` builtin is tailor made for this...
* `{@;` Create a table of all pairs
* `]/.@` Get each diagonal
* `[:;` Flatten and unbox
[Answer]
# APL (dzaima\APL), 7 glyphs
```
∊⊂⍁⍤∘.,
```
* `∊` flatten into a list
* `⊂⍁` every diagonal
* `∘.,` of the table of all pairs of the input
[Answer]
# [Scala](http://www.scala-lang.org/), 118 bytes
Golfed verson. [Try it online!](https://tio.run/##TZBRT4MwFIXf@RUnhCxtBoub@rKNJXMx@qBPxvhgfEAoW7GjjNYlG@G3Y6FgaNL09jvn9t5bFUciauR3xmKN14jnqBwgYSmO5kKicq@W2JZldPl80yXP9190ifeca4SdEzhHApoprQx54UqTjgLEdRFs4D4eC31xqf@Pn5kQ0mofshTJWNvJhFnpSYp0rMwXt1bYPuzGXBWCa6tgzKeBhSbv7t6lHadOd3TdzlJZsig@9FMAcaQYiJr7UAuKcNNjoDBja5ET5Zrlqbmp46mFfd2rYpmfpTizIbNuXbZc7bTbaT9ocC0Jsd/o24OGmz5A2JDCPxlQEdNadV0HN/jNNRcoZoLle32YnvpgxVtRS1xXWXgN@Iqn4OvBNplk68FZXzgTCZRptCCc1l51Ipnpkc6OP7Zw3dTNHw)
```
(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!](https://tio.run/##XVDRasIwFH33Kw5FJGFW1m57ERWcjO1hexpjD2MPWZtqXNpIbxRE@u1d2rRSVii5Oefck3suJUKLujY/e5lYvAlV4DICUpkhdxcmyi3NsS5Lcf56t6Uqtt98jo9CWSxbJXASGlaSJYe8KrKsRQEWBAhXCJ7ygz0HfHqFX6TWxnOfptTpkNuYVHrq2ehsyETxnSfWj5shTgetrGcwxG9CD7q@@4eAtzgftUc77SwzpRTJrksBJIIkGEVTUMyxXHUwcHCxrS4YBe4bU@TeGVPs3ceXxBQno0@y76walX@uGjV/t86Bbg6/ykbf17wvrntlbsDrcHTMsQhxi2NhlQZFMy2Lrd3hxnl0dSdVXmhN09Rhe@faWIRQvSprhAOjycSpFv/cKpyV1CnIBaWIKV65M2Z7l5LP8l8/cZuyGtX1Hw)
```
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
  }
}
```
[Answer]
# [Haskell](https://www.haskell.org), ~~72~~ 66 bytes
*-6 bytes thanks to [@xnor](https://codegolf.stackexchange.com/users/20260/xnor)*
```
import Data.List
f=(map snd=<<).sortOn(sum.map fst).mapM(zip[0..])
```
[Attempt This Online!](https://ato.pxeger.com/run?1=NY4xDsIwDEX3nsKKGFoJIkaGZkEMGUCMGaoOkZKICDeuknTpVVi6IM7EbUgFTP_J3_7fj9dNp7tFXJbnlN3u8D76YaSY4aSz5mefcuVEPegRUjCibRueinsNdZoGvo5dys0Kl3r2Y7fnvG9-SXoGAQ46Jks-sS0wRREN66tB-1C8MfqQYQNlTwCTSpJVMlpCJdFGXNWU00KkrMFCRFh0TSEkw75F_9c_)
[Attempt This Online!](https://ato.pxeger.com/run?1=NY6xCsIwEIb3PsURHFrQ4OjQgINDBsUxQ-kQSILBa64k6dJXcekiPpNvY4o6_R_33_3_PV43ne4WcVmeU3a7w_voh5FihpPOmp99ypUTgx4hBSPalqfiXUOdpoGvU5dys8Klnv3Y7Tnvm1-OnkGAg47Jkk5sC0xRRMP6atA-FG-MPmTYQNkTwKSSZJWMllBJtBFXNeW0EClrsBARFl1TCMmwb9H_8Q8)
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), 30 bytes
```
{,/+l@'d\<,/+\:/!'d:#'l:(x;y)}
```
[Try it online!](https://ngn.codeberg.page/k#eJw1j1FrgzAQx9/zKWKERUmdi7YvdmzVMLSvfXEDYStLbIVbT1S2lbF+9l2RBcL9L/x+F67Nfhaxgo20zT2FJos9aTNfQhZ8r8/hL2MxE4KLp49+OgsePXDq/k8cc3d95+M0dKcDE5UDQKJrHMDOdFVX6OpqcAh1BW6Aa7XEUcLaWaCECFSvDgJawYRB62hMidDOU0xpEEtDii1NSzi6ElsLDm3rwLXk6CQlJS/MbOhcF0muTVKkeWLSIjXEjD10E1F8Zkbec+Adn6inXU44OT4d6Q77Dmgh/nXsJjf2+3fHhIpIo0+Wq1lWWiWRVmmUqGWUqlW0jFaCNSx4Xr+sd2EWJJ7nZ6GvRCNEI7cb/XpzCbaPCylF3DQilJ6/ze6yt/1w+OSa7S7trVRXO2R/xZ5tVA==)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Ẉp/SÞị"€
```
A full program that accepts a pair of lists of characters and prints the result.
**[Try it online!](https://tio.run/##y0rNyan8///hro4C/eDD8x7u7lZ61LTm////Stq6SjoKSoZGxiamSgA "Jelly – Try It Online")** Or see the [test-suite](https://tio.run/##y0rNyan8///hro4C/eDD8x7u7lZ61LTm/@F2IBn5/390tJKSjoKSa25BSaVSrA6XQrSSB1BHPkgwPL8oJwUq6JyfkgoSc8/PSYMKGRoZg0QcnZyhAsUFOZklICEFqIC2LogHVGdiChKJBQA "Jelly – Try It Online").
### 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
```
[Answer]
# [Python](https://www.python.org), 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!](https://ato.pxeger.com/run?1=m72soLIkIz9vweI025ilpSVpuhY3_dJscxJzk1ISFRJ1knQybQ2sgKy8FHV1vaz8zDyN4tJcjarMAg2gZHSmlZWuYaymjoampqZ2mkZidJKtbVK0Vaa2YaxVLEiztqEm1NTegqLMvBKNNA2ljNScnHwlHaXy_KKcFCVNTS64jLYuUNjQyNjEFEW4uCAnswQoo4Ai6pyfkgoUdM_PSUMRB4ql5haUVKIIOjo5u7i6QU0HykActWABhAYA)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 17 bytes
```
⭆⁺θη⭆θ⭆Φη⁼κ⁺μξ⁺λν
```
[Try it online!](https://tio.run/##S85ILErOT8z5/z@gKDOvRCO4BEil@yYWaATklBZrFOooZGjqKCBEC5E5bpk5JalFGhk6Cq6FpYk5xRrZOgpgbbk6ChWamppQXo6OQp4mCFj//@@cn5LK5Z6fk/ZftywHAA "Charcoal – 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
```
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 47 bytes
```
Lw$`(.).*¶.*(.)
$.`*¶$.>`*¶$1$2
O$`(¶+).+
$1
¶
```
[Try it online!](https://tio.run/##K0otycxLNPyvqhGcwPnfp1wlQUNPU0/r0DY9LSCDS0UvAchW0bMDU4YqRlz@QBWHtmlr6mlzqRhyHdrG9f8/p2tuQUkll0dqTk4@Z3h@UU4Kl3N@Siqne35OGpehkTGno5MzV3FBTmYJpwKXti4nUMjEFAA "Retina – 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.
[Answer]
# 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!](https://tio.run/##VcxLCsIwEIDhfU4xdNOExoIvEKELLUVv4EK6KCTR1JiEmEKLePaaVBC6G75/Zuzg70avd9aNY1Vw3T25azxHjAsQuKcD2SNgxfuDQBgHkjYgNVS4jz5RSx8/CqvsKrO2Llh@4x6HkaYpyZrsgcBx3zmdpnlrpMZhr57exUtGRuuk9ljgJKGQVE/rh4QQ9NczV8rEdDFOsVkqDeOxnIwSs7BcraMfjuWMX1ZJHwPMOFtECzebbfDxCw)
[Answer]
# [Ruby](https://www.ruby-lang.org/), 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!](https://ato.pxeger.com/run?1=TY1NCsIwGET33ymyEITaFvzFTQUtongBFzFIYlMbTE1II6JtT-KmoB7K29iigrt5D2bm9jAndqnucbB5nmzsjV8rb0Jd5jomp34mrty3IuVZXoiC_bPBh0B0tl0SYKfOxKVYEJfh2pCyBOO02-V3cXROhORoz20GiKIAtbb-LlGpBsRqavyPNYpx_U6AH6NPu3oNYZ5qe4Ell1LBWhkZQagiDgslY-j2-jCdhZBpKSwg6HiNGgw_7Tc)
[Answer]
# 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.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 14 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
€.ā`âΣ€θO}€€н˜
```
Input as a pair of strings; output as a list of characters.
[Try it online](https://tio.run/##yy9OTMpM/f//UdMavSONCYcXnVsMZJ7b4V8LpIDowt7Tc/7/j1bySM3JyVfSUQrPL8pJUYoFAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeX/R01r9I40JhxedG4xkHluh38tkAKiC3tPz/nv9ahhmdLh/Uo6/6OjlZR0lFxzC0oqlWJ1opU8UnNy8oEi4flFOSlgEef8lFSggHt@ThqYb2hkDOQ6OjmDecUFOZklQL4CmKetC2QCFZiYKsXGAgA).
**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)
```
[Answer]
# [**T-SQL**](https://learn.microsoft.com/en-us/sql/t-sql/language-reference?view=sql-server-ver16), 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:
[![enter image description here](https://i.stack.imgur.com/vcv6B.png)](https://i.stack.imgur.com/vcv6B.png)
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.
]