# Identify a string from its substrings

## Introduction

I've previously created two challenges where the idea is to reconstruct an object using as few query-type operations as possible; this will be the third.

Your inputs shall be a non-empty string S over the alphabet abc and its length, and your output shall be S. With no restrictions, this would of course be a trivial task; the catch is that you're not allowed to access S directly. The only thing you're allowed to do to S is to call the function num_occur(T, S), where T is some other string, and num_occur counts the number of occurrences of T in S. Overlapping occurrences are counted as distinct, so num_occur(T, S) really returns the number of indices i such that

S[i, i+1, …, i+length(T)-1] == T

For example, num_occur("aba", "cababaababb") will return 3. Note also that num_occur(S, S) will return 1. The result of num_occur("", S) is undefined, and you should not call the function on an empty string.

In short, you should write a function or program that takes S and length(S) as inputs, calls num_occur on some shorter strings and S some number of times, reconstructs S from that information and returns it.

## Rules and scoring

Your goal is to write a program that makes as few calls to num_occur as possible. In this repository, you will find a file called abc_strings.txt. The file contains 100 strings, each on its own line, between lengths 50 and 99. Your score is the total number of calls to num_occur on these inputs, lower score being better. Your solution will preferably keep track of this number as it runs, and print it upon finishing. The strings are generated by choosing uniformly random letters from abc; you are allowed to optimize for this method of generating the strings, but not the strings themselves.

There is no time limit, except that you should run your solution on the test cases before submitting it. You solution should work for any valid input S, not just the test cases.

You are encouraged to share your implementation of num_occur too, if you're not using someone else's. To get the ball rolling, here's an implementation in Python:

def num_occur(needle, haystack):
num = 0
for i in range(len(haystack) - len(needle) + 1):
if haystack[i : i + len(needle)] == needle:
num += 1
return num

• Does our algorithms have to work for all possible strings S, or just for the test cases? – Loovjo Aug 16 '16 at 17:41
• @Loovjo Good question. They should theoretically work for all non-empty strings. I'll edit the challenge. – Zgarb Aug 16 '16 at 17:43
• all non-empty strings of whatever length? – edc65 Aug 16 '16 at 18:20
• @edc65 Theoretically yes. You can ignore bounded memory addresses and other practical limitations. – Zgarb Aug 16 '16 at 18:31
• It is possible to add a VW algorithm to pass the evaluation test with success: Check first for occurrence of the known strings of abc_strings.txt – Emmanuel Aug 17 '16 at 15:49

## Javascript, 14325 14311 calls

We start with an empty string and go our way recursively by adding a new letter at the end or at the beginning of the current string while we still have at least one match.

All previous results from numOccur() are saved in the sym object and we use this data to reject immediately any new string that can't possibly be a candidate.

EDIT: Because we always start with 'a', we always know the exact number of a in the string. We use this information to end the process earlier when we detect that only a sequence of a is missing. Also fixed the regular expression which was invalid in Chrome and IE.

var test = [
'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
// etc.
];
var call = 0;

function guess(S, len) {
var sym = {};
recurse(S, len, "", sym);
return sym.result;
}

function recurse(S, len, s, sym) {
var dictionary = [];

if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
if(s.length == len) {
sym.result = s;
}
else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
dictionary = [ Array(len - s.length + 1).join('a') ];
}
else {
dictionary = [ "a", "b", "c" ];
}
dictionary.some(function(e) {
return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
});
return true;
}
return false;
}

function isCandidate(s, sym) {
return sym[s] === undefined && Object.keys(sym).every(function(k) {
return count(s, k) <= sym[k];
});
}

function count(s0, s1) {
return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
call++;
return count(S, s);
}

test.forEach(function(S) {
if(guess(S, S.length) != S) {
console.log("Failed for: '" + S + "'");
}
});
console.log(call + " calls");


Full executable snippet below.

var test = [
'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
'caccbbababbaaaccbcabbaabaabcacabacaababcabcbbacaac',
'bbbbaacabcabacaccaaaabaaacaacabbcbacabaccbbcbabbcbc',
'abbcbcbccbccaacaccaccaabaccbbcabaaccabccbbbabbbcabc',
'aabacbbbcaaabcccaccccbcaabcacaccbabbbcccacabaaababca',
'bccbbaaccaaccacabaaaabbbbaababacabaaabacbcacbbbbabaa',
'bbbcbcabbacbaacbacabcbabbacacbbcbcabbaabbbccbacaaacac',
'ccbcbbbaaaaaccbaacbabbbcbccbabaabccbcbcbcbabcbbccacba',
'aacbcbcabcbcbccbabbacacbcaaababbbcacaacaccbabbbbabcaac',
'bcabacaabbacccacaabcaaacbcbcbacabbababcabbbbacbaaaabbb',
'abbaccccabbbcbbaacccacbcaacababaccabbabbacbbbaabaacbaba',
'cabbacabacccabcabacbaacbaababcaccbacbaaaacbbabbbccabbbb',
'bcabccaaabcbaaccaabccbbcbabaccababbbaccccacaaccaccacbcab',
'abbcbabaacbcbbabbccccbccabcbbaccacbabcacbaacbccbcabcccbc',
'bcbacabbaabcccabccacbcbccbcbbbccacbbccaabaacccccbcabaaccc',
'baccbcacaccacbbbcccbaaacbaccacbbacbbbaccccacbabcbbbaacabb',
'bcccabaaaabcbbbaaccbcaccbaabacccaaacbaabaccccacabaccacbcac',
'baabcbbcaabcacbabbcacccbcabbabaacbbbababbbbbccccccbcbbcbcc',
'bacacbbabbcbbcaacabcccccbbacabcaabbbcbbabaacbcbbaccaaacbbac',
'ccabccbccbaaacbcccccabacbbabbbbccbccccabaabaabbaacbabcabbcb',
'abbaccbcaabacbbacabaabbcbacbacacabccbbcccaccbbacbbbaacbaccab',
'bbbbaaabababcccbbbababacbacbaabbabccacccaaacabaccababaccbcac',
'bbcbbbbcccaccbbbcbcaaccbcacaabbbbabaaabbbaaacbbaaccbacaccabbb',
'cacabcabcbcbbbbcabbbccccccccacaaabaacbcaabbabcacbcbcccccacaab',
'babbcacabaabbccabcbbaacccaaccbabcbbcbcbbbcabbcccbcacbabccaccac',
'ccbbcbcbcaacbcaaccacbcaabbbcbbaccbbabacacccccaccaababcacccccba',
'bcccbcacccccabccabccbcbccaccaaacbcacabaabcbcccaccaaaabbcacbbcaa',
'cbbcacbbacaacbabccaabbaabacacbcbcbabcaccabbbbcabbbabaaacccaabcc',
'aabbaacccaaacbcaabcabaabbbaababbbbcbacabbbbbbbbccaccccbbaccbbaaa',
'abbcccabbabbaccccaacbabbccccbbbbccaaacaabacbabbabcabacbaabcbcacb',
'bcacbccccaacbbcaccbcbcbbabacabacabbcaaabbccabcccbaacabcbbcacababb',
'acabacaabcabbcccccbcacaccccbccaaaacacbbbccbcaabaacbbbacabcbcaabca',
'caabbaccaacbbcbaacbcabccacacabbcbcbbacabbbaacccaacccabaaaccbbacbaa',
'baaabbcbbbaacabacbcaaacabbacaacbacabbcabcccbabcbbacacbbababccacabc',
'abbbacbaabcabbcabbbabaababbaabcacbabbaababcabbbccccbcaacbbcccabaccb',
'caaababcacccaccababaccbabbccaabbbbbabaabcabccbabbbbbbcbacbabcbcccbb',
'abbbcaaaaacaaacbbbcbacabbcbbbccacaccacacabacacbbccbbbcbaccabbcbaabbc',
'bacacbcccabcabaabacccbcaaabcabbbcccaacbabacbaabbcccacaacbabbcacbaabb',
'bacaaaccbaababbbbbcaabcabaacccabacccbabcbccbbcbcaacbbaabcaccaaaacaabb',
'bbacaacccaaacacccbbacbcbbaaaccccabbbbcbbbabaaaaccbccaababaccbbccacaca',
'aacccccbabaccbcbcbbaccbacbcbacaababaaaccbaaabaabcccccacbbaabcccaababcc',
'babacacbbbacbbbbbabbabababacabacaaacbbccaccabacaacbabbbaccacccbcaaabbb',
'bcaccabbabbcbcabccbbcaacbbcbacbcabaaaaaacaaacaccbcaaccaaccacbaccacaabbc',
'acbcbbcbbaacbbbabbaabacabbcccabacabcabacccacbcaacacabcaaaabbabcccbcbabb',
'ccbcbcccbccbbbabaabbaababbcbacacbcbaacaccccccbcbacacbcabaaaacaacbbbbacba',
'cccbcbaaabcbbcbabbbaccabbabcacbaccbcababbababcbcaccabbbccabaabaaccccacbb',
'bbabcbcaabbacaabcababbbccbccccaaaabaccbbbbababbcabbabbaccaaaabbcbbbcbaccc',
'cbacaccaaaacaacbbcbbacaccabacaacacaacaacabccaaaccccacaaaaabcbcabaabaacccb',
'bcacbccabcccabababbbbcabaacabcbbaacaaaabbbacccaaabccbaabcbbabbbcccabaabbbb',
'cbccacabaaacabbccbacabccacabcbaccbababcccabbabbbbbbccbaabbaacaacaaaabcbabb',
'abcbcabbcabaababccbcacabbcbcabcaabbbabbcaaabaaaaacbaabaaababccacbabcbaccbab',
'aabbabbbcacaaaabcbcabccccacbacbccacacaabccacccaaacacbcccaabbbccacacbbccbbac',
'caacbbccacaaaacabaacbcaaaccbbabbcacababbbabcbccbaabccaababbcbacbccababbcbbbc',
'aaabaaaabbbbbcbbbacabccbaaaaabaacbacbcccbccacccacaaacaccbbabcbcccbbccccabbcb',
'cccccacacbacbbcbbcabcbaabbcbbbacabcbbccccaaacabcababbcaaccaabccabaccbcaccbaba',
'ccaaaccbccacabcacaccbccaabacacabaabbbaacbcacaacbaaabbbbabbabcccabcabbaccacacc',
'cbbbcaccbcacccbacccaaaabacaacccbcbcbabbbaababacccccccabbaaabbcbaabbbbbbaaaaaaa',
'ccbcbcbaabbccabbabbccbacbabacbcacbccacaabbcacaaccabbbbcbacbbcaaabaabccaacccacb',
'caaabcabaacbbabcbccabcacbbcccabcacbbcaabaacaaabbbcacaaccaccaaaacaaccbbaaaacaaac',
'bbacacbbaaaacbcabbbbbaabacaccabcbabbccbbbabbbacccababbcababcbbcacbababbbaaabcca',
'bbacbbacacaccccbabbbbcabbcccbcacaabbcabbccaaaaabcbbcccaccbcbbbccabcbaccacbacbaba',
'baccbcababbacabcbabacaababbaabcabbcbcbccabacbbaaaaabacaaacaacbacbcabacabaaccbcab',
'accacccabccbabcbcbaababacabcabbcaccbccabbabcbcabbaabccacbbbbcaacbccaababbababbaba',
'bbcccbcbcbccccbcaaccaaacacbbaacbcccbbcabbbccabaacbacaaaccbcbaacababaccacbcbaaccac',
'acbccccaabcabbbcbbccbccbacbcabcccacbcabbaacbababbbcbbccacbacccbbbaccbaaaabbbabaccb',
'babcacaccbccbaaabaabbbaabcaabaaccccacaacbaccbcbabbbbbbabcbbbbacbacbabcbbbacbbbbbbc',
'caabcaaaaabacccacbbbaabaabccaabcbaabbcbcbbbccbabbccbcbabbbbccacbcbcbacaaccccacbbabc',
'bbaaabbabccaccacbcbbccaaaaababbacccbabcbacabacbaacbcabaaacacaaaaacaaacabbbbccabbbca',
'bbcbccababbbaabbabcbbaacbccbaacbababbabcbaaccbcbcabacaabacaacabcababbaaabbbbbbccccbb',
'acabcabccaaccccacbcaabaccacaaabcbabbabbaccbbaaacacabcabbcabababaccccbcbabaacbbcccbab',
'bacaaaaacbcacbbbaaaaabbbbcbbcbbbcaccccbacaccbbcbabbbccbaaabbcbaccacacbcbcacbcbaaabacc',
'bbcaabccbcaccbabbacbaacacccccaabbbccbccbbbcccbacaaaccccbccbbbbabccaaacaabbbbacaacabab',
'aaaccccbbabbcacabaacacbabbcacbcccbcbaaacaabaabacbbaabcbbbbbcacbaccaacaacbccacbbcacbbaa',
'bbcacabcbbcbabbabbbacaaabcabbbbacbacbabacbbbbbabacabbabaabcabbaabbbaaccbcabcababcaaacc',
'ccccbaacbbcaccaccbaaacaccbabbabaabbababcacacaaccbbcbccaaaaaaacbccacbacbabbbabcabaabaabb',
'abacacbaccacaaacaccbcbabcaacbccaccbbacbabcababcaabcaabcbcabbcbacabaaaaaabaccccbbbcbabac',
'ccccacbaaabaaacabbabacbbacbabcbbcaaaaacaccacabcaacabcbcbcaccabcaaccbaccabcccbccacccbacbc',
'bcaabcaacacccbcababccacacbccccccbbaaabacabbcbbbcbaaacbbacababbaccccacbbcbacaacbabcbaccbc',
'cbcbbaabacbaacbbcabbbbaccbaabbacbcccaaabbabacabbbababcaabcacbaccacacaccbbbbcbcbbaaacbcbba',
'ccbcabcaabcbabbbcbcbbabacabacbbaccbbcbcabcaccaaccbaccbaacacacbbaacaaaaabcaaaacbcccbcccaaa',
'cbbababacbbabbabaabaaaabcacbacbcccbacbccbbcaabcabaccacccbbcaacacccccaccabaabccacbaccabaaba',
'cbbbaaacaccbcabccacbccabacbcbcccccacaccbbcccbcbbbaababcaaaacaabbbccbacbaccabccccbbbcaaaabb',
'bbabbacaaccacccbbcabbacbcbabcccaccacbacbccababbbcacbabbbcabbbbacabcabcbaacbaabcbccacaaaccbc',
'babcbaabccabcabaaabcaaaabaaaaccbcbcacbbbccaccccaacbcbabbbaaaccacaaabacbbabbcacbcaaaaabaabab',
'acbabbccacaccabccbcbabacccbabbaacbccbcaabccbcbababccacbbbaabbaaaababbcaaaaabccbacbbcacbcacba',
'cbccbbaacacccacacacbbbcbbccabcaaaabbcacacacaccbacaacbcbcbccaacaaaaaacbacacbabbbcccabbbbababa',
'cabaabaccbbcccabaccbbacbcabbbbbaccccccbcbcbcbbccbaaabbbbcabacabccaacbcbcbabccbbcabacababccaab',
'bccaacbabcbccaccbabcbbcbaaccbaacabbcabbbacbbccabcabccabccbacbaacbccabccaabaaabcaababacacccaac',
'aacabcccaaccacbbcbbbbacaacacbcbcaabbcbbacbabcbccaabcbbbbaabccbbbacaababcabaacaccababacbcbccbba',
'caaabbcbcbcabccccacacaaababbacbabacbaaccbcbabbaaacbbccccaaaabbccbcabcbccbbaaccbbbabcaabcbbbcab',
'aacbbcbbcbaccccbaaaabcbaaabaaacaacaaacacacabaaabacbaaaacccbaaabbbcbbbacbcbccabccaabbaabcbcbccba',
'abaccbcacabbbbacabaacaccbcbaabbaccaabbbbbababbbcbbbbacaacabbbabcaccbacabbabcbbacbbaaccbcbacaabc',
'aacaaaacccabcccacacbaaccccababcaccaccacbbbacabccbbcbbbacaccbbbbbaabacbacbcbcabccaaccababacaabcbb',
'baabbabaaccabcbbabcacccccaabbccbccbcaacbbbccccbbcbacaabcccccbbabbabbcacbbccbcacabbbbaaaaccbcacca',
'aabacbaacbbccabbbacbcbbbabacaacccabbcabacacaaaabbcbbbcbbbcababbccbbacbbabcaacbacbbcaabbbcbaaaccaa',
'aacabaaccaaabcacccabbaabbcacbabccacabaccaaaaccccccaabcbbbaabcbcccacaccbcaaacaaaabaababccbbbcccaac',
'bcaccbcacaccbacbcccbcbbcabaabbabcccbaaababbbabbcbcbcaabbabbccccbabccabbccccabaaabccbacabccabbbacaa',
'ccaacbabcccbabacabaccccbcbbcccbbbacbbbcccacababccbbaaaaababbabccbccabcccbccabaccbcbcacbbbaacabccaa',
'caccbababcbcbabccabcbbaccbbbabcbacbcbcbcabcbacbcacabbcaabbbbbbbcbbaabcacccbcaabccacbccbbcccaabcbcac',
'bbcccaabacbacbccbbbbbaabccaaabbaabcaabbcbabbbaabcbcbacbaccabacacaaaababccaaaccacaabaabcacbcaccbaabb'
];
var call = 0;

function guess(S, len) {
var sym = {};
recurse(S, len, "", sym);
return sym.result;
}

function recurse(S, len, s, sym) {
var dictionary = [];

if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
if(s.length == len) {
sym.result = s;
}
else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
dictionary = [ Array(len - s.length + 1).join('a') ];
}
else {
dictionary = [ "a", "b", "c" ];
}
dictionary.some(function(e) {
return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
});
return true;
}
return false;
}

function isCandidate(s, sym) {
return sym[s] === undefined && Object.keys(sym).every(function(k) {
return count(s, k) <= sym[k];
});
}

function count(s0, s1) {
return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
call++;
return count(S, s);
}

test.forEach(function(S) {
if(guess(S, S.length) != S) {
console.log("Failed for: '" + S + "'");
}
});
console.log(call + " calls");

• "In short, you should write a function or program that [...], reconstructs S from that information and returns it." – KarlKastor Aug 17 '16 at 0:21
• @KarlKastor - Oops. You're right. That's fixed. Thanks! – Arnauld Aug 17 '16 at 8:54

# Python, 15205 calls

def findS(S, len_s, alphabeth = "abc"):
if len_s == 0:
return ""
current = ""
while len(current) < len_s:
worked = False
for letter in alphabeth:
current_new = current + letter
else:
current_new = letter + current
if num_occur(current_new, S) > 0:
current = current_new
worked = True
break
if not worked:
return current


This submission is most likely suboptimal, because it only uses num_occur to check if a string is a substring of S, and it never uses it to actually count the amount of substrings.

The algorithm works by storing a string current which is built up to be equal to S in the end. Here are all the steps in the algorithm:

1. We set current equal to ''

2. Go through each letter in the alphabet, and do the following:

2.1. Create a new string current_new, and set it equals to current followed by the letter.

2.2. Check if current_new is included in S by running num_occur on it and see if the result is greater than one.

2.3. If current_new is included in S, set current to current_new and go back to step 2. Else, we go to the next letter.

3. If the length of current is equal to the length of S we can say that we are done. Else, we go back to step 2, but modify step 2.1 to make current_new equal to the letter followed by current instead. When we reach this step again, we are done.

• Python's for loop has an else clause. This would be a perfect use case for it. – Jakube Aug 16 '16 at 18:19

# Python 2, 14952 14754 calls

Very similar to the first answer, but doesn't try next characters which result in impossible substrings that:

• we know from num_occur that they don't occur in the target (from previous calls)

• we already used the substring more often than it occurs according to num_occur

(will add counting of substrings in a minute) done

def get_that_string(h,l,alpha = "abc"):
dic = {}
s = ""
##costs 1 additional call per example, but its worth it
char_list = [num_occur(j,h) for j in alpha[:-1]]
char_list.append(l - sum(char_list))
for y, z in zip(char_list,alpha):
dic[z] = y
end_reached = False
while len(s) < l:
for t in alpha:
if not end_reached:
neu_s = s + t
substrings = [neu_s[i:]   for i in range(len(neu_s))]
else:
neu_s = t + s
substrings = [neu_s[:i+1] for i in range(len(neu_s))]
## Test if we know that that can't be the next char
all_in_d = [suff for suff in substrings if suff in dic.keys()]
poss=all(map(dic.get,all_in_d))
if poss:
if not neu_s in dic.keys():
dic[neu_s] = num_occur(neu_s,h)
if dic[neu_s] > 0:
s=neu_s
for suff in all_in_d:
dic[suff] -= 1
break
else:
end_reached = True
##print s
return s

## test suite start
import urllib

def num_occur(needle, haystack):
global calls
calls += 1
num = 0
for i in range(len(haystack) - len(needle) + 1):
if haystack[i : i + len(needle)] == needle:
num += 1
return num

calls = 0
url = "https://raw.githubusercontent.com/iatorm/random-data/master/abc_strings.txt"
print "Check: ", inputs == map(lambda h: get_that_string(h, len(h)), inputs)
print "Calls: ", calls


# Python 12705 12632 calls

1. make a list of 2 characters strings occurrences
2. sort the list
3. build the string trying the most probable character first, don't test if there is only one possibility
4. update the list
5. if the list is empty it is finished else step 2

I used Loovjo function skeleton. I never code in Python I needed a bootsrap

EDIT:
Added code for one character length strings

def finds(S):

if len(S) == 0:
return ""
if len(S) == 1
if num_occur("a",S) == 1 :
return "a"
if num_occur("b",S) == 1 :
return "b"
return "c"
tuples=[]
alphabet=[ "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb"]
for s in alphabet : tuples.append( (num_occur(s,S), s) )

sum=0
for (i,s) in tuples :   sum+=i
tuples.append( (len(S)-sum-1, "cc") )
tuples.sort(key=lambda x:(-x[0],x[1]))

(i, current) = tuples[0]
tuples[0] = (i-1, current)

nomatch=[]
while len(tuples) > 0:
worked = False
tuples.sort(key=lambda x:(-x[0],x[1]))
count=0
for (n, s) in tuples :
if s[0]==current[-1:] :         count+=1
for i in range(len(tuples)):
(n, s)=tuples[i]
if current[0] == s[1] :
current_new = s[0] + current
possible=True
for nm in nomatch :
lng=len(nm)
if current_new[0:lng] == nm :
possible=False
break
if possible and num_occur(current_new, S) > 0:
current = current_new
worked = True
else :
nomatch.append(current_new)
else:
if current[-1:] == s[0] :
current_new =  current + s[1]
possible=True
for nm in nomatch :
lng=len(nm)
if current_new[-lng:] == nm :
possible=False
break
if count == 1 or (possible and num_occur(current_new, S) > 0) :
current = current_new
worked = True
else :
nomatch.append(current_new)
if worked :
if n == 1:
del tuples[i]
else    :
tuples[i] = (n-1, s)
break
if not worked:

• @Sparr "cc" is calculated, that's saves 100 calls :  tuples.append( (len(S)-sum-1, "cc") )  – Emmanuel Aug 18 '16 at 8:38