Normalisation des sous-chaînes communistes

13

Si une chaîne T de longueur K apparaît K ou plusieurs fois dans une chaîne S , alors elle est potentiellement communiste . Par exemple, 10en 10/10est potentiellement communiste, car il apparaît 2 fois et est de longueur 2 . Notez que ces sous-chaînes ne peuvent pas se chevaucher.

Une transformation communistic est celui qui prend cette chaîne T et se déplace chaque caractère t i de T à la i occurrence de T à S . Ainsi, pour l'exemple précédent, la transformation communiste céderait 1/0; le premier caractère de 10remplace 10la première fois 10est trouvé, et 0la deuxième fois.

Une normalisation communiste est une fonction qui prend toutes ces chaînes T avec K ≥ 2 et effectue une transformation communiste sur elles.

Quelques détails sur l'algorithme:

  1. Effectuer des transformations les plus longues sur communistic chaînes valides T premières . Favoriser les premières occurrences de T .
  2. Ensuite, effectuez des transformations communistes sur les chaînes les plus longues, puis sur la chaîne suivante-suivante ... etc.
  3. Répétez jusqu'à ce qu'aucune chaîne de ce type n'existe dans la chaîne.

Notez que certaines chaînes, comme l'exemple "Bonjour, Bonjour" dans les cas de test, peuvent être interprétées de deux manières différentes. Vous pouvez utiliser ellpour T , mais vous pouvez également utiliser llo. Dans ce cas, votre code peut choisir l'une ou l'autre option. Le scénario de test illustré utilise llo, mais vous pouvez obtenir une sortie différente et tout aussi valide.


Votre tâche consiste à mettre en œuvre la normalisation communiste. L'entrée sera uniquement composée de caractères ASCII imprimables (0x20 à 0x7E, espace à tilde). Vous pouvez écrire un programme ou une fonction pour résoudre cette tâche; l'entrée peut être prise comme une ligne de STDIN, un argument de chaîne de caractères / tableau, un argument d'ARGV, etc.

Cas de test

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

Cas de test élaboré

Le format est 'string', 'substring', à chaque étape de remplacement. Les bits remplacés sont entre crochets.

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

Un autre cas de test:

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

Code de référence (Python)

Vous pouvez trouver cela utile pour visualiser l'algorithme.

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

Merci à @ ConorO'Brien d'avoir posté l'idée originale de ce défi.

Rɪᴋᴇʀ
la source
Les cas de test: ababab1ababab,1ab2ab3ab4ab5ab6
Zgarb
Pourquoi n'y a-t-il pas de changement? abse produit au moins deux fois dans les deux chaînes.
Zgarb
@Zgarb semble que mon testeur est mauvais, je le réparerai plus tard. Correction manuelle des cas de test.
Rɪᴋᴇʀ

Réponses:

2

Pyth, 22 octets

u.xse.iLcGdf>cGTlTt#.:

Suite de tests

Pour voir réellement ce que fait le programme, consultez ceci:

Internes

En particulier, le programme utilise toujours le remplacement définitif des remplacements les plus longs.

Explication:

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.
isaacg
la source
4

JavaScript (ES6), 121 octets

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

Correspond récursivement au modèle:

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

… Jusqu'à ce que le motif ne soit pas trouvé. (Cela garantit que la chaîne la plus longue est traitée en premier.)

Il effectue ensuite les "transformations communistes" sur le dernier motif trouvé, en se divisant sur la correspondance et en se joignant à chacun des personnages de la correspondance. ( mapest utilisé à cet effet. Dommage joinne prend pas de rappel.)

Elle revient finalement sur cette nouvelle chaîne jusqu'à ce qu'elle ne soit plus communiste .

Cas de test:

Rick Hitchcock
la source
1

Nettoyer , 420 ... 368 octets

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

Essayez-le en ligne!

Οurous
la source
Cette réponse n'est pas valide. Vois ici. Cela devrait être changé, voir les cas de test.
Rɪᴋᴇʀ
@Riker intéressant, car c'est un port direct de la solution de référence. Je vais supprimer jusqu'à ce qu'il soit corrigé.
Janurous
@Riker corrigé maintenant.
Οurous