14
\$\begingroup\$

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
\$\endgroup\$
0

12 Answers 12

13
\$\begingroup\$

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.

\$\endgroup\$
14
  • 2
    \$\begingroup\$ lower can be 𝓵𝓸𝔀𝓮𝓻 and exec can be 𝓮𝔁𝓮𝓬 :) \$\endgroup\$ Oct 19, 2022 at 19:40
  • 3
    \$\begingroup\$ I assume the answer should be 8. If you use .count it won't check for overlapping occurrences. \$\endgroup\$ Oct 19, 2022 at 23:34
  • 2
    \$\begingroup\$ I think it's fixed (and the score is now zero). \$\endgroup\$ Oct 20, 2022 at 0:31
  • 4
    \$\begingroup\$ @Seb See PEP-3131. \$\endgroup\$
    – RootTwo
    Oct 20, 2022 at 14:31
  • 1
    \$\begingroup\$ @Seb You can also see this trick and more on our tips for restricted source in Python. It's got a bunch of weird exploits you can use for challenges like this. \$\endgroup\$
    – Wheat Wizard
    Oct 21, 2022 at 3:26
7
\$\begingroup\$

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.

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

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

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
\$\endgroup\$
4
  • \$\begingroup\$ Did not expect a Java answer with score 0! \$\endgroup\$
    – Fatalize
    Oct 20, 2022 at 7:27
  • \$\begingroup\$ @Fatalize Luckily Java has the unicode escaping, otherwise it would never be possible. ;) \$\endgroup\$ Oct 20, 2022 at 7:31
  • 1
    \$\begingroup\$ Compare length rather than double include \$\endgroup\$
    – l4m2
    Jan 2 at 17:35
  • \$\begingroup\$ @l4m2 Thanks. :) \$\endgroup\$ Jan 2 at 20:07
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Why are there two operators which do the Cartesian product? Is there a reason for it? \$\endgroup\$ Oct 19, 2022 at 13:22
  • \$\begingroup\$ So you have 2 built-ins for cartesian product? ಠ_ಠ \$\endgroup\$
    – Fatalize
    Oct 19, 2022 at 13:22
  • \$\begingroup\$ clearly lyxal knew this was going to be a challenge while designing vyxal \$\endgroup\$ Oct 19, 2022 at 13:24
  • \$\begingroup\$ Π is cartesian product of list of lists, while is cartesian product of two items on the stack \$\endgroup\$
    – lyxal
    Oct 19, 2022 at 13:26
  • 1
    \$\begingroup\$ Even worse though, , ʁ, and all do the exact same thing. github.com/Vyxal/Vyxal/discussions/820 \$\endgroup\$
    – naffetS
    Oct 20, 2022 at 0:20
3
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ This is exactly the kind of answer I was hoping for: standard languages with which lowering your score is not obvious. \$\endgroup\$
    – Fatalize
    Oct 19, 2022 at 13:27
  • 1
    \$\begingroup\$ g("aa", "aaa") and g("aaa", "aa") return different values, which seems wrong. \$\endgroup\$
    – Neil
    Oct 19, 2022 at 17:49
  • \$\begingroup\$ Hmm not sure what the correct result in that case would be. Maybe @Fatalize could clarify \$\endgroup\$
    – mousetail
    Oct 19, 2022 at 18:43
  • \$\begingroup\$ @mousetail You should get the same value regardless of the order. The example algorithm I give in the challenge description illustrates why. \$\endgroup\$
    – Fatalize
    Oct 20, 2022 at 7:21
  • \$\begingroup\$ Yea but which one is correct in this case? \$\endgroup\$
    – mousetail
    Oct 20, 2022 at 7:36
3
\$\begingroup\$

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

Charcoal, 56 bytes, score = 0

First program, 31 bytes:

IΣEθΣE⊕κ№EηΦη№…ξ⁻⊕κ⁻λξρΦθ№…λ⊕κξ

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
  E                             Map over characters
       κ                        Current index
      ⊕                         Incremented
     E                          Map over implicit range
          η                     Second input
         E                      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
I                               Cast to string
                                Implicitly print

Second program, 25 bytes:

SζSε⭆ψL⭆ζ⭆⁺¹μ⭆⌕Aε✂ζν⁺¹μ¹ψ

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.

Sζ                          Rename first input
  Sε                        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
              ⌕A            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
      L                     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.
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ It's not much, but w+1 can be 1+w for -3 and q+=len(...) can be q=len(...)+q for -11 in score. \$\endgroup\$ Oct 21, 2022 at 15:12
  • \$\begingroup\$ I think adding some extraneous spaces between tokens to break up longer strings can help you. In the first program adding a space before range and before the first len should both help. \$\endgroup\$
    – Wheat Wizard
    Oct 21, 2022 at 15:41
  • \$\begingroup\$ You can also definitely choose better variable names. Changing a and c to v and z helps \$\endgroup\$
    – Wheat Wizard
    Oct 21, 2022 at 15:46
  • \$\begingroup\$ I've made some changes, and verified that they output the same score \$\endgroup\$
    – bigyihsuan
    Oct 21, 2022 at 17:06
  • \$\begingroup\$ Can still be improved a bit \$\endgroup\$
    – Wheat Wizard
    Oct 21, 2022 at 19:51
1
\$\begingroup\$

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

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!

\$\endgroup\$

Your Answer

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

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