Substituição recursiva de string

25

A tarefa

Escreva um programa ou função que, com três seqüências de caracteres, A, B, Cproduza uma sequência de saída em que cada instância de Bin Afoi recursivamente substituída por C. Substituir recursivamente significa repetir uma substituição em que em cada etapa todas as instâncias não sobrepostas de Bin A(escolhidas avidamente da esquerda para a direita) são substituídas por Caté que Bnão esteja mais contida A.

Entrada / Saída

  • Você pode usar qualquer um dos métodos padrão para I / O .
  • As seqüências conterão apenas caracteres ASCII imprimíveis (e podem conter qualquer um deles).
  • Bnunca será uma string vazia, enquanto Ae Cpode ser.
  • Seqüências de caracteres devem ser consideradas texto sem formatação, você não pode, por exemplo, tratar Bcomo um padrão Regex.
  • Algumas combinações de entradas nunca terminam. Seu programa pode fazer qualquer coisa nesses casos.

Casos de teste

Estes estão no formato: 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}
)

Exemplos que não terminam:

grow/ow/oow

loop/lo/lo
Leo
fonte
3
Outro caso de teste:((())())())/()/
Conor O'Brien
@ ConorO'Brien adicionou
Leo
1
No começo, não consegui diferenciar maiúsculas de minúsculas. downpercase is down
Engenheiro brinde

Respostas:

7

05AB1E , 2 bytes

`:

Experimente online!

Explicação

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

Pode ser :de 1 byte se não tivermos que lidar com cadeias vazias.

Emigna
fonte
3
Se entendi corretamente, sua solução de 4 bytes é válida. "Algumas combinações de entradas nunca terminam. Seu programa pode fazer qualquer coisa nesses casos."
Leo
@Leo. Você está certo. I desnatado sobre a parte :)
Emigna
1
Então, basicamente, :é um builtin que resolve todo o desafio? Eu deveria ter proibido builtins;)
Leo
@ Leo: Se não fosse pelas cordas vazias, um único construído resolveria isso sim. E a única diferença com cadeias de caracteres vazias é que precisamos especificar que existem 3 entradas, que de outra forma seriam implicitamente inferidas pela operação :) #
1715 Emigna
É algo como este também é possível?
Adnan
9

Python 2 , 43 bytes

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

Experimente online!

Avalia uma sequência do formulário

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

Para atingir um ponto fixo, se houver, basta fazer substituições iguais ao comprimento da string original.

xnor
fonte
7

ES6 (Javascript), 47, 43 bytes

  • Salvo 4 bytes usando currying (Obrigado @ Neil!)

Golfe

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

Tente

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

zepelim
fonte
Você pode salvar 4 bytes por currying os argumentos na ordem inversa: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, entendo.
Metoniem
5

Retina , 27 bytes

A contagem de bytes assume a codificação ISO 8859-1.

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

A entrada deve ser separada pela alimentação de linha.

Experimente online! (Por conveniência, usa um formato de entrada do conjunto de testes em que cada linha é um caso de teste separado por barra).

Martin Ender
fonte
4

C #, 44 bytes

Versão curta:

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

Programa de exemplo:

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

Explicação: A função é escrita como uma expressão recursiva de cauda, ​​evitando a palavra-chave de retorno e os colchetes, explorando o seguinte:

  • Uma atribuição entre parênteses retorna o valor atribuído
  • O lado esquerdo da verificação de igualdade será avaliado antes da atribuição do lado direito, permitindo comparar antes / depois da linha e ainda acessar o resultado

Isso nos permite manter uma única declaração.

EDIT: Voltamos a omitir o tipo de função r, pois isso parece ser aceitável. Na declaração de tipo usando matrizes, são 68 caracteres. Sem, são 44 caracteres.

Daniel
fonte
Se a função funcionar apenas se receber um nome específico, você precisará gastar os bytes para atribuir esse nome à função. Não é imediatamente óbvio para mim se são 2 bytes r=ou mais para uma declaração (em parte porque não conheço completamente as regras, em parte porque não conheço C # suficientemente bem para aplicá-las).
Sim, eu estava consertando isso depois de ler o comentário de outra pessoa em uma entrada diferente. E é muito mais, pois todos os tipos devem ser especificados. Eu mudei para usar uma matriz para economizar nisso e salvar bytes na chamada recursiva.
Daniel
O que você quer dizer com não produz a saída correta ? Eu não acho que você precise fornecer a entrada, de fato, algumas das outras respostas não o fazem. Perdi um comentário dizendo que eu precisava produzir a entrada?
21417 auhmaan
Não importa, eu encontrei o problema, não é recursivo.
auhmaan
2

Japonês , 15 bytes

@¥(U=UqV qW}a@U

Teste online!

Como funciona

@¥(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

O Japt possui uma substituição recursiva integrada, mas vê a primeira entrada como um regex. Se fosse garantido que as entradas contivessem apenas caracteres alfanuméricos, esta solução de três bytes funcionaria:

eVW

Se a entrada tiver permissão para conter qualquer caractere ^, exceto,, \ou ], essa solução de 12 bytes será válida:

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

C #, 33 49 bytes

Provavelmente, um dos menores trechos escritos em C # ... E como Replaceé nativo da stringestrutura, não há necessidade de usings ( pelo menos não no recurso interno do VS, C # interativo ... )

Além disso, como Bsempre tem um valor, o código não precisa de validações.


Golfe

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

Código completo

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

Lançamentos

  • v1.1 - +19 bytes- Solução fixa não sendo recursiva.
  • v1.0 -  33 bytes- Solução inicial.
auhmaan
fonte
1
Vejo c # I
voto positivo
@NelsonCasanova Soa como eu.
Metoniem
Não Replacerealizar a substituição recursiva?
Laikoni
@Laikoni no. Por exemplo, "((())())())".Replace("()", "")retorna (())).
21417 auhmaan
Então essa solução não é válida sob as regras do desafio. Você deve excluí-lo para evitar votos negativos, depois corrigir sua solução para lidar com a substituição recursiva e, finalmente, cancelar a exclusão.
Laikoni
1

Processando, 75 72 bytes

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

Imprime os resultados. Chame comog("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
fonte
1

Mathematica, 35 32 Bytes

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

Argumentos dados como uma sequência. Nunca termina por growexemplo, retorna looppor loopexemplo. Três bytes de folga graças à sugestão de Martin.

A Simmons
fonte
FixedPointtende a ser muito longo e pode ser emulado com //.:#//.x_:>StringReplace[x,#2->#3]&
Martin Ender
Obrigado @MartinEnder. Essa é uma boa maneira de começar ReplaceRepeateda trabalhar para strings!
Um Simmons
btw, isso vai apenas laço $RecursionLimitvezes, o que é 2^16, por padrão, não que isso afeta a sua resposta
ngenisis
@ngenesis Eu não tenho certeza que ReplaceRepeatedé controlado por $RecursionLimit- Eu só testei, definindo o limite para 20 e o programa ainda feliz laços ao longo para a entrada de não-encerramento ..
A Simmons
Pois ReplaceRepeatedhá uma opção separada (que não pode ser usada com a //.sintaxe), chamada MaxIterations. O padrão é 2 ^ 16. (cc @ngenisis)
Martin Ender
1

Ruby, 29 bytes

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

Dados 3 argumentos, aplique a substituição ao primeiro até que não haja mais nada para substituir.

Explicação

  • 1antes do whileé simplesmente um nop
  • gsub!retorna a string ou nilse nenhuma substituição ocorreu
GB
fonte
1

/// , 3 bytes

///

Coloque a corda B após a primeira barra, C após a segunda e A no final, ou seja:

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

Experimente online!

steenbergh
fonte
Eu não acho que essa seja uma maneira aceitável de receber informações #::
Leo
Que eu saiba, ///não aceita entrada de nenhuma outra maneira.
21417 stanbergh
2
Bem, acho que seria interessante discutir se isso é aceitável ou não, então :) De qualquer forma, notei outro problema com a sua submissão: não funciona se a /estiver presente em qualquer uma das strings de entrada
Leo
1

JavaScript (Firefox 48 ou anterior), 43 bytes

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

Aceita argumentos em ordem inversa. O Firefox costumava ter um terceiro parâmetro não padrão para o replacequal os sinalizadores de regexp especificados. Este parâmetro foi removido no Firefox 49.

Neil
fonte
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

Um dos raros casos em que a criação de uma função é realmente MAIS CURTA no SmileBASIC.

12Me21
fonte
0

Javascript 130 bytes

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

O Javascript substituirá tudo simultaneamente se você fornecer um regex. Para fazer esse regex funcionar para todos os valores, todos os caracteres usados ​​para regex precisam ser substituídos pela versão de escape. Finalmente, a substituição é avaliada para substituir todas as instâncias de B em A por C e passando isso de volta para a função novamente.

fəˈnɛtɪk
fonte
0

q, 15 bytes

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

Exemplo:

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

ligação para download do intérprete

Explicação: ssr , / (converge)

skeevey
fonte
0

Cheddar, 37 bytes

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

No telefone, é um pouco difícil adicionar o link TIO. Basicamente, usa recursão enquanto a verificação é b está em a. A solução poderia ter sido, (a,b,c)->a.sub(Regex{b,"cr"},c)mas não funciona por algum motivo.

Downgoat
fonte
O sub substitui todos ou apenas o primeiro?
15167
@LliwTelracs porque eles são cordas .sub irá substituir todos
Downgoat
Isso não parece funcionar? Experimente online!
Conor O'Brien
@ ConorO'Brien porcaria erro bobo lados do ternário estão desligados
Downgoat 17/02/17
0

Perl 6 , 40 bytes

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

Experimente (se tio.run for atualizado)
Experimente uma versão alterada

Expandido:

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

PHP, 46 bytes

function g($a,$b,$c){echo strtr($a,[$b=>$c]);}
MonkeyZeus
fonte
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;

Casos de teste (funcionais)

Caso de teste com erro de loop

roberto06
fonte
Oi! Normalmente, ao enviar uma função, você deve adicionar ao número de bytes todas as coisas necessárias para que a função seja definida (no seu caso function replace(...){...}, caso contrário, seu envio é apenas um trecho, que não
Leo
@Leo Não sabia disso, editei minha resposta #;)
roberto06 20/02
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];}

Para entrada vazia, ele retorna uma string vazia.

StackOverflowExceptionFalha com erro quando Bestá vazio ou é alimentado com dados como este A/A/A.

Como funciona:

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

Código de código ungolfed com comentários:

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)
}
biscoito
fonte
0

AutoHotkey, 87 bytes

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

%1%,, %2%e %3%são os 3 primeiros argumentos passados ​​para uma função
Se uma função espera um argumento variável, os %s são descartados. A
alteração da configuração de distinção entre maiúsculas e minúsculas custa 19 bytes, mas, sem ela, você obtém coisas como downpercase is down.

Engenheiro Toast
fonte