20
\$\begingroup\$

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.

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 the shortest solution (per language) wins.

\$\endgroup\$

18 Answers 18

7
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

APL (NARS2000), 7 glyphs

,/⍞,⍡,⍞
  • ,/ Concatenate
  • ,⍡, the convolution by concatenation and concatenation
  • of a string input
  • and another string input
\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ +þŒdṙL{UFṚ for ten. \$\endgroup\$ Aug 5, 2023 at 17:24
  • \$\begingroup\$ @JonathanAllan huh, that's an interesting way to do it, thanks \$\endgroup\$
    – hyper-neutrino
    Aug 5, 2023 at 19:06
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

APL (dzaima\APL), 7 glyphs

∊⊂⍁⍤∘.,
  • flatten into a list
  • ⊂⍁ every diagonal
  • ∘., of the table of all pairs of the input
\$\endgroup\$
3
\$\begingroup\$

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
  }
}
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ You can do (map snd=<<) for concatMap(map snd) \$\endgroup\$
    – xnor
    Aug 6, 2023 at 2:16
  • 1
    \$\begingroup\$ I think you need the parens or it won't parse \$\endgroup\$
    – xnor
    Aug 6, 2023 at 19:35
2
\$\begingroup\$

K (ngn/k), 30 bytes

{,/+l@'d\<,/+\:/!'d:#'l:(x;y)}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Couldn't you use d.values() instead of d[i]for i in d? \$\endgroup\$
    – xigoi
    Aug 5, 2023 at 19:23
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 14 bytes

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

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

Try it online or verify all test cases.

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)
\$\endgroup\$
1
\$\begingroup\$

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:

enter image description here

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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