Identifier une chaîne de ses sous-chaînes

20

introduction

J'ai déjà créé deux défis où l'idée est de reconstruire un objet en utilisant le moins possible d'opérations de type requête; ce sera le troisième.

La tâche

Vos entrées doivent être une chaîne non vide Ssur l'alphabet abcet sa longueur, et votre sortie doit l'être S. Sans aucune restriction, ce serait bien sûr une tâche insignifiante; le hic, c'est que vous n'êtes pas autorisé à accéder Sdirectement. La seule chose que vous êtes autorisé à faire Sest d'appeler la fonction num_occur(T, S), où se Ttrouve une autre chaîne, et num_occurcompte le nombre d'occurrences de Tin S. Les occurrences qui se chevauchent sont comptées comme distinctes, donc num_occur(T, S)renvoie vraiment le nombre d'indices itels que

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

Par exemple, num_occur("aba", "cababaababb")reviendra 3. Notez également que num_occur(S, S)cela reviendra 1. Le résultat de num_occur("", S)n'est pas défini et vous ne devez pas appeler la fonction sur une chaîne vide.

En bref, vous devez écrire une fonction ou un programme qui prend Set length(S)comme entrées, appelle num_occurdes chaînes plus courtes et Sun certain nombre de fois, reconstruit à Spartir de ces informations et les renvoie.

Règles et notation

Votre objectif est d'écrire un programme qui appelle le moins d'appels num_occurpossible. Dans ce référentiel , vous trouverez un fichier appelé abc_strings.txt. Le fichier contient 100 chaînes, chacune sur sa propre ligne, entre les longueurs 50 et 99. Votre score est le nombre total d'appels vers num_occurces entrées , un score plus bas étant meilleur. Votre solution conservera de préférence ce numéro pendant son exécution et l'imprimera à la fin. Les chaînes sont générées en choisissant des lettres uniformément aléatoires parmi abc; vous êtes autorisé à optimiser pour cette méthode de génération des chaînes, mais pas les chaînes elles-mêmes.

Il n'y a pas de limite de temps, sauf que vous devez exécuter votre solution sur les cas de test avant de la soumettre. Votre solution doit fonctionner pour toute entrée valide S, pas seulement pour les cas de test.

num_occurNous vous encourageons à partager votre mise en œuvre de trop, si vous n'utilisez pas quelqu'un d'autre. Pour démarrer, voici une implémentation en 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
la source
Nos algorithmes doivent-ils fonctionner pour toutes les chaînes possibles S, ou seulement pour les cas de test?
Loovjo
@Loovjo Bonne question. Ils devraient théoriquement fonctionner pour toutes les chaînes non vides. Je vais éditer le défi.
Zgarb
all non-empty stringsquelle que soit la longueur?
edc65
@ edc65 Théoriquement oui. Vous pouvez ignorer les adresses mémoire limitées et d'autres limitations pratiques.
Zgarb
Il est possible d'ajouter un algorithme VW pour réussir le test d'évaluation avec succès: Vérifiez d'abord l'occurrence des chaînes connues de abc_strings.txt
Emmanuel

Réponses:

6

Javascript, 14325 14311 appels

Nous commençons avec une chaîne vide et nous reprenons notre chemin de manière récursive en ajoutant une nouvelle lettre à la fin ou au début de la chaîne actuelle alors que nous avons encore au moins une correspondance.

Tous les résultats précédents numOccur()sont enregistrés dans l' symobjet et nous utilisons ces données pour rejeter immédiatement toute nouvelle chaîne qui ne peut éventuellement pas être candidate.

EDIT : Parce que nous commençons toujours par 'a', nous connaissons toujours le nombre exact de adans la chaîne. Nous utilisons ces informations pour terminer le processus plus tôt lorsque nous détectons qu'il ne amanque qu'une séquence de . Correction également de l'expression régulière qui n'était pas valide dans Chrome et 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");

Extrait exécutable complet ci-dessous.

Afficher l'extrait de code

Arnauld
la source
"En bref, vous devez écrire une fonction ou un programme qui [...], reconstruit S à partir de ces informations et les renvoie ."
KarlKastor
@KarlKastor - Oups. Tu as raison. C'est fixe. Merci!
Arnauld
4

Python, 15205 appels

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

Cette soumission est très probablement sous-optimale, car elle utilise uniquement num_occur qu'à vérifier si une chaîne est une sous-chaîne de S, et elle ne l'utilise jamais pour réellement compter la quantité de sous-chaînes.

L'algorithme fonctionne en stockant une chaîne current qui est construite pour être égale à Sla fin. Voici toutes les étapes de l'algorithme:

  1. Nous fixons current égal à''

  2. Parcourez chaque lettre de l'alphabet et procédez comme suit:

    2.1. Créez une nouvelle chaîne current_newet définissez-la égale àcurrent suivie de la lettre.

    2.2. Vérifiez si current_newest inclus dans Sen exécutantnum_occur dessus et voyez si le résultat est supérieur à un.

    2.3. Si current_newest inclus dans S, ensemble currentà current_newet revenir à l' étape 2. Sinon, nous allons à la lettre suivante.

  3. Si la longueur de currentest égale à la longueur de Snous pouvons dire que nous avons terminé. Sinon, nous revenons à l'étape 2, mais modifions l'étape 2.1 pour qu'elle soit current_newégale à la lettre suivie par à la currentplace. Lorsque nous atteignons à nouveau cette étape, nous avons terminé.

Loovjo
la source
1
La boucle for de Python a une clause else. Ce serait un cas d'utilisation parfait pour cela.
Jakube
4

Appels Python 2, 14952 14754

Très similaire à la première réponse, mais n'essaie pas les caractères suivants, ce qui entraîne des sous-chaînes impossibles qui:

  • nous savons num_occurqu'ils ne se produisent pas dans la cible (des appels précédents)

  • nous avons déjà utilisé la sous-chaîne plus souvent qu'elle ne se produit selon num_occur

(ajoutera le comptage des sous-chaînes dans une minute) fait

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
la source
4

Appels Python 12705 12632

  1. faire une liste de 2 occurrences de chaînes de caractères
  2. trier la liste
  3. construisez la chaîne en essayant d'abord le caractère le plus probable, ne testez pas s'il n'y a qu'une seule possibilité
  4. mettre à jour la liste
  5. si la liste est vide c'est fini sinon étape 2

J'ai utilisé le squelette de la fonction Loovjo. Je n'ai jamais codé en Python, j'avais besoin d'une botte

EDIT:
Code ajouté pour les chaînes de longueur d'un caractère
Code ajouté pour rejeter les modèles déjà appariés

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
la source
pas de «cc» dans votre alphabet?
Sparr
@Sparr "cc" est calculé, ce qui économise 100 appels: `tuples.append ((len (S) -sum-1," cc "))`
Emmanuel