Recursive string substitution

Question

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

Another test case: ((())())())/()/ – Conor O'Brien yesterday — Conor O'Brien, yesterday

xnor · Answer 1 · 2017-02-16 15:16:30Z

up vote 9 down vote

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.

edited yesterday

answered yesterday

xnor

56.4k11117295

add a comment |

zeppelin · Answer 2 · 2017-02-16 20:15:51Z

up vote 7 down vote

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

edited yesterday

answered yesterday

zeppelin

4,5961528

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) – Neil yesterday

add a comment |

Emigna · Answer 3 · 2017-02-16 19:07:21Z

up vote 6 down vote

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.

edited yesterday

answered yesterday

Emigna

18.9k31567

3

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." – Leo yesterday

@Leo. Right you are. I skimmed over that part :) – Emigna yesterday

1

So basically : is a builtin that solves the whole challenge? I should have banned builtins ;) – Leo yesterday

@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 :) – Emigna yesterday

Is something like this also possible? – Adnan yesterday

| show 1 more comment

Martin Ender · Answer 4 · 2017-02-16 14:58:14Z

up vote 4 down vote

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

answered yesterday

Martin Ender♦

128k44289670

add a comment |

Kritixi Lithos · Answer 5 · 2017-02-16 15:24:33Z

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

A Simmons · Answer 6 · 2017-02-16 15:37:40Z

up vote 1 down vote

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.

edited yesterday

answered yesterday

A Simmons

2,8951519

FixedPoint tends to be too long and can be emulated with //.: #//.x_:>StringReplace[x,#2->#3]& – Martin Ender♦ yesterday

Thanks @MartinEnder. That's a good way of getting ReplaceRepeated to work for strings! – A Simmons yesterday

btw, this will only loop $RecursionLimit times, which is 2^16 by default, not that it affects your answer – ngenisis 20 hours ago

@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.. – A Simmons 15 hours ago

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) – Martin Ender♦ 10 hours ago

| show 1 more comment

G B · Answer 7 · 2017-02-16 15:59:29Z

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

muddyfish · Answer 8 · 2017-02-16 17:56:42Z

up vote 1 down vote

Pyke, 6 bytes

hVQtX:

Try it here!

answered yesterday

muddyfish

16.7k62980

add a comment |

DJMcMayhem · Answer 9 · 2017-02-16 18:04:33Z

V, 10, 7 bytes

òóa/b

Try it online!

Here is the readable version, which can also be ran online:

òó<C-r>a/<C-r>b

The explanation is pretty straightforward, since òó is literally recursively substitute.

ò               " Recursively:
 ó              "   Substitute:
  <C-r>a        "     Arg 1
        /<C-r>b "     With Arg 2

ETHproductions · Answer 10 · 2017-02-16 18:12:10Z

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

steenbergh · Answer 11 · 2017-02-16 18:39:51Z

up vote 1 down vote

///, 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!

answered yesterday

steenbergh

3,27011234

I don't think this is an acceptable way of taking inputs – Leo yesterday

To my knowledge, /// doesn't accept input in any other way. – steenbergh yesterday

2

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 – Leo yesterday

add a comment |

auhmaan · Answer 12 · 2017-02-17 14:45:19Z

C#, 33 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)=>{return a.Replace(b,c);}

Ungolfed

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

Full code

using System;

namespace Namespace {
    class Program {
        static void Main( string[] args ) {
            Func<string, string, string, string> func = (a, b, c) => {
                return a.Replace( b, c ); // Simply use the built-in method to replace
                                          // the value. It's recursive.
            };

            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.0 - 33 bytes - Initial solution.

Daniel · Answer 13 · 2017-02-17 23:43:25Z

C#, 68 Bytes

Short Version:

string r(string[]v)=>v[0]==(v[0]=v[0].Replace(v[1],v[2]))?v[0]:r(v);

Full program:

using System;

namespace ConsoleApplication1
{
    class Program
    {
        string r(string[]v)=>v[0]==(v[0]=v[0].Replace(v[1],v[2]))?v[0]:r(v);

        static void Main(string[] args)
        {
            Action<string, string, string, string> test =
                (a, b, c, answer) =>
                {
                    var result = new Program().r(new string[] { 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();
        }
    }
}

NOTE: There is another, shorter C# entry, but the other, 33-byte C# entry does not produce the correct outputs. This one does.

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

New function syntax in VS 2015
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.

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). — ais523, 3 hours ago
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. — Daniel, 3 hours ago

12Me21 · Answer 14 · 2017-02-16 14:51:53Z

up vote 0 down vote

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.

answered yesterday

12Me21

2,690321

add a comment |

LliwTelracs · Answer 15 · 2017-02-16 15:12:37Z

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.

skeevey · Answer 16 · 2017-02-16 18:59:40Z

up vote 0 down vote

q, 15 bytes

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

Example:

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

link to interpreter download

Explanation: ssr, / (converge)

edited yesterday

answered yesterday

skeevey

3,6231021

add a comment |

Neil · Answer 17 · 2017-02-16 20:04:40Z

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.

Downgoat · Answer 18 · 2017-02-17 00:51:51Z

up vote 0 down vote

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.

edited yesterday

answered yesterday

Downgoat

18.7k551133

Does sub replace all or just the first? – LliwTelracs yesterday

@LliwTelracs because they are strings .sub will replace all – Downgoat yesterday

This doesn't seem to work? Try it online! – Conor O'Brien yesterday

@ConorO'Brien crap silly mistake sides of ternary are off – Downgoat yesterday

add a comment |

Brad Gilbert b2gills · Answer 19 · 2017-02-17 04:01:39Z

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

roberto06 · Answer 20 · 2017-02-17 15:10:34Z

up vote 0 down vote

PHP, 78 bytes

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

To be used in a function, as such :

function replace($s, $as, $b) {
    $f=str_replace($a,$b,$s);while($s!=$f){$s=$f;$f=str_replace($a,$b,$s);}echo$f;
}
echo replace('Hello, world!', 'world!', 'PPCG');

Test cases (functional)

Test case with loop error

answered 10 hours ago

roberto06

1813

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 – Leo 7 hours ago

add a comment |

MonkeyZeus · Answer 21 · 2017-02-17 21:52:36Z

up vote 0 down vote

PHP, 46 bytes

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

answered 3 hours ago

MonkeyZeus

43128

add a comment |

asked	yesterday
viewed	1237 times
active	today

current community

your communities

more stack exchange communities

Recursive string substitution

The task

Input/Output

Test cases

21 Answers 21

Python 2, 43 bytes

ES6 (Javascript), 47, 43 bytes

05AB1E, 2 bytes

Retina, 27 bytes

Processing, 75 72 bytes

Mathematica, 35 32 Bytes

Ruby, 29 bytes

Explanation

Pyke, 6 bytes

V, 10, 7 bytes

Japt, 15 bytes

How it works

///, 3 bytes

C#, 33 bytes

SmileBASIC, 72 68 bytes

Javascript 130 bytes

q, 15 bytes

JavaScript (Firefox 48 or earlier), 43 bytes

Cheddar, 37 bytes

Perl 6, 40 bytes

Expanded:

PHP, 78 bytes

PHP, 46 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf string substitution or ask your own question.

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Recursive string substitution

The task

Input/Output

Test cases

21 Answers 21

Python 2, 43 bytes

ES6 (Javascript), 47, 43 bytes

05AB1E, 2 bytes

Retina, 27 bytes

Processing, 75 72 bytes

Mathematica, 35 32 Bytes

Ruby, 29 bytes

Explanation

Pyke, 6 bytes

V, 10, 7 bytes

Japt, 15 bytes

How it works

///, 3 bytes

C#, 33 bytes

SmileBASIC, 72 68 bytes

Javascript 130 bytes

q, 15 bytes

JavaScript (Firefox 48 or earlier), 43 bytes

Cheddar, 37 bytes

Perl 6, 40 bytes

Expanded:

PHP, 78 bytes

PHP, 46 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf string substitution or ask your own question.

Visit Chat

Related

Hot Network Questions