introduction
Dans ce défi, votre tâche consiste à trouver des sous-séquences généralisées de chaînes. Les sous-séquences ne sont pas nécessairement contiguës, et elles peuvent également "boucler" la chaîne, en dépassant sa fin et en recommençant depuis le début. Vous voudrez cependant minimiser le nombre de tours.
Plus formellement, laissez u
et v
soyez deux chaînes quelconques et k ≥ 0
un entier. Nous disons que u
c'est une k
sous-séquence enveloppante de v
, s'il existe des indices distincts tels que , et au plus des indices satisfont . Cela signifie que vous pouvez le trouver à l'intérieur en allant de gauche à droite, en choisissant certains de ses personnages en chemin et en vous déplaçant la plupart du temps (de manière équivalente, en faisant tout au plus des balayages ). Notez qu'aucun caractère ne peut être choisi plus d'une fois, même après un bouclage , et que les sous-séquences -wrapping sont exactement les sous-séquences ordinaires que nous connaissons tous.i1, i2, ..., ilen(u)
u == v[i1] v[i2] ... v[ilen(u)]
k
ij
ij > ij+1
u
v
k
k+1
v
0
La tâche
Vos entrées sont deux chaînes alphanumériques non vides u
et v
, et votre sortie est le plus petit entier k
tel que u
la k
sous-séquence d'habillage v
. S'il n'en k
existe pas, la sortie doit être -1
.
Exemple
Considérez les entrées u := xyzyxzzxyx
et v := yxzzazzyxxxyz
. Si nous commençons à chercher les personnages de u
de v
manière gourmande, nous allons envelopper 3 fois:
yxzzazzyxxxyz
>─x─────y────z┐
┌─────────────┘
└y───────x────┐
┌─────────────┘
└──zz─────x─y─┐
┌─────────────┘
└──────────x──>
Ainsi, la sortie correcte est au maximum de 3. Notez comment le caractère le plus à gauche x
est sélectionné une fois, puis ignoré lors du deuxième balayage, car il ne peut pas être réutilisé. Cependant, il existe une méthode plus courte avec seulement 2 bouclages:
yxzzazzyxxxyz
>──────────xyz┐
┌─────────────┘
└yxzz────x────┐
┌─────────────┘
└───────y─x───>
Il s'avère qu'un bouclage (c'est-à-dire deux balayages) n'est pas suffisant, donc la sortie correcte est 2
.
Règles et bonus
Vous pouvez écrire une fonction ou un programme complet, et vous pouvez également modifier l'ordre des entrées si nécessaire. Le nombre d'octets le plus bas gagne et les failles standard sont interdites.
Il y a un bonus de -10% pour le calcul de tous les cas de test en moins de 10 secondes au total. Je vais tester des cas peu clairs sur ma machine; mon implémentation de référence en Python prend environ 0,6 seconde. J'ai un ordinateur portable de 7 ans avec un processeur dual core 1,86 GHz, dont vous voudrez peut-être tenir compte.
Cas de test
"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
la source
x
est utilisé dans trois balayages distincts. Il ne peut être utilisé qu'une seule fois.Réponses:
Pyth, 34 octets
Ceci définit une fonction
g
, qui prend deux chaînes en paramètre. Essayez-le en ligne: Pyth Compiler / ExecutorCe code est très inefficace. Il a une complexité de temps et de mémoire de
len(v)!/(len(v)-len(u))!
. Il n'est pas en mesure de résoudre les cas de test plus longs en moins de 10 secondes. (Il se bloquera également très probablement, car il manquera de mémoire.)la source
Haskell, 160 * 0,9 = 144 octets
Timing pour tous les cas de test (remarque: les arguments sont inversés):
Comment ça marche (version courte): simple force brute qui prend le minimum d'utiliser un caractère correspondant et de le sauter. J'arrête la recherche lorsque vous avez terminé (retour du nombre de cycles) ou lorsque vous avez fait plus de vélo que le minimum jusqu'à présent (retour -1).
Économisé beaucoup d'octets par rapport à ma première version, principalement parce que je suis passé d'un programme complet à une fonction.
Avec quelques commentaires et un espacement approprié, Haskell est assez lisible:
Pour référence: ancienne version, programme complet, 187 octets
la source
JavaScript (ES6) 174 (193 - 10%)
Recherche récursive, comme la réponse de @ nimi, en gardant le minimum de tours. L'espace des solutions est grand (surtout pour le dernier exemple) mais couper la recherche au min actuellement trouvé permet de garder le temps bas. Edit 1 Ajoutez un cas de test manquant, raccourci un peu Edit 2 Pas besoin de passer le paramètre w around, c'est corrigé
Non golfé
Tester dans la console Firefox / FireBug
Sortie (la dernière ligne est le temps d'exécution en ms)
la source