Count the shared substrings with 2 programs

Question

Write 2 programs in the same language which count the number of shared subsequences of consecutive elements from 2 given sequences.

For example, given "test" and "enter", there are 5 shared subsequences of consecutive elements:

t
t
e
e
te

One possible algorithm consists in counting, for each subsequence of consecutive elements of one sequence, the number of times it appears in the list of subsequences of the other one.

In our previous example, for "test", "t" appears once in "enter", "e" appears twice, "t" appears once, and "te" appears once; therefore we get 5 as output. (it does not matter if you pick "test" or "enter" as the "first" sequence).

Scoring

Your score will be the result of one of your programs, when given your 2 programs as input. That is, the number of shared subsequences of consecutive elements between both programs.

Lowest score wins. In case of a tie, the lowest byte count of the sum of your 2 programs wins.

Inputs

Both sequences will have at least 1 element.

The two input sequences can either be strings, or lists of chars, or lists of numbers, or any other fitting format for your language.

For example, if you take lists of numbers as inputs, your will transform your programs as lists of char codes according to your language’s code page.

Test cases

a, b                  -> 0
test, enter           -> 5
hello, hello          -> 17
yes, yeyeyeah         -> 9

Answer 1

Python, score 0, 520 bytes

-25 from @Grain Ghost
-78 from @Jonathan Allan
-61 from @RootTwo
-4 from @Grain Ghost

class l:__class_getitem__=len
class r:__class_getitem__=range
class s:__class_getitem__=sum
f=lambda a,b:s[[b[g:h]==a[i:j]for j in r[l[a]+True]for i in r[j]for h in r[l[b]+True]for g in r[h]]]

𝓮𝔁𝓮𝓬("\x67\x3D\x6C\x61\x6D\x62\x64\x61\x20\x61\x2C\x62\x3A\x61\x3E\x27\x27\x61\x6E\x64\x20\x73\x75\x6D\x28\x62\x2E\x63\x6F\x75\x6E\x74\x28\x61\x5B\x3A\x70\x5B\x30\x5D\x2B\x31\x5D\x29\x66\x6F\x72\x20\x70\x20\x69\x6E\x20\x65\x6E\x75\x6D\x65\x72\x61\x74\x65\x28\x61\x29\x29\x2B\x66\x28\x61\x5B\x31\x3A\x5D\x2C\x62\x29")

Attempt This Online!

It was a team effort.

Answer 2

05AB1E, score 0 (15 bytes)

Program 1 (3 bytes):

΢O

Try it online or verify all test cases.

Program 2 (12 bytes):

•K&}Í•3ôçJ.V

Try it online or verify all test cases.

The second program is pretty unimpressive, so I'll see if I can find a more original shorter approach.

Explanation:

Π       # Get all substrings of the first (implicit) input-string
 ¢       # Count how many times each substring occurs in the second (implicit) input-string
  O      # Sum those counts together
         # (after which the result is output implicitly)

•K&}Í•   # Push compressed integer 388162079
 3ô      # Split it into parts of size 3: [338,162,079]
   ç     # Convert each to a character with this codepoint: ["Œ","¢","O"]
    J    # Join it to a string: "΢O"
     .V  # Evaluate and execute as 05AB1E code (basically the program above)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why •K&}Í• is 388162079.

Answer 3

Jelly, 14 bytes, score 0

6 bytes

ẆċⱮẆ}S

Try it online!

8 bytes

⁼þŒD§RF§

Try it online!

How?

ẆċⱮẆ}S - Link a, b:      e.g.  "tent", "spent"
Ẇ      - sublists (a)          ["t","e","n","t","te","en","nt","ten","ent","tent"]
   Ẇ}  - sublists (b)          ["s","p","e","n","t","sp","pe","en","nt","spe","pen","ent","spen","pent","spent"]
  Ɱ    - map with:
 ċ     -   (left) count occurrences (of right)
                               [0,0,1,1,2,0,0,1,1,0,0,1,0,0,0]
     S - sum                   7

⁼þŒD§RF§ - Link a, b:    e.g.  'tent', 'spent'
 þ       - table of:
⁼        -   equals?           [[0,0,0,0],[0,0,0,0],[0,1,0,0],[0,0,1,0],[1,0,0,1]]
  ŒD     - diagonals           [[0,0,0,0],[0,0,0],[0,0],[0],[1],[0,0],[0,0,0],[0,1,1,1]]
    §    - sums                [0,0,0,0,1,0,0,3]
     R   - range               [[],[],[],[],[1],[],[],[1,2,3]]
      F  - flatten             [1,1,2,3]
       § - sums                7

Answer 4

Java 8, score 0 (1287 1263 1248 1243 bytes)

Function 1 (261 237 234 229 bytes):

a->b->{int l=a.length,z=l-l,r=z,i=z,j,L=b.length,I,J,x;for(String s,t;i<l;i++)for(j=i;j++<l;)for(I=z;I<L;I++)for(J=I;J++<L;r+=s.contains(t)&j-i==J-I?1:0){for(s=t="",x=i;x<j;)s+=a[x++];for(x=I;x<J;)t+=b[x++];}System.err.print(r);}

Inputs as character-arrays. Outputs the result to STDERR.

-3 bytes thanks to @ceilingcat
-5 bytes thanks to @l4m2

Try it online.

Function 2 (1026 1014 bytes):

\u0061\u002D\u003E\u0062\u002D\u003E\u007B\u0069\u006E\u0074\u0020\u0072\u003D\u0030\u002C\u006C\u003D\u0061\u002E\u006C\u0065\u006E\u0067\u0074\u0068\u0028\u0029\u002C\u0069\u003D\u0030\u002C\u006A\u002C\u004C\u003D\u0062\u002E\u006C\u0065\u006E\u0067\u0074\u0068\u0028\u0029\u002C\u0049\u002C\u004A\u003B\u0066\u006F\u0072\u0028\u003B\u0069\u003C\u006C\u003B\u0069\u002B\u002B\u0029\u0066\u006F\u0072\u0028\u006A\u003D\u0069\u003B\u006A\u002B\u002B\u003C\u006C\u003B\u0029\u0066\u006F\u0072\u0028\u0049\u003D\u0030\u003B\u0049\u003C\u004C\u003B\u0049\u002B\u002B\u0029\u0066\u006F\u0072\u0028\u004A\u003D\u0049\u003B\u004A\u002B\u002B\u003C\u004C\u003B\u0029\u0069\u0066\u0028\u0061\u002E\u0073\u0075\u0062\u0073\u0074\u0072\u0069\u006E\u0067\u0028\u0069\u002C\u006A\u0029\u002E\u0065\u0071\u0075\u0061\u006C\u0073\u0028\u0062\u002E\u0073\u0075\u0062\u0073\u0074\u0072\u0069\u006E\u0067\u0028\u0049\u002C\u004A\u0029\u0029\u0029\u0072\u002B\u002B\u003B\u0072\u0065\u0074\u0075\u0072\u006E\u0020\u0072\u003B\u007D

Inputs as Strings. Returns the integer-result.

-12 bytes thanks to @ceilingcat.

Try it online.

Explanation:

The golfed function is this:

a->b->{int r=0,l=a.length(),i=0,j,L=b.length(),I,J;for(;i<l;i++)for(j=i;j++<l;)for(I=0;I<L;I++)for(J=I;J++<L;)if(a.substring(i,j).equals(b.substring(I,J)))r++;return r;}

This golfed version is also the direct translation of the second function above using a simple converter.

In order to use the unicode escaped Java function, we'll have to prevent using the characters \u0123456789ABCDEF in the other function. We're currently using three 0 and four u:

• To get rid of the three 0, I've added an additional z=l-l integer to reuse;
• To get rid of the two u in substring, I create the substrings manually using ,x ... String s,t; ... for(s=t="",x=i;x<j;)s+=a.split("")[x++];for(x=I;x<J;)t+=b.split("")[x++]; (minor note: I couldn't use .charAt(x++) instead of .split("")[x++] here, since it contains an A);
• To get rid of the u in equals, I've used s.contains(t)&j-i==J-I;
• And to get rid of the u in return, I've printed to STDERR with System.err.print(r);.

After that, both .split("") were removed and both .length() were golfed to .length by taking the arguments as character-arrays instead of Strings.

Explanation of the golfed base function:

a->b->{                       // Method with two string arguments
  int r=0,                    //  Result-count integer, starting at 0
      l=a.length(),           //  Length of the first input-String
      i=0,j,                  //  Index-integers for the substrings of the first input
      L=b.length(),           //  Length of the second input-String
      I,J;                    //  Index-integers for the substrings of the second input
  for(;i<l;i++)               //  Loop `i` in the range [0,l):
    for(j=i;j++<l;)           //   Inner loop `j` in the range (i,l]:
      for(I=0;I<L;I++)        //    Inner loop `I` in the range [0,L):
        for(J=I;J++<L;)       //     Inner loop `J` in the range (J,L]:
          if(a.substring(i,j) //      If the [i,j)-substring of the first input
             .equals(b.substring(I,J)))
                              //      equals the [I,J)-substring of the second:
            r++;              //       Increase the result-count by 1
  return r;}                  //  After the loops, return the result

Answer 5

Stax, score 0 (23 bytes)

12 bytes

:e{n:es|#m|+
:e              all substrings of b
  {      m      map over them:
   n:e            all substrings of a
      s|#         count occurrences
          |+    sum

Run and debug it at staxlang.xyz!

11 bytes

ü╪ ·§╢┌Æ=gy

Run and debug it at staxlang.xyz!

The second is the same as the first, but with a $ (number to string) appended before packing to get rid of a pesky m that was trying to give me a positive score.

Answer 6

Vyxal, 21 bytes, Score = 0

Program 1 (14 bytes):

wJƛfÞS;Π'÷⁼;żt

Try it Online!

Program 2 (7 bytes):

ǎ$ǎẊ~≈L

Try it Online!

I'm very good at golfing language design as you can tell by the fact that there's multiple built-ins to do the same thing.

Both programs take 2 strings.

Explained

wJƛfÞS;Π'÷⁼;żt
wJ             # Put the two inputs into a list
  ƛfÞS;        # Get the sublists of each - returns a list of lists
       Π       # Cartesian product of the two lists
        '÷⁼;   # Keep only those where all the items are equal
            żt # Length of list

ǎ$ǎẊ~≈L
ǎ       # Get the substrings of the first input
 $ǎ     # and of the second input - leaves two strings on the stack
   Ẋ    # Cartesian product of the two lists
    ~≈  # Keep only those where all the items are equal
      L # Length of list

Answer 7

Python, 542 533 479

A, 89 bytes

def g(a,b):h=range;return sum(b.count(a[c:][:1+d])for c in h(len(a))for d in h(len(a)-c))

B, 80 bytes

lambda i,l:sum(l.count(i[j:k+1]) for j in range(len(i)) for k in range(j,len(i)))

Not really sure how to optimize this. Will play a bit more. Submitting the same program twice would give me a score of 3,160 bytes.

Answer 8

Haskell, 67, 58, 57 score

a((f,j):q)|(9>8)>(f>j)&&(9>8)>(j>f)=a(q)+1
a(f)=0
f!h=scanr(+)0(((a.).zip)<$>scanr(:)[]f<*>scanr(:)[]h)!!0

x%y|t:u<-x,w:e<-y,t==w=1:u%e;_%_=mempty;k t|_:m<-t=t:k m;k _=mempty;t?u= sum$do{x<-k t;e<-k u;x%e}

Attempt This Online!

I really wanted to get this under 64. But it just seems like it is not going to happen. Got it under 64!

The characters that cause overlap are:

,|1=p$<s:

Answer 9

Charcoal, 56 bytes, score = 0

First program, 31 bytes:

ＩΣＥθΣＥ⊕κ№ＥηΦη№…ξ⁻⊕κ⁻λξρΦθ№…λ⊕κξ

Try it online! Link is to verbose version of code. Explanation: Generates all substrings of the first input in order of last character index followed by first character index, for each substring extracts all substrings of that length from the second input, counts the number of matches, then takes the grand total.

   θ                            First input
  Ｅ                             Map over characters
       κ                        Current index
      ⊕                         Incremented
     Ｅ                          Map over implicit range
          η                     Second input
         Ｅ                      Map over characters
            η                   Second input
           Φ                    Filtered where
              …                 Range from
               ξ                Inner index to
                     ξ          Inner index
                   ⁻            Subtracted from
                    λ           Outer value
                ⁻               Subtracted from
                  κ             Outermost index
                 ⊕              Incremented
             №                  Contains
                      ρ         Innermost index
        №                       Count matches of
                        θ       First input
                       Φ        Filtered where
                          …     Range from
                           λ    Inner value to
                             κ  Outer index
                            ⊕   Incremented
                         №      Contains
                              ξ Innermost index
    Σ                           Take the sum
 Σ                              Take the sum
Ｉ                               Cast to string
                                Implicitly print

Second program, 25 bytes:

ＳζＳε⭆ψＬ⭆ζ⭆⁺¹μ⭆⌕Ａε✂ζν⁺¹μ¹ψ

Try it online! Link is to verbose version of code. Explanation: Generates all substrings of the first input as before, then maps the indices of overlapping matches in the second input to null bytes, concatenates everything and takes the total length.

Ｓζ                          Rename first input
  Ｓε                        Rename second input
     ψ                      Null byte
    ⭆                       Map over characters and join
        ζ                   First input
       ⭆                    Map over characters and join
            μ               Current index
          ⁺                 Plus
           ¹                Literal integer `1`
         ⭆                  Map over implicit range and join
                ε           Second input
              ⌕Ａ            Find all matching indices of
                  ζ         First input
                 ✂    ¹     Sliced from
                   ν        Inner value to
                      μ     Outer index
                    ⁺       Plus
                     ¹      Literal integer `1`
             ⭆              Map over indices and join
                        ψ   Null byte
      Ｌ                     Take the length
                            Implicitly print

Using StringMap to stringify the count has the added bonus of renaming the loop variables thereby reducing the number of shared substrings. Other techniques I used:

• The second program uses StringMap instead of Map. I can do this by representing integers in unary as the length of the resulting string.
• The second program uses Plus(1, k) instead of Incremented(k), as it needs a 1 for Slice() anyway.
• The first program uses Minus(Incremented(k), Minus(l, x)) to avoid having to add k and x (because the second program is now using Plus).
• The first program uses Filter to extract substrings to avoid using Slice.

Answer 10

Go, 265 bytes, score 772

thanks golang for not giving you that many ways of doing things (reasonably)

A, 113 bytes

import."strings"
func f(v,b string)(z int){for i:= range v{for j:=i+1;j<= len(v);j++{z+=Count(b,v[i:j])}}
return}

Attempt This Online!

B, 152 bytes

import."regexp"
func g(x,y[]byte)(q int){for w:=range x{for p:=1+w;p<=len(x);p++{q=len(MustCompile(QuoteMeta(string(x[w:p]))).FindAll(y,-1))+q}}
return}

Attempt This Online!

Changelog

• A/B: Some changes (@Kevin Cruijssen)
• (footers): Make sure they use the same inputs (@Grain Ghost)

Answer 11

Brachylog, Score: 0 (15 + 38 = 53 bytes)

tT⁰&hsᶠ{∋~sT⁰}ᶜ

Try it online!

↰₁ᵐẋ=ˢl
↰₂ᵇbᵐ²
l⟦₁;?zZ∧[A,.,C]cZ∧.l>0∧

Try it online!

Program 1 with programs as input.

Program 2 with programs as input

Explanation

Brachylog doesn't actually have that many built-ins; in addition, certain control flow symbols are used all the time. This makes it harder to write 2 programs that don't share symbols, which means we have to do some plumbing for the second program.

The main difficulty is that the direct way to generate substrings of consecutive elements is s, and getting substrings with another method that also doesn't generate duplicates (but works for strings with duplicate symbols!) is not that obvious.

Program 1

This is a fairly straightforward declarative implementation of the problem:

tT⁰                Call the second input T⁰
   &hsᶠ            Find all subsequences of consecutive elements of the first input
       {     }ᶜ    Count:
        ∋~sT⁰        The number of such subsequences which are also subsequences of T⁰

Program 2

We use a more imperative approach, computing all subsequences of consecutive elements and checking how many equal couples we get after cartesian product.

We can't use brackets to declare predicates, so we have to declare them using linebreaks. Predicate 3 computes the subsequences. Predicate 2 cleans up some plumbing set up in Predicate 3 to avoid duplicate subsequences.

We can't use ᶠ - findall to generate stuff, so we use ᵇ - bagof which does the same in cases where we're not generating unbounded variables.

                          - Predicate 0
↰₁ᵐ                       Map predicate 1 on each of the 2 inputs
   ẋ                      Cartesian product
    =ˢ                    Select the couples of equal elements
      l                   Output the length of this list


                          - Predicate 1
↰₂ᵇ                       Find all outputs of Predicate 2
   bᵐ²                    Remove the indices


                          - Predicate 2
l⟦₁;?zZ                   Zip the string with indices [1,...,N]; call it Z
       ∧[A,.,C]cZ∧       [A, Output, C] concatenates into Z
                          We avoid duplicate situations with the zipped indices
                   .l>0∧  This Output has length > 0
                          This avoids all cases where the output is the empty string

Answer 12

JavaScript (Node.js), score 0, 322 bytes

JavaScript (Node.js), 129 bytes

x=>y=>[g=_=>j--?[h=_=>j%z-v-z?x[j%z-v]==y[j/z-v|0]?--v|--Z|h``:0:0][v=0][h``]|g``:-Z][Z=0][j=y[l='l\x65\x6Eg\x74h']*[z=x[l]]]|g``

Try it online!

JavaScript (Node.js), 193 bytes

function(A,B){return A.reduce(function(M,K,I){return B.reduce(function(M,L,N){return A.reduce(function(M,K,J){return(I<++J)*Array(A.slice(I,J)+1).includes(B.slice(N,J+~I+1+N)+1)+M},M)},M)},!1)}

Try it online!