Substitusi string rekursif

25

Tugas

Tulis sebuah program atau fungsi yang diberi tiga string A, B, Cmenghasilkan string output di mana setiap instance Bin Atelah diganti secara rekursif C. Rekursif mengganti cara mengulang substitusi di mana pada setiap langkah semua contoh yang tidak tumpang tindih dari Bdalam A(dipilih rakus dari kiri ke kanan) diganti dengan Csampai Btidak lebih terkandung dalam A.

Input output

  • Anda dapat menggunakan salah satu metode default untuk I / O .
  • Strings hanya akan berisi karakter ASCII yang dapat dicetak (dan mungkin mengandung salah satunya).
  • Btidak akan pernah menjadi string kosong, sementara Adan Cmungkin.
  • String harus dianggap plaintext, misalnya Anda tidak dapat memperlakukan Bsebagai pola Regex.
  • Beberapa kombinasi input tidak akan pernah berakhir. Program Anda dapat melakukan apa saja dalam kasus-kasus itu.

Uji kasus

Ini dalam 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}
)

Contoh yang tidak berakhir:

grow/ow/oow

loop/lo/lo
Leo
sumber
3
Test case lain:((())())())/()/
Conor O'Brien
@ ConorO'Brien menambahkan
Leo
1
Awalnya, saya gagal membuatnya case-sensitive. downpercase is down
Engineer Toast

Jawaban:

7

05AB1E , 2 byte

`:

Cobalah online!

Penjelasan

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

Ini bisa :untuk 1 byte jika kita tidak harus berurusan dengan string kosong.

Emigna
sumber
3
Jika saya memahaminya dengan benar, solusi 4-byte Anda valid. "Beberapa kombinasi input tidak akan pernah berakhir. Program Anda dapat melakukan apa saja dalam hal ini."
Leo
@Leo. Kamu benar. Saya membaca bagian itu :)
Emigna
1
Jadi pada dasarnya :adalah builtin yang menyelesaikan seluruh tantangan? Seharusnya saya melarang builtin;)
Leo
@ Leo: Jika bukan karena string kosong satu built-in akan menyelesaikan ini ya. Dan satu-satunya perbedaan dengan string kosong adalah bahwa kita perlu menentukan bahwa ada 3 input, yang sebaliknya akan disimpulkan secara implisit oleh operasi :)
Emigna
Apakah hal seperti ini juga mungkin?
Adnan
9

Python 2 , 43 byte

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

Cobalah online!

Mengevaluasi string formulir

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

Untuk mencapai titik tetap jika ada, cukup untuk melakukan penggantian yang sama dengan panjang string asli.

Tidak
sumber
7

ES6 (Javascript), 47, 43 byte

  • Disimpan 4 byte menggunakan currying (Terima kasih @Neil!)

Golf

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

Cobalah

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
sumber
Anda dapat menyimpan 4 byte dengan mengolah argumen dalam urutan terbalik:c=>b=>g=a=>a==(a=a.split(b).join(c))?a:g(a)
Neil
Ups. i.imgur.com/vPCycwR.png
Metoniem
@MetoniemSome combinations of inputs will never terminate. Your program can do anything in those cases.
zeppelin
@ zeppelin Oh, begitu.
Metoniem
5

Retina , 27 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

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

Input harus dipisahkan dengan linefeed.

Cobalah online! (Untuk kenyamanan, gunakan format input test-suite di mana setiap baris adalah kasus uji yang dipisahkan dengan slash.)

Martin Ender
sumber
4

C #, 44 Bytes

Versi pendek:

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

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

Penjelasan: Fungsi ini ditulis sebagai ekspresi rekursif ekor, menghindari kata kunci kembali dan kurung keriting dengan mengeksploitasi yang berikut:

  • Tugas dalam kurung mengembalikan nilai yang diberikan
  • Sisi kiri pemeriksaan kesetaraan akan dievaluasi sebelum penugasan sisi kanan, memungkinkan kami untuk membandingkan sebelum / sesudah inline, dan masih mengakses hasilnya

Ini memungkinkan kita menyimpannya dalam satu pernyataan.

EDIT: Kembali ke menghilangkan jenis fungsi r, karena itu tampaknya dapat diterima. Dengan tipe deklarasi menggunakan array, itu adalah 68 karakter. Tanpa, itu adalah 44 karakter.

Daniel
sumber
Jika fungsi hanya akan berfungsi jika diberi nama tertentu, Anda harus menghabiskan byte untuk memberikan fungsi itu nama. Tidak segera jelas bagi saya apakah itu 2 byte untuk r=atau lebih banyak untuk deklarasi (sebagian karena saya tidak sepenuhnya tahu aturannya, sebagian karena saya tidak tahu C # cukup baik untuk menerapkannya).
Ya, saya baru saja memperbaikinya setelah membaca komentar orang lain pada entri yang berbeda. Dan masih banyak lagi, karena semua jenis harus ditentukan. Saya beralih menggunakan array untuk menghemat itu, dan menyimpan byte pada panggilan rekursif.
Daniel
Apa maksud Anda dengan tidak menghasilkan output yang benar ? Saya tidak berpikir Anda perlu menampilkan input, pada kenyataannya, beberapa jawaban lain tidak melakukannya. Apakah saya melewatkan komentar yang mengatakan bahwa saya perlu menampilkan input?
auhmaan
Bagaimanapun, saya telah menemukan masalah, itu tidak rekursif.
auhmaan
2

Japt , 15 byte

@¥(U=UqV qW}a@U

Uji secara online!

Bagaimana itu bekerja

@¥(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 memiliki built-in rekursif-ganti, tetapi melihat input pertama sebagai regex. Jika input dijamin hanya mengandung karakter alfanumerik, solusi tiga byte ini akan berfungsi:

eVW

Jika input diizinkan mengandung arang apapun kecuali ^, \, atau ], solusi 12-byte ini akan berlaku sebaliknya:

eV®"[{Z}]"ÃW
Produksi ETH
sumber
2

C #, 33 49 byte

Mungkin, salah satu cuplikan terkecil yang ditulis dalam C # ... Dan karena Replacemerupakan bawaan dari stringstruct, tidak perlu untuk usings ( Setidaknya tidak pada fitur bawaan VS, C # Interactive ... )

Juga, karena Bselalu memiliki nilai, kode tidak memerlukan validasi apa pun.


Golf

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

Tidak disatukan

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

    return a;
}

Kode lengkap

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

Rilis

  • v1.1 - +19 bytes- Solusi tetap tidak bersifat rekursif.
  • v1.0 -  33 bytes- Solusi awal.
auhmaan
sumber
1
Saya melihat c # I upvote
Nelz
@NelsonCasanova Kedengarannya seperti saya.
Metoniem
Apakah Replacemelakukan penggantian rekursif?
Laikoni
@Laikoni no. Misalnya, "((())())())".Replace("()", "")kembali (())).
auhmaan
Maka solusi ini tidak sah menurut aturan tantangan. Anda harus menghapusnya untuk mencegah downvotes, kemudian memperbaiki solusi Anda untuk menangani penggantian rekursif dan akhirnya membatalkan penghapusan itu.
Laikoni
1

Memproses, 75 72 byte

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

Mencetak hasilnya. Sebut saja sepertig("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
sumber
1

Mathematica, 35 32 Bytes

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

Argumen diberikan sebagai suatu urutan. Tidak pernah berakhir untuk growcontoh, kembali loopuntuk loopmisalnya. Tiga byte off berkat saran Martin.

A Simmons
sumber
FixedPointcenderung terlalu panjang dan dapat ditiru dengan //.:#//.x_:>StringReplace[x,#2->#3]&
Martin Ender
Terima kasih @MartinEnder. Itu cara yang baik untuk mulai ReplaceRepeatedbekerja untuk senar!
A Simmons
btw, ini hanya akan mengulang $RecursionLimitkali, yang secara 2^16default, tidak mempengaruhi jawaban Anda
ngenisis
@ngenesis Saya tidak yakin itu ReplaceRepeateddikendalikan oleh $RecursionLimit- Saya baru saja mengujinya dengan menetapkan batas ke 20 dan program masih dengan senang hati menerima input yang tidak berakhir ..
A Simmons
Karena ReplaceRepeatedada opsi terpisah (yang tidak dapat digunakan dengan //.sintaks), dipanggil MaxIterations. Yang default ke 2 ^ 16. (cc @ngenisis)
Martin Ender
1

Ruby, 29 byte

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

Diberikan 3 argumen, terapkan substitusi ke yang pertama sampai tidak ada yang bisa diganti lagi.

Penjelasan

  • 1sebelum whilehanyalah sebuah nop
  • gsub!mengembalikan string atau niljika tidak ada substitusi yang terjadi
GB
sumber
1

/// , 3 byte

///

Masukkan string B setelah slash pertama, C setelah yang kedua dan A di akhir, yaitu:

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

Cobalah online!

steenbergh
sumber
Saya tidak berpikir ini adalah cara yang dapat diterima untuk mengambil input
Leo
Sepengetahuan saya, ///tidak menerima input dengan cara lain.
steenbergh
2
Yah, saya pikir akan menarik untuk membahas apakah ini dapat diterima atau tidak, maka :) Pokoknya, saya telah melihat masalah lain dengan kiriman Anda: tidak berfungsi jika /ada di salah satu string input
Leo
1

JavaScript (Firefox 48 atau yang lebih lama), 43 byte

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

Membawa argumen yang digulung terbalik. Firefox dulu memiliki parameter ketiga non-standar replaceyang ditandai bendera regexp tertentu. Parameter ini dihapus di Firefox 49.

Neil
sumber
0

SmileBASIC, 72 68 byte

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

Salah satu kasus langka di mana membuat fungsi sebenarnya adalah SHORTER di SmileBASIC.

12Me21
sumber
0

Javascript 130 byte

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

Javascript hanya akan menggantikan semua secara bersamaan jika Anda memberinya regex. Agar regex ini berfungsi untuk semua nilai, semua karakter yang digunakan untuk regex perlu diganti dengan versi yang diloloskan. Akhirnya, penggantian dievaluasi untuk mengganti semua instance B dalam A dengan C dan meneruskannya kembali ke fungsi lagi.

fəˈnɛtɪk
sumber
0

q, 15 byte

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

Contoh:

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

link ke unduhan juru bahasa

Penjelasan: ssr , / (konvergen)

skeevey
sumber
0

Cheddar, 37 byte

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

Di ponsel, jadi tautan TIO agak sulit ditambahkan. Pada dasarnya menggunakan rekursi saat memeriksa apakah b ada dalam a. Solusi bisa saja (a,b,c)->a.sub(Regex{b,"cr"},c)tetapi tidak berhasil karena suatu alasan.

Downgoat
sumber
Apakah sub menggantikan semua atau hanya yang pertama?
fəˈnɛtɪk
@LliwTelracs karena mereka adalah string. Sub akan menggantikan semua
Downgoat
Ini sepertinya tidak berhasil? Cobalah online!
Conor O'Brien
@ ConorO'Brien omong kosong sisi kesalahan konyol ternary tidak aktif
Downgoat
0

Perl 6 , 40 byte

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

Cobalah (jika tio.run diperbarui)
Cobalah versi yang diubah

Diperluas:

{
  $^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
sumber
0

PHP, 46 byte

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

PHP, 102 byte

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 case (fungsional)

Test case dengan loop loop

roberto06
sumber
Hai! Biasanya, ketika mengirimkan fungsi, Anda harus menambahkan bytecount semua hal yang diperlukan agar fungsi tersebut didefinisikan (dalam kasus Anda function replace(...){...}, jika tidak, pengiriman Anda hanya cuplikan, yang tidak diizinkan secara default
Leo
@ Leo Tidak tahu itu, mengedit jawaban saya;)
roberto06
0

Java - 157 byte

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

Untuk input kosong mengembalikan string kosong.

Gangguan dengan StackOverflowExceptionkesalahan saat Bkosong atau diumpankan dengan data seperti iniA/A/A .

Bagaimana itu bekerja:

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

Kode kode tanpa komentar dengan komentar:

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)
}
Kue kering
sumber
0

AutoHotkey, 87 byte

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

%1%,, %2%dan %3%merupakan 3 argumen pertama yang diteruskan ke suatu fungsi.
Jika suatu fungsi mengharapkan argumen variabel, maka %s akan dihapus.
Mengubah pengaturan sensitivitas kasus biayanya 19 byte tetapi, tanpa itu, Anda akan mendapatkan hal-hal seperti downpercase is down.

Toast insinyur
sumber