Introducción

En este desafío, su tarea es encontrar subsecuencias generalizadas de cadenas. Las subsecuencias no son necesariamente contiguas, y también pueden "envolver" la cadena, pasando su final y comenzando de nuevo desde el principio. Sin embargo, querrás minimizar la cantidad de envolturas.

Más formalmente, deja uy vser dos cuerdas, y k ≥ 0un número entero. Decimos que ues una ksubsecuencia de ajuste de v, si hay índices distintos de ese tipo , y como máximo satisfacen los índices . Esto significa que se puede encontrar en el interior yendo de izquierda a derecha, eligiendo algunos de sus personajes en el camino y envolviéndose en la mayoría de las veces (de manera equivalente, haciendo como máximo barridos ). Tenga en cuenta que no se puede elegir ningún personaje más de una vez, incluso después de un ajuste, y que las subsecuencias de ajuste son exactamente las subsecuencias ordinarias con las que todos estamos familiarizados.i1, i2, ..., ilen(u)u == v[i1] v[i2] ... v[ilen(u)]kijij > ij+1uvkk+1v0

La tarea

Sus entradas son dos cadenas alfanuméricas uy no vacías v, y su salida es el entero más pequeño k, que ues una ksubsecuencia de ajuste de v. Si no kexiste tal , la salida será -1.

Ejemplo

Considere las entradas u := xyzyxzzxyxy v := yxzzazzyxxxyz. Si partimos en busca de los personajes de uen vde una manera codiciosa, vamos a envolver alrededor de 3 veces:

 yxzzazzyxxxyz
>─x─────y────z┐
┌─────────────┘
└y───────x────┐
┌─────────────┘
└──zz─────x─y─┐
┌─────────────┘
└──────────x──>

Por lo tanto, la salida correcta es como máximo 3. Observe cómo xse selecciona el carácter más a la izquierda una vez, y luego se ignora en el segundo barrido, ya que no se puede reutilizar. Sin embargo, existe un método más corto con solo 2 envolturas:

 yxzzazzyxxxyz
>──────────xyz┐
┌─────────────┘
└yxzz────x────┐
┌─────────────┘
└───────y─x───>

Resulta que una envoltura (es decir, dos barridos) no es suficiente, por lo que la salida correcta es 2.

Reglas y bonos

Puede escribir una función o un programa completo, y también puede cambiar el orden de las entradas si es necesario. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Hay una bonificación de -10% para calcular todos los casos de prueba en menos de 10 segundos en total. Probaré casos poco claros en mi máquina; Mi implementación de referencia en Python toma alrededor de 0.6 segundos. Tengo una computadora portátil de 7 años con una CPU de doble núcleo de 1.86 GHz, que es posible que desee tener en cuenta.

Casos de prueba

"me" "moe" -> 0
"meet" "metro" -> -1
"ababa" "abaab" -> 1
"abaab" "baabaa" -> 1
"1c1C1C2B" "1111CCCcB2" -> 3
"reverse" "reserved" -> 2
"abcdefg" "gfedcba" -> 6
"xyzyxzzxyx" "yxzzazzyxxxyz" -> 2
"aasdffdaasdf" "asdfddasdfsdaafsds" -> 2

Pyth, 34 bytes

Mh+Smssm>.ukC,[email protected]_1

Esto define una función g, que toma dos cadenas como parámetro. Pruébelo en línea: Pyth Compiler / Executor

Este código es muy ineficiente. Tiene una complejidad de tiempo y memoria de len(v)!/(len(v)-len(u))!. No puede resolver los casos de prueba más largos en menos de 10 segundos. (También se bloqueará muy probablemente, ya que se quedará sin memoria).

M                                    define g(G, H): return _
                          .PUHlG        all permutations of [0, 1, ..., len(H)-1] of length len(G)
                 fqGsm@HkT              filter the permutations which form the string G
    mssm>.ukC,dtd                       compute the number of wraps for each of the remaining permutations
  +S                            _1      sort the numbers and append -1
 h                                      return the first element

Haskell, 160 * 0.9 = 144 bytes

a#(-1)=a
a#b=min a b
f y=w(y++" ")0$length y
w _ n _[]=n
w(c:d)n o g@(a:b)|n>o=(-1)|a==c=z#w y n z g|c==' '=w y(n+1)o g|1<2=w y n o g where z=w d n o b;y=d++[c]

Tiempo para todos los casos de prueba (nota: se invierten los argumentos):

*Main> map (uncurry f) [
             ("moe", "me"),
             ("metro", "meet"),
             ("abaab", "ababa"),
             ("baabaa", "abaab"),
             ("1111CCCcB2", "1c1C1C2B"),
             ("reserved", "reverse"),
             ("gfedcba", "abcdefg"),
             ("yxzzazzyxxxyz", "xyzyxzzxyx"),
             ("asdfddasdfsdaafsds", "aasdffdaasdf")]
[0,-1,1,1,3,2,6,2,2]
(0.08 secs, 25794240 bytes)

Cómo funciona (versión corta): fuerza bruta simple que requiere el mínimo uso de un personaje coincidente y omitirlo. Paro la búsqueda cuando finalizo (devolviendo el número de ciclos) o cuando hice un ciclo más que el mínimo hasta ahora (devolviendo -1).

Ahorré muchos bytes en comparación con mi primera versión, principalmente porque cambié de un programa completo a una función.

Con algunos comentarios y un espaciado adecuado, Haskell es bastante legible:

-- a minimum function that ignores a -1 in the right argument to prevent
-- "not solvable" cases in parts of the recursive search to dominate low numbers
-- of solvable parts. If the case isn't solvabale at all, both arguments are
-- -1 and are carried on.
a # (-1) = a
a # b    = min a b

-- the main function f calls the worker funktion w with arguments
-- * the string to search in (STSI), appended by a space to detect cycles
-- * the number of cycles so far
-- * the minimum of cycles needed so far, starting with the length of STSI
-- * the string to search for (STSF) (partial applied away and therefore invisible)
f y = w (y++" ") 0 (length y)

-- the worker function 
w _ n _ [] = n          -- base case: if STSF is empty the work is done and the 
                        -- number of cycles is returned

w (c:d) n o g@(a:b)     -- "c" is first char of STSI, "d" the rest
                        -- "n" number of cycles, "o" minimum of cycles so far
                        -- "g" is the whole STSF, "a" the 1st char, "b" the rest
  | n>o    = (-1)             -- if current cycle is more than a previous result,
                              -- indicate failure
  | a==c   = z # w y n z g    -- if there's a character match, take the min of
                              -- using it and skipping it
  | c==' ' = w y (n+1) o g    -- cycle detected, repeat and adjust n
  | 1<2    = w y n o g        -- otherwise try next char in STSI

  where                 -- just some golfing: short names for common subexpressions
  z = w d n o b;        -- number of cycles if a matching char is used
  y = d ++ [c]          -- rotated STSI

Para referencia: versión anterior, programa completo, 187 bytes

main=interact$show.f.lines
a#(-1)=a
a#b=min a b
f[x,y]=w x(y++" ")0 0
w[]_ n _=n
w g@(a:b)(c:d)n m|a==c=w b d n 1#y|c==' '&&m==1=w g(d++" ")(n+1)0|c==' '=(-1)|1<2=y where y=w g(d++[c])n m

JavaScript (ES6) 174 (193 - 10%)

Búsqueda recursiva, como la respuesta de @ nimi, manteniendo el mínimo de envolturas. El espacio de soluciones es grande (sobre todo para el último ejemplo), pero cortar la búsqueda en el mínimo encontrado actualmente mantiene el tiempo bajo. Editar 1 Agregar un caso de prueba faltante, acortar un poco Editar 2 No es necesario pasar el parámetro w, está solucionado

K=(w,s,x)=>
  ~-(R=(r,l,p=0,q=1,z=w[p],i=0)=>
  {
    if(z&&!(q>x)){
      if(~(r+l).indexOf(z))
        for(t=l?R(l+r,'',p,q+1):x;x<t?0:x=t,i=~r.indexOf(z,-i);)
          t=R(r.slice(-i),l+r.slice(0,~i),p+1,q);
      q=x
    }
    return q
  })(s,'')

Sin golf

K=(word, astring)=>
{
  var minWraps // undefined at first. All numeric comparison with undefined give false 
  var R=(right, left, pos, wraps)=>
  {
    var cur = word[pos]
    var i,t;
    if (! cur) // when all chars of word are managed
      return wraps;
    if (wraps > minWraps) // over the minimum wrap count already found, stop search
      return wraps; 
    if ( (right+left).indexOf(cur) < 0 ) // if the current char is not found in the remaining part of the string
      return minWraps; // return the current min, could still be undefined (that means 'no way')
    if ( left ) // if there is a left part, try a wrapping search with the current char
    {
      t = R(left+right, '', pos, wraps+1)
      if ( !(minWraps < t)) minWraps = t; // set current min if t is less than current min or current min is still undefined
    }
    // find all occurrences of current char in the remaining part
    // for each occurrence, start a recursive search for the next char
    for(i = 0; (i = right.indexOf(cur, i)) >= 0; i++)
    {
      var passed = right.slice(0,i) // the passed chars go in the left part
      var rest = right.slice(i+1) 
      t = R(rest, left+passed, pos+1, wraps) // try next char in the remaining part, no wrap
      if ( !(minWraps < t)) minWraps = t; // set current min if t is less than current min or current min is still undefined
    }
    return minWraps
  }
  var result = R(astring, '', 0, 1) // start with right=string and left empty
  return ~-result; // decrement. convert undefined to -1
}

Prueba en la consola Firefox / FireBug

time=~new Date;
[['me','moe']
,['meet','metro']
,['ababa','abaab']
,['abaab','baabaa']
,['1c1C1C2B','1111CCCcB2']
,['reverse','reserved']
,['abcdefg','gfedcba']
,['xyzyxzzxyx','yxzzazzyxxxyz']
,['aasdffdaasdf','asdfddasdfsdaafsds']]
.forEach(s=>console.log(s,r=K(...s)))
time-=~new Date

Salida (la última línea es el tiempo de ejecución en ms)

["yo", "moe"] 0
["conocer", "metro"] -1
["ababa", "abaab"] 1
["abaab", "baabaa"] 1
["1c1C1C2B", "1111CCCcB2"] 3
["reverso", "reservado"] 2
["abcdefg", "gfedcba"] 6
["xyzyxzzxyx", "yxzzazzyxxxyz"] 2
["aasdffdaasdf", "asdfddasdfsdaafsds"] 2
116