Se uma string T de comprimento K aparecer K ou mais vezes em uma string S , é potencialmente comunista . Por exemplo, 10in 10/10é potencialmente comunista, pois aparece 2 vezes e tem comprimento 2 . Observe que essas substrings não podem se sobrepor.

A transformação comunista é aquele que leva esta cadeia T e move cada personagem t _i de T ao i ocorrência de T em S . Assim, no exemplo anterior, a transformação comunista renderia 1/0; o primeiro caractere de 10substitui 10a primeira vez que 10é encontrada e 0a segunda vez.

Uma normalização comunista é uma função que pega todas essas cordas T com K ≥ 2 e executa uma transformação comunista nelas.

Algumas especificidades do algoritmo:

1. Executar transformações comunistas na maior cadeias válidas T primeiros . Favorecer as primeiras ocorrências de t .
2. Em seguida, execute transformações comunistas nas próximas seqüências mais longas, depois na próxima sequência mais longa ... etc.
3. Repita até que essas cadeias não existam na cadeia.

Observe que algumas seqüências de caracteres, como o exemplo "Olá, Olá" nos casos de teste, podem ser interpretadas de duas maneiras diferentes. Você pode usar ellpara T , mas também pode usar llo. Nesse caso, seu código pode escolher uma das opções. O caso de teste mostrado usa llo, mas você pode obter uma saída diferente e igualmente válida.

Sua tarefa é implementar a normalização comunista. A entrada será sempre composta apenas por caracteres ASCII imprimíveis (0x20 a 0x7E, espaço para til). Você pode escrever um programa ou função para resolver esta tarefa; a entrada pode ser tomada como uma linha de STDIN, argumento de cadeia de caracteres / caracteres, argumento de ARGV, etc.

Casos de teste

'123' -> '123'
'111' -> '111'
'1111' -> '11'
'ABAB' -> 'AB'
'111111111' -> '111'
'asdasdasd' -> 'asd'
'10/10' -> '1/0'
'100/100+100' -> '1/0+0'
'   +   +   ' -> ' + '
'Hello, hello, dear fellow!' -> 'Hel he, dear feow!' OR 'Heo hl, dear flow!'
'11122333/11122333/11122333' -> '112/13' OR '132/23'

'ababab1ababab' -> 'a1bab'
'1ab2ab3ab4ab5ab6' -> '1a2b3a4b5ab6'

Caso de teste elaborado

O formato é 'string', 'substring', em cada etapa da substituição. Os bits substituídos estão entre colchetes.

'11[122]333/11[122]333/11[122]333', '122'
'111[333]/112[333]/112[333]', '333'
'1113/11[23]/11[23]', '23'
'11[13]/112/1[13]', '13'
'1[11]/[11]2/13', '11'
'1[/1]12[/1]3', '/1'
'112/13', ''

Outro caso de teste:

'Hello, hello, dear fellow!', 'llo'
'Hel, hel, dear feow!', 'l,'
'Hel he, dear feow!', ''

Código de referência (Python)

Você pode achar isso útil para visualizar o algoritmo.

#!/usr/bin/env python

import re

def repeater(string):
    def repeating_substring(substring):
        return (string.count(substring) == len(substring)) and string.count(substring) > 1

    return repeating_substring

def get_substrings(string):
    j = 1
    a = set()
    while True:
        for i in range(len(string) - j+1):
            a.add(string[i:i+j])
        if j == len(string):
            break
        j += 1
    return list(a)

def replace_each_instance(string, substring):
    assert `string`+',', `substring`
    for i in substring:
        string = re.sub(re.escape(substring), i, string, 1)

    return string


def main(s):
    repeats = repeater(s)
    repeating_substr = filter(repeater(s), get_substrings(s))

    while repeating_substr:
        repeating_substr.sort(lambda x,y: cmp(len(y), len(x)))
        s = replace_each_instance(s, repeating_substr[0])
        repeating_substr = filter(repeater(s), get_substrings(s))

    return s

assert main('123') == '123'
assert main('111') == '111'
assert main('1111') == '11'
assert main('ABAB') == 'AB'
assert main('111111111') == '111'
assert main('asdasdasd') == 'asd'
assert main('10/10') == '1/0'
assert main('100/100+100') == '1/0+0'
assert main('   +   +   ') == ' + '
assert main('Hello, hello, dear fellow!') == 'Hel he, dear feow!'
assert main('11122333/11122333/11122333') == '112/13'

Agradecemos a @ ConorO'Brien por postar a ideia original deste desafio.

Pitão, 22 bytes

u.xse.iLcGdf>cGTlTt#.:

Suíte de teste

Para realmente ver o que o programa está fazendo, confira o seguinte:

Internals

Em particular, o programa sempre usa a substituição final das substituições mais longas.

Explicação:

u.xse.iLcGdf>cGTlTt#.:
u.xse.iLcGdf>cGTlTt#.:G)GQ    Implicit
u                        Q    Starting with the input, repeat the following
                              until a fixed point is reached.
                    .:G)      Construct all substrings of the current value
                              ordered smallest to largest, front to back.
                  t#          Filter on having more than 1 element.
                              These are the eligible substrings.
           f                  Filter these substrings on
             cGT              Chop the current value on the substring,
            >   lT            Then remove the first len(substring) pieces.
                              The result is nonempty if the substring is
                              one we're looking for. 
                              Chopping gives nonoverlapping occurrences.
     .iL                      Interlace the substrings with
        cGd                   Chop the current value on that substring
   se                         Take the final result, make it a string.
 .x                     G     If there weren't any, the above throws an error,
                              So keep the current value to halt.

JavaScript (ES6), 121 bytes

f=(s,j=2,o,m=s.match(`(.{${j}})(.*\\1){${(j-1)}}`))=>m?f(s,j+1,s.split(m[1]).map((e,i)=>e+(m[1][i]||'')).join``):o?f(o):s

Corresponde recursivamente ao padrão:

(.{2})(.*\1){1}  //2 characters, repeated 1 time 
(.{3})(.*\1){2}  //3 characters, repeated 2 times 
(.{4})(.*\1){3}  //4 characters, repeated 3 times 
etc.

... até que o padrão não seja encontrado. (Isso garante que a cadeia mais longa seja tratada primeiro.)

Em seguida, ele realiza as "transformações comunistas" no último padrão encontrado, dividindo a partida e juntando-se a cada um dos personagens da partida. ( mapé usado para essa finalidade. Pena joinque não recebe retorno de chamada.)

Finalmente, ele se repete nessa nova sequência até que não seja mais comunista .

Casos de teste:

f=(s,j=2,o,m=s.match(`(.{${j}})(.*\\1){${(j-1)}}`))=>m?f(s,j+1,s.split(m[1]).map((e,i)=>e+(m[1][i]||'')).join``):o?f(o):s

console.log(f('123'));  //123
console.log(f('111'));  //111
console.log(f('1111')); //11
console.log(f('ABAB')); //AB
console.log(f('111111111')); //111
console.log(f('asdasdasd')); //asd
console.log(f('10/10')); //1/0
console.log(f('100/100+100')); //1/0+0
console.log(f('   +   +   ')); // + 
console.log(f('Hello, hello, dear fellow!')); //Heo hl, dear flow!
console.log(f('11122333/11122333/11122333')); //132/23

Limpo , 420 ... 368 bytes

import StdEnv,StdLib
l=length
%q=any((==)q)
?_[]=[]
?a[(y,x):b]|isPrefixOf a[x:map snd b]=[y: ?a(drop(l a-1)b)]= ?a b
$s=sortBy(\a b=l a>l b)(flatten[[b: $a]\\(a,b)<-map((flip splitAt)s)[0..l s-1]])
f s#i=zip2[0..]s
#r=filter(\b=l(?b i)>=l b&&l b>1)($s)
|r>[]#h=hd r
#t=take(l h)(?h i)
=f[if(%n t)(h!!hd(elemIndices n t))c\\(n,c)<-i|not(%n[u+v\\u<-t,v<-[1..l h-1]])]=s

Experimente online!