Подпоследовательность Подстановка

30

Большинство языков поставляется со встроенным для поиска в строке всех вхождений данной подстроки и замены их на другую. Я не знаю ни одного языка, который обобщает эту концепцию на (не обязательно смежные) подпоследовательности. Так что это ваша задача в этом вызове.

Ввод будет состоять из трех строк 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

Мартин Эндер
источник
Будет ли список строк из одного символа в порядке для ввода / вывода?
FryAmTheEggman
@FryAmTheEggman Хм, единственное согласие, которое я могу найти, это то, что списки односимвольных строк не рассматриваются как допустимые строковые представления. Возможно, стоит написать мета-пост (особенно потому, что я думаю, что это также связано с последним вызовом xnor). Я собираюсь сказать нет сейчас.
Мартин Эндер
А как насчет массивов символов? Это , кажется, подразумевает , что они позволили даже если язык имеет правильный тип строки.
Деннис
@Dennis Да, массивы символов - это хорошо, но одиночные строки - это все равно, что принимать массив целых чисел [[1], [2], [3]].
Мартин Эндер
Хорошо, спасибо за разъяснение.
Деннис

Ответы:

3

Желе , 23 22 21 байт

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

Попробуйте онлайн! Обратите внимание, что в двух последних тестовых случаях не хватит памяти.

верификация

$ 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)

Как это работает

='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.
Деннис
источник
12

Python 2, 88 байт

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>'']

Функция, которая принимает три строки и выводит результат в STDOUT. Функция просто пропускает строку, беря соответствующий символ и обновляя его по b,cмере продвижения.

Для тестирования (после замены printс 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
источник
9

Ява 7, 141

Я думаю, что есть еще что-то, что я могу сделать с этим, но я должен бежать пока. Это просто простая итерация / замена с сохранением индекса в A и 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;}

Пробелы для вашего удовольствия:

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
источник
Whitespacedда, это полностью читаемо
кошка
Разве это не так? Основная причина, по которой я добавляю многострочную версию с отступом, заключается в том, чтобы избежать горизонтальной прокрутки, чтобы все это можно было увидеть сразу. Встроенные пробелы не так
уж важны,
[функция-запрос] еще больше пробелов
Алекс А.
@AlexA. Вот и ты!
Geobits
@Geobits Сохраните байт в конце, если вы это сделаетеj<k?a:d
Xanderhall
7

Луа, 121 байт

Простое решение, gsubпозволяет нам выполнять итерации ровно один раз для каждого символа и заменять их в новом экземпляре строки.

Он принимает ввод через 3 аргумента командной строки и выводит строку в 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)

Ungolfed

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
источник
6

Python 3, 127 байт.

Сохранено 16 байтов благодаря Katenkyo.

Все еще работая над этим немного, человек был таким противнее, чем я думал.

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

Пояснение: Оу, да, рекурсия.

Тестовые случаи:

assert f('abcdeedcba', 'ada', 'BOB') == 'BbcOeedcbB'
assert f('abcdeedcbaabcde', 'ed', '12') == 'abcd1e2cbaabcde'
assert f('012345678901234567890123456789', '42', 'TT') == '0123T5678901T34567890123456789'
assert f('ABC', 'ABCD', '1234') == 'ABC'
Морган Трепп
источник
+1 для игры в гольф 50, но продолжайте! Это должно превзойти мой ответ на Java как минимум;)
Geobits
7
@ Geobits Да, я никогда не проигрывал Java. Это мой величайший позор.
Морган Трепп
Я не очень разбираюсь в python, но all(x in a for x in b)также проверяю, что элементы в b и a появляются в том же порядке, или только если они здесь?
Катенкё
@Katenkyo Только то, что они все там, но порядок обрабатывается нарезкой, когда мы повторяем.
Морган Трепп
Хорошо, кроме того, не 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заставит вас сохранить несколько байтов?
Катенкё
5

Python 3.5, 87 байт

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

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.

Деннис
источник
4

Пиф, 27

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

Тестирование

Набор тестов пропускает последние два случая, потому что им не хватит памяти. Алгоритм, используемый здесь, заключается в том, чтобы найти все индексы каждого символа во второй строке в первой строке, затем найти все возможные упорядочения этих индексов и выбрать только те, которые находятся в отсортированном порядке. Затем используйте первый из них в отсортированном порядке в качестве списка индексов в первой строке, чтобы обновить значения из третьей строки.

Я чувствую, что должно быть что-то короче, чем .nM*F...

FryAmTheEggman
источник
4

MATL , 33 байта

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

Попробуйте онлайн!

объяснение

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)
Луис Мендо
источник
3

JavaScript (ES6), 84 байта

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

Объяснение / Тест

user81655
источник
3

JavaScript (ES6), 84 76 байт

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

Потому что я был уверен, что это работа для RegExp.

Редактировать: Сохранено 8 байтов благодаря @ MartinBüttner ♦.

Порт ответа @ KevinLau Ruby занял 82 байта:

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

Я также попробовал рекурсивное решение RegExp, но это заняло 90 байт:

f=(a,[b,...d],[c,...e])=>b?a.replace(RegExp(b+'(.*'+d.join`.*`+'.*)'),(_,s)=>c+f(s,d,e)):a
Нил
источник
3

Юлия, 89 70 байт

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

Использует индекс iдля перебора строк шаблона / замены по ходу работы. -19 байтов благодаря @Dennis!

Sp3000
источник
2

C 98 байт

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;}

/ * Расширенный код * /

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;
}

Аргументы: я Nput строки, о utput буфера, ˙s нити поиска строки, г Дороги.Cтроительства и .

Запомнив начало ввода и вывода, мы проходим ввод, заменяя и продвигая замену всякий раз, когда мы нажимаем один. В конце, если у нас закончились замены, верните выходной буфер, иначе неизмененный ввод.

/ * Тесты * /

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;
}
Тоби Спейт
источник
2

R, 76 байт

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

используется subдля замены первого совпадения

Ungolfed

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
источник
2

C ++, 204 байта

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;}

Ungolfed

#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;
}
Мишельфрансис Бустильос
источник
Я не думаю, что вы используете stdдостаточно, чтобы оправдать использование using namespace std;. Использование std::cin, std::coutи std::stringсэкономит 5 байтов, поскольку они, по-видимому, являются единственным использованием этого пространства имен.
Value Ink
@KevinLau Спасибо! Вы очень правы, я думал об этом, но на самом деле не рассчитывал понять, что это спасет символы.
Мишельфрансис Бустильос
Ой! Еще одна вещь, так как это важно. После повторного прочтения вашего кода я понял, что вы жадно заменяете самое левое вхождение каждой буквы в bin a, но более поздние буквы также должны быть после более ранних. (Посмотрите на тестовый пример 3 и сравните с вашим выводом, я думаю, вы обнаружите, что ваш код будет выводиться, abc21ed...когда ожидаемый результат будет abcd1e2...!)
Value Ink
В вводе компилятором ideone C ++ 14 "Adregffftd \ nA23 \ nzac \ n" выше кода 10 минут назад генерируйте выходные данные "zdregffftd" вместо "Adregffftd"
RosLuP
2

Haskell, 87 байт

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#)

Я заметил отсутствие ответа на Haskell и решил это исправить. Это определяет троичную функцию !с аргументом pattern-replace-string. Попробуй это здесь.

объяснение

Вспомогательная функция #принимает список xпар символов (шаблон и замена) и строку y. Если символы «шаблона» xобразуют подпоследовательность y, возвращается пустой список, и yкаждый символ шаблона заменяется его аналогом. В противном случае он возвращает пару (x,y). Функция !упаковывает строки шаблона и замены в третью строку, xприменяет ее #к xтретьей строке и возвращает ее, а также возвращает второй компонент результата.

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.

Если шаблон является подпоследовательностью строки, код выполняется за O (n) времени, делая один рекурсивный проход по строке и жадно создавая замену в процессе. Однако, если шаблон не является подпоследовательностью, в худшем случае он выполняется за O (2 n ) времени. Это происходит потому, что в каждой позиции, где шаблон и строка имеют совпадающий символ, функция вызывает себя, чтобы проверить, является ли шаблон на самом деле подпоследовательностью, обнаруживает, что это не так, и вызывает себя во второй раз для фактического вычисления результата.

Zgarb
источник
2

JavaScript (ES6), 100 95 байт

(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

Это действительная JavaScript-функция Lambda. Выходы как функция return. Принимает три аргумента ( a,b,c). Добавить f=в начале и вызвать как 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")))

Арджун
источник
Добро пожаловать в PPCG! Безымянные функции, как правило, приемлемы , поэтому вам не нужно, f=если ваша функция не является рекурсивной, но она не выглядит так, как она есть.
Мартин Эндер
@ MartinBüttner Спасибо! :) Обновил мой ответ.
Арджун
К сожалению, это не удастся, если aне содержит шаблон. Я также не уверен, что возвращение массива строк является приемлемым.
Деннис
@ Денис Я обновил свое решение. Я думаю, что сейчас это правильно. Извините за такой поздний ответ и обновление. (Я только что заметил ваш комментарий, отсюда и отсрочка)
Арджун,
@MartinEnder Пока я просматривал все свои решения, я обнаружил, что это неверно. Но я исправил это сейчас; и он на пять байт короче (так как я оставил много мест для игры в гольф нетронутыми; в то время я был начинающим игроком в гольф; хотя сейчас я не великолепен: p). Извините за публикацию неправильного решения.
Арджун,
1

Октава, 97 байт

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;

Выполните итерацию по подпоследовательности для замены; найти первое вхождение первого символа, найти следующий символ в оставшейся строке, повторить. Один интересный момент этого:

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

Так как ideone по-прежнему не принимает функции с именами, отличными от '', я просто оставлю здесь пример выполнения. Входы показаны только для первых нескольких тестов для краткости. keyявляется ожидаемым результатом, ansявляется выходом функции.

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
мерный стакан
источник
Эти задания Октавы в неожиданных местах ( D(t=...)) продолжают озадачивать меня :-)
Луис Мендо,
1
@ LuisMendo хаха ... это почти как ... стек! :)
стакан
1

Python 3, 123 байта

Я хотел бы поделиться другим подходом, который на несколько байт короче. Нет никаких правил против стандартной библиотеки / регулярных выражений, верно?

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)

PS. Это мой первый гольф. Дайте мне знать о любых проблемах / улучшениях.

Марк Дж
источник
1

Pyth, 22 байта

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

Проверьте все контрольные примеры в компиляторе Pyth .

Задний план

Мы строим регулярное выражение из шаблона, добавляя a $и помещая (.*?)между всеми символами. Это регулярное выражение будет соответствовать подпоследовательности, подлежащей замене, и всем, что находится между его элементами, и чему угодно, вплоть до конца строки.

Поскольку квантификаторы ленивы, каждый (.*?)будет соответствовать как можно символов.

Для образца-призрака построенное регулярное выражение g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)$ .

Если шаблон соответствует входу, встроенный r<str><regex>3 вернет массив, содержащий предварительное совпадение (все до подпоследовательности), все захваченные группы (все в промежутке между подпоследовательностью и после) и постматч (пустая строка).

Если шаблон не совпадает, встроенная функция вернет одноэлементный массив, содержащий исходные данные.

Как это работает

|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.
Деннис
источник
1

Желе , 23 байта

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

Это на два байта длиннее, чем мой другой ответ желе , но он заканчивается мгновенно. Попробуйте онлайн!

верификация

$ 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

Как это работает

⁴='-;ç\ñ⁴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.
Деннис
источник
1

Java 7, 102 байта

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++];}

Подробная попытка здесь

// 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
источник
1

Юлия, 93 90 86 байт

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

Необходимость отдельно проверить, был ли матч успешным, своего рода уничтожает счет. Замена потребует приведения кBase.SubstitutionString , что, вероятно, не стоит ...

Тестовый забег

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"
Деннис
источник
1

Юлия, 62 59 58 байт

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

Ввод / вывод осуществляется в виде символьных массивов.

верификация

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"
Деннис
источник
1

PHP, 130 109 байт

Я все еще хотел бы это короче; может сохранить 3 байта ( ""<), если Bгарантированно не содержит 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;

принимает аргументы из командной строки. Беги с -r.

Заменяет персонажей, когда находит их;
печатает копию, если все символы были заменены; оригинал остальное.

Titus
источник
1

Рубин, 70 64 59 58 байт

Анонимная функция. Пройдите через строку, aчтобы построить новую строку с заменой букв в соответствии со следующим символом вb и c, затем, если все символы в bконце исчерпаны, верните вновь созданную строку, в противном случае верните исходную строку.

@histocrat помог сохранить 6 байтов через gsub.

Сохранено 1 байт благодаря @Cyoce.

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

Попробуйте онлайн!

Значение чернил
источник
Вы можете сохранить байт, заменив -1+i+=1на~-i+=1
Cyoce
0

Perl, 80 + 1 = 81 байт

Беги с -pфлагом

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

Попробуйте онлайн!

Код процедурно генерирует команду 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;'
Уилл Кроуфорд
0

Clojure, 113 байт

#(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))

Основное reduce, не слишком рад всех тех , кто долго first, restи conjвызовы функций. Надеюсь увидеть лучший подход.

NikoNyrh
источник