14
\$\begingroup\$

[Question inspired by Can you calculate the average Levenshtein distance exactly? . Thank you Anush. ]

The longest common substring between two strings is the longest substring which is common to both. Please note this is not the same as the longest common subsequence whose fastest algorithm takes quadratic time.

The challenge is to compute the average length of the longest common substring between two independent and uniformly random chosen binary strings of length n each. Your output must be exact but can be given in any easy to understand human readable form.

Examples for n = 1..12

  • 1/2
  • 9/8
  • 7/4
  • 295/128
  • 361/128
  • 6741/2048
  • 15217/4096
  • 8389/2048
  • 291431/65536
  • 2500643/524288
  • 2657159/524288
  • 22420789/4194304

Score

Your score is the highest value of 𝑛 you can reach. I will run your code on my Linux machine for 1 minute and then kill the job to get the score.

I will maintain a leaderboard that shows the best score for each language used in an answer.

Worked example

Following a request, here is the full set of distances for n = 3. I have not include strings B and A if A and B are already listed. This is because the distance function is symmetric.

000 000 3
000 001 2
000 010 1
000 011 1
000 100 2
000 101 1
000 110 1
000 111 0
001 001 3
001 010 2
001 011 2
001 100 2
001 101 2
001 110 1
001 111 1
010 010 3
010 011 2
010 100 2
010 101 2
010 110 2
010 111 1
011 011 3
011 100 1
011 101 2
011 110 2
011 111 2
100 100 3
100 101 2
100 110 2
100 111 1
101 101 3
101 110 2
101 111 1
110 110 3
110 111 2
111 111 3

Leaderboard

  • n = 22 in C++ by my pronoun is monicareinstate.
  • n = 18 in Rust by Plasma_000.
  • n = 14 in C by Mitchel Spector.
  • n = 11 in Python with pypy 3 by Alex.
| improve this question | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Do the fractions have to be reduced? \$\endgroup\$ – Adám Mar 12 at 16:37
  • 5
    \$\begingroup\$ @Adám It's a fastest-code question so surely this must be covered by a standard loop-hole. Your code should actually compute the answers it outputs. If you find a closed form formula that is of course OK to use. \$\endgroup\$ – fomin Mar 12 at 16:41
  • 2
    \$\begingroup\$ @S.S.Arne It is linear time to find the longest common substring between two strings \$\endgroup\$ – Anush Mar 13 at 18:03
  • 2
    \$\begingroup\$ @PeterCordes Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz \$\endgroup\$ – Anush Apr 3 at 9:30
  • 1
    \$\begingroup\$ @mypronounismonicareinstate But they were right in any case :) (We talked in a chat room.) \$\endgroup\$ – fomin Apr 3 at 16:03
9
\$\begingroup\$

C++, n = 21 (40s on an AMD Ryzen 5 2500U)

This used to be a fast brute force answer that got up to n=17. That is currently preserved in the revision history.

#include <cstring>
#include <omp.h>
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>

typedef unsigned uint;
typedef unsigned char byte;
const int threadnum = 8;
const int maxn = 22; //for 24 bytes total size of Row
struct Row; struct hasher { size_t operator ()(const Row& row) const; };
struct Row
{
    char max = 0;
    std::array<char, maxn+1> row {0};
    Row() { }
    Row(int nmax)
    {
        max = nmax;
    }
    bool operator ==(const Row& rhs) const
    {
        const uint64_t* x = reinterpret_cast<const uint64_t*>(this);
        const uint64_t* y = reinterpret_cast<const uint64_t*>(&rhs);
        return x[0] == y[0] && x[1] == y[1] && x[2] == y[2];
    }
};
uint64_t rotl(uint64_t x, char a)
{
    return (x << a) | (x >> (64 - a));
}
size_t hasher::operator() (const Row& row) const
{
    const uint64_t* mem = reinterpret_cast<const uint64_t*>(&row);
    //I tried really many different hashes...
    uint64_t h = mem[0]; h += rotl(h, 4);
    h         ^= mem[1]; h += rotl(h, 4);
    h         ^= mem[2]; h += rotl(h, 4);
    return h;
}
const short hashTableSize = 1009;
struct Map
{
    std::array<std::pair<Row, int>, hashTableSize> table {};
    Map()
    {
    }
    void add_or_add(const Row row, const int delta)
    {
        size_t hash = hasher()(row) % hashTableSize;
        while(table[hash].second != 0 && !(table[hash].first == row))
        {
            hash++;
            if(hash == hashTableSize) hash = 0; //just loop :)
        }
        if(table[hash].second == 0)
            table[hash].first = row;
        table[hash].second += delta;
    }
    void clear()
    {
        std::memset(table.data(), 0, sizeof(table));
    }
};

constexpr uint bitRev(uint n)
{
    n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
        n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
        n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
        n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
        n = ((n >>16) & 0x0000ffff) | ((n <<16) & 0xffff0000);
        return n;
}
constexpr bool is_substring(int target, char n, short subs, char m)
{
    //n=2, m=1 -> i from 0 to 1
    int max = n-m+1;
    bool flag = false;
    for(int i = 0; i < max; i++)
        flag |= (((target >> i) ^ subs) & ((1<<m) - 1)) == 0;
    return flag;
}
int supermax = 0;
int main()
{
    uint n; std::cin >> n;
    std::vector<uint64_t> sums(threadnum);
    uint64_t sum = 0;
#pragma omp parallel for num_threads(threadnum) schedule(dynamic)
    for(uint sa = 0; sa < 1<<~-n; sa++) //the second half is the bitwise complement of the first one
    {
        uint sb = bitRev(sa);
        sb ^= -(sb >> 31);
        sb >>= 32 - n;
        if(sb < sa) continue;
        //find a lower bound = len(the shortest non-substring of sa) - 1
        //if Row.max is immediately set to it, that reduces the number of states slightly
        char lb = 0; bool found = false;
        for(char len = 0; len < 10; len++)
        {
            for(short j = 0; j < (1<<len); j++)
                if(!is_substring(sa, n, j, len))
                {
                    lb = len - 1;
                    goto out;
                }
        }
        out:;
        Map dpcur;
        Map dpnext;
        dpcur.add_or_add(Row(lb), 1);
        int ans = 0;
        for(char j = 0; j < n; j++)
        {
            for(auto[row, cnt] : dpcur.table)
            {
                if(!cnt) continue;
                Row nr0 {}, nr1 {};
                nr0.max = nr1.max = row.max;
                for(char i = 0; i < n; i++)
                {
                    Row& r = (sa >> i)&1 ? nr0 : nr1;
                    r.row[i+1] = row.row[i] + 1;
                }
                char n0max = 0, n1max = 0;
                for(char i = 0; i < 23; i++)
                    n0max = std::max(n0max, nr0.row[i]);
                for(char i = 0; i < 23; i++)
                    n1max = std::max(n1max, nr1.row[i]);
                //possibly, cut an entire would-be branch that would never improve!
                if(n0max + n - j - 1 <= nr0.max)
                    ans += (cnt * nr0.max) << (n - j - 1);
                else
                    nr0.max = std::max(nr0.max, n0max), dpnext.add_or_add(nr0, cnt);
                if(n1max + n - j - 1 <= nr1.max)
                    ans += (cnt * nr1.max) << (n - j - 1);
                else
                    nr1.max = std::max(nr1.max, n1max), dpnext.add_or_add(nr1, cnt);
            }
            std::memcpy(dpcur.table.data(), dpnext.table.data(), sizeof(Map));
            dpnext.clear();
        }
        for(auto[row, cnt] : dpcur.table)
            ans += cnt * row.max;
        sums[omp_get_thread_num()] += ans;
        if(sb != sa)
            sums[omp_get_thread_num()] += ans;
    }
    for(uint64_t e : sums) sum += e;
    sum *= 2;
    printf("%ld\n", sum);
    uint64_t num = sum, denom = 1ll<<(2*n);
    while(num % 2 == 0) num /= 2, denom /= 2;
    printf("%ld/%ld\n", num, denom);
}

This uses OpenMP for multi-threading. To be compiled with clang++ -std=c++17 -Ofast -march=native -flto -fopenmp file.cpp.

Explanation I tried (please don't use it as a Rust translation guide)

The longest common substring can be found in \$O(n^2)\$ time via dynamic programming. That dynamic programming can be calculated (if the strings are \$s\$ and \$t\$) via the formula $$dp_{i,j} = \begin{cases}dp_{i-1,j-1} + 1& s_i = t_j\\0& \text{otherwise}\end{cases}$$ (and then the answer is just the highest value in \$dp\$). A naive solution would be to iterate over pairs of strings of length \$n\$ (resulting in \$O(4^n n^2)\$ time complexity). However, instead of simply doing that, my program only iterates over all possible values of the first string. Then, it simply does that, but instead of storing a proper dynamic programming array (that wouldn't be possible because there is no second string), it stores an array of all possible rows in it with counters of how many ways exist to reach this row. To calculate the next array of possible rows from the current array of possible rows, my program simply tries all of them with both possible values of the next bit in the second string. This leads to a speedup, because if two prefixes of the second string lead to the same state, they can be "merged" into one execution path.

I suspect this is similar to the optimization from the top answer in a similar challenge but for Levenshtein distance, but the explanation there is so bad I couldn't understand it at all.

The optimization that got this to 21: if at a certain point a possible row is encountered such that all its numbers are too small to ever improve the length of the longest substring in it, it can be directly calculated how much it will add to the answer.

Takes input as a single number from stdin. Outputs 734551/131072 for 13, 392340511/67108864 for 14, 1630366263/268435456 for 15, 6751032665/1073741824 for 16, 6967595579/1073741824 for 17, 114759115773/17179869184 for 18, 235733542633/34359738368 for 19, 1933121200141/27877906944 for 20 and 7912473298597/1099511627776 for 21.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Ah, very nice! Smart to use a bitmask and bitwise shifts to check for common binary substrings! No need to convert to a binary-string at all in that case, since you're working on the integer-bits. Looks so obvious now that I see it, but you'd still have to come up with an approach like that. \$\endgroup\$ – Kevin Cruijssen Mar 13 at 20:01
  • \$\begingroup\$ Thanks for this. Do you think this can be made multi-threaded? I will be very interested if an n log n or even linear time longest common subsequence algorithm can beat this in the end. \$\endgroup\$ – fomin Mar 13 at 20:20
  • 3
    \$\begingroup\$ @fomin I was actually working on multi-threading while you were writing the comment. I have not tried (or even properly read about) better longest common substring algorithms yet. \$\endgroup\$ – my pronoun is monicareinstate Mar 13 at 20:23
  • \$\begingroup\$ I like your speedup a lot! Out of interest, is it as fast as the fastest Levenshtein solution? You might have thought this problem should be easier than the Levenshtein one given that the longest common substring problem has a linear time solution, but maybe not. \$\endgroup\$ – Anush Mar 14 at 19:05
  • 1
    \$\begingroup\$ @PeterCordes I knew there are better ways to reverse bits, but in this case it does exactly 2^(n-1) or something similar bit reversals, so it is not a bottleneck at all. I have improved the code slightly since the last edit, including rewriting the innermost loop to use SIMD, but I have also increased maxn to 30, so the gains are small. \$\endgroup\$ – my pronoun is monicareinstate Apr 2 at 8:41
4
\$\begingroup\$

Wolfram Language (Mathematica), n=12 (~53s TIO)

t=0;
For[i=0,i<2^a,i++,
   For[j=0,j<2^(a-1),j++, 
    t=t+Length@LongestCommonSubsequence[IntegerDigits[i,2,a],IntegerDigits[j,2,a]]]]

Try it online!

| improve this answer | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Is this longest common substring? It looks like you are computing longest common subsequence which is not the same thing. \$\endgroup\$ – Anush Mar 12 at 18:05
  • \$\begingroup\$ @Anush Did you try it on line? It produces the exact correct results! do you just downvote based on watching the code? \$\endgroup\$ – J42161217 Mar 12 at 18:08
  • \$\begingroup\$ Hmm..I am happy to change the vote but you have to edit the question to let me do that. Why is it called subsequence if it is really computing substrings? \$\endgroup\$ – Anush Mar 12 at 18:36
  • 1
    \$\begingroup\$ @Anush the best way to test an algorithm is to tio and to see if it answers the question. If you want to find details on a specific command try the Wolfram Language online documentation... \$\endgroup\$ – J42161217 Mar 12 at 18:44
2
\$\begingroup\$

Python 3 308 293 bytes, n=10 (30sec TIO)

a=lambda S,T:max((*(i+1 for i in range(len(S)) for j in range(len(S)-i)if S[j:j+i+1]in T),0));b=lambda i,n:'0'*(n-len(bin(i)[2:]))+bin(i)[2:]
for n in range(1,11):m=2**n;t=sum([a(b(i,n),b(j,n))for i in range(m)for j in range(m)]);y=bin(t);v=2**(len(y)-len(y.rstrip('0')));print(t/v,'/',4**n/v)

Try it online!

Not elegant or super fast but it's the first time I've been able to get something like this on so few lines. Potential speed up possible with numpy functions.

I feel like this problem is similar to Project Euler Question 701. Maybe with an algorithm for that this problem could be done in sub-exponential time.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ This is not code golf so no need to worry about bytes. \$\endgroup\$ – Anush Mar 13 at 19:32
  • 1
    \$\begingroup\$ Slight performance improvement with b=lambda i,n:bin((2<<n)+i)[4:]. \$\endgroup\$ – mypetlion Mar 13 at 21:37
2
\$\begingroup\$

Java, n=11 (~30-35 sec on TIO)

import java.util.ArrayList;
import java.util.List;
class Main{
  public static void main(String[] args){
    for(int n=1; ; n++){
      String binaryFormat="%"+n+"s";
      int sum=0, c=0;
      double powerOf2=Math.pow(2,n);
      for(int a=0; a<powerOf2; a++){
        String binaryA=toBinary(n,a);
        for(int b=0; b<powerOf2/2; b++){
          String binaryB=toBinary(n,b);
          sum += solve(binaryA, binaryB);
          c++;
        }
      }
      System.out.println(n+": "+sum+"/"+c);
    }
  }

  private static String toBinary(int n, int a){
    return String.format("%"+n+"s", Integer.toBinaryString(a)).replace(' ','0');
  }

  private static int solve(String a,String b){
    String s=a+2+b+3;
    List<Integer> M = new ArrayList<>();
    for(int c : s.getBytes())
      M.add(c);
    List<Integer> S = suffixList(M, 51);
    List<Integer> I = new ArrayList(S);
    for(int i=0; i<S.size(); i++)
      I.set(S.get(i), i);
    int L=0,R=0,m=0,h=0;
    for(int i=0; i<S.size(); i++){
      if(I.get(i)!=0){
        int j=S.get(I.get(i)-1);
        while(s.charAt(i+h)==s.charAt(j+h))
          h++;
        if(h>m){
          int len = a.length();
          int sortedMid = (i-j)*(j-len)>0 ? j
                                          : (i-j)*(i-len)>0 ? len
                                                            : i;
          if(len == sortedMid){
            m=h;
            L=i<j?i:j;
            R=L+h;
          }
        }
        if(h>0)
          h--;
      }
    }
    return R-L;
  }

  private static List<Integer> suffixList(List<Integer> s, int K){
    int n=s.size();
    s.add(0);s.add(0);s.add(0);
    int n0=(n+2)/3, n1=(n+1)/3, n2=n/3;
    int n02=n0+n2;
    int adj=n0-n1;
    int length=(n+adj)/3;
    List<Integer> A=new ArrayList<>();
    for(int x=0; x<n+adj; x++)
      if(x%3!=0)
        A.add(x);
    A.add(0);A.add(0);A.add(0);
    radixPass(K,s,A,2,n02);
    radixPass(K,s,A,1,n02);
    radixPass(K,s,A,0,n02);
    List<Integer> B=new ArrayList<>();
    for(int i=0; i<n02; i++)
      B.add(0);
    int[] t=new int[3];
    int m=0;
    for(int i=0; i<n02; i++){
      int x=A.get(i);
      int[] u=new int[3];
      for(int j=x; j<x+3; j++)
        u[j-x]=s.get(j);
      if(t[0]!=u[0]||t[1]!=u[1]||t[2]!=u[2])
        m++;
      t=u;
      B.set(x/3+x%3/2*n0, m);
    }
    if(n02==1)
      for(int i=0; i<n02; i++)
        A.set(i, 0);
    else{
      List<Integer> X = suffixList(B,m);
      for(int i=0; i<n02; i++)
        A.set(i, X.get(i));
    }
    List<Integer> I = new ArrayList<>(A);
    for(int i=0; i<n02; i++)
      I.set(A.get(i), i+1);
    B = new ArrayList<>();
    for(int x:A)
      if(x<n0)
        B.add(3*x);
    radixPass(K,s,B,0,n0);
    List<Integer> R = new ArrayList<>();
    int p=0;
    for(int T=adj; T<n02; ){
      int x = A.get(T);
      boolean bool = x>=n0;
      int b = bool?1:0;
      int i=(x-b*n0)*3-~b;
      int j=B.get(p);
      if(p==n0
         || (bool ? s.get(i)<s.get(j) || (s.get(i)==s.get(j)&&s.get(i+1)<s.get(j+1)) || (s.get(i)==s.get(j)&&s.get(i+1)==s.get(j+1)&&I.get(A.get(T)-n0+1)<I.get(j/3+n0))
                  : s.get(i)<s.get(j) || (s.get(i)==s.get(j)&&I.get(A.get(T)+n0)<I.get(j/3)))){
        R.add(i);
        T++;
      }else{
        R.add(j);
        p++;
      }
    }
    for(int i=p; i<n0; i++)
      R.add(B.get(i));
    return R;
  }

  private static void radixPass(int K, List<Integer> s, List<Integer> a, int o, int n){
    int[] c=new int[K+3];
    for(int i=0; i<n; i++)
      c[s.get(a.get(i)+o)+1]++;
    for(int i=0; i<K+3; i++)
      c[i]+=c[i<1?c.length-1:i-1];
    List<Integer> A = new ArrayList<>(a);
    for(int i=0; i<n; i++){
      int x=A.get(i);
      int j=s.get(x+o);
      a.set(c[j], x);
      c[j]++;
    }
  }
}

NOTE: The fractions aren't normalized like in the challenge description. The decimal values the fractions represent are correct, though.

Try it online with indefinite printing - times out after 60 sec or try it online with given argument \$n\$.

Only just got it working, so will try to improve its performance later on.

Short explanation of my solution:

I first modified @MitchSchwartz' Python 2 answer for the Longest common substring in linear time challenge so it will loop over the binary-string pairs we want to check. This challenge asks for the starting and ending index of the longest common substring between two strings, in lineair time (\$O(n)\$ complexity).
His answer implements 'The Skew Algorithm' described in Juha Kärkkäinen's & Peter Sanders' Simple Linear Work Suffix Array Construction article, with the implementation of the Longest Common Prefix part using the algorithm described in Toru Kasai's, Gunho Lee's, Hiroki Arimura's, Setsuo Arikawa's, and Kunsoo Park's Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications article.

Since we basically want to check all binary-string pairs \$A\$ and \$B\$, where \$A\$ are binary strings for integers \$a\$ in the range \$a=[0, 2^n)\$ and \$B\$ are binary strings for integers \$b\$ in the range \$b=[0,\frac{2^n}{2})\$ (similar as the existing Mathematica answer does), I've modified @MitchSchwartz' ungolfed answer to take the difference between the found indices, and sum those together for our numerator (the denominator will be \$n^{2n-1}\$ for any given \$n\$).

Here is that modified Python code:
Try it online printing indefinitely or try it online with given input \$n\$ (which produces \$n=9\$ in about 25-30 sec on TIO).

Since I'm not too skilled with Python, I decided to port everything to Java which I use on a daily basis. This allows me to make performance enhancing modifications (which I will try to do later on) easier. And I also knew that the larger \$n\$ would become, the better the performance of the Java program in comparison to the Python program would be (which can also be seen by checking some \$n\$ in both programs on TIO - i.e. the inputs \$n=1,5,7,9\$ will take approximately 1.5, 2.25, 1.75, 4.0 seconds in Java, but 0.02, 0.1, 1.5, 30.0 seconds in Python 2 respectively.

Long explanation:

TODO: I will describe the actual implementation and perhaps add some comments to the code later on. This already took long enough to modify and port to Java for now.

| improve this answer | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ This looks great but any idea why it isn't much faster than the naive python solution of @Alec? I feel it ought to be much faster. \$\endgroup\$ – Anush Mar 13 at 19:29
  • \$\begingroup\$ @Anush Ignore my now deleted comment, I actually was checking correctly.. It's too damn late on a Friday evening.. >.> So not sure why the performance of his answer is better than the Python implementation I have. If you see any potential bottlenecks in the implementation, let me know, since I'd love to improve the performance in my Java port as well then. \$\endgroup\$ – Kevin Cruijssen Mar 13 at 19:58
  • \$\begingroup\$ You could probably get some extra performance out of a solution that does bitwise operations directly on the int instead of converting it to a String representation of the binary. \$\endgroup\$ – mypetlion Mar 13 at 20:33
  • \$\begingroup\$ @mypetlion Yeah, I've seen the C++ answer. I might port it later on to see what the performance in Java is. But for now I'm enjoying the weekend, since I've already been working on both work and this thing above for a bit too long. xD \$\endgroup\$ – Kevin Cruijssen Mar 13 at 20:36
2
\$\begingroup\$

Rust, (n=15 ~6 sec, n=16 ~25 sec on 2.5GHz intel i7)

More heavily parallelised rewrite of @monicareinstate's answer in rust

src/main.rs

use rayon::prelude::*;

const MAX_N: usize = 22;

const ARRAY_SIZE: usize = 1 << MAX_N;

static mut LOOKUP: [u8; ARRAY_SIZE] = [0; ARRAY_SIZE];

#[inline]
fn longest_sub(left: u32, right: u32, bits: u8) -> (u8, u8) {
    // Uses of unsafe are sound here since we are only reading immutably
    let mask = (1u32 << bits) - 1;
    let unshifted = mask & !(left ^ right);
    let max_unshifted = unsafe { *LOOKUP.get_unchecked(unshifted as usize) };
    let max_shifted = (1..bits)
        .map(|shift| {
            let mask = (1u32 << (bits - shift)) - 1;
            let shift_l = mask & !((left >> shift) ^ right);
            let shift_r = mask & !(left ^ (right >> shift));
            unsafe {
                std::cmp::max(
                    *LOOKUP.get_unchecked(shift_l as usize),
                    *LOOKUP.get_unchecked(shift_r as usize),
                )
            }
        })
        .max()
        .unwrap();

    let max = std::cmp::max(max_unshifted, max_shifted);
    if left == right {
        (max, 1)
    }
    else {
        (2 * max, 2)
    }
}

#[inline]
fn calculate(bits: u8) -> (u64, u64) {
    for number in 1..1usize << bits {
        // Safe since we have no other references to LOOKUP in the current program
        unsafe {
            *LOOKUP.get_unchecked_mut(number) = 1 + LOOKUP.get_unchecked(number & (number >> 1))
        }
    }

    (0..1u32 << bits)
        .into_par_iter()
        .flat_map(move |left| {
            (left..1u32 << bits)
                .into_par_iter()
                .map(move |right| longest_sub(left, right, bits))
        })
        .map(|(max, weight)| (max as u64, weight as u64))
        .reduce(|| (0, 0), |a, b| (a.0 + b.0, a.1 + b.1))
}

fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    let line = line.trim();
    let number = line.parse().unwrap();

    let (num, denom) = calculate(number);
    let (num, denom) = {
        let (mut a, mut b) = (num, denom);
        while a % 2 == 0 && b % 2 == 0 {
            a /= 2;
            b /= 2;
        }
        (a, b)
    };
    println!("{}/{}", num, denom);
}

Cargo.toml

[package]
name = "golf"
version = "0.1.0"
authors = ["Plasma_000"]
edition = "2018"

[profile.release]
opt-level = 3
lto = true

[dependencies]
rayon = "1.3"

Build with

RUSTFLAGS="-Ctarget-cpu=native" cargo +nightly build --release

Using nightly compiler 1.43.0

This performs a very slightly faster than the @monicareinstate's current answer on my machine:

❯ time "echo 15 | ./target/release/golf"
Benchmark #1: echo 15 | ./target/release/golf
  Time (mean ± σ):      5.872 s ±  0.114 s    [User: 21.332 s, System: 0.127 s]
  Range (min … max):    5.665 s …  6.017 s    10 runs

VS @monicareinstate's

❯ time "echo 15 | ./a.out"
Benchmark #1: echo 15 | ./a.out
  Time (mean ± σ):      5.983 s ±  0.092 s    [User: 22.038 s, System: 0.120 s]
  Range (min … max):    5.868 s …  6.157 s    10 runs

EDIT: well done @monicareinstate on your latest edit, you have me beat :)

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ no targets specified in the manifest either src/lib.rs, src/main.rs, a [lib] section, or [[bin]] section must be present \$\endgroup\$ – Anush Apr 3 at 9:56
  • \$\begingroup\$ @anush Did you fail to name the file src/main.rs? If it’s named main you shouldn’t have to add [[bin]] to the manifest \$\endgroup\$ – Plasma_000 Apr 3 at 10:23
  • \$\begingroup\$ Thanks. You have reached n = 18. \$\endgroup\$ – Anush Apr 3 at 10:30
1
\$\begingroup\$

C (gcc), 1769 bytes, n=14 in 31 sec. on TIO

n=15 in 2 min 7sec on my MacBook Pro (3.1 GHz Intel Core i7)

NOTE: If you test this program to see how far it can get in one minute, change #define END to be some larger number, say (17). The value of (14) was picked so as not to time out in 1 minute on TIO.

Output will be computed from n = START to n = END.

Do not change the #define CUTOFF value -- this is the point at which long longs are needed, instead of just longs.

#include <stdlib.h>
#include <stdio.h>

#define START (1)
#define END (14)

#define CUTOFF (15)

// Find length of longest common substring of binary numbers a and b, of length l.
int f(int a, int b, int l)
  {
   int i, j;

   for (int lengthOfMatch=1, mask=1; lengthOfMatch<=l; lengthOfMatch++, mask = 2*mask+1)
      {
       for (i=0; i <= l-lengthOfMatch; i++)
          {
           for (j=0; j <= l-lengthOfMatch; j++)
                {
                   if ( ((a>>i)& mask) == ((b>>j) & mask) )
                     {
                      if (lengthOfMatch == l)
                        return lengthOfMatch;

                      goto NextMatchLength;
                     }
                } // for j
          } // for i

       return lengthOfMatch - 1;

NextMatchLength:
       ;
      } // for lengthOfMatch

 return 0;
} // f


int main(void)
{
 for (int numberOfBits=START; numberOfBits <= END; numberOfBits++)
  {
   if (numberOfBits >= CUTOFF)
     {
      long long t=0;

      for (int a=0;a<(1<<numberOfBits);a++)
         {
          for (int b=0; b<a; b++)
              t += f(a, b, numberOfBits);
         } // for a

// Make up for the entries f(a, a, numberOfBits) that weren't counted above.
      t += numberOfBits*(1<<(numberOfBits-1));

      printf("%d => %lld/%lld\n", numberOfBits, t, 1ll<<(2*numberOfBits-1));
     }
    else
     {
      long t=0;

      for (int a=0;a<(1<<numberOfBits);a++)
         {
          for (int b=0; b<a; b++)
              t += f(a, b, numberOfBits);
         } // for a

// Make up for the entries f(a, a, numberOfBits) that weren't counted yet.
      t += numberOfBits*(1<<(numberOfBits-1));

      printf("%d => %ld/%ld\n", numberOfBits, t, 1l<<(2*numberOfBits-1));
     }
   }

exit(0);
} // main

Try it online!


Sample output for \$n=15\$ from my MacBook Pro (3.1 GHz Intel Core i7) -- 2 min 7 sec.

$ time ./l5
1 => 1/2
2 => 9/8
3 => 56/32
4 => 295/128
5 => 1444/512
6 => 6741/2048
7 => 30434/8192
8 => 134224/32768
9 => 582862/131072
10 => 2500643/524288
11 => 10628636/2097152
12 => 44841578/8388608
13 => 188045056/33554432
14 => 784681022/134217728
15 => 3260732526/536870912

real    2m6.814s
user    2m5.842s
sys 0m0.402s
| improve this answer | | | | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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