Jeśli ciąg T o długości K pojawia się K lub więcej razy w ciągu S , wówczas jest potencjalnie komunistyczny . Na przykład, 10in 10/10jest potencjalnie komunistyczny, ponieważ pojawia się 2 razy i ma długość 2 . Pamiętaj, że te podciągi nie mogą się pokrywać.

Communistic transformacja jest, że przy tej łańcuch T i porusza się każdy znak T _I z T na ı występowania T w S . Tak więc w poprzednim przykładzie transformacja komunistyczna przyniosłaby 1/0; pierwszy znak 10zastępuje 10za pierwszym razem 10, a 0za drugim razem.

Communistic normalizacja jest funkcją, która przyjmuje wszystkie takie ciągi T z K ł 2 i wykonuje communistic transformacji na nich.

Niektóre szczegóły dotyczące algorytmu:

1. Wykonaj komunistycznych przemian na najdłuższym ważnych ciągów T pierwszych . Faworyzować pierwszych wystąpień T .
2. Następnie wykonaj transformacje komunistyczne na następnych najdłuższych ciągach, a następnie na następnych, najdłuższych ... itd.
3. Powtarzaj, aż w łańcuchu nie będzie takich łańcuchów.

Zauważ, że niektóre ciągi znaków, takie jak przykład „Cześć, Cześć” w przypadkach testowych, można interpretować na dwa różne sposoby. Możesz użyć elldla T , ale możesz także użyć llo. W takim przypadku kod może wybrać dowolną opcję. Przedstawiony przypadek testowy używa llo, ale możesz uzyskać inne i równie poprawne dane wyjściowe.

Twoim zadaniem jest wdrożenie normalizacji komunistycznej. Dane wejściowe zawsze będą się składać wyłącznie z drukowalnych znaków ASCII (0x20 do 0x7E, spacja do tyldy). Możesz napisać program lub funkcję, aby rozwiązać to zadanie; dane wejściowe mogą być pobierane jako wiersz z STDIN, argument ciąg znaków / tablica znaków, argument z ARGV itp.

Przypadki testowe

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

Opracowany przypadek testowy

Format jest 'string', 'substring'na każdym etapie wymiany. Zamienione bity są w nawiasach.

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

Kolejny przypadek testowy:

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

Kod referencyjny (Python)

Może to być przydatne do wizualizacji algorytmu.

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

Dziękujemy @ ConorO'Brien za opublikowanie oryginalnego pomysłu na to wyzwanie.

Pyth, 22 bajty

u.xse.iLcGdf>cGTlTt#.:

Zestaw testowy

Aby zobaczyć, co robi program, sprawdź to:

Wewnętrzne

W szczególności program zawsze korzysta z ostatniej wymiany najdłuższych zamienników.

Wyjaśnienie:

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 bajtów

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

Rekurencyjnie pasuje do wzoru:

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

… Dopóki wzór nie zostanie znaleziony. (Gwarantuje to, że najpierw obsługiwany jest najdłuższy ciąg).

Następnie wykonuje „transformacje komunistyczne” według ostatnio znalezionego wzorca, dzieląc mecz i łącząc każdą z postaci meczu. ( mapsłuży do tego celu. Szkoda, joinże nie odbiera oddzwonienia).

W końcu powraca na tym nowym łańcuchu, dopóki nie będzie już komunistyczny .

Przypadki testowe:

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

Czysty , 420 ... 368 bajtów

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

Wypróbuj online!