Определить строку из ее подстрок

20

Вступление

Ранее я создал две задачи, в которых идея состоит в том, чтобы реконструировать объект, используя как можно меньше операций типа запроса; это будет третий.

Задание

Ваши входные данные должны быть непустой строкой Sнад алфавитом abcи его длиной, а ваши выходные данные должны быть S. Без ограничений это, конечно, тривиальная задача; подвох в том, что вам не разрешен Sпрямой доступ . Единственное, что вам разрешено делать, Sэто вызывать функцию num_occur(T, S), где Tнаходится какая-то другая строка, и num_occurподсчитывает количество вхождений Tin S. Перекрывающиеся экземпляры считаются различными, поэтому на num_occur(T, S)самом деле возвращает количество индексов i, так что

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

Например, num_occur("aba", "cababaababb")вернется 3. Обратите внимание также, что num_occur(S, S)вернется 1. Результат num_occur("", S)не определен, и вы не должны вызывать функцию с пустой строкой.

Короче говоря, вы должны написать функцию или программу, которые принимают Sи в length(S)качестве входных данных, вызывают num_occurнесколько более коротких строк и Sнесколько раз, восстанавливают Sэту информацию и возвращают ее.

Правила и оценки

Ваша цель - написать программу, которая будет делать num_occurкак можно меньше звонков . В этом хранилище вы найдете файл с именем abc_strings.txt. Файл содержит 100 строк, каждая в своей строке, между длинами 50 и 99. Ваша оценка - это общее количество обращений к num_occurэтим входам , причем более низкая оценка лучше. Ваше решение предпочтительно будет отслеживать этот номер во время работы и распечатывать его по окончании. Строки генерируются путем выбора равномерно случайных букв из abc; Вы можете оптимизировать этот метод генерации строк, но не сами строки.

Ограничения по времени нет, за исключением того, что вы должны запустить свое решение в тестовых случаях перед его отправкой. Ваше решение должно работать для любого корректного ввода S, а не только для тестовых случаев.

Вам также рекомендуется поделиться своей реализацией num_occur, если вы не используете чужую. Чтобы начать работу, вот реализация на 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
string fewest-operations Zgarb
источник
Должны ли наши алгоритмы работать для всех возможных строк Sили только для тестовых случаев?
Loovjo
@Loovjo Хороший вопрос. Теоретически они должны работать для всех непустых строк. Я отредактирую вызов.
Згарб
all non-empty stringsкакой длины?
edc65
@ edc65 Теоретически да. Вы можете игнорировать ограниченные адреса памяти и другие практические ограничения.
Згарб
Можно добавить алгоритм VW для успешного прохождения оценочного теста: сначала проверьте наличие известных строк в файле abc_strings.txt
Эммануэль

Ответы:

6

Javascript, 14325 14311 звонков

Мы начинаем с пустой строки и идем рекурсивно, добавляя новую букву в конце или в начале текущей строки, пока у нас еще есть хотя бы одно совпадение.

Все предыдущие результаты numOccur()сохраняются в symобъекте, и мы используем эти данные, чтобы немедленно отклонить любую новую строку, которая не может быть кандидатом.

РЕДАКТИРОВАТЬ : потому что мы всегда начинаем с 'a', мы всегда знаем точное число aв строке. Мы используем эту информацию, чтобы завершить процесс раньше, когда обнаруживаем, что отсутствует только последовательность a. Также исправлено регулярное выражение, которое было неверно в Chrome и 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");

Полный исполняемый фрагмент ниже.

Показать фрагмент кода

Arnauld
источник
«Короче говоря, вы должны написать функцию или программу, которые [...] восстанавливают S из этой информации и возвращают ее ».
КарлКастор
@KarlKastor - Упс. Ты прав. Это исправлено. Благодарность!
Арно
4

Python, 15205 звонков

def findS(S, len_s, alphabeth = "abc"):
    if len_s == 0:
        return ""
    current = ""
    add_at_start = True
    while len(current) < len_s:
        worked = False 
        for letter in alphabeth:
            if add_at_start:
                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:
            add_at_start = False
    return current

Это представление, скорее всего, неоптимально, поскольку оно использует только num_occurдля проверки, является ли строка подстрокой S, и никогда не использует ее для фактического подсчета количества подстрок.

Алгоритм работает, сохраняя строку, currentкоторая построена, чтобы быть равной Sв конце. Вот все шаги в алгоритме:

  1. Мы устанавливаем currentравным''

  2. Просмотрите каждую букву в алфавите и сделайте следующее:

    2.1. Создайте новую строку current_newи установите для нее значение, currentза которым следует буква.

    2.2. Проверьте, current_newвключен ли он S, запустив num_occurего, и посмотрите, будет ли результат больше единицы.

    2,3. Если current_newвключена в S, набор currentк current_newи вернуться к шагу 2. В противном случае, мы переходим к следующему письму.

  3. Если длина currentравна длине Sмы можем сказать, что мы сделали. Иначе, мы вернемся к шагу 2, но изменим шаг 2.1, чтобы сделать его current_newравным букве, за которой следует currentвместо. Когда мы снова достигаем этого шага, мы закончили.

Loovjo
источник
1
В цикле Python for есть еще условие. Это было бы идеальным вариантом использования для этого.
Якуб
4

Python 2, 14952 14754 звонков

Очень похоже на первый ответ, но не пробует следующие символы, которые приводят к невозможным подстрокам, которые:

  • мы знаем из того, num_occurчто они не встречаются в цели (из предыдущих вызовов)

  • мы уже использовали подстроку чаще, чем это происходит в соответствии с num_occur

(добавим подсчет подстрок за минуту) сделано

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"
inputs = urllib.urlopen(url).read().split("\n")
print "Check: ", inputs == map(lambda h: get_that_string(h, len(h)), inputs)
print "Calls: ", calls
KarlKastor
источник
4

Python 12705 12632 звонков

  1. составить список из 2 символов строк
  2. сортировать список
  3. сначала соберите строку, пытаясь найти наиболее вероятный символ, не проверяйте, есть ли только одна возможность
  4. обновить список
  5. если список пуст, он завершается еще шаг 2

Я использовал функцию скелета Loovjo. Я никогда не пишу в Python

РЕДАКТИРОВАТЬ:
Добавлен код для строк длиной в один символ
Добавлен код для отклонения уже сопоставленных образцов

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)

    add_at_start = True
    nomatch=[]
    while len(tuples) > 0:
            worked = False
            tuples.sort(key=lambda x:(-x[0],x[1]))
            count=0
            if not add_at_start :
                    for (n, s) in tuples :
                            if s[0]==current[-1:] :         count+=1
            for i in range(len(tuples)):
                    (n, s)=tuples[i]
                    if add_at_start:
                            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:
                    add_at_start = False
    return current
Эммануэль
источник
нет "cc" в вашем алфавите?
Спарр
@Sparr "cc" рассчитывается, это сохраняет 100 вызовов: `tuples.append ((len (S) -sum-1," cc "))`
Эммануил