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
, B
y C
, donde B
y C
están garantizados para ser de la misma longitud. Si B
aparece 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 B
como 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 B
se puede encontrar en múltiples lugares disjuntos:
A: abcdeedcbaabcde
B: ed
C: 12
Result: abcd1e2cbaabcde
and NOT: abcd112cbaabc2e (or similar)
Cuando B
no aparece en A
, debe salir A
sin cambios.
Reglas
Como se indicó anteriormente, tome tres cadenas A
, B
y C
como entrada y reemplace la ocurrencia más a la izquierda B
como subsecuencia A
con 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 B
y C
tener la misma longitud. Todas las cadenas solo contendrán caracteres alfanuméricos.
Aplican reglas estándar de código de golf .
Casos de prueba
Cada caso de prueba es de cuatro líneas: A
, B
, C
seguido 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 N
está 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
/* Configuration */
var QUESTION_ID = 77719; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
return "http://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}
function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
return a.owner.display_name;
}
function process() {
var valid = [];
answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});
var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});
else console.log(body);
});
valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});
var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;
var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);
var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();
languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});
var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);
langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});
for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}
}
body { text-align: left !important}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">
</tbody>
</table>
</div>
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
[[1], [2], [3]]
.Respuestas:
Jalea ,
232221 bytesPruébalo en línea! Tenga en cuenta que los dos últimos casos de prueba se quedarán sin memoria.
Verificación
Cómo funciona
fuente
Python 2, 88 bytes
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,c
medida que avanzamos.Para probar (después de reemplazar
print
conreturn
):fuente
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.
Espacios en blanco para su placer:
fuente
Whitespaced
sí, eso es totalmente legiblej<k?a:d
Lua, 121 bytes
La solución
gsub
directa 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.
Sin golf
fuente
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.
Explicación: Awww sí, recursión.
Casos de prueba:
fuente
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í?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 a
te haría guardar algunos bytes?Python 3.5, 87 bytes
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 esg(.*?)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\n
lo haría.Para el reemplazo
12345
, la cadena construida es1\g<1>2\g<2>3\g<3>4\g<4>5
.re.sub(...,...,s,1)
realiza como máximo un reemplazo en la cadenas
.fuente
Pyth, 27
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
...fuente
MATL , 33 bytes
Pruébalo en línea!
Explicación
fuente
JavaScript (ES6), 84 bytes
Explicación / Prueba
Mostrar fragmento de código
fuente
JavaScript (ES6),
8476 bytesPorque 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:
También probé una solución recursiva RegExp pero que tomó 90 bytes:
fuente
Julia,
8970 bytesUtiliza un índice
i
para recorrer las cadenas de patrón / reemplazo a medida que avanzamos. -19 bytes gracias a @Dennis!fuente
C, 98 bytes
/ * Código ampliado * /
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 * /
fuente
R, 76 bytes
usos
sub
para reemplazar el primer partidoSin golf
fuente
C ++, 204 bytes
Golfed
Sin golf
fuente
std
lo suficiente como para justificar el usousing namespace std;
. El uso destd::cin
,std::cout
ystd::string
ahorrará 5 bytes, ya que estos parecen ser los únicos usos de ese espacio de nombres.b
dea
, 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 seaabcd1e2...
!)Retina , 63 bytes
Entrada se toma con el fin
B
,C
,A
, separadas por saltos de línea.Pruébalo en línea.
fuente
Haskell, 87 bytes
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 listax
de pares de caracteres (patrón y reemplazo) y una cadenay
. Si los caracteres de "patrón"x
forman una subsecuencia dey
, devuelve la lista vacía yy
con 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 reemplazox
, se aplica#
ax
la tercera cadena y devuelve el segundo componente del resultado.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.
fuente
JavaScript (ES6),
10095 bytesEsta es una función válida de JavaScript Lambda. Salidas como función
return
. Toma tres argumentos (a,b,c
). Agreguef=
al principio e invoque comof(arg1,arg2,arg3)
.fuente
f=
menos que su función sea recursiva, pero no parece que lo sea.a
no contiene el patrón. Tampoco estoy seguro de que sea aceptable devolver una serie de cadenas.C (gcc),
67626159 bytesPruébalo en línea!
fuente
Octava, 97 bytes
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:
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.
key
es la salida esperada,ans
es la salida de la función.fuente
D(t=...)
) me siguen desconcertando :-)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?
PD. Este es mi primer golf. Avíseme de cualquier problema / mejora.
fuente
Pyth, 22 bytes
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>3
devolverá 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
fuente
Jalea , 23 bytes
Esto es dos bytes más largo que mi otra respuesta de Jelly , pero termina instantáneamente. Pruébalo en línea!
Verificación
Cómo funciona
fuente
CJam, 29 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
fuente
Java 7, 102 bytes
Prueba detallada aquí
fuente
Julia,
939086 bytesTener 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
fuente
Julia,
625958 bytesLa E / S está en forma de matrices de caracteres.
Verificación
fuente
PHP,
130109 bytesTodavía me gustaría más corto; podría guardar 3 bytes (
""<
) siB
se garantiza que no contiene0
.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
fuente
Ruby,
70645958 bytesFunción anónima. Camine a través de la cadena
a
para construir una nueva cadena con letras reemplazadas de acuerdo con el siguiente carácterb
yc
, 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.
Pruébalo en línea!
fuente
-1+i+=1
con~-i+=1
Perl, 80 + 1 = 81 bytes
Corre con la
-p
banderaPrué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
ghost
en el primer ejemplo se convierte en la cadenag(.*?)h(.*?)o(.*?)s(.*?)t(.*?)
, lo que significag
seguido de 0 o más caracteres, seguido deh
seguido 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
12345
se convierte en1 .$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,$5
es en realidad una referencia a un grupo de captura (entre paréntesis) de la primera cadena.fuente
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!perl -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;'
Clojure, 113 bytes
Un básico
reduce
, no muy contento con todos esos largosfirst
,rest
yconj
llamadas a funciones. Con la esperanza de ver un mejor enfoque.fuente