Рекурсивная подстановка строк

25

Задание

Напишите программу или функцию, которая с учетом трех строк A, B, Cсоздает выходную строку, в которой каждый экземпляр Bin Aбыл рекурсивно заменен C. Под рекурсивной подстановкой понимается повторение подстановки, когда на каждом шаге все неперекрывающиеся экземпляры Bin A(выбираются жадно слева направо) заменяются на, Cпока Bбольше не содержится в A.

Ввод, вывод

  • Вы можете использовать любой из методов по умолчанию для ввода / вывода .
  • Строки будут содержать только печатаемые символы ASCII (и могут содержать любые из них).
  • Bникогда не будет пустой строкой, Aа Cможет быть.
  • Строки следует рассматривать как открытый текст, например, вы не можете рассматривать их Bкак шаблон Regex.
  • Некоторые комбинации входов никогда не прекратятся. Ваша программа может делать что угодно в этих случаях.

Контрольные примеры

Это в формате: A/B/C\nOutput

Hello, world!/world!/PPCG
Hello, PPCG

Uppercase is up/up/down
Uppercase is down

ababababa/aba/ccc
cccbcccba

delete/e/{empty string}
dlt

{empty string}/no/effect
{empty string}

llllrrrr/lr/rl
rrrrllll

+-+-+-+/+-+/+
+

ababababa/aba/bada
badabbadbada

abaaba/aba/ab
abb

((())())())/()/{empty string}
)

Примеры, которые не заканчиваются:

grow/ow/oow

loop/lo/lo
Лео
источник
3
Еще один контрольный пример:((())())())/()/
Конор О'Брайен,
@ ConorO'Brien добавил
Лев
1
Сначала я не смог сделать это с учетом регистра. downpercase is down
Тост инженера

Ответы:

7

05AB1E , 2 байта

`:

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

объяснение

`    # split input to stack
 :   # replace (until string doesn't change)

Это может быть :за 1 байт, если нам не нужно иметь дело с пустыми строками.

Emigna
источник
3
Если я правильно понимаю, ваше 4-байтовое решение действительно. «Некоторые комбинации входов никогда не прекратятся. Ваша программа может делать что угодно в этих случаях».
Лев
@Лео. Вы правы. Я
пролистал
1
Таким образом, в основном :это встроенный, который решает всю проблему? Я должен был запретить buildins;)
Лев
@Leo: Если бы не пустые строки, встроенная единственная решала бы это да. И единственная разница с пустыми строками заключается в том, что нам нужно указать, что существует 3 входа, которые иначе были бы неявно выведены операцией :)
Emigna
Это что - то вроде этого возможно?
Аднан
9

Python 2 , 43 байта

lambda s,*l:eval('s'+'.replace(*l)'*len(s))

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

Оценивает строку вида

s.replace(*l).replace(*l).replace(*l) ...

Чтобы достичь фиксированной точки, если она существует, достаточно сделать замены, равные длине исходной строки.

XNOR
источник
7

ES6 (Javascript), 4743 байта

  • Сохранено 4 байта с использованием каррирования (спасибо @Neil!)

Golfed

c=>b=>R=a=>(x=a.split(b).join(c))==a?x:R(x)

Попытайся

Q=c=>b=>R=a=>(x=a.split(b).join(c))==a?x:R(x)

function doit() {
  console.log(Q(C.value)(B.value)(A.value));
}
A: <input type="text" value="abaaba" id="A"/> B: <input type="text" value="aba" id="B"/> C: <input type="text" value="ab" id="C"/> <input type="submit" onclick="doit();" value="REPLACE"/>

дирижабль
источник
Вы можете сэкономить 4 байта, каррируя аргументы в обратном порядке:c=>b=>g=a=>a==(a=a.split(b).join(c))?a:g(a)
Нейл
К сожалению. i.imgur.com/vPCycwR.png
Metoniem
@MetoniemSome combinations of inputs will never terminate. Your program can do anything in those cases.
дирижабль
@zeppelin О, я вижу.
Метония
5

Сетчатка , 27 байт

Число байтов предполагает кодировку ISO 8859-1.

+`(.+)(?=.*¶\1¶(.*))
$2
G1`

Ввод должен быть разделен переводом строки.

Попробуйте онлайн! (Для удобства используется формат ввода набора тестов, где каждая строка представляет собой разделенные слешем тестовые случаи.)

Мартин Эндер
источник
4

C #, 44 байта

Укороченная версия:

r=(a,b,c)=>a==(a=a.Replace(b,c))?a:r(a,b,c);

Пример программы:

using System;

namespace ConsoleApplication1
{
    class Program
    {
    static void Main(string[] args)
        {
            Func<string, string, string, string> r = null;
            r=(a,b,c)=>a==(a=a.Replace(b,c))?a:r(a,b,c);

            Action <string, string, string, string> test =
                (a, b, c, answer) =>
                {
                    var result = r(a, b, c);
                    Console.WriteLine("A: \"{0}\"\r\nB: \"{1}\"\r\nC: \"{2}\"\r\nResult: \"{3}\"\r\n{4}\r\n\r\n",
                        a, b, c, result, result == answer ? "CORRECT" : "INCORRECT"
                        );
                };

            test("Hello, world!", "world!", "PPCG", "Hello, PPCG");
            test("Uppercase is up", "up", "down", "Uppercase is down");
            test("ababababa", "aba", "ccc", "cccbcccba");
            test("delete", "e", "", "dlt");
            test("", "no", "effect", "");
            test("llllrrrr", "lr", "rl", "rrrrllll");
            test("+-+-+-+", "+-+", "+", "+");
            test("ababababa", "aba", "bada", "badabbadbada");
            test("abaaba", "aba", "ab", "abb");
            test("((())())())", "()", "", ")");


            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }
    }
}

Объяснение: Функция написана как хвостовое рекурсивное выражение, избегая ключевого слова return и фигурных скобок, используя следующее:

  • Присвоение в скобках возвращает присвоенное значение
  • Левая сторона проверки на равенство будет оценена перед правым присваиванием, что позволит нам сравнивать до / после встраивания и по-прежнему получать доступ к результату.

Это позволяет нам сохранить это в одном утверждении.

РЕДАКТИРОВАТЬ: Вернулся к пропущению типа функции r, так как это кажется приемлемым. При объявлении типа с использованием массивов это 68 символов. Без, это 44 символа.

Даниил
источник
Если функция будет работать, только если ей присвоено определенное имя, вам нужно потратить байты, чтобы присвоить функции это имя. Для меня не сразу очевидно, будет ли это 2 байта для объявления r=или еще больше для объявления (частично потому, что я не полностью знаю правила, частично потому, что я не знаю C # достаточно хорошо, чтобы их применять).
Да, я просто исправлял это после прочтения чужого комментария к другой записи. И это гораздо больше, так как все типы должны быть указаны. Я переключился на использование массива, чтобы сэкономить на этом, и сохранить байты при рекурсивном вызове.
Даниэль
Что вы имеете в виду с не дает правильный вывод ? Я не думаю, что вам нужно выводить входные данные, на самом деле, некоторые другие ответы не делают этого. Я пропустил комментарий о том, что мне нужно вывести ввод?
17
Неважно, я нашел проблему, это не рекурсивно.
auhmaan
2

Japt , 15 байт

@¥(U=UqV qW}a@U

Проверьте это онлайн!

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

@¥(U=UqV qW}a@U  // Implicit: U, V, W = input strings
            a@U  // Return the first non-negative integer mapped by the function X => U
@          }     // that returns truthily when mapped through this function:
     UqV qW      //   Split U at instances of V, and rejoin with W.
  (U=            //   Set U to this new value.
 ¥               //   Return (old U == new U). This stops the loop when U stops changing.
                 // Implicit: output result of last expression

Japt имеет встроенную рекурсивную замену, но он видит первый вход как регулярное выражение. Если входные данные гарантированно содержат только буквенно-цифровые символы, это трехбайтовое решение будет работать:

eVW

Если бы входные данные могли содержать любой символ кроме ^, \или ], это 12-байтовое решение было бы правильным:

eV®"[{Z}]"ÃW
ETHproductions
источник
2

C #, 33 49 байт

Вероятно, один из самых маленьких фрагментов, написанных на C # ... А поскольку он Replaceявляется родным для stringструктуры, в s нет необходимости using(по крайней мере, для встроенной функции VS, C # Interactive ... )

Кроме того, так как Bвсегда имеет значение, код не нуждается в каких-либо проверках.


Golfed

(a,b,c)=>{while(a!=(a=a.Replace(b,c)));return a;}

Ungolfed

(a, b, c) => {
    while( a != ( a = a.Replace( b, c ) ) );

    return a;
}

Полный код

using System;

namespace Namespace {
    class Program {
        static void Main( string[] args ) {
            Func<string, string, string, string> func = (a, b, c) => {
                // Recursively ( now truly recursive ) replaces every 'b' for 'c' on 'a',
                // while saving the value to 'a' and checking against it. Crazy, isn't it?
                while( a != ( a = a.Replace( b, c ) ) );

                return a;
            };

            int index = 1;

            // Cycle through the args, skipping the first ( it's the path to the .exe )

            while( index + 3 < args.Length ) {
                Console.WriteLine( func(
                    args[index++],
                    args[index++],
                    args[index++]) );
            }

            Console.ReadLine();
        }
    }
}

релизы

  • v1.1 - +19 bytes- Исправлено не рекурсивное решение.
  • v1.0 -  33 bytes- Исходное решение.
auhmaan
источник
1
Я вижу, что C # I upvote
Nelz
@NelsonCasanova Похоже на меня.
Метония
Выполняет ли Replaceрекурсивная замена?
Лайкони
@ Лайкони нет. Например, "((())())())".Replace("()", "")возвращает (())).
auhmaan
Тогда это решение не действует по правилам конкурса. Вы должны удалить его, чтобы избежать отрицательных голосов, затем исправить ваше решение для обработки рекурсивной замены и, наконец, восстановить его.
Лайкони
1

Обработка, 75 72 байта

void g(String a,String[]s){for(;a!=(a=a.replace(s[0],s[1])););print(a);}

Печатает результаты. Назови это какg("llllrrrr", new String[]{"lr","rl"});

void Q110278(String a, String[]s){             //a is the string to be replaced
                                               //s is the array containing the subsitution

  for(; a!=                                    
            (a = a.replace(s[0], s[1])) ;);

  //for-loop where we continuously perform substitution on a
  //until a is equal to substituted a


  //at the end, print the final version of a
  print(a);
}
Kritixi Lithos
источник
1

Mathematica, 35 32 байта

#//.x_:>StringReplace[x,#2->#3]&

Аргументы приведены в виде последовательности. Никогда не прекращается в течение , growнапример, возвращается loopк loopпримеру. Три байта прочь благодаря предложению Мартина.

Симмонс
источник
FixedPointимеет тенденцию быть слишком длинным и может эмулироваться с помощью //.:#//.x_:>StringReplace[x,#2->#3]&
Мартин Эндер
Спасибо @MartinEnder. Это хороший способ заставить ReplaceRepeatedработать на струнах!
Симмонс
Кстати, это будет только $RecursionLimitвремя цикла , что 2^16по умолчанию не влияет на ваш ответ
ngenisis
@ngenesis Я не уверен, что ReplaceRepeatedэто контролируется $RecursionLimit- я только что проверил это, установив ограничение в 20, и программа все еще счастливо циклично выполняет непрерывный ввод ..
Симмонс
Ибо ReplaceRepeatedесть отдельная опция (которую нельзя использовать с //.синтаксисом), называется MaxIterations. Это по умолчанию 2 ^ 16. (cc @ngenisis)
Мартин Эндер
1

Рубин, 29 байт

->a,b,c{1while a.gsub! b,c;a}

Учитывая 3 аргумента, применяйте замену к первому, пока больше не будет ничего заменить.

объяснение

  • 1прежде чем whileэто просто nop
  • gsub!возвращает строку или nilесли подстановка не произошла
гигабайт
источник
1

/// , 3 байта

///

Поместите строку B после первой косой черты, C после второй и A в конце, то есть:

/<B>/<C>/<A>

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

steenbergh
источник
Я не думаю, что это приемлемый способ получения входных данных
Лев
Насколько мне известно, ///не принимает входные данные любым другим способом.
Steenbergh
2
Что ж, я думаю, что было бы интересно обсудить, является ли это приемлемым, тогда :) В любом случае, я заметил еще одну проблему с вашей отправкой: она не работает, если /присутствует a в любой из входных строк
Лев
1

JavaScript (Firefox 48 или более ранняя версия), 43 байта

c=>b=>g=a=>a==(a=a.replace(b,c,'g'))?a:g(a)

Принимает аргументы карри в обратном порядке. В Firefox был нестандартный третий параметр, для replaceкоторого указывались флаги регулярного выражения. Этот параметр был удален в Firefox 49.

Нил
источник
0

SmileBASIC, 72 68 байт

I=0DEF R A,B,C
I=INSTR(A,B)?A*(I<0)A=SUBST$(A,I,LEN(B),C)R A,B,C
END

Одним из редких случаев, когда создание функции на самом деле является SHORTER в SmileBASIC.

12Me21
источник
0

Javascript 130 байт

f=(a,b,c)=>a.indexOf(b)<0?a:f(eval("a.replace(/"+b.replace(/([\/\,\!\\\^\$\{\}\[\]\(\)\.\*\+\?\|\<\>\-\&])/g,"\\$&")+"/g,c)"),b,c)

Javascript заменит все одновременно, если вы дадите ему регулярное выражение. Чтобы это регулярное выражение работало для всех значений, все символы, используемые для регулярного выражения, должны быть заменены на экранированную версию. Наконец, замена вычисляется, чтобы заменить все экземпляры B в A на C и снова передать это обратно в функцию.

fənɛtɪk
источник
0

Чеддер, 37 байт

(a,b,c)f->a has b?f(a.sub(b,c),b,c):a

На телефоне, поэтому добавить ссылку TIO немного сложно. В основном использует рекурсию, в то время как проверка находится в. Решение могло бы быть, (a,b,c)->a.sub(Regex{b,"cr"},c)но по какой-то причине не работает.

Downgoat
источник
Sub заменяет все или только первое?
f17n attɪk
@LliwTelracs, потому что они строки .sub заменит все
Downgoat
Это не похоже на работу? Попробуйте онлайн!
Конор О'Брайен,
@ ConorO'Brien дерьмо глупые ошибки стороны троичного не в порядке
Downgoat
0

Perl 6 , 40 байт

{$^b;$^c;($^a,{S:g/$b/$c/}...*eq*)[*-1]}

Попробуй (если обновится tio.run)
Попробуй измененную версию

Expanded:

{
  $^b;           # declare second parameter ( not used here )
  $^c;           # declare third parameter  ( not used here )

  (

    $^a,         # declare first parameter, and use it to seed the sequence

    {S:g/$b/$c/} # replace globally

    ...          # keep doing that

    * eq *       # until there are two that match

  )[*-1]
}
Брэд Гилберт b2gills
источник
0

PHP, 46 байт

function g($a,$b,$c){echo strtr($a,[$b=>$c]);}
MonkeyZeus
источник
0

PHP, 102 байта

list($n,$s,$a,$b)=$argv;$f=str_replace($a,$b,$s);while($s!=$f){$s=$f;$f=str_replace($a,$b,$s);}echo$f;

Тестовые случаи (функциональные)

Тестовый случай с ошибкой цикла

roberto06
источник
Здравствуй! Обычно при отправке функции вы должны добавить к байту все, что необходимо для определения функции (в вашем случае function replace(...){...}, иначе ваша отправка - просто фрагмент, который по умолчанию запрещен
Лев
@Leo Не знал этого, отредактировал мой ответ;)
roberto06
0

Java - 157 байт

String r(String f){if(f.length()<1)return "";String[]x=f.split("/");if(x[0].contains(x[1]))return r(x[0].replace(x[1],x[2])+'/'+x[1]+'/'+x[2]);return x[0];}

Для пустого ввода возвращает пустую строку.

Вылетает с StackOverflowExceptionошибкой, когда Bпусто или оно снабжено такими даннымиA/A/A .

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

r("ABCD/A/F") returns value of r("FBCD/A/F") which returns FBCD
If there is no more characters to be replaced it returns the final output

Развернутый код с комментариями:

String r (String f) {
    if(f.length() < 1)
        return ""; // For empty input return empty output
    String[] x = f.split("/"); // Get all 3 parameters
    if (x[0].contains(x[1])) // If input contains replaced value
        return r(x[0].replace(x[1],x[2])+'/'+x[1]+'/'+x[2]); // Return value of r() with one character replaced
    return x[0]; // If nothing to replace return the output(modified input)
}
печенье
источник
0

AutoHotkey, 87 байт

StringCaseSense,On
Loop{
IfNotInString,1,%2%,Break
StringReplace,1,1,%2%,%3%
}
Send,%1%

%1%,, %2%и %3%первые 3 аргумента, переданные в функцию.
Если функция ожидает переменный аргумент, %s отбрасывается.
Изменение значения чувствительности к регистру стоит 19 байт, но без него вы получите такие вещи, как downpercase is down.

Инженер Тост
источник