Identificar una cadena de sus subcadenas.

20

Introducción

Anteriormente he creado dos desafíos en los que la idea es reconstruir un objeto utilizando la menor cantidad posible de operaciones de tipo consulta; Este será el tercero.

La tarea

Sus entradas serán una cadena no vacía Ssobre el alfabeto abcy su longitud, y su salida será S. Sin restricciones, esto sería, por supuesto, una tarea trivial; El problema es que no se te permite acceder Sdirectamente. Lo único que puede hacer Ses llamar a la función num_occur(T, S), donde Thay alguna otra cadena, y num_occurcontar el número de ocurrencias de Tin S. Las ocurrencias superpuestas se cuentan como distintas, por lo que num_occur(T, S)realmente devuelve el número de índices de imanera que

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

Por ejemplo, num_occur("aba", "cababaababb")volveremos 3. Tenga en cuenta también que num_occur(S, S)volverá 1. El resultado de num_occur("", S)no está definido y no debe llamar a la función en una cadena vacía.

En resumen, debe escribir una función o programa que tome Sy length(S)como entradas, invoque num_occuralgunas cadenas más cortas y Salgunas veces, reconstruya a Spartir de esa información y la devuelva.

Reglas y puntaje

Su objetivo es escribir un programa que haga la menor cantidad de llamadas num_occurposible. En este repositorio , encontrará un archivo llamado abc_strings.txt. El archivo contiene 100 cadenas, cada una en su propia línea, entre las longitudes 50 y 99. Su puntaje es el número total de llamadas a num_occurestas entradas , siendo menor el puntaje menor. Preferiblemente, su solución realizará un seguimiento de este número a medida que se ejecuta e imprimirá al finalizar. Las cadenas se generan al elegir letras aleatoriamente uniformes de abc; puede optimizar para este método de generación de cadenas, pero no las cadenas en sí.

No hay límite de tiempo, excepto que debe ejecutar su solución en los casos de prueba antes de enviarla. Su solución debería funcionar para cualquier entrada válida S, no solo para los casos de prueba.

Le recomendamos que también comparta su implementación num_occur, si no está usando la de otra persona. Para que la pelota ruede, aquí hay una implementación 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
fuente
¿Nuestros algoritmos tienen que funcionar para todas las cadenas posibles S, o solo para los casos de prueba?
Loovjo
@Loovjo Buena pregunta. Teóricamente deberían funcionar para todas las cadenas no vacías. Editaré el desafío.
Zgarb
all non-empty stringsde cualquier longitud?
edc65
@ edc65 Teóricamente sí. Puede ignorar las direcciones de memoria limitadas y otras limitaciones prácticas.
Zgarb
Es posible agregar un algoritmo VW para pasar la prueba de evaluación con éxito: primero verifique la aparición de las cadenas conocidas de abc_strings.txt
Emmanuel

Respuestas:

6

Javascript, 14325 14311 llamadas

Comenzamos con una cadena vacía y seguimos nuestro camino de manera recursiva agregando una nueva letra al final o al comienzo de la cadena actual mientras todavía tenemos al menos una coincidencia.

Todos los resultados anteriores numOccur()se guardan en el symobjeto y usamos estos datos para rechazar inmediatamente cualquier nueva cadena que no pueda ser candidata.

EDITAR : Debido a que siempre comenzamos con 'a', siempre sabemos el número exacto de aen la cadena. Utilizamos esta información para finalizar el proceso antes cuando detectamos que solo afalta una secuencia de . También se corrigió la expresión regular que no era válida en Chrome e 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");

Fragmento ejecutable completo a continuación.

Mostrar fragmento de código

Arnauld
fuente
"En resumen, debe escribir una función o programa que [...] reconstruya S a partir de esa información y la devuelva ".
KarlKastor
@KarlKastor: ¡Vaya! Tienes razón. Eso está arreglado. ¡Gracias!
Arnauld
4

Python, 15205 llamadas

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

Es muy probable que este envío sea subóptimo, porque solo se usa num_occurpara verificar si una cadena es una subcadena S, y nunca la usa para contar la cantidad de subcadenas.

El algoritmo funciona almacenando una cadena currentque se construye para que sea igual al Sfinal. Aquí están todos los pasos en el algoritmo:

  1. Ponemos currentigual a''

  2. Revisa cada letra del alfabeto y haz lo siguiente:

    2.1. Cree una nueva cadena current_newy configúrela igual a currentseguida de la letra.

    2.2. Verifique si current_newestá incluido Sejecutándolo num_occury vea si el resultado es mayor que uno.

    2.3. Si current_newse incluye en S, conjunto currenta current_newy volver al paso 2. Si no, vamos a la siguiente letra.

  3. Si la longitud de currentes igual a la longitud de Spodemos decir que hemos terminado. De lo contrario, volvemos al paso 2, pero modificamos el paso 2.1 para que sea current_newigual a la letra seguida en su currentlugar. Cuando alcanzamos este paso de nuevo, hemos terminado.

Loovjo
fuente
1
El bucle for de Python tiene una cláusula else. Este sería un caso de uso perfecto para ello.
Jakube
4

Python 2, 14952 14754 llamadas

Muy similar a la primera respuesta, pero no prueba los siguientes caracteres que resultan en subcadenas imposibles que:

  • sabemos num_occurque no ocurren en el objetivo (de llamadas anteriores)

  • ya usamos la subcadena con más frecuencia de lo que ocurre de acuerdo con num_occur

(agregará el recuento de subcadenas en un minuto) hecho

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

Python 12705 12632 llamadas

  1. hacer una lista de ocurrencias de cadenas de 2 caracteres
  2. ordenar la lista
  3. construya la cadena probando primero el carácter más probable, no pruebe si solo hay una posibilidad
  4. actualizar la lista
  5. si la lista está vacía, está terminada; de lo contrario, paso 2

Usé el esqueleto de la función Loovjo. Nunca codifiqué en Python, necesitaba un arranque

EDITAR:
Código agregado para cadenas de longitud de un carácter
Código agregado para rechazar patrones ya coincidentes

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
fuente
no 'cc' en tu alfabeto?
Sparr
@Sparr "cc" se calcula, eso ahorra 100 llamadas: `tuples.append ((len (S) -sum-1," cc "))`
Emmanuel