Einführung

Bei dieser Herausforderung besteht Ihre Aufgabe darin, verallgemeinerte Teilfolgen von Zeichenfolgen zu finden. Die Teilsequenzen sind nicht unbedingt zusammenhängend, und sie können die Zeichenfolge auch "umwickeln", über ihr Ende hinausgehen und von vorne beginnen. Sie sollten jedoch die Anzahl der Wraps minimieren.

Formal lassen uund valle zwei Saiten, und sein k ≥ 0eine ganze Zahl. Wir sagen, dass dies ueine kumhüllende Folge von ist v, wenn es unterschiedliche Indizes gibt, so dass und höchstens die Indizes erfüllen . Dies bedeutet, dass man das Innere finden kann, indem man von links nach rechts geht, einige seiner Charaktere auf dem Weg auswählt und sich meistens umhüllt (äquivalent, höchstens überstrichen ). Beachten Sie, dass selbst nach einem Wrap-Around kein Zeichen mehr als einmal ausgewählt werden kann und dass -wrapping-Teilsequenzen genau die gewöhnlichen Teilsequenzen sind, mit denen wir alle vertraut sind.i1, i2, ..., ilen(u)u == v[i1] v[i2] ... v[ilen(u)]kijij > ij+1uvkk+1v0

Die Aufgabe

Ihre Eingaben sind zwei nicht leere alphanumerische Zeichenfolgen uund v, und Ihre Ausgabe ist die kleinste Ganzzahl, kso dass ues sich um eine kumschließende Teilsequenz von handelt v. Wenn dies nicht kder Fall ist, erfolgt die Ausgabe -1.

Beispiel

Betrachten Sie die Eingaben u := xyzyxzzxyxund v := yxzzazzyxxxyz. Wenn wir anfangen, gierig nach den Charakteren von uin zu suchen v, werden wir uns dreimal umwickeln:

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

Somit ist die korrekte Ausgabe höchstens 3. Beachten Sie, wie das Zeichen ganz links xeinmal ausgewählt und dann beim zweiten Durchlauf ignoriert wird, da es nicht wiederverwendet werden kann. Es gibt jedoch eine kürzere Methode mit nur 2 Wrap-arounds:

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

Es stellt sich heraus, dass ein Wrap-Around (dh zwei Sweeps) nicht ausreicht, sodass die richtige Ausgabe erfolgt 2.

Regeln und Boni

Sie können entweder eine Funktion oder ein vollständiges Programm schreiben und bei Bedarf auch die Reihenfolge der Eingaben ändern. Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.

Es gibt einen Bonus von -10% für die Berechnung aller Testfälle in insgesamt weniger als 10 Sekunden. Ich werde unklare Fälle auf meiner Maschine testen. Meine Referenzimplementierung in Python dauert ungefähr 0,6 Sekunden. Ich habe einen 7 Jahre alten Laptop mit 1,86 GHz Dual-Core-CPU, den Sie vielleicht berücksichtigen möchten.

Testfälle

"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

Dies definiert eine Funktion g, die zwei Zeichenfolgen als Parameter verwendet. Probieren Sie es online aus: Pyth Compiler / Executor

Dieser Code ist sehr ineffizient. Es hat eine Zeit- und Speicherkomplexität von len(v)!/(len(v)-len(u))!. Die längeren Testfälle können nicht in weniger als 10 Sekunden gelöst werden. (Es wird auch sehr wahrscheinlich abstürzen, da der Speicher knapp wird.)

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]

Timing für alle Testfälle (Hinweis: Argumente werden umgedreht):

*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)

So funktioniert es (Kurzversion): einfache Brute Force, bei der nur ein passender Charakter verwendet und übersprungen werden muss. Ich stoppe die Suche, wenn entweder fertig (Rückgabe der Anzahl der Zyklen) oder wenn mehr als das Minimum zurückgelegt wurde (Rückgabe -1).

Ich habe im Vergleich zu meiner ersten Version viele Bytes gespart, hauptsächlich weil ich von einem vollständigen Programm zu einer Funktion gewechselt bin.

Mit einigen Kommentaren und dem richtigen Abstand ist Golf Haskell gut lesbar:

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

Als Referenz: alte Version, Vollprogramm, 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%)

Rekursive Suche, wie die Antwort von @ nimi, wobei das Minimum an Wraps erhalten bleibt. Der Lösungsraum ist groß (vor allem für das letzte Beispiel), aber das Reduzieren der Suche auf die aktuell gefundene Minute hält die Zeit niedrig. Bearbeiten 1 Fügen Sie einen fehlenden Testfall hinzu, der etwas verkürzt wurde. Bearbeiten 2 Keine Notwendigkeit, Parameter weiterzugeben, es ist behoben

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,'')

Ungolfed

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
}

Test In Firefox / Firebug - Konsole

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

Ausgabe (letzte Zeile ist die Ausführungszeit in ms)

["ich", "moe"] 0
["treffen", "metro"] -1
["abeba", "abaab"] 1
["abaab", "baabaa"] 1
["1c1C1C2B", "1111CCCcB2"] 3
["umgekehrt", "reserviert"] 2
["abcdefg", "gfedcba"] 6
["xyzyxzzxyx", "yxzzazzyxxxyz"] 2
["aasdffdaasdf", "asdfddasdfsdaafsds"] 2
116