Wenn eine Zeichenfolge T der Länge K erscheint K oder mehrmals in einem String S , dann ist es möglicherweise kommunistisch . Zum Beispiel 10in 10/10potentiell kommunistisch, denn es erscheint 2 - mal und ist mit einer Länge von 2 . Beachten Sie, dass sich diese Teilzeichenfolgen nicht überlappen können.

Eine kommunistische Transformation ist eine Transformation , bei der diese Zeichenfolge T verwendet und jedes Zeichen t _i von T zum i- Vorkommen von T in S verschoben wird . Für das vorige Beispiel würde die kommunistische Transformation also nachgeben 1/0; Das erste Zeichen von 10ersetzt 10das erste Mal 10und 0das zweite Mal.

Eine kommunistische Normalisierung ist eine Funktion, die alle diese Zeichenketten T mit K ≥ 2 nimmt und eine kommunistische Transformation an ihnen durchführt.

Einige Besonderheiten des Algorithmus:

1. Führen Sie kommunistische Transformationen mit den längsten gültigen Zeichenfolgen T zuerst durch . Favor die ersten Vorkommen von T .
2. Führen Sie dann kommunistische Transformationen für die nächstlängsten Zeichenfolgen durch, dann für die nächstlängsten ... usw.
3. Wiederholen Sie diesen Vorgang, bis keine derartigen Zeichenfolgen mehr in der Zeichenfolge vorhanden sind.

Beachten Sie, dass einige Zeichenfolgen, z. B. das Beispiel "Hallo, Hallo" in den Testfällen, auf zwei verschiedene Arten interpretiert werden können. Sie können ellfür T verwenden , aber Sie können auch verwenden llo. In diesem Fall kann Ihr Code eine der beiden Optionen auswählen. Der gezeigte Testfall wird verwendet llo, Sie erhalten jedoch möglicherweise eine andere und gleichermaßen gültige Ausgabe.

Ihre Aufgabe ist es, die kommunistische Normalisierung umzusetzen. Die Eingabe besteht immer nur aus druckbaren ASCII-Zeichen (0x20 bis 0x7E, Leerzeichen bis Tilde). Sie können ein Programm oder eine Funktion schreiben, um diese Aufgabe zu lösen. Die Eingabe kann als Zeile aus STDIN, String / Character-Array-Argument, Argument aus ARGV usw. übernommen werden.

Testfälle

'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'

Testfall ausgearbeitet

Format ist 'string', 'substring'bei jedem Schritt der Ersetzung. Ersetzte Bits werden in eckige Klammern gesetzt.

'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', ''

Ein weiterer Testfall:

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

Referenzcode (Python)

Dies kann hilfreich sein, um den Algorithmus zu visualisieren.

#!/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'

Vielen Dank an @ ConorO'Brien für die Veröffentlichung der ursprünglichen Idee dieser Herausforderung.

Pyth, 22 Bytes

u.xse.iLcGdf>cGTlTt#.:

Testsuite

Überprüfen Sie Folgendes, um zu sehen, was das Programm tatsächlich tut:

Interna

Insbesondere verwendet das Programm immer die endgültig auftretende Ersetzung der längsten Ersetzungen.

Erläuterung:

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 Byte

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

Stimmt rekursiv mit dem Muster überein:

(.{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.

... bis das Muster nicht mehr gefunden wird. (Dies garantiert, dass die längste Zeichenfolge zuerst verarbeitet wird.)

Anschließend werden die "kommunistischen Transformationen" für das zuletzt gefundene Muster ausgeführt, indem das Match aufgeteilt und die einzelnen Charaktere des Matches zusammengefügt werden. ( mapwird für diesen Zweck verwendet. Schade, joinnimmt keinen Rückruf entgegen.)

Es wiederholt sich schließlich auf dieser neuen Zeichenfolge, bis es nicht mehr kommunistisch ist .

Testfälle:

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

Sauber , 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

Probieren Sie es online!