24
\$\begingroup\$

The task

Write a program or function that given three strings A, B, C produces an output string where each instance of B in A has been recursively substituted with C. Recursively substituting means repeating a substitution where at each step all non-overlapping instances of B in A (chosen greedily from left to right) are replaced with C until B is no more contained in A.

Input/Output

  • You may use any of the default methods for I/O.
  • Strings will contain only printable ASCII characters (and may contain any of them) .
  • B will never be an empty string, while A and C might be.
  • Strings are to be considered plaintext, you can't for example treat B as a Regex pattern.
  • Some combinations of inputs will never terminate. Your program can do anything in those cases.

Test cases

These are in the format: 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}
)

Examples that don't terminate:

grow/ow/oow

loop/lo/lo
\$\endgroup\$
3
  • 3
    \$\begingroup\$ Another test case: ((())())())/()/ \$\endgroup\$ Feb 16, 2017 at 18:08
  • \$\begingroup\$ @ConorO'Brien added \$\endgroup\$
    – Leo
    Feb 16, 2017 at 18:37
  • 1
    \$\begingroup\$ At first, I failed to make it case-sensitive. downpercase is down \$\endgroup\$ Feb 24, 2017 at 21:35

22 Answers 22

9
\$\begingroup\$

Python 2, 43 bytes

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

Try it online!

Evaluates a string of the form

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

To reach a fixed point if one exists, it suffices to do replacements equal to the length of the original string.

\$\endgroup\$
0
7
\$\begingroup\$

05AB1E, 2 bytes

`:

Try it online!

Explanation

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

This could be : for 1 byte if we didn't have to deal with empty strings.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ If I understand it correctly, your 4-byte solution is valid. "Some combinations of inputs will never terminate. Your program can do anything in those cases." \$\endgroup\$
    – Leo
    Feb 16, 2017 at 15:33
  • \$\begingroup\$ @Leo. Right you are. I skimmed over that part :) \$\endgroup\$
    – Emigna
    Feb 16, 2017 at 15:47
  • 1
    \$\begingroup\$ So basically : is a builtin that solves the whole challenge? I should have banned builtins ;) \$\endgroup\$
    – Leo
    Feb 16, 2017 at 15:54
  • \$\begingroup\$ @Leo: If it weren't for the empty strings a single built in would solve this yes. And the only difference with empty strings is that we need to specify that there are 3 inputs, which otherwise would be implicitly inferred by the operation :) \$\endgroup\$
    – Emigna
    Feb 16, 2017 at 16:17
  • \$\begingroup\$ Is something like this also possible? \$\endgroup\$
    – Adnan
    Feb 16, 2017 at 18:27
7
\$\begingroup\$

ES6 (Javascript), 47, 43 bytes

  • Saved 4 bytes using currying (Thanks @Neil !)

Golfed

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

Try It

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"/>

\$\endgroup\$
4
  • \$\begingroup\$ You can save 4 bytes by currying the arguments in reverse order: c=>b=>g=a=>a==(a=a.split(b).join(c))?a:g(a) \$\endgroup\$
    – Neil
    Feb 16, 2017 at 19:58
  • \$\begingroup\$ Oops. i.imgur.com/vPCycwR.png \$\endgroup\$
    – Metoniem
    Feb 20, 2017 at 12:37
  • \$\begingroup\$ @Metoniem Some combinations of inputs will never terminate. Your program can do anything in those cases. \$\endgroup\$
    – zeppelin
    Feb 20, 2017 at 12:47
  • \$\begingroup\$ @zeppelin Oh, I see. \$\endgroup\$
    – Metoniem
    Feb 20, 2017 at 13:16
5
\$\begingroup\$

Retina, 27 bytes

Byte count assumes ISO 8859-1 encoding.

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

Input should be linefeed-separated.

Try it online! (For convenience, uses a test-suite input format where each line is a slash-separated test cases.)

\$\endgroup\$
4
\$\begingroup\$

C#, 44 Bytes

Short Version:

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

Example Program:

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

Explanation: The function is written as a tail recursive expression, avoiding the return keyword and curly brackets by exploiting the following:

  • An assignment within parenthesis returns the value assigned
  • The left side of the equality check will be evaluated before the right side assignment, allowing us to compare before/after inline, and still access the result

This lets us keep it to a single statement.

EDIT: Went back to omitting the type of function r, since that appears to be acceptable. With type declaration using arrays, it is 68 characters. Without, it is 44 characters.

\$\endgroup\$
4
  • \$\begingroup\$ If the function will only work if given a specific name, you'll need to spend the bytes to give the function that name. It's not immediately obvious to me whether that's 2 bytes for r= or many more for a declaration (partly because I don't fully know the rules, partly because I don't know C# well enough to apply them). \$\endgroup\$
    – user62131
    Feb 17, 2017 at 21:41
  • \$\begingroup\$ Yeah, I was just fixing that after having read someone else's comment on a different entry. And it is many more, since the types must all be specified. I switched to using an array to save on that, and save bytes on the recursive call. \$\endgroup\$
    – Daniel
    Feb 17, 2017 at 21:43
  • \$\begingroup\$ What do you mean with does not produce the correct output? I don't think you need to output the input, in fact, some of the other answers don't do it. Did I missed a comment saying that I need to output the input? \$\endgroup\$
    – auhmaan
    Feb 20, 2017 at 14:54
  • \$\begingroup\$ Nevermind, I've found the problem, it isn't recursive. \$\endgroup\$
    – auhmaan
    Feb 20, 2017 at 15:00
2
\$\begingroup\$

Ruby, 29 bytes

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

Given 3 arguments, apply substitution to the first until there is nothing to substitute anymore.

Explanation

  • 1 before the while is simply a nop
  • gsub! returns the string or nilif no substitution occurred
\$\endgroup\$
2
\$\begingroup\$

Japt, 15 bytes

@¥(U=UqV qW}a@U

Test it online!

How it works

@¥(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 has a recursive-replace built-in, but it sees the first input as a regex. If the inputs were guaranteed to only contain alphanumeric characters this three-byte solution would work:

eVW

If the input were allowed to contain any char except ^, \, or ], this 12-byte solution would be valid instead:

eV®"[{Z}]"ÃW
\$\endgroup\$
2
\$\begingroup\$

C#, 33 49 bytes

Probably, one of the smallest snippets written in C#... And since Replace is native to the string struct, there's no need for usings ( At least not on VS built-in feature, C# Interactive... )

Also, since B always has a value, the code doesn't need any validations.


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

Full code

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

Releases

  • v1.1 - +19 bytes - Fixed solution not being recursive.
  • v1.0 -  33 bytes - Initial solution.
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I see c# I upvote \$\endgroup\$
    – Nelson
    Feb 17, 2017 at 20:06
  • \$\begingroup\$ @NelsonCasanova Sounds like me. \$\endgroup\$
    – Metoniem
    Feb 20, 2017 at 12:38
  • \$\begingroup\$ Does Replace perform recursive replacement? \$\endgroup\$
    – Laikoni
    Feb 20, 2017 at 23:03
  • \$\begingroup\$ @Laikoni no. For instance, "((())())())".Replace("()", "") returns (())). \$\endgroup\$
    – auhmaan
    Feb 21, 2017 at 13:24
  • \$\begingroup\$ Then this solution is not valid under the rules of the challenge. You should delete it to prevent downvotes, then fix your solution to handle recursive replacement and finally undelete it. \$\endgroup\$
    – Laikoni
    Feb 21, 2017 at 14:06
1
\$\begingroup\$

Processing, 75 72 bytes

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

Prints the results. Call it like 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);
}
\$\endgroup\$
0
1
\$\begingroup\$

Mathematica, 35 32 Bytes

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

Arguments given as a sequence. Never terminates for grow example, returns loop for loop example. Three bytes off thanks to Martin's suggestion.

\$\endgroup\$
6
  • \$\begingroup\$ FixedPoint tends to be too long and can be emulated with //.: #//.x_:>StringReplace[x,#2->#3]& \$\endgroup\$ Feb 16, 2017 at 15:36
  • \$\begingroup\$ Thanks @MartinEnder. That's a good way of getting ReplaceRepeated to work for strings! \$\endgroup\$
    – A Simmons
    Feb 16, 2017 at 15:38
  • \$\begingroup\$ btw, this will only loop $RecursionLimit times, which is 2^16 by default, not that it affects your answer \$\endgroup\$
    – user61980
    Feb 17, 2017 at 4:49
  • \$\begingroup\$ @ngenesis I'm not sure that ReplaceRepeated is controlled by $RecursionLimit- I just tested it by setting the limit to 20 and the program still happily loops along for non-terminating input.. \$\endgroup\$
    – A Simmons
    Feb 17, 2017 at 10:24
  • \$\begingroup\$ For ReplaceRepeated there's a separate option (which can't be used with the //. syntax), called MaxIterations. That one defaults to 2^16. (cc @ngenisis) \$\endgroup\$ Feb 17, 2017 at 14:53
1
\$\begingroup\$

Pyke, 6 bytes

hVQtX:

Try it here!

\$\endgroup\$
1
\$\begingroup\$

///, 3 bytes

///

Put string B after the first slash, C after the second and A at the end, ie:

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

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ I don't think this is an acceptable way of taking inputs \$\endgroup\$
    – Leo
    Feb 16, 2017 at 18:43
  • \$\begingroup\$ To my knowledge, /// doesn't accept input in any other way. \$\endgroup\$
    – steenbergh
    Feb 16, 2017 at 18:44
  • 2
    \$\begingroup\$ Well, I think it would be interesting to discuss whether this is acceptable or not, then :) Anyway, I've noticed another problem with your submission: it doesn't work if a / is present in any of the input strings \$\endgroup\$
    – Leo
    Feb 16, 2017 at 18:53
1
\$\begingroup\$

JavaScript (Firefox 48 or earlier), 43 bytes

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

Takes arguments curried in reverse order. Firefox used to have a non-standard third parameter to replace which specified regexp flags. This parameter was removed in Firefox 49.

\$\endgroup\$
0
\$\begingroup\$

SmileBASIC, 72 68 bytes

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

One of the rare cases where making a function is actually SHORTER in SmileBASIC.

\$\endgroup\$
0
\$\begingroup\$

Javascript 130 bytes

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

Javascript will only replace all simultaneously if you give it a regex. In order to make this regex work for all values, all characters that are used for regex need to be replaced with the escaped version. Finally, the replace is evaluated to replace all instances of B in A with C and passing that back around to the function again.

\$\endgroup\$
0
\$\begingroup\$

q, 15 bytes

{ssr[;y;z]/[x]}

Example:

q){ssr[;y;z]/[x]}["llllrrrr";"lr";"rl"]
"rrrrllll"

link to interpreter download

Explanation: ssr, / (converge)

\$\endgroup\$
0
\$\begingroup\$

Cheddar, 37 bytes

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

On phone so TIO link is a bit difficult to add. Basically uses recursion while checking is b is in a. Solution could of been (a,b,c)->a.sub(Regex{b,"cr"},c) but doesn't work for some reason.

\$\endgroup\$
4
  • \$\begingroup\$ Does sub replace all or just the first? \$\endgroup\$ Feb 16, 2017 at 15:24
  • \$\begingroup\$ @LliwTelracs because they are strings .sub will replace all \$\endgroup\$
    – Downgoat
    Feb 16, 2017 at 15:29
  • \$\begingroup\$ This doesn't seem to work? Try it online! \$\endgroup\$ Feb 16, 2017 at 19:40
  • \$\begingroup\$ @ConorO'Brien crap silly mistake sides of ternary are off \$\endgroup\$
    – Downgoat
    Feb 17, 2017 at 0:51
0
\$\begingroup\$

Perl 6, 40 bytes

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

Try it (if tio.run gets updated)
Try an altered version

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]
}
\$\endgroup\$
0
\$\begingroup\$

PHP, 46 bytes

function g($a,$b,$c){echo strtr($a,[$b=>$c]);}
\$\endgroup\$
0
\$\begingroup\$

PHP, 102 bytes

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;

Test cases (functional)

Test case with loop error

\$\endgroup\$
2
  • \$\begingroup\$ Hi! Usually, when submitting a function, you should add to the bytecount all the things needed for the function to be defined (in your case function replace(...){...}, otherwise your submission is just a snippet, which is disallowed by default \$\endgroup\$
    – Leo
    Feb 17, 2017 at 17:59
  • \$\begingroup\$ @Leo Didn't know that, edited my answer ;) \$\endgroup\$
    – roberto06
    Feb 20, 2017 at 9:03
0
\$\begingroup\$

Java - 157 bytes

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

For empty input it returns an empty string.

Crashes with StackOverflowException error when B is empty or it is fed with data like this A/A/A.

How it works:

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

Ungolfed code code with comments:

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)
}
\$\endgroup\$
0
\$\begingroup\$

AutoHotkey, 87 bytes

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

%1%,%2%, and %3% are the first 3 arguments passed to a function
If a function expects a variable argument, the %s are dropped
Changing the case-sensitivity setting costs 19 bytes but, without it, you get things like downpercase is down.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.