Compute the convolution of two strings

Question

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

l4m2 · Accepted Answer · 2023-08-05 07:01:13Z

7

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!

answered Aug 5, 2023 at 7:01

l4m2

28.5k2 gold badges25 silver badges103 bronze badges

Add a comment |

RubenVerg · Accepted Answer · 2023-08-05 09:00:33Z

6

APL (NARS2000), 7 glyphs

,/⍞,⍡,⍞

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

edited Aug 5, 2023 at 9:00

answered Aug 5, 2023 at 8:34

RubenVerg

9544 silver badges17 bronze badges

Add a comment |

hyperneutrino · Accepted Answer · 2023-08-05 19:17:17Z

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:

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

@JonathanAllan huh, that's an interesting way to do it, thanks — hyperneutrino, Commented Aug 5, 2023 at 19:06

Jonah · Accepted Answer · 2023-08-05 08:28:43Z

4

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

edited Aug 5, 2023 at 8:28

answered Aug 5, 2023 at 8:14

Jonah

33.8k4 gold badges40 silver badges94 bronze badges

Add a comment |

RubenVerg · Accepted Answer · 2023-08-05 08:57:03Z

4

APL (dzaima\APL), 7 glyphs

∊⊂⍁⍤∘.,

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

answered Aug 5, 2023 at 8:57

RubenVerg

9544 silver badges17 bronze badges

Add a comment |

138 Aspen · Accepted Answer · 2023-08-05 09:07:22Z

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

matteo_c · Accepted Answer · 2023-08-07 00:08:31Z

3

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!

edited Aug 7, 2023 at 0:08

answered Aug 5, 2023 at 11:00

matteo_c

6,95015 silver badges28 bronze badges

\$\begingroup\$ You can do (map snd=<<) for concatMap(map snd) \$\endgroup\$
– xnor
Commented Aug 6, 2023 at 2:16
1

\$\begingroup\$ I think you need the parens or it won't parse \$\endgroup\$
– xnor
Commented Aug 6, 2023 at 19:35

Add a comment |

doug · Accepted Answer · 2023-08-05 09:12:12Z

2

K (ngn/k), 30 bytes

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

Try it online!

answered Aug 5, 2023 at 9:12

doug

1,3803 silver badges9 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2023-08-05 18:09:37Z

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

loopy walt · Accepted Answer · 2023-08-06 16:25:15Z

2

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!

answered Aug 6, 2023 at 16:25

loopy walt

16.8k2 gold badges11 silver badges69 bronze badges

Add a comment |

DLosc · Accepted Answer · 2024-04-04 00:01:26Z

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)

Neil · Accepted Answer · 2023-08-05 12:01:34Z

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

Neil · Accepted Answer · 2023-08-05 12:19:13Z

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.

Ajax1234 · Accepted Answer · 2023-08-05 15:58:32Z

1

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!

answered Aug 5, 2023 at 15:58

Ajax1234

7,7111 gold badge15 silver badges28 bronze badges

1

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

Add a comment |

Value Ink · Accepted Answer · 2023-08-05 21:28:07Z

1

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!

answered Aug 5, 2023 at 21:28

Value Ink

12.6k1 gold badge17 silver badges42 bronze badges

Add a comment |

Ruud Helderman · Accepted Answer · 2023-08-07 06:42:33Z

1

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.

edited Aug 7, 2023 at 6:42

answered Aug 6, 2023 at 19:26

Ruud Helderman

6213 silver badges9 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2023-08-08 07:27:29Z

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)

DanielOnMSE · Accepted Answer · 2023-08-09 02:06:20Z

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.

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

Stack Exchange Network

Compute the convolution of two strings

Examples:

18 Answers 18

JavaScript (Node.js), 62 bytes

APL (NARS2000), 7 glyphs

Jelly, 10 bytes

Explanation

Step-by-step

Credits

J, ^{17 14 12} 10 bytes

APL (dzaima\APL), 7 glyphs

Scala, 118 bytes

Haskell, 72 66 bytes

K (ngn/k), 30 bytes

Jelly, 8 bytes

How?

Python, 78 bytes

Pip, 22 bytes

Explanation

Charcoal, 17 bytes

Retina, 47 bytes

Python3, 121 bytes:

Ruby, 74 bytes

C, 123 121 bytes

05AB1E, 14 bytes

T-SQL, 323 bytes

Your Answer

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

Hot Network Questions

Compute the convolution of two strings

Examples:

18 Answers 18

JavaScript (Node.js), 62 bytes

APL (NARS2000), 7 glyphs

Jelly, 10 bytes

Explanation

Step-by-step

Credits

J, 17 14 12 10 bytes

APL (dzaima\APL), 7 glyphs

Scala, 118 bytes

Haskell, 72 66 bytes

K (ngn/k), 30 bytes

Jelly, 8 bytes

How?

Python, 78 bytes

Pip, 22 bytes

Explanation

Charcoal, 17 bytes

Retina, 47 bytes

Python3, 121 bytes:

Ruby, 74 bytes

C, 123 121 bytes

05AB1E, 14 bytes

T-SQL, 323 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

J, ^{17 14 12} 10 bytes

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