Zidentyfikuj ciąg z jego podciągów

20

Wprowadzenie

Wcześniej stworzyłem dwa wyzwania, w których pomysł polega na rekonstrukcji obiektu przy użyciu jak najmniejszej liczby operacji typu zapytania; to będzie trzeci.

Zadanie

Twoje dane wejściowe będą niepustym ciągiem znaków Sna alfabecie abci jego długości, a twój wynik będzie S. Bez ograniczeń byłoby to oczywiście trywialne zadanie; haczykiem jest to, że nie masz Sbezpośredniego dostępu . Jedyne, co możesz zrobić, Sto wywołać funkcję num_occur(T, S), gdzie Tjest jakiś inny ciąg znaków i num_occurzlicza liczbę wystąpień Tin S. Nakładające się wystąpienia są liczone jako odrębne, więc num_occur(T, S)naprawdę zwraca liczbę itakich wskaźników , że

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

Na przykład num_occur("aba", "cababaababb")wróci 3. Zauważ też, że num_occur(S, S)powróci 1. Wynik num_occur("", S)jest niezdefiniowany i nie powinieneś wywoływać funkcji na pustym ciągu.

Krótko mówiąc, powinieneś napisać funkcję lub program, który pobiera Si length(S)jako dane wejściowe wywołuje num_occurniektóre krótsze ciągi znaków i Skilka razy, rekonstruuje Ste informacje i zwraca je.

Zasady i punktacja

Twoim celem jest napisanie programu, który wykona jak najmniej wywołań num_occur. W tym repozytorium znajdziesz plik o nazwie abc_strings.txt. Plik zawiera 100 ciągów znaków, każdy na osobnej linii, o długości od 50 do 99. Twój wynik to łączna liczba wywołań num_occurna tych wejściach , przy czym niższy wynik jest lepszy. Twoje rozwiązanie najlepiej będzie śledzić tę liczbę podczas jej drukowania i drukuje ją po zakończeniu. Ciągi znaków są generowane przez wybranie równomiernie losowych liter abc; możesz optymalizować tę metodę generowania ciągów, ale nie same ciągi.

Nie ma limitu czasu, z wyjątkiem tego, że powinieneś uruchomić swoje rozwiązanie na przypadkach testowych przed jego przesłaniem. Twoje rozwiązanie powinno działać dla każdego ważnego wejścia S, nie tylko dla przypadków testowych.

Zachęcamy również do udostępnienia swojej implementacji num_occur, jeśli nie korzystasz z cudzej. Aby rzucić piłkę, oto implementacja w Pythonie:

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
źródło
Czy nasze algorytmy muszą działać dla wszystkich możliwych ciągów S, czy tylko dla przypadków testowych?
Loovjo,
@Loovjo Dobre pytanie. Powinny teoretycznie działać dla wszystkich niepustych ciągów. Zmienię wyzwanie.
Zgarb,
all non-empty stringsjakiejkolwiek długości?
edc65,
@ edc65 Teoretycznie tak. Możesz zignorować ograniczone adresy pamięci i inne praktyczne ograniczenia.
Zgarb
Możliwe jest dodanie algorytmu VW, aby pomyślnie przejść test oceny: Najpierw sprawdź występowanie znanych ciągów abc_strings.txt
Emmanuel

Odpowiedzi:

6

JavaScript, 14325 14311 połączeń

Zaczynamy od pustego ciągu i idziemy rekurencyjnie, dodając nową literę na końcu lub na początku bieżącego ciągu, dopóki nadal mamy co najmniej jedno dopasowanie.

Wszystkie poprzednie wyniki z numOccur()są zapisywane w symobiekcie i używamy tych danych do natychmiastowego odrzucenia każdego nowego ciągu, który nie może być kandydatem.

EDYCJA : Ponieważ zawsze zaczynamy od 'a', zawsze znamy dokładną liczbę aw ciągu. Używamy tych informacji, aby zakończyć proces wcześniej, gdy wykryjemy, że abrakuje tylko sekwencji . Naprawiono także wyrażenie regularne, które było niepoprawne w Chrome i 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");

Poniżej znajduje się pełny plik wykonywalny.

Pokaż fragment kodu

Arnauld
źródło
„Krótko mówiąc, powinieneś napisać funkcję lub program, który [...] rekonstruuje S z tych informacji i zwraca je .”
KarlKastor,
@KarlKastor - Ups. Masz rację. To naprawione. Dzięki!
Arnauld,
4

Połączenia w języku 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

To przesłanie jest najprawdopodobniej nieoptymalne, ponieważ używa tylko num_occurdo sprawdzenia, czy ciąg znaków jest podciągiem S, i nigdy nie używa go do zliczania ilości podciągów.

Algorytm działa poprzez przechowywanie łańcucha, currentktóry jest zbudowany tak, aby był równy Sna końcu. Oto wszystkie kroki algorytmu:

  1. Ustalamy currentrówne''

  2. Przejrzyj każdą literę alfabetu i wykonaj następujące czynności:

    2.1 Utwórz nowy ciąg znaków current_newi ustaw go tak, aby currentnastępował po nim litera.

    2.2 Sprawdź, czy current_newjest uwzględniony S, uruchamiając num_occurgo i sprawdź, czy wynik jest większy niż jeden.

    2.3 Jeśli current_newjest włączone S, zestaw currentdo current_newi wróć do kroku 2. Else, idziemy do następnego listu.

  3. Jeśli długość currentjest równa długości S, możemy powiedzieć, że skończyliśmy. W przeciwnym razie wracamy do kroku 2, ale modyfikujemy krok 2.1, aby był current_newrówny literze, po której następuje current. Kiedy ponownie osiągniemy ten krok, jesteśmy skończeni.

Loovjo
źródło
1
Pythonowa pętla for ma klauzulę else. Byłby to idealny przypadek użycia.
Jakube
4

Połączenia w języku Python 2, 14952 14754

Bardzo podobny do pierwszej odpowiedzi, ale nie próbuje następnych znaków, co powoduje niemożliwe podciągi, które:

  • wiemy z num_occurtego, że nie występują w celu (z poprzednich połączeń)

  • używaliśmy już podciągów częściej niż to wynika z num_occur

(doda liczenie podciągów za minutę) gotowe

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
źródło
4

Połączenia w języku Python 12705 12632

  1. sporządzić listę wystąpień ciągów 2 znaków
  2. posortuj listę
  3. najpierw zbuduj ciąg, próbując najbardziej prawdopodobnego znaku, nie sprawdzaj, czy jest tylko jedna możliwość
  4. zaktualizuj listę
  5. jeśli lista jest pusta, kończy się w innym kroku 2

Użyłem szkieletu funkcji Loovjo. Nigdy nie piszę w Pythonie. Potrzebowałem bootrapu

EDYCJA:
Dodano kod dla ciągów o długości jednego znaku
Dodano kod, aby odrzucić już dopasowane wzorce

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
źródło
brak „cc” w twoim alfabecie?
Sparr
@Sparr "cc" oblicza się, że to oszczędność 100 połączeń: `tuples.append ((len (S) -sum-1, "cc"))`
Emmanuel