Rekursive Zeichenfolgensubstitution

25

Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die mit drei Zeichenfolgen A, B, Ceine Ausgabezeichenfolge erzeugt, durch die jede Instanz von Bin Arekursiv ersetzt wurde C. Rekursives Ersetzen bedeutet das Wiederholen eines Ersetzens, wobei bei jedem Schritt alle nicht überlappenden Instanzen von Bin A(gierig von links nach rechts gewählt) durch ersetzt werden, Cbis Bnicht mehr in enthalten ist A.

Input-Output

  • Sie können eine der Standardmethoden für E / A verwenden .
  • Zeichenfolgen enthalten nur druckbare ASCII-Zeichen (und können beliebige davon enthalten).
  • Bwird niemals eine leere Zeichenfolge sein, während Aund Cmöglicherweise.
  • Zeichenfolgen sind als Klartext zu betrachten, Sie können sie beispielsweise nicht Bals Regex-Muster behandeln.
  • Einige Kombinationen von Eingaben werden niemals beendet. Ihr Programm kann in diesen Fällen alles tun.

Testfälle

Diese sind im 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}
)

Beispiele, die nicht enden:

grow/ow/oow

loop/lo/lo
Löwe
quelle
3
Ein weiterer Testfall:((())())())/()/
Conor O'Brien
@ ConorO'Brien hinzugefügt
Leo
1
Zuerst habe ich es nicht geschafft, Groß- und Kleinschreibung zu berücksichtigen. downpercase is down
Ingenieur Toast

Antworten:

7

05AB1E , 2 Bytes

`:

Probieren Sie es online!

Erläuterung

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

Dies könnte :für 1 Byte sein, wenn wir uns nicht mit leeren Zeichenfolgen befassen müssten .

Emigna
quelle
3
Wenn ich es richtig verstehe, ist Ihre 4-Byte-Lösung gültig. "Einige Kombinationen von Eingaben werden niemals beendet. In diesen Fällen kann Ihr Programm alles tun."
Leo
@Löwe. Du hast Recht. Ich
überflog
1
:Ist also im Grunde eine integrierte Lösung, die die gesamte Herausforderung löst? Ich hätte builtins verbieten sollen;)
Leo
@Leo: Wenn es nicht die leeren Zeichenketten gäbe, würde ein einziges eingebautes dies ja lösen. Und der einzige Unterschied zu leeren Zeichenfolgen besteht darin, dass wir angeben müssen, dass es 3 Eingaben gibt, die andernfalls implizit von der Operation abgeleitet würden :)
Emigna
Ist so etwas wie dies auch möglich?
Adnan
9

Python 2 , 43 Bytes

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

Probieren Sie es online!

Wertet eine Zeichenfolge des Formulars aus

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

Um einen festen Punkt zu erreichen, genügt es, Ersetzungen vorzunehmen, die der Länge der ursprünglichen Zeichenfolge entsprechen.

xnor
quelle
7

ES6 (Javascript), 4743 Bytes

  • 4 Bytes mit currying gespeichert (Danke @Neil!)

Golf gespielt

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

Versuch es

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

Zeppelin
quelle
Sie können 4 Bytes sparen, indem Sie die Argumente in umgekehrter Reihenfolge c=>b=>g=a=>a==(a=a.split(b).join(c))?a:g(a)
Neil
Hoppla. i.imgur.com/vPCycwR.png
Metoniem
@MetoniemSome combinations of inputs will never terminate. Your program can do anything in those cases.
Zeppelin
@zeppelin Oh, ich verstehe.
Metoniem
5

Retina , 27 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.

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

Der Eingang sollte durch Zeilenvorschub getrennt sein.

Probieren Sie es online! (Verwendet der Einfachheit halber ein Testsuite-Eingabeformat, bei dem jede Zeile durch Schrägstriche getrennte Testfälle darstellt.)

Martin Ender
quelle
4

C #, 44 Bytes

Kurzfassung:

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

Beispielprogramm:

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

Erläuterung: Die Funktion ist als rekursiver Ausdruck mit Endung geschrieben, wobei das Schlüsselwort return und geschweifte Klammern vermieden werden, indem Folgendes ausgenutzt wird:

  • Eine Zuordnung in Klammern gibt den zugewiesenen Wert zurück
  • Die linke Seite der Gleichheitsprüfung wird vor der Zuweisung auf der rechten Seite ausgewertet, sodass wir vor / nach dem Inline-Vergleich noch auf das Ergebnis zugreifen können

So können wir es auf eine einzige Aussage beschränken.

BEARBEITEN: Ging zurück, um die Art der Funktion r wegzulassen, da dies akzeptabel erscheint. Bei der Typdeklaration mit Arrays sind es 68 Zeichen. Ohne ist es 44 Zeichen.

Daniel
quelle
Wenn die Funktion nur unter einem bestimmten Namen ausgeführt werden kann, müssen Sie die Bytes ausgeben, um der Funktion diesen Namen zu geben. Mir ist nicht sofort klar, ob das 2 Bytes r=oder mehr für eine Deklaration sind (teils, weil ich die Regeln nicht genau kenne, teils, weil ich C # nicht gut genug kenne, um sie anzuwenden).
Ja, ich habe das gerade behoben, nachdem ich den Kommentar einer anderen Person zu einem anderen Eintrag gelesen hatte. Und es ist noch viel mehr, da alle Typen angegeben werden müssen. Ich wechselte zu einem Array, um das zu speichern, und speichere Bytes beim rekursiven Aufruf.
Daniel
Was meinst du mit nicht die richtige Ausgabe produzieren ? Ich glaube nicht, dass Sie die Eingabe ausgeben müssen, in der Tat tun es einige der anderen Antworten nicht. Habe ich einen Kommentar verpasst, der besagt, dass ich die Eingabe ausgeben muss?
auhmaan
Vergiss nicht, ich habe das Problem gefunden, es ist nicht rekursiv.
auhmaan
2

Japt , 15 Bytes

@¥(U=UqV qW}a@U

Online testen!

Wie es funktioniert

@¥(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 verfügt über eine integrierte Funktion zum rekursiven Ersetzen, sieht die erste Eingabe jedoch als regulären Ausdruck. Wenn die Eingaben garantiert nur alphanumerische Zeichen enthalten würden, würde diese Drei-Byte-Lösung funktionieren:

eVW

Wenn die Eingabe Zeichen außer ^, \oder enthalten darf, ist ]stattdessen diese 12-Byte-Lösung gültig:

eV®"[{Z}]"ÃW
ETHproductions
quelle
2

C #, 33 49 Bytes

Wahrscheinlich eines der kleinsten in C # geschriebenen Snippets ... Und da Replacees in der stringStruktur enthalten ist, ist kein usings erforderlich ( Zumindest nicht in der integrierten VS-Funktion C # Interactive ... )

Da Bder Code immer einen Wert hat, muss er auch nicht validiert werden.


Golf gespielt

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

Vollständiger 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- Problem, bei dem die Lösung nicht rekursiv war - gefixt
  • v1.0 -  33 bytes- Anfangslösung.
auhmaan
quelle
1
Ich sehe c # Ich upvote
Nelz
@ NelsonCasanova Klingt wie ich.
Metoniem
Führt Replaceeine rekursive Ersetzung durch?
Laikoni
@ Laikoni Nr. Zum Beispiel "((())())())".Replace("()", "")kehrt zurück (())).
auhmaan
Dann ist diese Lösung nach den Regeln der Challenge nicht gültig. Sie sollten es löschen, um Abstimmungen zu vermeiden, dann Ihre Lösung für rekursives Ersetzen reparieren und schließlich wiederherstellen.
Laikoni
1

Verarbeitung, 75 bis 72 Bytes

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

Druckt die Ergebnisse. Nenne es sog("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
quelle
1

Mathematica, 35 32 Bytes

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

Argumente als Folge angegeben. Kündigt zum growBeispiel nie ab , kehrt loopzum loopBeispiel zurück. Drei Bytes weniger dank Martins Vorschlag.

Ein Simmons
quelle
FixedPointneigt dazu, zu lang zu sein und kann emuliert werden mit //.:#//.x_:>StringReplace[x,#2->#3]&
Martin Ender
Danke @MartinEnder. Das ist ein guter Weg, ReplaceRepeatedum für Streicher zu arbeiten!
Ein Simmons
Übrigens wird dies nur die Schleifenzeiten $RecursionLimitsein, was 2^16standardmäßig nicht Ihre Antwort beeinflusst
ngenisis
@ngenesis Ich bin mir nicht sicher, ob das von ReplaceRepeatedgesteuert wird $RecursionLimit- ich habe es gerade getestet, indem ich das Limit auf 20 gesetzt habe, und das Programm schleift immer noch gerne für nicht abschließende Eingaben mit.
A Simmons
Für ReplaceRepeatedgibt es eine separate Option (die nicht mit der //.Syntax verwendet werden kann), genannt MaxIterations. Der Standardwert ist 2 ^ 16. (cc @ngenisis)
Martin Ender
1

Ruby, 29 Bytes

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

Wenden Sie bei 3 Argumenten die Substitution auf die erste an, bis nichts mehr zu ersetzen ist.

Erläuterung

  • 1 Vor dem while ist einfach ein noppe
  • gsub!Gibt den String zurück oder nilwenn keine Ersetzung stattgefunden hat
GB
quelle
1

/// , 3 Bytes

///

Setzen Sie den String B nach dem ersten Schrägstrich, C nach dem zweiten und A am Ende, dh:

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

Probieren Sie es online!

steenbergh
quelle
Ich denke nicht, dass dies eine akzeptable Möglichkeit ist, Eingaben zu machen
Leo
///Akzeptiert meines Wissens keine anderen Eingaben.
Steenbergh
2
Nun, ich denke, es wäre interessant zu diskutieren, ob dies akzeptabel ist oder nicht :) Wie auch immer, ich habe ein weiteres Problem mit Ihrer Eingabe festgestellt: Es funktioniert nicht, wenn /in einer der Eingabezeichenfolgen ein vorhanden ist
Leo
1

JavaScript (Firefox 48 oder früher), 43 Byte

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

Nimmt Argumente in umgekehrter Reihenfolge auf. Firefox hatte früher einen nicht standardmäßigen dritten Parameter, für replaceden reguläre Ausdrücke festgelegt wurden. Dieser Parameter wurde in Firefox 49 entfernt.

Neil
quelle
0

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

Einer der seltenen Fälle, in denen eine Funktion erstellt wird, ist SHORTER in SmileBASIC.

12Me21
quelle
0

Javascript 130 Bytes

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

Javascript wird nur dann alle gleichzeitig ersetzen, wenn Sie ihm einen regulären Ausdruck geben. Damit dieser reguläre Ausdruck für alle Werte funktioniert, müssen alle Zeichen, die für den regulären Ausdruck verwendet werden, durch die maskierte Version ersetzt werden. Schließlich wird das Ersetzen ausgewertet, um alle Instanzen von B in A durch C zu ersetzen und das wieder an die Funktion zurückzugeben.

fəˈnəˈtɪk
quelle
0

q, 15 Bytes

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

Beispiel:

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

Verknüpfung zum Dolmetscher-Download

Erklärung: ssr , / (konvergieren)

Skeevey
quelle
0

Cheddar, 37 Bytes

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

Am Telefon ist also TIO-Link etwas schwer hinzuzufügen. Verwendet im Allgemeinen die Rekursion, während das Überprüfen von b in a erfolgt. Die Lösung könnte gewesen sein (a,b,c)->a.sub(Regex{b,"cr"},c), funktioniert aber aus irgendeinem Grund nicht.

Downgoat
quelle
Ersetzt sub alles oder nur das erste?
16.
@LliwTelracs, weil es sich um Zeichenfolgen handelt .sub ersetzt all
Downgoat
Das scheint nicht zu funktionieren? Probieren Sie es online!
Conor O'Brien
@ ConorO'Brien Mist dumme Fehler Seiten von
Ternary
0

Perl 6 , 40 Bytes

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

Probieren Sie es aus (wenn tio.run aktualisiert wird)
Probieren Sie eine geänderte Version aus

Erweitert:

{
  $^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]
}
Brad Gilbert b2gills
quelle
0

PHP, 46 Bytes

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

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;

Testfälle (funktional)

Testfall mit Schleifenfehler

roberto06
quelle
Hallo! Wenn Sie eine Funktion einreichen, sollten Sie in der Regel alle für die Definition der Funktion erforderlichen Elemente zum bytecount hinzufügen (in Ihrem Fall function replace(...){...}ist Ihre Einreichung sonst nur ein Ausschnitt, der standardmäßig nicht zulässig ist
Leo
@Leo Wusste nicht, dass, bearbeitete meine Antwort;)
roberto06
0

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

Bei leerer Eingabe wird eine leere Zeichenfolge zurückgegeben.

Abstürze mit StackOverflowExceptionFehler, wenn Bleer ist oder Daten wie diese eingespeist werdenA/A/A .

Wie es funktioniert:

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 mit Kommentaren:

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)
}
Plätzchen
quelle
0

AutoHotkey, 87 Bytes

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

%1%,, %2%und %3%sind die ersten 3 Argumente, die an eine Funktion übergeben werden.
Wenn eine Funktion ein variables Argument erwartet, werden die %s gelöscht. Das
Ändern der Einstellung für die Groß- und Kleinschreibung kostet 19 Byte, aber ohne diese Angabe erhalten Sie Dinge wie downpercase is down.

Ingenieur Toast
quelle