Большинство языков поставляется со встроенным для поиска в строке всех вхождений данной подстроки и замены их на другую. Я не знаю ни одного языка, который обобщает эту концепцию на (не обязательно смежные) подпоследовательности. Так что это ваша задача в этом вызове.
Ввод будет состоять из трех строк A
, B
и C
, где B
и C
гарантированно, будет одинаковой длины. Если B
фигурирует как подпоследовательность, A
его следует заменить на C
. Вот простой пример:
A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345
Это будет обработано так:
abcdefghijklmnopqrstuvwxyz
|| | ||
abcdef12ijklmn3pqr45uvwxyz
Если есть несколько способов найти B
в качестве подпоследовательности, вы должны жадно заменить самый левый:
A: abcdeedcba
B: ada
C: BOB
Result: BbcOeedcbB
and NOT: BbcdeeOcbB
То же самое применимо, если B
можно найти в нескольких непересекающихся местах:
A: abcdeedcbaabcde
B: ed
C: 12
Result: abcd1e2cbaabcde
and NOT: abcd112cbaabc2e (or similar)
Когда B
не появляется в A
, вы должны вывести A
без изменений.
правила
Как было указано выше, взять три строки A
, B
и в C
качестве входных данных и заменить самое левое вхождение в B
качестве подпоследовательности в A
с C
, если есть.
Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).
Вы можете взять три строки в любом последовательном порядке, который вы должны указать в своем ответе. Вы можете предположить, что B
и C
имеют одинаковую длину. Все строки будут содержать только буквенно-цифровые символы.
Применяются стандартные правила игры в гольф .
Тестовые случаи
Каждый тест четыре линии: A
, B
, C
после чего результат.
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
Leaderboard
Фрагмент стека внизу этого поста генерирует списки лидеров из ответов а) в виде списка кратчайшего решения для каждого языка и б) в качестве общего списка лидеров.
Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:
## Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:
## Perl, 43 + 2 (-p flag) = 45 bytes
Вы также можете сделать имя языка ссылкой, которая будет отображаться во фрагменте кода:
## [><>](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]]
.Ответы:
Желе ,
232221 байтПопробуйте онлайн! Обратите внимание, что в двух последних тестовых случаях не хватит памяти.
верификация
Как это работает
источник
Python 2, 88 байт
Функция, которая принимает три строки и выводит результат в STDOUT. Функция просто пропускает строку, беря соответствующий символ и обновляя его по
b,c
мере продвижения.Для тестирования (после замены
print
сreturn
):источник
Ява 7, 141
Я думаю, что есть еще что-то, что я могу сделать с этим, но я должен бежать пока. Это просто простая итерация / замена с сохранением индекса в A и B.
Пробелы для вашего удовольствия:
источник
Whitespaced
да, это полностью читаемоj<k?a:d
Луа, 121 байт
Простое решение,
gsub
позволяет нам выполнять итерации ровно один раз для каждого символа и заменять их в новом экземпляре строки.Он принимает ввод через 3 аргумента командной строки и выводит строку в STDOUT.
Ungolfed
источник
Python 3, 127 байт.
Сохранено 16 байтов благодаря Katenkyo.
Все еще работая над этим немного, человек был таким противнее, чем я думал.
Пояснение: Оу, да, рекурсия.
Тестовые случаи:
источник
all(x in a for x in b)
также проверяю, что элементы в b и a появляются в том же порядке, или только если они здесь?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
заставит вас сохранить несколько байтов?Python 3.5, 87 байт
repl.it для проверки всех тестовых случаев .
Как это работает
'(.*?)'.join(p)
создает шаблон поиска, который соответствует подпоследовательности, подлежащей замене, и чему-либо между его элементами.Поскольку квантификаторы ленивы, каждый из них
(.*?)
будет соответствовать как можно меньшему числу символов.Для шаблона
ghost
построено регулярное выражениеg(.*?)h(.*?)o(.*?)s(.*?)t
.'\g<%d>'.join(r)%(*range(1,len(r)),)
строит заменяющую строку, используя форматирование строки.Каждый
\g<n>
относится к n- й захваченной группе, как и\n
прежде.Для замены
12345
построенная строка имеет вид1\g<1>2\g<2>3\g<3>4\g<4>5
.re.sub(...,...,s,1)
выполняет не более одной замены в строкеs
.источник
Пиф, 27
Тестирование
Набор тестов пропускает последние два случая, потому что им не хватит памяти. Алгоритм, используемый здесь, заключается в том, чтобы найти все индексы каждого символа во второй строке в первой строке, затем найти все возможные упорядочения этих индексов и выбрать только те, которые находятся в отсортированном порядке. Затем используйте первый из них в отсортированном порядке в качестве списка индексов в первой строке, чтобы обновить значения из третьей строки.
Я чувствую, что должно быть что-то короче, чем
.nM*F
...источник
MATL , 33 байта
Попробуйте онлайн!
объяснение
источник
JavaScript (ES6), 84 байта
Объяснение / Тест
Показать фрагмент кода
источник
JavaScript (ES6),
8476 байтПотому что я был уверен, что это работа для RegExp.
Редактировать: Сохранено 8 байтов благодаря @ MartinBüttner ♦.
Порт ответа @ KevinLau Ruby занял 82 байта:
Я также попробовал рекурсивное решение RegExp, но это заняло 90 байт:
источник
Юлия,
8970 байтИспользует индекс
i
для перебора строк шаблона / замены по ходу работы. -19 байтов благодаря @Dennis!источник
C 98 байт
/ * Расширенный код * /
Аргументы: я Nput строки, о utput буфера, ˙s нити поиска строки, г Дороги.Cтроительства и .
Запомнив начало ввода и вывода, мы проходим ввод, заменяя и продвигая замену всякий раз, когда мы нажимаем один. В конце, если у нас закончились замены, верните выходной буфер, иначе неизмененный ввод.
/ * Тесты * /
источник
R, 76 байт
используется
sub
для замены первого совпаденияUngolfed
источник
C ++, 204 байта
Golfed
Ungolfed
источник
std
достаточно, чтобы оправдать использованиеusing namespace std;
. Использованиеstd::cin
,std::cout
иstd::string
сэкономит 5 байтов, поскольку они, по-видимому, являются единственным использованием этого пространства имен.b
ina
, но более поздние буквы также должны быть после более ранних. (Посмотрите на тестовый пример 3 и сравните с вашим выводом, я думаю, вы обнаружите, что ваш код будет выводиться,abc21ed...
когда ожидаемый результат будетabcd1e2...
!)Сетчатка , 63 байта
Ввод принимается в порядке
B
,C
,A
, разделенный пробельных символами.Попробуйте онлайн.
источник
Haskell, 87 байт
Я заметил отсутствие ответа на Haskell и решил это исправить. Это определяет троичную функцию
!
с аргументом pattern-replace-string. Попробуй это здесь.объяснение
Вспомогательная функция
#
принимает списокx
пар символов (шаблон и замена) и строкуy
. Если символы «шаблона»x
образуют подпоследовательностьy
, возвращается пустой список, иy
каждый символ шаблона заменяется его аналогом. В противном случае он возвращает пару(x,y)
. Функция!
упаковывает строки шаблона и замены в третью строку,x
применяет ее#
кx
третьей строке и возвращает ее, а также возвращает второй компонент результата.Если шаблон является подпоследовательностью строки, код выполняется за O (n) времени, делая один рекурсивный проход по строке и жадно создавая замену в процессе. Однако, если шаблон не является подпоследовательностью, в худшем случае он выполняется за O (2 n ) времени. Это происходит потому, что в каждой позиции, где шаблон и строка имеют совпадающий символ, функция вызывает себя, чтобы проверить, является ли шаблон на самом деле подпоследовательностью, обнаруживает, что это не так, и вызывает себя во второй раз для фактического вычисления результата.
источник
JavaScript (ES6),
10095 байтЭто действительная JavaScript-функция Lambda. Выходы как функция
return
. Принимает три аргумента (a,b,c
). Добавитьf=
в начале и вызвать какf(arg1,arg2,arg3)
.источник
f=
если ваша функция не является рекурсивной, но она не выглядит так, как она есть.a
не содержит шаблон. Я также не уверен, что возвращение массива строк является приемлемым.C (gcc),
67626159 байтПопробуйте онлайн!
источник
Октава, 97 байт
Выполните итерацию по подпоследовательности для замены; найти первое вхождение первого символа, найти следующий символ в оставшейся строке, повторить. Один интересный момент этого:
Так как ideone по-прежнему не принимает функции с именами, отличными от '', я просто оставлю здесь пример выполнения. Входы показаны только для первых нескольких тестов для краткости.
key
является ожидаемым результатом,ans
является выходом функции.источник
D(t=...)
) продолжают озадачивать меня :-)Python 3, 123 байта
Я хотел бы поделиться другим подходом, который на несколько байт короче. Нет никаких правил против стандартной библиотеки / регулярных выражений, верно?
PS. Это мой первый гольф. Дайте мне знать о любых проблемах / улучшениях.
источник
Pyth, 22 байта
Проверьте все контрольные примеры в компиляторе Pyth .
Задний план
Мы строим регулярное выражение из шаблона, добавляя a
$
и помещая(.*?)
между всеми символами. Это регулярное выражение будет соответствовать подпоследовательности, подлежащей замене, и всем, что находится между его элементами, и чему угодно, вплоть до конца строки.Поскольку квантификаторы ленивы, каждый
(.*?)
будет соответствовать как можно символов.Для образца-призрака построенное регулярное выражение
g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)$
.Если шаблон соответствует входу, встроенный
r<str><regex>3
вернет массив, содержащий предварительное совпадение (все до подпоследовательности), все захваченные группы (все в промежутке между подпоследовательностью и после) и постматч (пустая строка).Если шаблон не совпадает, встроенная функция вернет одноэлементный массив, содержащий исходные данные.
Как это работает
источник
Желе , 23 байта
Это на два байта длиннее, чем мой другой ответ желе , но он заканчивается мгновенно. Попробуйте онлайн!
верификация
Как это работает
источник
CJam, 29 байт
Попробуйте онлайн! или проверьте все контрольные примеры .
источник
Java 7, 102 байта
Подробная попытка здесь
источник
Юлия,
939086 байтНеобходимость отдельно проверить, был ли матч успешным, своего рода уничтожает счет. Замена потребует приведения к
Base.SubstitutionString
, что, вероятно, не стоит ...Тестовый забег
источник
Юлия,
625958 байтВвод / вывод осуществляется в виде символьных массивов.
верификация
источник
PHP,
130109 байтЯ все еще хотел бы это короче; может сохранить 3 байта (
""<
), еслиB
гарантированно не содержит0
.принимает аргументы из командной строки. Беги с
-r
.Заменяет персонажей, когда находит их;
печатает копию, если все символы были заменены; оригинал остальное.
источник
Рубин,
70645958 байтАнонимная функция. Пройдите через строку,
a
чтобы построить новую строку с заменой букв в соответствии со следующим символом вb
иc
, затем, если все символы вb
конце исчерпаны, верните вновь созданную строку, в противном случае верните исходную строку.@histocrat помог сохранить 6 байтов через
gsub
.Сохранено 1 байт благодаря @Cyoce.
Попробуйте онлайн!
источник
-1+i+=1
на~-i+=1
Perl, 80 + 1 = 81 байт
Беги с
-p
флагомПопробуйте онлайн!
Код процедурно генерирует команду regex для поиска и замены, которую затем выполняет в последнем бите кода.
Строка
ghost
в первом примере превращается в строкуg(.*?)h(.*?)o(.*?)s(.*?)t(.*?)
, что означает 0, заg
которыми следуют 0 или более символов, за которымиh
следуют 0 или более символов, а затем и т. Д.*?
Квантификатор означает, что поиск должен быть не жадным и «gobble». msgstr "как можно меньше символов вместо соответствия по умолчанию.Строка
12345
затем превращается в1 .$1.2 .$2.3 .$3.4 .$4.5 .$5
, который оценивается после выполнения регулярного выражения. Каждый из$1,$2,$3,$4,$5
них на самом деле является обратной ссылкой на группу захвата (в скобках) из первой строки.источник
perl -pe 'eval"s/".<>=~s/.\K/(.*?)/gr."/".<>=~s/.\K/"\${".++$i."}"/gre."/"'
. Я придумал это сам, но он довольно близок к вашему, поэтому я не буду публиковать его, это будет два очень близких ответа, но вы можете редактировать свой!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 байт
Основное
reduce
, не слишком рад всех тех , кто долгоfirst
,rest
иconj
вызовы функций. Надеюсь увидеть лучший подход.источник