Subsecuencia Sustitución

30

La mayoría de los idiomas vienen con una función integrada para buscar en una cadena todas las ocurrencias de una subcadena determinada y reemplazarlas por otras. No conozco ningún lenguaje que generalice este concepto a subsecuencias (no necesariamente contiguas). Entonces esa es tu tarea en este desafío.

La entrada constará de tres cuerdas A, By C, donde By Cestán garantizados para ser de la misma longitud. Si Baparece como una subsecuencia A, debe reemplazarse por C. Aquí hay un ejemplo simple:

A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345

Sería procesado así:

abcdefghijklmnopqrstuvwxyz
      ||      |   ||
abcdef12ijklmn3pqr45uvwxyz

Si hay varias formas de encontrar Bcomo una subsecuencia, debe reemplazar con avidez la más a la izquierda:

A: abcdeedcba
B: ada
C: BOB

Result:   BbcOeedcbB
and NOT:  BbcdeeOcbB

Lo mismo se aplica si Bse puede encontrar en múltiples lugares disjuntos:

A: abcdeedcbaabcde
B: ed
C: 12

Result:   abcd1e2cbaabcde
and NOT:  abcd112cbaabc2e (or similar)

Cuando Bno aparece en A, debe salir Asin cambios.

Reglas

Como se indicó anteriormente, tome tres cadenas A, By Ccomo entrada y reemplace la ocurrencia más a la izquierda Bcomo subsecuencia Acon C, si hay alguna.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Puede tomar las tres cadenas en cualquier orden consistente que debe especificar en su respuesta. Puede suponer eso By Ctener la misma longitud. Todas las cadenas solo contendrán caracteres alfanuméricos.

Aplican reglas estándar de .

Casos de prueba

Cada caso de prueba es de cuatro líneas: A, B, Cseguido por el resultado.

abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

abcdeedcba
ada
BOB
BbcOeedcbB

abcdeedcbaabcde
ed
12
abcd1e2cbaabcde

121
121
aBc
aBc

abcde
acb
123
abcde

ABC
ABCD
1234
ABC

012345678901234567890123456789
42
TT
0123T5678901T34567890123456789

edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba

edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba

daccdedca
ace
cra
dcrcdadca

aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca

aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44

Tabla de clasificación

El fragmento de pila al final de esta publicación genera tablas de clasificación a partir de las respuestas a) como una lista de la solución más corta por idioma yb) como una tabla de clasificación general.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

## Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

## Perl, 43 + 2 (-p flag) = 45 bytes

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Martin Ender
fuente
¿Sería adecuada una lista de cadenas de caracteres individuales para entrada / salida?
FryAmTheEggman
@FryAmTheEggman Hm, el único consenso que puedo encontrar es este que no aborda las listas de cadenas de un solo carácter como representaciones de cadenas válidas. Podría valer la pena hacer una meta publicación (especialmente porque creo que esto también surgió en el último desafío de xnor). Voy a decir que no por ahora.
Martin Ender
¿Qué pasa con las matrices de caracteres? Esto parece implicar que están permitidos incluso si el idioma tiene un tipo de cadena adecuado.
Dennis
@Dennis Sí, las matrices de caracteres están bien, pero las cadenas singleton son como tomar una matriz de enteros como [[1], [2], [3]].
Martin Ender
Ok, gracias por aclarar eso.
Dennis

Respuestas:

3

Jalea , 23 22 21 bytes

='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?

Pruébalo en línea! Tenga en cuenta que los dos últimos casos de prueba se quedarán sin memoria.

Verificación

$ head -n 5 test-cases
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

$ cat subseq-short
while read s; do
        read p; read r; read o; echo $o; read
        timeout 1s jelly eun $1 "='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?" "'$s'" "'$p'" "'$r'"
        (($?)) && echo '(killed)'
done < test-cases
$ ./subseq-short
abcdef12ijklmn3pqr45uvwxyz
abcdef12ijklmn3pqr45uvwxyz
BbcOeedcbB
BbcOeedcbB
abcd1e2cbaabcde
abcd1e2cbaabcde
aBc
aBc
abcde
abcde
ABC
ABC
0123T5678901T34567890123456789
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcba
edcb1edc2aed3bae4cba5dcba
edcb1edc2aed3bae4cba5dcba
dcrcdadca
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
(killed)
1ac2cb2bccc33b3bab4aa4bbbc44
(killed)

Cómo funciona

='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?  Main link. Arguments: string s, pattern p, replacement r

='                     Compare each character of s with each character of p.
                       This yields a 2D list. Each row corresponds to a char in p.
  T€                   Compute the truthy indices of each row, i.e., the indices
                       of all occurrences of that char in s.
   Œp                  Compute the Cartesian product of the lists of indices.
        $              Combine the two links to the left into a monadic chain:
      Ṣ€                 Sort each list of indices.
     f                   Filter, removing all non-sorted lists of indices.
         Ḣ             Head; take the first (sorted) list of indices.
          Ṭ            Truth; generate a list with 1's at those indices.
           œp³         Partition; split s at all 1's, removing those characters.
                  Ḋ?   If the partition has more than more than one element:
              ż⁵$        Zip the partition with r.
                 ³       Else, return s.
Dennis
fuente
12

Python 2, 88 bytes

def f(a,b,c,o=""):
 for q in a:x=q==b[:1];o+=c[:x]or q;b=b[x:];c=c[x:]
 print[o,a][c>'']

Una función que toma las tres cadenas y envía el resultado a STDOUT. La función simplemente pasa una vez por la cadena, toma el carácter apropiado y lo actualiza a b,cmedida que avanzamos.

Para probar (después de reemplazar printcon return):

S = """
<test cases here>
"""

for T in S.split("\n\n"):
    A,B,C,D = T.split()
    assert f(A,B,C) == D
Sp3000
fuente
9

Java 7, 141

Creo que hay algo más que puedo hacer con esto, pero tengo que correr por ahora. Es solo un simple iterar / reemplazar, manteniendo un índice en A y B.

char[]h(char[]a,char[]b,char[]c){char[]d=a.clone();int i=0,j=0,k=b.length;for(;i<a.length&j<k;i++)if(a[i]==b[j])d[i]=c[j++];return j==k?d:a;}

Espacios en blanco para su placer:

char[]h(char[]a,char[]b,char[]c){
    char[]d=a.clone();
    int i=0,j=0,k=b.length;
    for(;i<a.length&j<k;i++)
        if(a[i]==b[j])d[i]=c[j++];
    return j==k?d:a;
}
Geobits
fuente
Whitespacedsí, eso es totalmente legible
gato
¿No es así? La razón principal por la que agrego la versión con sangría de varias líneas es para evitar el desplazamiento horizontal, solo para que todo se pueda ver a la vez. El espacio en blanco en línea no es un gran problema OMI;)
Geobits
[característica-petición] aún más espacio en blanco
Alex A.
@AlexA. ¡Aqui tienes!
Geobits
@Geobits Guarde un byte al final si lo hacej<k?a:d
Xanderhall
7

Lua, 121 bytes

La solución gsubdirecta nos permite iterar exactamente una vez en cada carácter y reemplazarlos en una nueva instancia de la cadena.

Toma entrada a través de 3 argumentos de línea de comando y genera una cadena en STDOUT.

a,b,c=...d=a:gsub(".",function(s)if b:find(s)then b=b:sub(2)x=c:sub(1,1)c=c:sub(2)return x end end)print(b~=''and a or d)

Sin golf

a,b,c=...               -- unpack the arguments into a, b and c
d=a:gsub(".",function(s)-- iterate over each character of the first argument
  if b:find(s)then      -- if the current character is in the set b
    b=b:sub(2)          -- remove it from b
    x=c:sub(1,1)        -- save the replacement character in x
    c=c:sub(2)          -- remove it from c
    return x            -- replace the current character with x
  end
end)
print(b~=''             -- if b is empty, we replaced all the character
      and a or d)       -- so output the result of gsub, else, output the first argument
Katenkyo
fuente
6

Python 3, 127 bytes.

Guardado 16 bytes gracias a Katenkyo.

Aún trabajando un poco en esto, el hombre era más desagradable de lo que pensaba.

f=lambda a,b,c:a.replace(b[0],c[0],1)[:a.index(b[0])+1]+f(a[a.index(b[0])+1:],b[1:],c[1:])if b and all(x in a for x in b)else a

Explicación: Awww sí, recursión.

Casos de prueba:

assert f('abcdeedcba', 'ada', 'BOB') == 'BbcOeedcbB'
assert f('abcdeedcbaabcde', 'ed', '12') == 'abcd1e2cbaabcde'
assert f('012345678901234567890123456789', '42', 'TT') == '0123T5678901T34567890123456789'
assert f('ABC', 'ABCD', '1234') == 'ABC'
Morgan Thrapp
fuente
+1 por jugar golf 50, ¡pero sigue adelante! Esto debe superar mi respuesta Java al menos;)
Geobits
77
@Geobits Sí, nunca antes había perdido con Java. Esta es mi mayor vergüenza.
Morgan Thrapp
No estoy realmente versado en Python, pero all(x in a for x in b)también comprueba que los elementos en by a aparecen en el mismo orden, ¿o solo si están aquí?
Katenkyo
@Katenkyo Solo que todos están allí, pero el corte se encargará de la orden cuando volvamos.
Morgan Thrapp
Ok, también, ¿no return a.replace(b[0],c[0],1)[:l(b[0])+1]+f(a[l(b[0])+1:],b[1:],c[1:])if b and all(x in a for x in b)else ate haría guardar algunos bytes?
Katenkyo
5

Python 3.5, 87 bytes

import re
lambda s,p,r:re.sub('(.*?)'.join(p),'\g<%d>'.join(r)%(*range(1,len(r)),),s,1)

repl.it para verificar todos los casos de prueba .

Cómo funciona

  • '(.*?)'.join(p) construye un patrón de búsqueda que coincide con la subsecuencia a ser reemplazada y cualquier cosa entre sus elementos.

    Como los cuantificadores son vagos, cada uno (.*?)coincidirá con la menor cantidad de caracteres posible.

    Para el patrón ghost, la expresión regular construida es g(.*?)h(.*?)o(.*?)s(.*?)t.

  • '\g<%d>'.join(r)%(*range(1,len(r)),) construye la cadena de reemplazo, utilizando el formato de cadena.

    Cada \g<n>refiere a la n º grupo capturado, al igual que \nlo haría.

    Para el reemplazo 12345, la cadena construida es 1\g<1>2\g<2>3\g<3>4\g<4>5.

  • re.sub(...,...,s,1)realiza como máximo un reemplazo en la cadena s.

Dennis
fuente
4

Pyth, 27

.xuXG.*HC,hSI#.nM*FxRcQ1zwQ

Banco de pruebas

El conjunto de pruebas omite los dos últimos casos porque se quedarán sin memoria. El algoritmo utilizado aquí es encontrar todos los índices de cada carácter en la segunda cadena en la primera cadena, luego encontrar todos los ordenamientos posibles de esos índices y tomar solo los que están ordenados. Luego use el primero de estos en orden ordenado como la lista de índices en la primera cadena para actualizar con los valores de la tercera cadena.

Siento que debería haber algo más corto que .nM*F...

FryAmTheEggman
fuente
4

MATL , 33 bytes

y!=[]0b"@n:!<@*fX<h5Mt?}.]]?iw(}x

Pruébalo en línea!

Explicación

y!      % Implicitly input first two strings. Duplicate the first and transpose
=       % Compare the two strings element-wise. Gives a 2D array with all combinations
[]      % Push empty array. Indices of matching elements will be appended to this
0       % Push a 0. This is the index of last character used up in first string
b       % Bubble up (rearrange elements in stack) to move 2D array to top
"       % For each column of that array (each char of the second string)
  @     %   Push current column
  n:!   %   Transform into column array of consecutive values starting from 1
  <     %   Compare with index of last character used up of first string
  @*    %   Push current column again. Multiply element-wise (logical AND)
  fX<   %   Find index of first matching character, or empty if there's none
  h     %   Append to array containing indices of matching elements
  5Mt   %   Push index of matching character again. Duplicate
  ?}    %   If it's empty
    .   %     Break loop
  ]     %   End if
]       % End for
        % The top of the stack now contains a copy of the index of last matching
        % character, or an empty array if there was no match
?       % If non-empty: all characters were matched
  i     %   Input third string
  w     %   Swap top two elements in stack
  (     %   Assign the characters of the third string to first string at found indices
}       % Else: the original string needs to be output
  x     %   Delete (partial) array of matching indices. Leave original string in stack
        % End if
        % Implicitly display (either modified string or original string)
Luis Mendo
fuente
3

JavaScript (ES6), 84 bytes

(a,b,c)=>[...b].every((q,i)=>r[p=a.indexOf(q,p)]=~p++&&c[i],p=0,r=[...a])?r.join``:a

Explicación / Prueba

usuario81655
fuente
3

JavaScript (ES6), 84 76 bytes

(a,b,c)=>a.replace(RegExp([...b].join`(.*?)`),c.replace(/\B/g,(_,i)=>'$'+i))

Porque estaba seguro de que este era un trabajo para RegExp.

Editar: Guardado 8 bytes gracias a @ MartinBüttner ♦.

Un puerto de la respuesta Ruby de @ KevinLau tomó 82 bytes:

([...a],[...b],[...c])=>(d=a.map(e=>e==b[0]?c.shift(b.shift()):e),b[0]?a:d).join``

También probé una solución recursiva RegExp pero que tomó 90 bytes:

f=(a,[b,...d],[c,...e])=>b?a.replace(RegExp(b+'(.*'+d.join`.*`+'.*)'),(_,s)=>c+f(s,d,e)):a
Neil
fuente
3

Julia, 89 70 bytes

f(s,a,b,i=0)=(o=join(["$a "[i+1]!=c?c:b[i+=1]for c=s]);i<endof(a)?s:o)

Utiliza un índice ipara recorrer las cadenas de patrón / reemplazo a medida que avanzamos. -19 bytes gracias a @Dennis!

Sp3000
fuente
2

C, 98 bytes

char*f(i,o,s,r)char*i,*o,*s,*r;{char*I=i,*O=o;for(;*i;++i,++o)*o=*i==*s?++s,*r++:*i;return*s?I:O;}

/ * Código ampliado * /

char *f(i, o, s, r)
    char *i, *o, *s, *r;
{
    char *I=i, *O=o;
    for (;  *i;  ++i,++o)
        *o = (*i==*s) ? (++s,*r++) : *i;
    return *s ? I : O;
}

Los argumentos son: i Nput cadena, o utput búfer, s cadena de bús, r eplacement.

Después de recordar el inicio de la entrada y la salida, caminamos la entrada, reemplazando y avanzando la sustitución cada vez que tocamos una. Al final, si nos hemos quedado sin sustituciones, devuelve el búfer de salida, de lo contrario, la entrada no modificada.

/ * Pruebas * /

struct T
{
    const char *input;
    const char *search;
    const char *replace;
    const char *expected;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int i;
    static const struct T test[] = {
        { "abcdefghijklmnopqrstuvwxyz",
          "ghost",
          "12345",
          "abcdef12ijklmn3pqr45uvwxyz"},
        { "abcdeedcba",
          "ada",
          "BOB",
          "BbcOeedcbB"},
        { "abcdeedcbaabcde",
          "ed",
          "12",
          "abcd1e2cbaabcde"},
        { "121",
          "121",
          "aBc",
          "aBc"},
        { "abcde",
          "acb",
          "123",
          "abcde"},
        { "ABC",
          "ABCD",
          "1234",
          "ABC"},
        { "012345678901234567890123456789",
          "42",
          "TT",
          "0123T5678901T34567890123456789"},
        { "edcbaedcbaedcbaedcba",
          "abcde",
          "12345",
          "edcbaedcbaedcbaedcba"},
        { "edcbaedcbaedcbaedcbaedcba",
          "abcde",
          "12345",
          "edcb1edc2aed3bae4cba5dcba"},
        { "daccdedca",
          "ace",
          "cra",
          "dcrcdadca"},
        { "aacbcbabcccaabcbabcaabbbbca",
          "abaaaccbac",
          "1223334444",
          "aacbcbabcccaabcbabcaabbbbca"},
        { "aacbcbabcccaabcbabcaabbbbcac",
          "abaaaccbac",
          "1223334444",
          "1ac2cb2bccc33b3bab4aa4bbbc44"
        }
    };

    for (i = 0;  i < (sizeof test) / (sizeof test[0]);  ++i) {
        const struct T *t = test+i;
        char *out = malloc(strlen(t->input)+1);
        char *result = f(t->input, out, t->search, t->replace);
        if (strcmp(t->expected, result))
            printf("Failed test %d; result = \"%s\"\n", i, result);
    }
    return EXIT_SUCCESS;
}
Toby Speight
fuente
2

R, 76 bytes

function(a,b,c){s=substr;for(x in 1:nchar(b)){a=sub(s(b,x,x),s(c,x,x),a)};a}

usos sub para reemplazar el primer partido

Sin golf

function(a,b,c){                    # function with 3 arguments as per description
  s=substr;                         # alias for substr (saves 1 byte)
   for(x in 1:nchar(b)){            # index 1 to number character in b
     a=sub(s(b,x,x),s(c,x,x),a)};   # replace first instance of b[x] in a  
                                    # with c[x] and reassign to a
 a}                                 # return a
mnel
fuente
2

C ++, 204 bytes

Golfed

#include<iostream>
#include<string>
int main(){std::string a, b, c;std::cin>>a>>b>>c;int t=0;for(int x=0;x<b.length();x++){t=a.find(b[x],t);if(t!=-1){a.replace(t,1,c.substr(x,1));}}std::cout<<a;return 0;}

Sin golf

#include<iostream>
#include<string>

int main()
{
    std::string a, b, c;
    std::cin>>a>>b>>c;
    int t = 0;
    for (int x=0;x<b.length();x++) {
        t = a.find(b[x], t);
        if (t != -1) {
            a.replace(t,1,c.substr(x, 1));
        }
    }
    std::cout<<a;
    return 0;
}
Michelfrancis Bustillos
fuente
No creo que estés usando stdlo suficiente como para justificar el uso using namespace std;. El uso de std::cin, std::couty std::stringahorrará 5 bytes, ya que estos parecen ser los únicos usos de ese espacio de nombres.
Value Ink el
@KevinLau ¡Gracias! Tienes mucha razón, pensé en eso, pero en realidad no conté para darme cuenta de que ahorraría caracteres.
Michelfrancis Bustillos
Oh! Una cosa más, ya que es importante. Después de leer sobre su código de nuevo me di cuenta de que está reemplazando con avidez la ocurrencia más a la izquierda de cada carta dentro bde a, pero las letras posteriores tienen que ser después de las letras anteriores también. (Mire el caso de prueba 3 y compárelo con su salida, ¡creo que encontrará que su código saldrá abc21ed...cuando la salida esperada sea abcd1e2...!)
Value Ink
En la entrada del compilador ideone C ++ 14 del código "Adregffftd \ nA23 \ nzac \ n" hace 10 minutos, genere la salida de "zdregffftd" en lugar de "Adregffftd"
RosLuP
2

Retina , 63 bytes

.+$
$&¶;$&
+`^(.)(.*¶)(.)([^;]+);(.*?)\1
$2$4$5$3;
A1`
;

G2=`.

Entrada se toma con el fin B, C, A, separadas por saltos de línea.

Pruébalo en línea.

Martin Ender
fuente
2

Haskell, 87 bytes

x@((a,b):c)#(d:e)|a==d,([],z)<-c#e=([],b:z)|0<1=(d:)<$>x#e
x#y=(x,y)
a!b=snd.(zip a b#)

Noté la falta de una respuesta de Haskell, y decidí arreglar eso. Esto define una función ternaria !con orden de argumento patrón-reemplazo-cadena. Pruébalo aquí.

Explicación

La función auxiliar #toma una lista xde pares de caracteres (patrón y reemplazo) y una cadena y. Si los caracteres de "patrón" xforman una subsecuencia de y, devuelve la lista vacía y ycon cada carácter de patrón reemplazado por su contraparte. De lo contrario, devuelve el par (x,y). La función !comprime el patrón y las cadenas de reemplazo x, se aplica #a xla tercera cadena y devuelve el segundo componente del resultado.

x@((a,b):c)#(d:e)  -- First case of #: both arguments nonempty.
  |a==d,           -- If the pattern char matches the string's head,
   ([],z)<-c#e     -- and the pattern's tail is a subsequence of the string's tail,
  =([],b:z)        -- tack the replacement char to the recursion result.
  |0<1             -- Otherwise,
  =(d:)<$>x#e      -- recurse with the same pairs and tack string's head to result.
x#y=(x,y)          -- If either argument is empty, just pair them.

Si el patrón es una subsecuencia de la cadena, el código se ejecuta en tiempo O (n) , haciendo un paso recursivo a través de la cadena y construyendo con codicia el reemplazo en el proceso. Sin embargo, si el patrón no es una subsecuencia, se ejecuta en tiempo O (2 n ) en el peor de los casos. Esto se debe a que en cada posición donde el patrón y la cadena tienen un carácter coincidente, la función se llama a sí misma para verificar si el patrón es realmente una subsecuencia, descubre que no lo es y se llama a sí misma por segunda vez para calcular el resultado.

Zgarb
fuente
2

JavaScript (ES6), 100 95 bytes

(a,b,c)=>1?(t=[...a].map(e=>b[0]==e?(u=c[0],b=b.slice(1),c=c.slice(1),u):e).join``,b==""?t:a):a

Esta es una función válida de JavaScript Lambda. Salidas como función return. Toma tres argumentos ( a,b,c). Agregue f=al principio e invoque como f(arg1,arg2,arg3).

f=(a,b,c)=>1?(t=[...a].map(e=>b[0]==e?(u=c[0],b=b.slice(1),c=c.slice(1),u):e).join``,b==""?t:a):a

console.log(f(prompt("Value for A"),prompt("Value for B"),prompt("Value for C")))

Arjun
fuente
Bienvenido a PPCG! Las funciones sin nombre son generalmente aceptables , por lo que no las necesita a f=menos que su función sea recursiva, pero no parece que lo sea.
Martin Ender
@ MartinBüttner Gracias! :) Actualicé mi respuesta.
Arjun
Desafortunadamente, esto fallará si a no contiene el patrón. Tampoco estoy seguro de que sea aceptable devolver una serie de cadenas.
Dennis
@ Dennis He actualizado mi solución. Creo que es correcto ahora. Perdón por la tardía respuesta y actualización. (Acabo de notar su comentario, de ahí el retraso)
Arjun
@MartinEnder Mientras revisaba todas mis soluciones, descubrí que esta era incorrecta. Pero, lo he corregido ahora; y es cinco bytes más corto (ya que había dejado intactos muchos lugares de golf; era un golfista novato en ese momento; no es que ahora sea uno excelente: p). Perdón por publicar una solución incorrecta.
Arjun
1

Octava, 97 bytes

function A=U(A,B,C)t=0;for s=B if p=find(A(t+1:end)==s,1) D(t=p+t)=~0;else return;end;end;A(D)=C;

Iterar sobre la subsecuencia para reemplazar; encuentre la primera aparición del primer carácter, encuentre el siguiente carácter en la cadena restante, repita. Lo único interesante de esto es:

D(t=p+t)=~0

D(     )      %// D is a logical mask of characters to replace in the input string
  t=p+t       %// t is the current end of D 
              %// p is the location of the character to replace
              %// update t and use as index to grow D
        =~0   %// make it so, number 1

Como ideone todavía no acepta funciones con nombres distintos a '', solo dejaré una muestra de ejecución aquí. Las entradas solo se muestran para los primeros casos de prueba de brevedad. keyes la salida esperada, anses la salida de la función.

A = abcdefghijklmnopqrstuvwxyz
B = ghost
C = 12345
key = abcdef12ijklmn3pqr45uvwxyz
ans = abcdef12ijklmn3pqr45uvwxyz
A = abcdeedcba
B = ada
C = BOB
key = BbcOeedcbB
ans = BbcOeedcbB
A = abcdeedcbaabcde
B = ed
C = 12
key = abcd1e2cbaabcde
ans = abcd1e2cbaabcde
key = aBc
ans = aBc
key = abcde
ans = abcde
key = ABC
ans = ABC
key = 0123T5678901T34567890123456789
ans = 0123T5678901T34567890123456789
key = edcbaedcbaedcbaedcba
ans = edcbaedcbaedcbaedcba
key = edcb1edc2aed3bae4cba5dcba
ans = edcb1edc2aed3bae4cba5dcba
key = dcrcdadca
ans = dcrcdadca
key = aacbcbabcccaabcbabcaabbbbca
ans = aacbcbabcccaabcbabcaabbbbca
key = 1ac2cb2bccc33b3bab4aa4bbbc44
ans = 1ac2cb2bccc33b3bab4aa4bbbc44
cubilete
fuente
Esas tareas de Octave en lugares inesperados ( D(t=...)) me siguen desconcertando :-)
Luis Mendo
1
@LuisMendo jaja ... es casi como ... ¡una pila! :)
vaso de precipitados
1

Python 3, 123 bytes

Un enfoque diferente que quería compartir, que es unos pocos bytes más corto. No hay reglas contra la biblioteca estándar / expresiones regulares, ¿verdad?

import re
j=''.join
m='(.*?)'
def f(A,B,C):
 *r,l=(re.findall(m+m.join(B)+'(.*)',A)or[[A]])[0]
 print(j(map(j,zip(r,C)))+l)

PD. Este es mi primer golf. Avíseme de cualquier problema / mejora.

Marc J
fuente
1

Pyth, 22 bytes

|eJ:Ej"(.*?)"+E\$3s.iJ

Verifique todos los casos de prueba en el compilador Pyth .

Fondo

Construimos una expresión regular a partir del patrón agregando ay $colocando(.*?) entre todos los caracteres. Esta expresión regular coincidirá con la subsecuencia a ser reemplazada y cualquier cosa entre sus elementos, y cualquier cosa hasta el final de la cadena.

Como los cuantificadores son vagos, cada uno (.*?)coincidirá con la menor cantidad de caracteres posible.

Para el patrón fantasma, la expresión regular construida es g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)$.

Si el patrón coincide con la entrada, el builtin r<str><regex>3devolverá una matriz que contiene el prematch (todo antes de la subsecuencia), todos los grupos capturados (todo entre y después de la subsecuencia), y el postmatch (la cadena vacía).

Si el patrón no coincide, el valor incorporado devolverá una matriz singleton que contiene la entrada original.

Cómo funciona

|eJ:Ej"(.*?)"+E\$3s.iJQ  (implicit) Store the first line of input in Q.

             +E\$        Read the third line of input (pattern) and append '$'.
     j"(.*?)"            Join the result, separating by "(.*?)".
    E                    Read the third line of input (string).
   :             3       Match the string against the regex, as detailed above.
  J                      Save the returned array in J.
 e                       Extract the last element of J. This is an empty string
                         for a successful match or the original string.
|                        Logical OR; replace an empty string with the following:
                   .iJQ    Interleave J and the replacement.
                  s        Flatten the resulting array of strings.
Dennis
fuente
1

Jalea , 23 bytes

Ṭœpż⁵
0ẋai1
⁴='-;ç\ñ⁴P?

Esto es dos bytes más largo que mi otra respuesta de Jelly , pero termina instantáneamente. Pruébalo en línea!

Verificación

$ head -n 5 test-cases
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

$ cat subseq-fast
while read s; do
        read p; read r; read o; echo $o; read
        timeout 10s jelly eun $1 "Ṭœpż⁵¶0ẋai1¶⁴='-;ç\ñ⁴P?" "'$p'" "'$s'" "'$r'"
        (($?)) && echo '(killed)'
done < test-cases
$ ./subseq-fast
abcdef12ijklmn3pqr45uvwxyz
abcdef12ijklmn3pqr45uvwxyz
BbcOeedcbB
BbcOeedcbB
abcd1e2cbaabcde
abcd1e2cbaabcde
aBc
aBc
abcde
abcde
ABC
ABC
0123T5678901T34567890123456789
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcba
edcb1edc2aed3bae4cba5dcba
edcb1edc2aed3bae4cba5dcba
dcrcdadca
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
aacbcbabcccaabcbabcaabbbbca
1ac2cb2bccc33b3bab4aa4bbbc44
1ac2cb2bccc33b3bab4aa4bbbc44

Cómo funciona

⁴='-;ç\ñ⁴P?  Main link. Arguments: pattern p, string s, replacement r

⁴='          Compare each character of s with each character of p.
             This yields a 2D list. Each row corresponds to a char in p.
   -;        Prepend -1 to the 2D list, yielding a ragged array.
     ç\      Cumulatively reduce the array by the second helper link.
         P?  If the product of the resulting list is non-zero:
       ñ       Call the first helper link with the list and s as arguments.
        ⁴      Else, return s.


Ṭœpż⁵        First helper link. Arguments: L (list of indices), r (replacement)

Ṭ            Truth; generate a list with 1's at those indices.
 œp          Partition; split s at all 1's, removing those characters.
   ż⁵        Zip the partition with r.


0ẋai1        Second helper link. Arguments: n (integer), B (list of Booleans)

0ẋ           Generate a list of n zeroes.
  a          Perform logical AND with B.
             This zeroes out the with n elements of B.
   i1        Compute the first index of 1.
Dennis
fuente
1

Java 7, 102 bytes

void L(char[]s,char[]l,char[]r){for(int x=0,y=0;x<s.length&&y<l.length;x++)if(s[x]==l[y])s[x]=r[y++];}

Prueba detallada aquí

// String, Lookup, Replacement
void L(char[]s, char[]l, char[]r)
{
    for(int x=0, y=0; x < s.length && y < l.length; x++)
        if(s[x] == l[y])
            s[x] = r[y++];
}
Khaled.K
fuente
1

Julia, 93 90 86 bytes

f(s,p,r)=(try s=join([match(Regex(join("^$p\$","(.*?)")),s).captures';[r...""]])end;s)

Tener que probar por separado si el partido fue exitoso destruye un poco el puntaje. Una sustitución requeriría lanzar Base.SubstitutionString, lo que probablemente no valga la pena ...

Prueba de funcionamiento

julia> f(s,p,r)=(try s=join([match(Regex(join("^$p\$","(.*?)")),s).captures';[r...""]])end;s)
f (generic function with 1 method)

julia> f("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> f("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"
Dennis
fuente
1

Julia, 62 59 58 bytes

f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)

La E / S está en forma de matrices de caracteres.

Verificación

julia> f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)
f (generic function with 2 methods)

julia> F(s,p,r)=join(f([s...],[p...],[r...])) # string/char array conversion
F (generic function with 1 method)

julia> F("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> F("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"
Dennis
fuente
1

PHP, 130 109 bytes

Todavía me gustaría más corto; podría guardar 3 bytes ( ""<) si Bse garantiza que no contiene 0.

for($s=($a=$argv)[1];""<$c=$a[2][$i++];)if($p=strpos(_.$s,$c,$p+1))$s[$p-1]=$a[3][$k++];echo$k<$i-1?$a[1]:$s;

toma argumentos de la línea de comando. Corre con-r .

Reemplaza a los personajes cuando los encuentra;
imprime copia si todos los caracteres han sido reemplazados; original más

Tito
fuente
1

Ruby, 70 64 59 58 bytes

Función anónima. Camine a través de la cadena apara construir una nueva cadena con letras reemplazadas de acuerdo con el siguiente carácter by c, luego, si todos los caracteres enb están agotados al final, devuelva la cadena recién construida, de lo contrario, devuelva la cadena original.

@histocrat ayudó a guardar 6 bytes a través de gsub .

Guardado 1 byte gracias a @Cyoce.

->a,b,c{i=0;s=a.gsub(/./){$&==b[i]?c[~-i+=1]:$&};b[i]?a:s}

Pruébalo en línea!

Tinta de valor
fuente
Puede guardar un byte reemplazándolo -1+i+=1con~-i+=1
Cyoce
0

Perl, 80 + 1 = 81 bytes

Corre con la -pbandera

$a=join"(.*?)",split//,<>;$b.=$_." .\$".++$;."."for split//,<>;chop$b;s/$a/$b/ee

Pruébalo en línea!

El código genera procesalmente un comando regex de búsqueda y reemplazo, que luego ejecuta en el último bit de código.

La cadena ghosten el primer ejemplo se convierte en la cadena g(.*?)h(.*?)o(.*?)s(.*?)t(.*?), lo que significa gseguido de 0 o más caracteres, seguido de hseguido de 0 o más caracteres, seguido de etc. El *?cuantificador significa que la búsqueda debe ser no codiciosa y "engullir" "tan pocos caracteres como sea posible, en lugar del valor predeterminado de coincidir tanto como sea posible.

La cadena 12345se convierte en 1 .$1.2 .$2.3 .$3.4 .$4.5 .$5, que se evalúa después de realizar la expresión regular. Cada uno de ellos $1,$2,$3,$4,$5es en realidad una referencia a un grupo de captura (entre paréntesis) de la primera cadena.

Gabriel Benamy
fuente
Sugiero este código para ahorrar unos pocos bytes: perl -pe 'eval"s/".<>=~s/.\K/(.*?)/gr."/".<>=~s/.\K/"\${".++$i."}"/gre."/"'. Se me ocurrió, pero está bastante cerca de la tuya, así que no lo publicaré, serían dos respuestas muy cercanas, ¡pero siéntete libre de editar la tuya!
Dada
Intenté esto porque lo vi listado como una pregunta "relacionada" a un problema reciente. Lo mejor que obtuve fueperl -E 'chomp(($f,$t,$s)=(<>));$f=join"(.*?)",split"",$f;@r=split"",$t;@t=shift@r;push@t,"\${",++$x,"}"for(@r);$t=join"",@t;say$s=~s/$f/$t/r;'
Will Crawford, el
0

Clojure, 113 bytes

#(apply str((reduce(fn[[b c r]a](if(=(first b)a)[(rest b)(rest c)(conj r(first c))][b c(conj r a)]))[%2%3[]]%)2))

Un básico reduce, no muy contento con todos esos largos first, resty conjllamadas a funciones. Con la esperanza de ver un mejor enfoque.

NikoNyrh
fuente