Identifizieren Sie eine Zeichenfolge anhand ihrer Teilzeichenfolgen

20

Einführung

Ich habe zuvor zwei Herausforderungen erstellt, bei denen es darum geht, ein Objekt mit möglichst wenigen Abfragearten zu rekonstruieren. Dies wird der dritte sein.

Die Aufgabe

Ihre Eingaben müssen eine nicht leere Zeichenfolge Süber dem Alphabet abcund seiner Länge sein, und Ihre Ausgabe muss sein S. Ohne Einschränkungen wäre dies natürlich eine triviale Aufgabe. der Haken ist, dass Sie nicht Sdirekt zugreifen dürfen . Das Einzige, was Sie tun dürfen, Sist, die Funktion aufzurufen num_occur(T, S), wobei Tes sich um eine andere Zeichenfolge handelt, und num_occurdie Anzahl der Vorkommen von Tin zu zählen S. Überlappende Vorkommen werden als eindeutig gezählt, sodass num_occur(T, S)die Anzahl der Indizes tatsächlich iso zurückgegeben wird, dass

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

Zum Beispiel num_occur("aba", "cababaababb")wird zurückkehren 3. Beachten Sie auch, dass num_occur(S, S)zurückkehren wird 1. Das Ergebnis von num_occur("", S)ist undefiniert, und Sie sollten die Funktion nicht für eine leere Zeichenfolge aufrufen.

Kurz gesagt, Sie sollten eine Funktion oder ein Programm schreiben, die Sbzw. das length(S)als Eingaben verwendet, num_occureinige kürzere Zeichenfolgen und Seinige Male aufruft , Saus diesen Informationen rekonstruiert und diese zurückgibt.

Regeln und Wertung

Ihr Ziel ist es, ein Programm zu schreiben, das so wenig num_occurwie möglich aufruft . In diesem Repository finden Sie eine Datei namens abc_strings.txt. Die Datei enthält 100 Zeichenfolgen, jede in einer eigenen Zeile, mit einer Länge zwischen 50 und 99. Ihre Punktzahl gibt die Gesamtzahl der Anrufe num_occuran diesen Eingängen an , wobei eine niedrigere Punktzahl besser ist. Ihre Lösung protokolliert diese Nummer vorzugsweise während der Ausführung und druckt sie nach Abschluss aus. Die Zeichenfolgen werden durch Auswahl von gleichmäßig zufälligen Buchstaben generiert abc. Sie können für diese Methode zum Generieren der Zeichenfolgen optimieren, jedoch nicht für die Zeichenfolgen selbst.

Es gibt keine zeitliche Begrenzung, außer dass Sie Ihre Lösung für die Testfälle ausführen sollten, bevor Sie sie senden. Ihre Lösung sollte für alle gültigen Eingaben funktionieren S, nicht nur für die Testfälle.

Sie werden ermutigt, auch Ihre Implementierung num_occurmitzuteilen, wenn Sie nicht die einer anderen Person verwenden. Um den Ball ins Rollen zu bringen, folgt eine Implementierung 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
string fewest-operations Zgarb
quelle
Müssen unsere Algorithmen für alle möglichen Zeichenfolgen Soder nur für die Testfälle funktionieren ?
Loovjo
@ Loovjo Gute Frage. Sie sollten theoretisch für alle nicht leeren Zeichenfolgen funktionieren. Ich werde die Herausforderung bearbeiten.
Zgarb
all non-empty stringsvon welcher Länge?
Edc65
@ edc65 Theoretisch ja. Sie können begrenzte Speicheradressen und andere praktische Einschränkungen ignorieren.
Zgarb
Es ist möglich, einen VW-Algorithmus hinzuzufügen, um den Bewertungstest mit Erfolg zu bestehen: Überprüfen Sie zuerst, ob die bekannten Zeichenfolgen von abc_strings.txt
Emmanuel

Antworten:

6

Javascript, 14325 14311 Anrufe

Wir beginnen mit einer leeren Zeichenfolge und gehen unseren Weg rekursiv, indem wir am Ende oder am Anfang der aktuellen Zeichenfolge einen neuen Buchstaben einfügen, solange wir noch mindestens eine Übereinstimmung haben.

Alle vorherigen Ergebnisse von numOccur()werden im symObjekt gespeichert und wir verwenden diese Daten, um neue Zeichenfolgen, die möglicherweise kein Kandidat sein können, sofort abzulehnen.

EDIT : Da wir immer mit beginnen 'a', kennen wir immer die genaue Anzahl ain der Zeichenfolge. Wir verwenden diese Informationen, um den Prozess früher zu beenden, wenn wir feststellen, dass nur eine Sequenz von afehlt. Außerdem wurde der reguläre Ausdruck behoben, der in Chrome und IE ungültig war.

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");

Vollständiges ausführbares Snippet unten.

Code-Snippet anzeigen

Arnauld
quelle
"Kurz gesagt, Sie sollten eine Funktion oder ein Programm schreiben, [...] das S aus diesen Informationen rekonstruiert und zurückgibt ."
KarlKastor
@ Karl Kastor - Ups. Du hast recht. Das ist behoben. Vielen Dank!
Arnauld
4

Python, 15205 Anrufe

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

Diese Übermittlung ist höchstwahrscheinlich suboptimal, da sie nur verwendet wird num_occur, um zu überprüfen, ob eine Zeichenfolge eine Teilzeichenfolge ist S, und sie wird niemals verwendet, um die Anzahl der Teilzeichenfolgen tatsächlich zu zählen.

Der Algorithmus speichert einen String, currentder so aufgebaut ist, dass er Sam Ende gleich ist. Hier sind alle Schritte des Algorithmus:

  1. Wir setzen currentgleich''

  2. Gehen Sie jeden Buchstaben im Alphabet durch und gehen Sie folgendermaßen vor:

    2.1. Erstellen Sie eine neue Zeichenfolge current_newund setzen Sie sie gleich, currentgefolgt von dem Buchstaben.

    2.2. Überprüfen Sie, ob current_newin enthalten ist, Sindem Sie darauf ausführen num_occur, und prüfen Sie, ob das Ergebnis größer als eins ist.

    2.3. Wenn current_newin enthalten ist S, setzen Sie currentauf current_newund fahren Sie mit Schritt 2 fort. Anderenfalls fahren wir mit dem nächsten Buchstaben fort.

  3. Wenn die Länge von currentgleich der Länge von ist S, können wir sagen, dass wir fertig sind. Andernfalls kehren wir zu Schritt 2 zurück, ändern jedoch Schritt 2.1, um current_newdem Buchstaben zu entsprechen, gefolgt von current. Wenn wir diesen Schritt wieder erreichen, sind wir fertig.

Loovjo
quelle
1
Die for-Schleife von Python enthält eine else-Klausel. Dies wäre ein perfekter Anwendungsfall dafür.
Jakube
4

Python 2, 14952 14754 Anrufe

Sehr ähnlich der ersten Antwort, aber es werden keine weiteren Zeichen ausprobiert, was zu unmöglichen Teilzeichenfolgen führt, die:

  • wir wissen, num_occurdass sie nicht im Ziel vorkommen (aus früheren Aufrufen)

  • wir haben den Teilstring schon öfter benutzt, als es laut vorkommt num_occur

(wird das Zählen von Teil in einer Minute hinzufügen) getan

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

Python 12705 12632 Anrufe

  1. Erstellen Sie eine Liste mit 2 Zeichenfolgen, die vorkommen
  2. sortiere die Liste
  3. Erstellen Sie den String mit dem wahrscheinlichsten Zeichen zuerst. Testen Sie nicht, ob es nur eine Möglichkeit gibt
  4. Aktualisieren Sie die Liste
  5. Wenn die Liste leer ist, ist sie fertig, ansonsten Schritt 2

Ich habe das Loovjo-Funktionsskelett verwendet. Ich habe nie in Python programmiert. Ich brauchte einen Bootsrap

BEARBEITEN:
Code für Strings mit einer Zeichenlänge hinzugefügt. Code
hinzugefügt, um bereits übereinstimmende Muster abzulehnen

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
quelle
nein 'cc' in deinem alphabet?
Sparr
@Sparr "cc" wird berechnet, das spart 100 Aufrufe: `tuples.append ((len (S) -sum-1," cc "))`
Emmanuel