Votre tâche pour résoudre le problème SLCSC, qui consiste à trouver le code le plus court possible pour résoudre le problème de la conséquence commune la plus longue .

Une solution valable au problème LCS pour deux ou plusieurs chaînes de ₁ , ... S _n est une chaîne T de longueur maximale telle que les caractères de T apparaissent dans tous les S _i , dans le même ordre que dans T .

Notez que T ne doit pas nécessairement être une sous- chaîne de S _i .

Exemple

Les chaînes axbyczet xaybzcont 8 sous-séquences communes de longueur 3:

abc abz ayc ayz xbc xbz xyc xyz

N'importe lequel d'entre eux serait une solution valable pour le problème LCS.

Détails

Écrivez un programme ou une fonction qui résout le problème LCS, comme expliqué ci-dessus, en respectant les règles suivantes:

• L'entrée consistera en deux chaînes ou plus contenant uniquement des lettres minuscules.

  Vous pouvez lire ces chaînes comme un tableau de chaînes ou une chaîne unique avec un délimiteur de votre choix.

• Votre code doit générer n'importe laquelle des solutions possibles au problème, éventuellement suivi d'un saut de ligne ou entouré de guillemets.

• Vous pouvez supposer que les chaînes sont plus courtes que 1000 caractères et qu'il y a au plus 20 chaînes.

  Dans ces limites, votre code devrait fonctionner comme prévu en théorie (avec un temps et une mémoire illimités).

• Votre code doit compléter les cas de test combinés de la section suivante en moins d'une heure sur ma machine (Intel Core i7-3770, 16 Go de RAM).

  Les approches qui itèrent simplement sur toutes les sous-séquences possibles ne respecteront pas le délai.

• L'utilisation de fonctions intégrées qui banalisent cette tâche, comme LongestCommonSequence, n'est pas autorisée.

Les règles de code-golf standard s'appliquent.

Cas de test

a
ab

Production: a

aaaaxbbbb
bbbbxcccc
ccccxaaaa

Production: x

hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl

Sortie: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrlou toute autre sous-séquence commune de même longueur

riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg

Sortie: icsvllvjnlktywuarou toute autre sous-séquence commune de même longueur

rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr

Sortie: krkkou toute autre sous-séquence commune de même longueur

bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja

Sortie: codeou toute autre sous-séquence commune de même longueur

nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt

Sortie: golfou toute autre sous-séquence commune de même longueur

epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp

Sortie: la chaîne vide

CJam, 31

q~L{_:&\f{_2$f#:).>j+}{,}$W>s}j

Essayez-le en ligne

9 octets joués au golf grâce à Dennis!

Explication:

Cet algorithme essaie tous les caractères possibles pour la première position de la sous-séquence, remplace chaque chaîne par la sous-chaîne après la première occurrence de ce caractère, puis s'appelle récursivement (avec mémorisation).

q~          read and evaluate the input (taken as an array)
L{…}j       execute block with recursive memoization and no starting values
  _         duplicate the array of strings
  :&\       intersect the strings as character sets and move before the array
             these are all the possible characters for the sequence
  f{…}      for each character and the array
    _2$     duplicate the array and the character
    f#      find the character position in each string
    :)      increment the positions (to skip the character)
    .>      slice each string starting at the corresponding position
    j       call the j block recursively
    +       concatenate the starting character with the result
  {,}$      sort resulting strings (one for each character) by length
  W>        keep only the last element, if any
  s         convert (from 0/1-string array) to string

Python - 665 644

Niveaux d'indentation:

1: space
2: tab
3: tab + space
4: 2 tabs
5: 2 tabs + space

Le code définit une fonction o, qui prend une liste de chaînes comme arguments et renvoie l'un des LCS pour les chaînes.

def o(t):
 t=[[y for y in x if y in reduce(lambda x,y:x.intersection(y),t,set(t[0]))]for x in t];l=map(len,t);C=[0]*reduce(lambda x,y:x*-~y,l,1);y=lambda z:[x-1for x in z];m=len(t);e=enumerate
 def g(h):
    r,x=0,1
    for k,j in e(h):r+=-~j*x;x*=-~l[k]
    return r
 def f(h):
    i=len(h)
    if i==m:
     b=g(h);c=t[0][h[0]]
     for k,j in e(h):
         if t[k][j]!=c:break
     else:C[b]=1+C[g(y(h))];return
     r=0
     for k,_ in e(h):a=h[:];a[k]-=1;r=max(r,C[g(a)])
     C[b]=r;return
    for j,_ in e(t[i]):f(h+[j])
 def p(h):
    if min(h)==-1:return''
    v=C[g(h)]
    for k,_ in e(h):
        a=h[:];a[k]-=1
        if v==C[g(a)]:return p(a)
    return p(y(h))+t[0][h[0]]
 f([]);return p(y(l))

Code de test:

tests = [
"""
a
ab
""",
"""
aaaaxbbbb
bbbbxcccc
ccccxaaaa
""",
"""
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
""",
"""
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
""",
"""
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
""",
"""
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
""",
"""
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
""",
"""
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
"""
]

for s in tests:
 print o(s.strip().split())

Temps nécessaire pour exécuter les tests sur mon ordinateur:

$ time python 52808-shortest-longest-common-subsequence-code-golfed.py
a
x
hecbpyhogntqtpcqgkxchpsieuhbncvhuqndbjqmclchqyfhtdvgoysuhrrl
icsvllvanlktywuar
krkk
code
golf

        9.03 real         8.99 user         0.03 sys

Pyth, 59 58 55 35 octets

L&@Fb?+yPMbeeb@FeMbeolNmyXJbdP@bdlb

Coupez 20 octets grâce à @isaacg!

Version 55 octets:

DCHR?k!&.AH@FH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Coupez 3 octets en changeant .U@bZpour @F(l'opérateur de pliage).

Version 58 octets:

DCHR?k!&.AH.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Coupez un octet en changeant le format d'un conditionnel booléen.

Version 59 octets:

DCHR?k|!.AH!.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

C'était dur! Python a continué de se briser! Je suis sûr que c'était une sorte de bogue, mais je n'ai pas pu obtenir de test minimal. Tant pis.

J'ai basé l'algorithme sur celui-ci . Ce qui est bien, sauf que celui-ci est conçu pour seulement deux cordes. J'ai dû le modifier un peu pour le faire fonctionner davantage. Ensuite, le dernier cas de test prenait trop de temps, j'ai donc dû ajouter une vérification supplémentaire pour quitter la récursivité s'il n'y a plus de caractères communs.

C'est assez lent, mais cela devrait prendre moins d'une heure (j'espère). Je teste mon Core i3 avec 6 Go de RAM, donc votre Core i7 16 Go devrait souffler. :)

J'ai également profité des fonctions de mémorisation automatique de Pyth pour le rendre un peu plus rapide.

EDIT : @Dennis a dit que ça passe!

Pour le tester, ajoutez la ligne suivante:

CQ

et lui donner une liste de chaînes via une entrée standard (par exemple ['a', 'ab']).

Explication pour la version 35 octets:

WIP.

Explication pour la version 55 octets:

DCH                                                        define a function C that takes a list of strings H
   R                                                       return the following expression
    ?                                                      if
      !&.AH@FH                                             there are no more common letters OR all the strings are empty
     k                                                     return the empty string
              ?          ql{medH1                          else if the last character of every string is equal
               +Cm<1dHeeH                                  return the result of adding the last character to recursion with every item without its last character
                                 h.MlZ.eC++<Hk]<1b>HhkH    otherwise, return the largest result of recursing len(H) times, each time with one element's last character cut off

C, 618 564 octets

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y=n-1,z,i,t,m=0,w=1;for(;y;)x[y--]=999;for(;y<N;y++){for(i=0;i<n&&s[i]==R[y][i];i++);if(i/n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)t&=!!*j[i];y&=j[i]-s[i]>x[i]?z=0,1:0;}t&=!y;I:if(t){if(z)for(i=0;i<n;i++)x[i]=j[i]-s[i];d++,t+=L(j,n),d--,m=t>m?a=c,t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Et ici, il est démêlé, pour la "lisibilité":

d,M,N,A[9999][2];
char*(R[9999][20]),b[1000];
L(char**s,n){
    char*j[20],c,a=0;
    int x[n],y=n-1,z,i,t,m=0,w=1;
    for(;y;)
        x[y--]=999;
    for(;y<N;y++){
        for(i=0;i<n&&s[i]==R[y][i];i++);
        if(i/n){
            a=A[y][0];
            m=A[y][1];
            w=0;
            if(m+d<M||!a)
                goto J;
            else{
                c=a;
                goto K;
            }
        }
    }
    for(c=97;w&&c<'{';c++){
        K:
        t=1,
        y=1,
        z=1;
        for(i=0;i<n;j[i++]++){
            for(j[i]=s[i];*j[i]-c;j[i]++)
                t&=!!*j[i];
            y&=j[i]-s[i]>x[i]?z=0,1:0;
        }
        t&=!y;
        I:
        if(t){
            if(z)
                for(i=0;i<n;i++)
                    x[i]=j[i]-s[i];
            d++,
            t+=L(j,n),
            d--,
            m=t>m?a=c,t:m;
        }
    }
    if(w){
        for(y=0;y<n;y++)R[N][y]=s[y];
        A[N][0]=a;
        A[N++][1]=m;
    }
    J:
    if(d+m>=M)
        M=d+m,b[d]=a;
    if(!d)
        N=0,M=0,puts(b);
    return m;
}

Mesdames et messieurs, j'ai fait une horrible erreur. Il permet d'être plus joli ... Et goto-less ... Au moins , il est maintenant rapide .

Nous définissons une fonction récursive Lqui prend en entrée un tableau sde tableaux de caractères et le nombre nde chaînes. La fonction renvoie la chaîne résultante sur stdout et renvoie accessoirement la taille en caractères de cette chaîne.

L'approche

Bien que le code soit alambiqué, la stratégie ici n'est pas trop complexe. Nous commençons par un algorithme récursif assez naïf, que je décrirai avec un pseudocode:

Function L (array of strings s, number of strings n), returns length:

Create array of strings j of size n;

For each character c in "a-z",
    For each integer i less than n,
         Set the i'th string of j to the i'th string of s, starting at the first appearance of c in s[i]. (e.g. j[i][0] == c)
         If c does not occur in the i'th string of s, continue on to the next c.
    end For

    new_length := L( j, n ) + 1; // (C) t = new_length
    if new_length > best_length
        best_character := c; // (C) a = best_character
        best_length := new_length; // (C) m = best_length
    end if
end For

// (C) d = current_depth_in_recursion_tree
if best_length + current_depth_in_recursion_tree >= best_found
     prepend best_character to output_string // (C) b = output_string
     // (C) M = best_found, which represents the longest common substring found at any given point in the execution.
     best_found = best_length + current_depth;
end if

if current_depth_in_recursion_tree == 0
    reset all variables, print output_string
end if 

return best_length

Maintenant, cet algorithme en lui-même est assez atroce (mais peut tenir dans environ 230 octets, j'ai trouvé). Ce n'est pas ainsi que l'on obtient des résultats rapides. Cet algorithme évolue incroyablement mal avec la longueur de la chaîne. Cet algorithme ne , cependant, échelle assez bien avec un plus grand nombre de chaînes. Le dernier cas de test serait résolu pratiquement instantanément, car aucune chaîne de caractères sn'a de caractère cen commun. J'ai mis en œuvre deux astuces principales ci-dessus qui ont entraîné une augmentation de vitesse incroyable:

• À chaque appel à L, vérifiez si nous avons déjà reçu cette même entrée. Étant donné que dans la pratique, les informations sont transmises via des pointeurs vers le même ensemble de chaînes, nous n'avons pas réellement à comparer des chaînes, uniquement des emplacements, ce qui est génial. Si nous constatons que nous avons obtenu ces informations auparavant, il n'est pas nécessaire de parcourir les calculs (la plupart du temps, mais obtenir des résultats rend les choses un peu plus compliquées) et nous pouvons nous en sortir en renvoyant simplement la longueur. Si nous ne trouvons pas de correspondance, enregistrez cet ensemble d'entrées / sorties pour le comparer aux appels futurs. Dans le code C, la deuxième forboucle tente de trouver des correspondances avec l'entrée. Les pointeurs d'entrée connus sont enregistrés dans R, et la longueur correspondante et les valeurs de sortie des caractères sont stockées dansA. Ce plan a eu un effet drastique sur l'exécution, en particulier avec des chaînes plus longues.

• Chaque fois que nous trouvons les emplacements cdans s, il y a une chance que nous savons dès le départ que ce que nous avons trouvé est pas optimale. Si chaque emplacement de capparaît après un emplacement connu d'une autre lettre, nous savons automatiquement que cela cne conduit pas à une sous-chaîne optimale, car vous pouvez y insérer une lettre de plus. Cela signifie que pour un petit coût, nous pouvons potentiellement supprimer plusieurs centaines d'appels à Lde grandes chaînes. Dans le code C ci-dessus, yest un indicateur défini si nous savons automatiquement que ce caractère conduit à une chaîne sous-optimale, et zest un indicateur défini si nous trouvons un caractère qui a des apparences exclusivement antérieures à tout autre caractère connu. Les premières apparitions actuelles des personnages sont stockées dansx. L'implémentation actuelle de cette idée est un peu compliquée, mais les performances ont presque doublé dans de nombreux cas.

Avec ces deux idées, ce qui n'a pas fini en une heure prend maintenant environ 0,015 seconde.

Il y a probablement beaucoup plus de petites astuces qui peuvent accélérer les performances, mais à ce stade, j'ai commencé à m'inquiéter de ma capacité à tout jouer au golf. Je ne suis toujours pas satisfait du golf, donc j'y reviendrai probablement plus tard!

Timings

Voici un code de test, que je vous invite à essayer en ligne :

#include "stdio.h"
#include "time.h"

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int main(int argc, char** argv) {
    /* Our test case */
    char* test7[] = {
        "nqrualgoedlf",
        "jgqorzglfnpa",
        "fgttvnogldfx",
        "pgostsulyfug",
        "sgnhoyjlnfvr",
        "wdttgkolfkbt"
    };

    printf("Test 7:\n\t");
    clock_t start = clock();

    /* The call to L */
    int size = L(test7, SIZE_ARRAY(test7));


    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("\tSize: %d\n", size);
    printf("\tElapsed time: %lf s\n", dt);

    return 0;
}

J'ai exécuté les cas de test de l'OP sur un ordinateur portable équipé d'une puce Intel Core i7 à 1,7 GHz, avec un paramètre d'optimisation de -Ofast. La simulation a signalé un pic de 712 Ko requis. Voici un exemple d'exécution de chaque scénario de test, avec des horaires:

Test 1:
    a
    Size: 1
    Elapsed time: 0.000020 s
Test 2:
    x
    Size: 1
    Elapsed time: 0.000017 s
Test 3:
    hecbpyhogntqppcqgkxchpsieuhbmcbhuqdjbrqmclchqyfhtdvdoysuhrrl
    Size: 60
    Elapsed time: 0.054547 s
Test 4:
    ihicvaoodsnktkrar
    Size: 17
    Elapsed time: 0.007459 s
Test 5:
    krkk
    Size: 4
    Elapsed time: 0.000051 s
Test 6:
    code
    Size: 4
    Elapsed time: 0.000045 s
Test 7:
    golf
    Size: 4
    Elapsed time: 0.000040 s
Test 8:

    Size: 0
    Elapsed time: 0.000029 s


Total time: 0.062293 s

En golf, j'ai atteint les performances de manière assez significative, et comme les gens semblaient aimer la vitesse brute (0,013624 s pour terminer tous les cas de test combinés) de ma précédente solution de 618 octets, je vais la laisser ici pour référence:

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y,z,i,t,m=0,w=1;for(y=0;y<n;y++)x[y]=999;for(y=0;y<N;y++){for(i=0;i<n;i++)if(s[i]!=R[y][i])break;if(i==n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)if(!*j[i]){t=0;goto I;}if(j[i]-s[i]>x[i])z=0;if(j[i]-s[i]<x[i])y=0;}if(y){t=0;}I:if(t){if(z){for(i=0;i<n;i++){x[i]=j[i]-s[i];}}d++,t+=L(j,n),d--,m=t>m?(a=c),t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

L'algorithme lui-même est inchangé, mais le nouveau code repose sur des divisions et des opérations au niveau du bit plus délicates qui finissent par ralentir le tout.

Python 2, 285

Code:

import re
def f(s,a,b):
  if b==[]:return s+f('',[],a)
  if a==[]:return s+max([f(b[0][i],[b[0][i+1:]],b[1:]) for i in range(len(b[0]))],key=len) if b[0]!='' else ''
  return max([f(s,a+[b[0][i.start()+1:]],b[1:]) for i in re.finditer(s[-1],b[0])],key=len) if ~b[0].find(s[-1]) else ''

Usage:

print f('',[],['axbycz','xaybzc'])

Explication:

Il s'agit d'une fonction récursive. sest le personnage que nous recherchons. acontient la liste des chaînes coupées après s. bcontient une liste de chaînes non encore couplée. frenvoie la chaîne commune la plus longue.

La première condition vérifie si nous avons fini de parcourir toutes les chaînes. si c'est le cas, cela signifie sest un caractère commun, et il revient set recherche des caractères plus communs.

La deuxième condition vérifie si nous ne commençons pas à parcourir une chaîne, ce qui signifie que nous n'avons même pas de caractère ( a==[]est équivalent à s==''). si c'est le cas, nous vérifions chaque caractère de la première chaîne b.

La dernière ligne déplace la première chaîne bvers a, en trouvant chaque occurrence de sdans cette chaîne.

Au premier appel, sdevrait être une chaîne vide. adevrait être une liste vide et bdevrait contenir toutes les chaînes.