Cordes jumelables

28

Une chaîne peut être couplée si elle peut être divisée en sous-chaînes, chacune étant une chaîne répétée deux fois de suite. Par exemple, aabaaababbbabapeut être jumelé comme:

aaba aaba
b b
ba ba

Étant donné une chaîne non vide de a'et b', affichez une valeur Truthy si elle est couplable et une valeur Falsey si ce n'est pas le cas.

Jumelable:

aa
abaaba
bbababbb
aabaaababbbaba
babababa
bbbbbbbbbbbb
aaababbabbabbbababbaabaabaababaaba
aaaabaab

Non jumelable:

a
ba
baab
abaabaaba
bbbbbbbbbbbbbbb
baababbabaaaab
aaaaabbaaaaa

Je vous encourage à trouver des solutions non basées sur des expressions rationnelles même s'il existe déjà une réponse d'expression rationnelle plus courte dans votre langue. Vous pouvez les marquer comme "aucune expression régulière". Par regex, je veux dire un sous-système de correspondance de modèle de chaîne intégré.


Classement:

xnor
la source
Pouvons-nous utiliser autre chose que ab?
Erik the Outgolfer
Si bbababbb peut être jumelé, pourquoi baab et aaaaabbaaaaa ne le sont pas?
rnso
@rnso D'après ma compréhension, bbababbb peut être déversé en 3 paires: bb, abab et bb qui concatène dans cet ordre pour former la chaîne d'origine, tandis que les deux autres ne le peuvent pas.
Sunny Pun
Par la question "dont chacun (sous-chaîne) est une chaîne répétée deux fois CONSÉCUTIVEMENT" et qui n'est pas satisfait de bbababbb. Sinon, baab peut également être divisé en baab et aaaaabbaaaaa en aaaaa bb aaaaa.
rnso
@rnso Vous ne savez pas ce que vous voulez dire là-bas. Par consécutivement, je veux dire que les deux répétitions sont côte à côte. Dans "baa b", les deux b sont séparés par des a, donc ça ne marche pas.
xnor

Réponses:

11

Python 2, 68 63 octets

f=lambda s,n=1:s==2*s[:n]or''<s[n:]>-f(s,n+1)<f(s[n:])*f(s[:n])

Renvoie True ou False . Testez-le sur Ideone .

Dennis
la source
4
C'est une récursion vraiment propre, en utilisant l'index pour le centre du double et le centre à partitionner. C'est drôle que la véracité soit vérifiée comme étant moins que quelque chose. Je vois des améliorations ...
xnor
8

Rétine , 11 octets

^((.+)\2)+$

Essayez tous les cas de test. Les deux premiers octets le rendent multiligne.

Interprétation assez littérale des règles, utilise évidemment regex, comme tous les programmes Retina.

FryAmTheEggman
la source
2
Dangit, j'attendais depuis 3 semaines pour poster ceci ...
ETHproductions
2
Martin attendait aussi .
xnor
5
Oups! Je ne l'ai battu que de 10 secondes aussi ... Eh bien, je suis sûr que si j'écris une réponse Hexagony, il me pardonnera!
FryAmTheEggman
5
@FryAmTheEggman J'ai hâte d'y être. :)
Martin Ender
2
C'est exactement la même chose avec Perl:perl -pE '$_=/^((.+)\2)+$/'
Dada
8

Gelée , 10 octets

ẆŒPẋ€€2F€ċ

Pas vraiment efficace ... Essayez-le en ligne!

Comment ça marche

ẆŒPẋ€€2F€ċ  Main link. Argument: s (string)

Ẇ           Window, generate the array of all substrings of s.
 ŒP         Powerset; generate all subarrays of substrings of s.
   ẋ€€2     Repeat each substring in each subarray twice.
            For example, ["ab", "a", "b"] becomes ["abab", "aa", "bb"].
       F€   Flatten the subarrays by concatenating their strings.
         ċ  Count how many times s appears in the generated strings.
Dennis
la source
Cela ... semble inefficace. Combien de temps les entrées peuvent-elles gérer dans un délai raisonnable?
John Dvorak
1
C'est extrêmement inefficace ( O (2 ^ n ^ 2) , je pense). Je devrais vérifier localement. TIO manque de mémoire pour les chaînes de longueur 6 .
Dennis
8
Une chaîne de longueur 6 prend 3:20 minutes sur ma machine et nécessite 6 Go de mémoire.
Dennis
1
@Dennis Ne faisons donc pas une entrée de longueur 100 , car tout va planter. Oui, même TIO.
Erik the Outgolfer
@EriktheGolfer C'est une bonne idée car cela ralentira inutilement TIO pour d'autres utilisations, mais cela ne le fera pas planter. Dès que le système manque de mémoire, le processus est simplement tué par le MOO.
Dennis
5

Haskell, 72 69 octets (pas d'expression régulière)

g(a:b:c)|a==b=g c
g x=x==[]
any(g.words.concat).mapM(\c->[[c],c:" "])

Une approche par force brute. Essayez-le sur Ideone .

Merci à BlackCap pour -3 octets.

Explication

La fonction d'assistance gprend une liste de chaînes et vérifie qu'elle est constituée de paires de chaînes identiques, comme ["aa","aa","bba","bba","ab","ab"]. La fonction principale (anonyme) divise une chaîne de toutes les manières possibles et vérifie qu'au moins un fractionnement aboutit à une liste qui gaccepte.

g(a:b:c)                                  g on list with elements a, b and tail c,
        |a==b                              in the case that a==b,
             =g c                          recurses to the tail c.
g x=                                      g on any other list x
    x==[]                                  checks that x is empty.
                                           This includes the case where a is not equal
                                           to b, resulting in False.
any(g.words.concat).mapM(\c->[[c],c:" "]) The main function:
                    mapM(\c->[[c],c:" "])  Replace each letter c with either "c" or "c "
                                           in all possible ways, return list of results.
any(              ).                       Check that at least one result satisfies this:
            concat                          Concatenate the 1- or 2-letter strings,
      words.                                split again at each space,
    g.                                      apply g.
Zgarb
la source
Vous pouvez remplacer or.mapparany
BlackCap
@BlackCap Bien sûr, merci! J'ai d' abord eu any g.map(words.concat)et je pensais « hey, je peux le golf anyà or» ...
Zgarb
5

Python 2, 60 octets

f=lambda s,t='':''<s>f(s[1:],t+s[0])|f(t and s)*f(t)>-(s==t)

J'espère que c'est correct. Il fonctionne assez lentement et andne semble pas optimal.

xsot
la source
1
J'ai essayé d'utiliser des chaînes, mais je n'ai pas réussi à me rapprocher de mon score basé sur l'index. C'est un astucieux que andvous avez là-bas.
Dennis
Félicitations! La récurrence sur la partition était l'astuce que j'avais en tête.
xnor
4

Gelée , 12 octets

ŒṖµœs€2ZEµ€S

Deux octets de plus que mon autre réponse , mais cette approche est beaucoup plus efficace et gère tous les cas de test sauf un.

Essayez-le en ligne!

Comment ça marche

ŒṖµœs€2ZEµ€S  Main link. Argument: s (string)

ŒṖ            Generate all partitions of s.
  µ      µ€   Map the monadic chain between the µ's over the partitions.
   œs€2         Split each string in the partition into two chunks of equal length.
       Z        Zip/transpose, collecting the first halves in one array and the
                second halves in another.
        E       Test the arrays of halves for equality.
           S  Return the sum of the results, counting the number of different
              ways s can be paired.
Dennis
la source
3

Pyth - sans regex - 13 12 octets

Vérifie si l'une des partitions est composée de toutes les chaînes égales lorsqu'elles sont coupées en deux.

sm.AqMcL2d./

Suite de tests .

Maltysen
la source
3

Brachylog , 14 octets (pas d'expression régulière)

lye~l:1j@2zcc?

Essayez-le en ligne!

C'est trop lent pour certains des cas de test

Explication

ly                  The list [0, …, length(Input)]
  e~l               A list whose length is an element of the previous list
     :1j            Append itself to this list
        @2zc        Split in half, zip and concatenate so that the list contains pairs of
                      consecutive identical elements
            c?      The concatenation of that list must result in the Input
Fatalize
la source
3

JavaScript (ES6), aucune expression rationnelle, 75 74 octets

f=s=>!s|[...s].some((_,i)=>i&&s[e='slice'](0,i)==s[e](i,i+=i)&&f(s[e](i)))

Retourne 1pour jumelage sinon 0. Edit: 1 octet enregistré grâce à @ edc65.

Neil
la source
Agréable! Même compte en utilisant substrsans modifier i. Mais avec slice3 répétitions, vous pouvez enregistrer 1 octet en le
replaçant
@ edc65 Comment obtenez-vous le même nombre sans modifier i? Je me rends compte que s.substr(i,i+i)renvoie le même que s.slice(i,i+=i)mais j'utilise ensuite la valeur modifiée de iplus tard ...
Neil
c'est s.substr(i,i)2 octets de moins, puis s.slice(i+i)2 octets de plus
edc65
@ edc65 Oh bien sûr que c'est, je dois avoir besoin de plus de café ...
Neil
3

Python, 58 octets

f=lambda s,p='':s>''and(f(p)>-(s==p)<f(s))|f(s[1:],p+s[0])

Ceci est basé sur la méthode récursive de Dennis . L'astuce de négation booléenne est également prise à partir de là.

La nouvelle idée est de récurrer sur les partitions (p,s)de la chaîne d'origine en commençant par ('',s)et en déplaçant à plusieurs reprises le premier caractère de spour qu'il soit le dernier caractère de p. Cela permet aux pièces d'être référencées directement sans trancher la chaîne. Mais, comme la partition commence par pvide, nous devons faire attention à éviter les boucles d' f(s)appel infinies f(s).

xnor
la source
2

JavaScript (ES6), 24 octets

x=>/^((.+)\2)+$/.test(x)

Probablement pas plus court que cela.

ETHproductions
la source
N'est-ce pas \2?
Neil
@Neil Pour une raison quelconque, je pensais que cela fonctionnait \1, mais aabrevient true... merci pour le correctif.
ETHproductions
2

PHP, 40 octets

affiche 0 pour faux et 1 pour vrai

<?=preg_match("#^((.+)\\2)+$#",$argv[1]);
Jörg Hülsermann
la source
2

Python, 66 64 octets

Merci @Zgarb pour -1 octet!

f=lambda x,s=1:x>x[:s]and(x==2*x[:s])|f(x[:s])&f(x[s:])|f(x,s+1)

Renvoie Trueou False.

Essayez-le en ligne!

Toute aide au golf serait appréciée.

Oliver Ni
la source
1

Raquette 230 octets

(let((sl string-length)(ss substring))(if(odd?(sl s))(printf ".~n")(begin(let p((s s))(if(equal? s "")(printf "!")
(for((i(range 1(add1(/(sl s)2)))))(when(equal?(ss s 0 i)(ss s i(* 2 i)))(p(ss s(* 2 i)(sl s)))))))(printf ".~n"))))

Imprime un '!' pour chaque façon dont la chaîne est appariable. Imprime un '.' à la fin.

Non golfé:

(define (f s)
  (let ((sl string-length)                              ; create short names of built-in fns
        (ss substring))
    (if (odd? (sl s))  (printf ".~n")                   ; odd length strings cannot be pairable; end here.
        (begin
          (let loop ((s s))                             ; start testing here
            (if (equal? s "") (printf "!")              ; if no remaining string, it must be pairable
                (for ((i (range 1 (add1 (/(sl s)2)))))  ; ch lengths varying from 1 to half of string length
                  (when (equal? (ss s 0 i)              ; ch if substrings are same
                                (ss s i (* 2 i)))
                    (loop (ss s (* 2 i) (sl s) ))))))   ; if yes, loop to check remaining string.
          (printf ".~n")))))                            ; End of testing.

Essai:

(println "Following should be pairable")
(f "bbaabbaa")            ; should produce 2 '!' since 2 ways are possible.
(f "aa")
(f "abaaba")
(f "bbababbb")
(f "aabaaababbbaba")
(f "babababa")                    ; should be pairable in 2 ways.
(f "bbbbbbbbbbbb")                ; should be pairable in many ways.
(f "aaababbabbabbbababbaabaabaababaaba")
(f "aaaabaab")
(println "Following should be unpairable")
; (f "a")
(f "ba")
(f "baab")
(f "abaabaaba")
(f "bbbbbbbbbbbbbbb")
(f "baababbabaaaab")
(f "aaaaabbaaaaa")

Sortie:

"Following should be pairable"
!!.
!.
!.
!.
!.
!!.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!.
!.
!.
"Following should be unpairable"
.
.
.
.
.
.
rnso
la source
1

Perl, 16 +2 = 18 octets (avec regex)

Courez avec les -nldrapeaux. -Eest libre.

say/^((.+)\2)+$/

Courir comme:

perl -nlE 'say/^((.+)\2)+$/'

Renvoie une liste des groupes de capture (une vérité) si couplable, une chaîne nulle si non couplable.

Explication

Les -nldrapeaux exécuteront le code dans une boucle ( -n), mettant l'entrée (avec le retour à la ligne retiré à cause de -l) dans la variable à $_chaque fois, puis évaluant le code chaque fois que l'entrée est entrée, jusqu'à ce que le programme se termine manuellement. L' -Eindicateur vous permet d'évaluer le code sur la ligne de commande et active la saycommande.

say/^((.+)\2)+$/

   /^((.+)\2)+$/  #The regex engine
      (.+)\2      #Find any set of at least one character, followed by itself
     (      )+    #Do this at least one time
   /^         $/  #Make sure that this matches the entire string from start to end
say               #Output the result of the regex

Si une correspondance est trouvée (par exemple, si la chaîne peut être jumelée), l'expression régulière renvoie une liste des groupes de capture, qui est évaluée comme une vérité, qui est ensuite transmise à say, et sortie. Si aucune correspondance n'est trouvée, l'expression régulière renvoie la chaîne vide, qui est évaluée à falsy, qui est ensuite passée à say, et sortie.

Échantillon:

$ perl -nlE 'say/^((.+)\2)+$/'
aaababbabbabbbababbaabaabaababaaba
baababaababaaba                      #Truthy
baababbabaaaab
                                     #Falsy
bbababbb
bbb                                  #Truthy
aabaaababbbaba
bababa                               #Truthy
abaabaaba
                                     #Falsy
Gabriel Benamy
la source
1

GNU Prolog, 49 46 octets

Fonctionne probablement aussi dans d'autres variantes, bien qu'elles ne représentent pas toutes les chaînes de la même manière; La représentation de GNU Prolog est utile pour ce problème.

Il n'est pas clair si cela compte comme l'utilisation d'expressions régulières ou non. Il n'utilise aucune fonctionnalité de type regex, mais toute la sémantique du langage est similaire à celle de regex.

Nouvelle version (utilise l'astuce de récursivité vue dans certaines autres réponses):

s(X):-append(A,B,X),(A=B;A\=X,B\=X,s(A),s(B)).

Ancienne version:

s(X):-X=[];append(A,B,X),B\=X,append(C,C,A),s(B).

C'est un prédicat (l'équivalent de Prolog d'une fonction) appelé s, pas un programme complet. Utilisez-le comme ceci:

| ?- s("aa").
true ?
yes
| ?- s("aaababbabbabbbababbaabaabaababaaba").
true ?
yes
| ?- s("baababbabaaaab").
no
| ?- s("bbbbbbbbbbbbbbb").
no

Une caractéristique intéressante de l'ancienne solution est que si vous demandez à l'interprète "y a-t-il d'autres solutions?" via l'utilisation de ;à l' true ?invite (plutôt que de demander "y a-t-il une solution" en appuyant sur retour à l'invite, comme je l'ai fait ci-dessus), il renvoie "vrai" un nombre de fois égal au nombre de façons différentes dont la chaîne peut être exprimée sous la forme donnée (par exemple, il renvoie "vrai" deux fois avec s("aaaa")., car cela peut être analysé comme (a a)(a a)ou comme (aa aa)).

Les programmes Prolog sont souvent réversibles (permettant sde générer une liste de chaînes avec la propriété donnée). L'ancien n'est pas (il entre dans une boucle infinie), mais c'est à cause de la méthode golfée que j'ai utilisée pour m'assurer que C n'est pas vide; si vous réécrivez le programme pour spécifier C comme non vide explicitement, il génère des chaînes de la forme "aa", "aabb", "aabbcc", etc. (Prolog étant Prolog, il ne spécifie pas les identités des caractères qui les rendent , juste une spécification des caractères identiques). Le plus récent génère des chaînes de la forme "aa", "abab", "abcabc", etc. il s'agit d'une boucle infinie à part entière, et n'atteint donc jamais le point auquel elle se bloquerait en raison de l'échec de la détection d'une chaîne de longueur nulle.


la source
1

Brainfuck, 177 octets

+[<<<<,]>>>>[>+[>+[[>>]<+<[<<]>+>-]<[>+<-]>>>,>>[>>]+<<[<+>>-<-]<[>+<-]>>[,>[-<<
<<]<[<<<<]>]<[[<<]>]>>]>>[[>+>>>]>>>[>]<<<<[>+[-<<<,<]<[<<<[[<<<<]>>]<]>]>>]<[[-
>>>>]>>[<]<]<<]<.

Formaté:

+[<<<<,]
>>>>
[
  >+
  [
    >+
    [
      [>>]
      <+<[<<]
      >+>-
    ]
    <[>+<-]>
    >>,>>[>>]
    +<<[<+> >-<-]
    <[>+<-]>
    >
    [
      not equal
      ,>[-<<<<]
      <[<<<<]
      >
    ]
    <
    [
      equal
      [<<]
      >
    ]
    >>
  ]
  >>
  [
    mismatch
    [>+>>>]
    >>>[>]
    <<<<
    [
      backtrack
      >+[-<<<,<]
      <
      [
        not done yet
        <<<
        [
          [<<<<]
          >>
        ]
        <
      ]
      >
    ]
    >>
  ]
  <
  [
    match
    [->>>>]
    >>[<]
    <
  ]
  <<
]
<.

Attend une entrée sans retour à la ligne. Imprime \x00pour faux et \x01pour vrai.

Essayez-le en ligne.

Cela implémente la recherche en profondeur. En particulier: vérifiez les préfixes répétés de longueur croissante à partir du suffixe actuel, puis passez au suffixe suivant si une correspondance est trouvée, sinon revenez en arrière.

Au début, la chaîne est inversée et une sentinelle \x01est placée à la fin.

La bande est divisée en nœuds à 4 cellules. La configuration de la mémoire d'un nœud est:

c h x 0

cest le caractère, hest un indicateur pour savoir si le caractère se trouve dans la première moitié d'un préfixe répété, et xest un indicateur pour garder une trace de la paire de caractères en cours de comparaison. Les hdrapeaux restent en place tandis que les xdrapeaux forment une fenêtre mobile.

Si la chaîne peut être jumelée, le pointeur atterrit à côté de la sentinelle à la fin de la boucle principale; sinon, le pointeur tombe du côté gauche de la chaîne lors du retour en arrière.

Mitch Schwartz
la source
1

Brachylog , 5 octets

~c~jᵐ

Essayez-le en ligne!

Notez que cet algorithme peut prendre très longtemps, en particulier sur les cas de falsey, car il vérifie chaque partition possible de la chaîne d'entrée.

Explication

~c     Reversed concatenate: find a list that, when concatenated, results in the input string
       This examines all partitions of the input
  ~jᵐ  Map reversed juxtapose: for each string in that list, is it the result of concatenating
       a string to itself?

Pour une chaîne d'entrée comme "ababcc", ~cessaie différentes partitions jusqu'à ce qu'elle arrive ["abab", "cc"], à quel point ~jréussit pour les deux éléments de la liste, les sorties ["ab", "c"]et le prédicat réussit.

DLosc
la source
1

R , 31 octets

grepl("^((.+)\\2)+$",scan(,""))

Essayez-le en ligne!

Basé sur la réponse de Retina.

R , 129 octets

Et voici une réponse originale, non regex:

o=(y=utf8ToInt(scan(,"")))<0;for(i in 2*1:(sum(y>0)/2))for(j in 1:(i/2)){w=i:(i-j+1);v=w-j;if(all(y[w]==y[v]))o[c(v,w)]=T};all(o)

Essayez-le en ligne!

Nick Kennedy
la source
0

Lithp , 57 caractères

#S::((? (!= (null) (match S "^((.+)\\2)+$")) true false))

Exemple d'utilisation:

% pairable_strings.lithp
(
    (def f #S::((? (!= (null) (match S "^((.+)\\2)+$")) true false)))
    (print (f "aa"))
    (print (f "aabaaababbbaba"))
    (print (f "aaababbabbabbbababbaabaabaababaaba"))
    (print (f "ba"))
)

# ./run.js pairable_strings.lithp
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 2, type: 'Atom', name: 'true' }
AtomValue { value: 3, type: 'Atom', name: 'false' }
Andrakis
la source