Identifique uma sequência de caracteres de suas substrings

20

Introdução

Eu já criei dois desafios em que a idéia é reconstruir um objeto usando o menor número possível de operações do tipo consulta; este será o terceiro.

A tarefa

Suas entradas devem ser uma sequência não vazia Ssobre o alfabeto abce seu comprimento, e sua saída deve ser S. Sem restrições, isso seria uma tarefa trivial; O problema é que você não tem permissão para acessar Sdiretamente. A única coisa que você pode fazer Sé chamar a função num_occur(T, S), onde Testá outra string, e num_occurconta o número de ocorrências de Tin S. As ocorrências sobrepostas são contadas como distintas; portanto, num_occur(T, S)realmente retorna o número de índices, de imodo que

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

Por exemplo, num_occur("aba", "cababaababb")retornará 3. Observe também que num_occur(S, S)retornará 1. O resultado de num_occur("", S)é indefinido e você não deve chamar a função em uma sequência vazia.

Em resumo, você deve escrever uma função ou programa que aceite Se length(S)como entradas, chame num_occuralgumas seqüências mais curtas e Svárias vezes, reconstrua a Spartir dessas informações e as retorne.

Regras e pontuação

Seu objetivo é escrever um programa que faça o menor número num_occurpossível de chamadas . Em este repositório , você encontrará um arquivo chamado abc_strings.txt. O arquivo contém 100 strings, cada uma em sua própria linha, entre os comprimentos 50 e 99. Sua pontuação é o número total de chamadas para num_occuressas entradas , sendo a pontuação menor melhor. Sua solução preferencialmente acompanhará esse número enquanto ele é executado e o imprimirá após o término. As strings são geradas escolhendo letras uniformemente aleatórias de abc; você pode otimizar esse método de geração de cadeias, mas não as próprias cadeias.

Não há limite de tempo, exceto que você deve executar sua solução nos casos de teste antes de enviá-la. Sua solução deve funcionar para qualquer entrada válida S, não apenas para os casos de teste.

Você também deve compartilhar sua implementação num_occur, se não estiver usando outra pessoa. Para começar, aqui está uma implementação em 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
fonte
Nossos algoritmos precisam funcionar para todas as sequências possíveis Sou apenas para os casos de teste?
Loovjo 16/08
@Loovjo Boa pergunta. Teoricamente, eles devem funcionar para todas as strings não vazias. Vou editar o desafio.
Zgarb
all non-empty stringsde qualquer tamanho?
Edc65
@ edc65 Teoricamente sim. Você pode ignorar endereços de memória limitados e outras limitações práticas.
Zgarb
É possível adicionar um algoritmo de VW para passar no teste de avaliação com sucesso: Verifique primeiro para a ocorrência das cordas conhecidos de abc_strings.txt
Emmanuel

Respostas:

6

Javascript, 14325 14311 chamadas

Começamos com uma string vazia e seguimos recursivamente adicionando uma nova letra no final ou no início da string atual enquanto ainda temos pelo menos uma correspondência.

Todos os resultados anteriores numOccur()são salvos no symobjeto e usamos esses dados para rejeitar imediatamente qualquer nova sequência que não possa ser candidata.

EDIT : Como sempre começamos 'a', sempre sabemos o número exato de ana string. Usamos essas informações para finalizar o processo mais cedo, quando detectamos que apenas uma sequência de aestá faltando. Também foi corrigida a expressão regular inválida no Chrome e no 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");

Snippet executável completo abaixo.

Mostrar snippet de código

Arnauld
fonte
"Em resumo, você deve escrever uma função ou programa que [...] reconstrua S a partir dessa informação e a retorne ."
KarlKastor
@KarlKastor - Ops. Você está certo. Isso está consertado. Obrigado!
Arnauld
4

Python, 15205 chamadas

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

É provável que esse envio seja abaixo do ideal, porque ele só usa num_occurpara verificar se uma sequência é uma subcadeia de caracteres Se nunca a utiliza para contar a quantidade de subcadeias.

O algoritmo funciona armazenando uma string currentque é construída para ser igual a Sno final. Aqui estão todas as etapas do algoritmo:

  1. Definimos currentigual a''

  2. Percorra cada letra do alfabeto e faça o seguinte:

    2.1 Crie uma nova sequência current_newe defina-a como currentseguida pela letra.

    2.2 Verifique se current_newestá incluído Sexecutando num_occurnele e veja se o resultado é maior que um.

    2.3 Se current_newestiver incluído S, defina currentcomo current_newe volte para a etapa 2. Senão, vamos para a próxima letra.

  3. Se o comprimento de currentfor igual ao comprimento de S, podemos dizer que terminamos. Senão, voltamos à etapa 2, mas modificamos a etapa 2.1 para current_newigualar a letra seguida por current. Quando chegamos a esse passo novamente, terminamos.

Loovjo
fonte
1
O loop for do Python possui uma cláusula else. Este seria um caso de uso perfeito para isso.
Jakube 16/08
4

Python 2, 14952 14754 chamadas

Muito semelhante à primeira resposta, mas não tenta os próximos caracteres que resultam em substrings impossíveis que:

  • sabemos num_occurque eles não ocorrem no alvo (de chamadas anteriores)

  • já usamos a substring com mais frequência do que ocorre de acordo com num_occur

(adicionará a contagem de substrings em um minuto) feito

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
fonte
4

Python Chamadas do 12705 12632

  1. faça uma lista de ocorrências de 2 caracteres
  2. ordenar a lista
  3. construa a string tentando primeiro o caractere mais provável, não teste se há apenas uma possibilidade
  4. atualizar a lista
  5. se a lista estiver vazia, está concluída, caso contrário, etapa 2

Eu usei o esqueleto da função Loovjo. Eu nunca codifico em Python, eu precisava de um bootrap

EDIT:
Adicionado código para cadeias de comprimento de um caractere
Adicionado código para rejeitar padrões já correspondentes

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
Emmanuel
fonte
não há 'cc' no seu alfabeto?
Sparr
O @Sparr "cc" é calculado, economizando 100 chamadas: `tuples.append ((len (S) -sum-1," cc "))`
Emmanuel