Zastępowanie ciągu rekurencyjnego

25

Zadanie

Napisz program lub funkcję, która podając trzy łańcuchy A, B, Ctworzy łańcuch wyjściowy, w którym rekurencyjnie podstawiono każde wystąpienie Bin . Rekurencyjne podstawianie oznacza powtarzanie podstawienia, w którym na każdym etapie wszystkie nie nakładające się wystąpienia in (wybrane zachłannie od lewej do prawej) są zastępowane przez, aż do momentu, gdy nie jest już zawarte w .ACBACBA

Wejście wyjście

  • Możesz użyć dowolnej domyślnej metody we / wy .
  • Ciągi będą zawierać tylko drukowalne znaki ASCII (i mogą zawierać dowolny z nich).
  • Bnigdy nie będzie pustym ciągiem Ai Cmoże być.
  • Ciągi znaków należy traktować jako zwykły tekst, nie można na przykład traktować go Bjako wzorca Regex.
  • Niektóre kombinacje wejść nigdy się nie zakończą. W takich przypadkach Twój program może zrobić wszystko.

Przypadki testowe

Są w formacie: 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}
)

Przykłady, które się nie kończą:

grow/ow/oow

loop/lo/lo
Lew
źródło
3
Kolejny przypadek testowy:((())())())/()/
Conor O'Brien
@ ConorO'Brien dodaje
Leo
1
Na początku nie rozróżniałem wielkości liter. downpercase is down
Inżynier Toast

Odpowiedzi:

7

05AB1E , 2 bajty

`:

Wypróbuj online!

Wyjaśnienie

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

To może być :dla 1 bajt , jeśli nie mamy do czynienia z pustymi strunami.

Emigna
źródło
3
Jeśli dobrze to rozumiem, twoje 4-bajtowe rozwiązanie jest prawidłowe. „Niektóre kombinacje danych wejściowych nigdy się nie zakończą. W takich przypadkach Twój program może zrobić wszystko”.
Leo
@Lew. Masz rację.
Przejrzałem
1
Więc w zasadzie :jest wbudowane, które rozwiązuje całe wyzwanie? Powinienem był zakazać wbudowanych;)
Leo
@Leo: Gdyby nie puste ciągi, jeden wbudowany rozwiązałby to tak. A jedyną różnicą w przypadku pustych ciągów jest to, że musimy określić, że istnieją 3 dane wejściowe, które w innym przypadku byłyby domyślnie wywnioskowane przez operację :)
Emigna
Czy coś takiego jest również możliwe?
Adnan
9

Python 2 , 43 bajty

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

Wypróbuj online!

Ocenia ciąg formularza

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

Aby osiągnąć ustalony punkt, jeśli taki istnieje, wystarczy wykonać zamianę równą długości oryginalnego łańcucha.

xnor
źródło
7

ES6 (JavaScript), 47, 43 bajty

  • Zaoszczędzono 4 bajty przy użyciu curry (Dzięki @Neil!)

Grał w golfa

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

Spróbuj

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

zepelin
źródło
Możesz zapisać 4 bajty, curryując argumenty w odwrotnej kolejności:c=>b=>g=a=>a==(a=a.split(b).join(c))?a:g(a)
Neil
@MetoniemSome combinations of inputs will never terminate. Your program can do anything in those cases.
zeppelin
@zeppelin Oh, rozumiem.
Metoniem
5

Siatkówka , 27 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

Dane wejściowe powinny być oddzielone od linii.

Wypróbuj online! (Dla wygody używa formatu wejściowego zestawu testów, w którym każdy wiersz jest przypadkiem oddzielonym ukośnikiem).

Martin Ender
źródło
4

C #, 44 bajtów

Krótka wersja:

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

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

Objaśnienie: Funkcja jest zapisywana jako wyrażenie rekurencyjne typu tail, unikając słowa kluczowego return i nawiasów klamrowych, wykorzystując następujące elementy:

  • Przypisanie w nawiasach zwraca przypisaną wartość
  • Lewa strona kontroli równości zostanie oceniona przed przypisaniem po prawej stronie, co pozwoli nam porównać przed / po wstawieniu i nadal uzyskać dostęp do wyniku

To pozwala nam zachować to w jednym stwierdzeniu.

EDYCJA: Wróciłem do pomijania typu funkcji r, ponieważ wydaje się to do przyjęcia. W przypadku deklaracji typu za pomocą tablic ma ona 68 znaków. Bez 44 znaków.

Daniel
źródło
Jeśli funkcja będzie działać tylko wtedy, gdy otrzyma określoną nazwę, musisz wydać bajty, aby nadać tej nazwie nazwę. Nie jest dla mnie od razu oczywiste, czy to 2 bajty na r=deklarację, czy też wiele więcej (częściowo dlatego, że nie znam w pełni reguł, częściowo dlatego, że nie znam C # wystarczająco dobrze, aby je zastosować).
Tak, naprawiłem to po przeczytaniu komentarza innej osoby na inny wpis. I to o wiele więcej, ponieważ wszystkie typy muszą zostać określone. Przełączyłem się na użycie tablicy, aby zaoszczędzić na tym i zapisać bajty na wywołaniu rekurencyjnym.
Daniel
Co masz na myśli mówiąc, że nie daje prawidłowego wyniku ? Nie sądzę, że musisz podać dane wejściowe, w rzeczywistości niektóre inne odpowiedzi tego nie robią. Czy przegapiłem komentarz mówiący, że muszę wysyłać dane wejściowe?
auhmaan
Nieważne, znalazłem problem, to nie jest rekurencyjne.
auhmaan
2

Japt , 15 bajtów

@¥(U=UqV qW}a@U

Przetestuj online!

Jak to działa

@¥(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 ma wbudowaną funkcję zastępowania rekurencyjnego, ale widzi pierwsze wejście jako wyrażenie regularne. Gdyby zagwarantowano, że dane wejściowe zawierają tylko znaki alfanumeryczne, to rozwiązanie 3-bajtowe działałoby:

eVW

Jeżeli wejście mogły zawierać węgiel odbarwiający wyjątkiem ^, \czy ]to rozwiązanie 12 bajtów będzie ważne, a nie:

eV®"[{Z}]"ÃW
ETHprodukcje
źródło
2

C #, 33 49 bajtów

Prawdopodobnie jeden z najmniejszych fragmentów napisanych w C # ... A ponieważ Replacejest natywny dla stringstruktury, nie ma potrzeby używania usings ( Przynajmniej nie na wbudowanej funkcji VS, C # Interactive ... )

Ponadto, ponieważ Bzawsze ma wartość, kod nie wymaga żadnych weryfikacji.


Grał w golfa

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

Nie golfił

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

    return a;
}

Pełny kod

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

Prasowe

  • v1.1 - +19 bytes- Naprawiono brak rekurencji rozwiązania.
  • v1.0 -  33 bytes- Wstępne rozwiązanie.
auhmaan
źródło
1
Widzę c # I głosowałem
Nelz
@NelsonCasanova Brzmi jak ja.
Metoniem
Czy Replacedokonuje wymiany rekurencyjnej?
Laikoni,
@Laikoni no. Na przykład "((())())())".Replace("()", "")zwraca (())).
auhmaan
To rozwiązanie nie jest ważne zgodnie z regułami wyzwania. Powinieneś go usunąć, aby zapobiec negatywnym ocenom, a następnie naprawić swoje rozwiązanie, aby obsługiwać rekurencyjne zastępowanie i ostatecznie cofnąć usunięcie.
Laikoni
1

Przetwarzanie, 75 72 bajtów

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

Drukuje wyniki. Nazwij to jakg("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
źródło
1

Mathematica, 35 32 bajtów

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

Argumenty podane jako sekwencja. Nigdy nie kończy się na growprzykład, powraca loopna loopprzykład. Trzy bajty wolne dzięki sugestii Martina.

Simmons
źródło
FixedPointbywa zbyt długi i można go emulować za pomocą //.:#//.x_:>StringReplace[x,#2->#3]&
Martina Endera
Dzięki @MartinEnder. To dobry sposób na rozpoczęcie ReplaceRepeatedpracy z łańcuchami!
A Simmons,
tak przy okazji, będzie to tylko pętla $RecursionLimitrazy, co jest 2^16domyślnie, a nie to, że wpływa na twoją odpowiedź
ngenisis
@ngenesis Nie jestem pewien, czy ReplaceRepeatedjest to kontrolowane przez $RecursionLimit- Właśnie przetestowałem to, ustawiając limit na 20, a program nadal szczęśliwie zapętla się dla nie kończących się danych wejściowych.
Simmons,
Dla ReplaceRepeatedtam oddzielna opcja (co nie może być używany z //.składni), zwany MaxIterations. Że jeden domyślnie 2 ^ 16. (cc @ngenisis)
Martin Ender
1

Rubinowy, 29 bajtów

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

Biorąc pod uwagę 3 argumenty, zastosuj podstawienie do pierwszego, dopóki nie będzie już nic do zastąpienia.

Wyjaśnienie

  • 1przed whilejest po prostu nop
  • gsub!zwraca ciąg znaków lub niljeśli nie wystąpiło podstawienie
GB
źródło
1

/// , 3 bajty

///

Umieść ciąg B po pierwszym ukośniku, C po drugim i A na końcu, tj .:

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

Wypróbuj online!

Steenbergh
źródło
Nie sądzę, że jest to akceptowalny sposób przyjmowania danych
Leo
Według mojej wiedzy, ///nie akceptuje danych wejściowych w żaden inny sposób.
steenbergh
2
Cóż, myślę, że byłoby interesujące przedyskutować, czy jest to do przyjęcia, czy nie :) W każdym razie zauważyłem inny problem z twoim przesłaniem: nie działa, jeśli a /jest obecne w dowolnym z ciągów wejściowych
Leo
1

JavaScript (Firefox 48 lub wcześniejszy), 43 bajty

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

Podejmuje argumenty curry w odwrotnej kolejności. Firefox miał niestandardowy trzeci parametr, dla replacektórego określono flagi wyrażeń regularnych. Ten parametr został usunięty w przeglądarce Firefox 49.

Neil
źródło
0

SmileBASIC, 72 68 bajtów

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

Jednym z rzadkich przypadków, w których wykonywanie funkcji jest w rzeczywistości SHORTER w SmileBASIC.

12Me21
źródło
0

JavaScript 130 bajtów

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

JavaScript zastąpi wszystkie jednocześnie, jeśli dasz mu wyrażenie regularne. Aby to wyrażenie regularne działało dla wszystkich wartości, wszystkie znaki używane w wyrażeniach regularnych muszą zostać zastąpione wersją zmiany znaczenia. Na koniec zamiana jest oceniana w celu zastąpienia wszystkich instancji B w A literą C i przekazania jej z powrotem do funkcji.

Fəˈnɛtɪk
źródło
0

q, 15 bajtów

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

Przykład:

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

link do pobrania tłumacza

Objaśnienie: ssr , / (zbieżność)

skeevey
źródło
0

Cheddar, 37 bajtów

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

Na telefonie, więc dodanie linku TIO jest nieco trudne. Zasadniczo używa rekurencji, podczas gdy sprawdzanie b jest w a. Rozwiązanie mogło być, (a,b,c)->a.sub(Regex{b,"cr"},c)ale z jakiegoś powodu nie działa.

Downgoat
źródło
Czy sub zastępuje wszystkie, czy tylko pierwsze?
fəˈnɛtɪk
@LliwTelracs, ponieważ są łańcuchami .sub zastąpi wszystko
Downgoat
To nie działa? Wypróbuj online!
Conor O'Brien
@ ConorO'Brien bzdury głupie pomyłki strony
trójki
0

Perl 6 , 40 bajtów

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

Wypróbuj (jeśli tio.run zostanie zaktualizowany)
Wypróbuj zmienioną wersję

Rozszerzony:

{
  $^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
źródło
0

PHP, 46 bajtów

function g($a,$b,$c){echo strtr($a,[$b=>$c]);}
MonkeyZeus
źródło
0

PHP, 102 bajty

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;

Przypadki testowe (funkcjonalne)

Przypadek testowy z błędem pętli

roberto06
źródło
Cześć! Zwykle, przesyłając funkcję, należy dodać do bajtu wszystkie rzeczy potrzebne do zdefiniowania funkcji (w twoim przypadku function replace(...){...}, w przeciwnym razie twoje zgłoszenie jest tylko fragmentem kodu, który domyślnie
Leo
@Leo Nie wiedziałem o tym, zredagowałem moją odpowiedź;)
roberto06
0

Java - 157 bajtów

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

W przypadku pustego wejścia zwraca pusty ciąg.

Awaria z StackOverflowExceptionbłędem, gdy Bjest pusty lub jest zasilany takimi danymi A/A/A.

Jak to dział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

Niekluczony kod z komentarzami:

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)
}
ciastko
źródło
0

AutoHotkey, 87 bajtów

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

%1%, %2%i %3%są pierwszymi 3 argumentami przekazanymi do funkcji
Jeśli funkcja oczekuje argumentu zmiennego, %s są pomijane
Zmiana ustawienia rozróżniania wielkości liter kosztuje 19 bajtów, ale bez tego można uzyskać rzeczy takie jakdownpercase is down .

Inżynier Toast
źródło